Ramifications of Transaction Introspection, CheckDataSig, and Exec

Examining virtuous interactions between multiple opcodes that together create a generalized way to allow any sighash algorithm to be enforced by any participant

Background

Since the original DataSigVerify (now CheckDataSig or CDS) proposal, it was recognized that transaction introspection and data signatures can be combined to replace CheckSig functionality.

This is done by using transaction introspection to grab data from the transaction, and CDS to verify a signature on that data.

Note that in CheckSig the satisfier script (the signer) decides what data should be taken from the transaction via the “sighash” field. This field chooses a sighash algorithm. But using transaction introspection would allow the constraint script to specify the interesting transaction data.

It is very important to understand these two roles within a transaction, because these two parties are not cooperative – the satisfier script (the signer) will exploit any problem in the constraint script’s formulation to spend money.

There are two proposed flavors of transaction introspection. In the first, there is a single opcode that takes a parameter specifying all the data from the transaction that should be pushed to the stack. In the second, each data item is a separate opcode. This latter formulation is the current proposal for Bitcoin Cash.

Use

• The following pseudo-code uses PUSH_TX_STATE_X to indicate one of any opcodes that pushes some transaction state to the stack.
• It also uses the form PUSH { [CODE] } to indicate “serialize CODE into a byte array and push it onto the stack”.
• It uses uncapitalized words such as “repeat” to indicate some kind of manual or macro “preprocessor” expansion of the contained code.

In pseudo-code, such a system would look like:

CheckSig Replacement

This replaces checksig, with the constraint script specifying the sighash:

// build the sighash from parts of the transaction
PUSH_TX_STATE_X
Repeat 
  {
  PUSH_TX_STATE_X
  CAT
  }
// turn it into a 32 byte hash (not strictly needed, because CDS does this automatically)
HASH256
// check signature
CHECKDATASIGVERIFY

script 1

Problem

This separate opcode formulation restricts the generality of introspection and CDS because it forces the constraint script to choose the sighash algorithm and contents. A satisfier script can customize the algorithm by providing output indexes, etc, but it cannot (say) increase the number of outputs to be signed.

A fully general formulation would both

• allow the constraint script to require that some portions of the transaction are signed,
• and allow the signer to include additional constraints upon the validity of his signature by specifying other portions of the transaction.

Enter EXEC

Exec allows code pushed onto the stack to be executed. So a constraint script could allow a signer to include additional constraints by executing some script that the signer provides. For example, this pseudo code allows the signer to provide ANY sighash data:

// Constraint
EXEC
HASH256
CHECKDATASIGVERIFY

// Satisfier
PUSH 
{
    PUSH_TX_STATE_X
    Repeat 
    {
        PUSH_TX_STATE_X
        CAT
    }
}

script 2

This is insecure. If the preimage of ANY data ever signed by this address is known then the satisfier can be replaced by:

PUSH 
{
    PUSH_DATA [known signed data]
}

script 3

To solve this problem, the constraint script can also require that some unique data be part of the signature. In other words, BOTH the constraint script and the satisfier script contribute to the sighash:

// Constraint   
EXEC  // First get the parts of the tx the satisfier script wants

// Next get parts the constraint script wants, AT LEAST 1 unique part of the tx
// must be included!
PUSH_TX_STATE_X
Repeat 
  {
  PUSH_TX_STATE_X
  CAT
  }
CAT // combine the satisfier script's parts with the constraint script parts
HASH256
CHECKDATASIGVERIFY

script 4

The satisfier script would still be script 2.

This is also insecure! Given a signed transaction, an attacker could create a double spend that strips away the satisfier’s signing requirements on the transaction data (and presumably replacing that data with his own exploit) by taking the output of script 2 from the signed transaction and using it as the known data in script 3.

A final formulation solves these problems. The constraint script must make the signature commit to the resulting data AND the program that produced that data:

// Constraint
DUP  // Take a copy of the satisfier script program     
EXEC  // Now execute that program to get the parts of the tx the satisfier script wants
// Next get parts the constraint script wants to enforce
PUSH_TX_STATE_X  
Repeat   
  {  
  PUSH_TX_STATE_X  
  CAT  
  }  
CAT // combine the satisfier script's parts with the constraint script parts 
CAT // combine that with the text of the satisfier script program 
HASH256  // So hashing [constraint script tx data || satisfier script tx data || satisfier script program]
CHECKDATASIGVERIFY

With this formulation, the signature requires that a certain program be executed to obtain the data that is subsequently signed. This means that this signature will not work for data provided by any other program.

Note that with this formulation, we could go back to allowing the constraint script to enforce no transaction data itself, and trust that the satisfier script doesn’t do something stupid.

Clearly, a boneheaded satisfier script program could still be replayed on other transactions. For example, not referring to the transaction at all (e.g. “OP_1”), or referring to data with low or no entropy (transaction version, or contents of OP_RETURN). But there are plenty of ways a script can accidentally become “any one can spend” (such as an “OP_1” constraint script). In sum, while it is better to protect script authors from themselves, we should not do so at the expense of functionality.