BCH floating transactions: SIGHASH_NOINPUT emulation using CHECKDATASIG covenants

covenant_noinput.md

BCH floating transactions: SIGHASH_NOINPUT emulation using CHECKDATASIG covenants

A new sighash flag has been proposed (originally for Lightning, now for Eltoo) which redacts information about the spending inputs, most notably their transaction IDs.

This facility is both powerful and dangerous: it means that signatures intended for one transaction can be used on other transactions. It also makes up a very strong increase in the malleability of transactions. SIGHASH_NOINPUT allows for much more flexible off-chain smart contracts than nonmalleable transactions. Note that Eltoo requires SIGHASH_NOINPUT, for instance. It's not clear whether such a dangerous feature will be adopted on BCH any time soon.

In this gist I'm going to explain that CHECKDATASIG covenants let us write smart contracts that emulate SIGHASH_NOINPUT. This capability alone should in principle allow to build Lightning, Eltoo with bilaterally funded smart contracts on BCH (though, with some significant additional awkwardness in setup, and some extra setup transactions).

-- Mark B Lundeberg, 2019 Feb 6. bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

Ideas

The structure of signature hashes

Signature hashes are created from the serialization of the following items:

1. nVersion of the transaction (4-byte little endian)
2. hashPrevouts (32-byte hash)
3. hashSequence (32-byte hash)
4. outpoint (32-byte hash + 4-byte little endian)
5. scriptCode of the input (serialized as scripts inside CTxOuts)
6. value of the output spent by this input (8-byte little endian)
7. nSequence of the input (4-byte little endian)
8. hashOutputs (32-byte hash)
9. nLocktime of the transaction (4-byte little endian)
10. sighash type of the signature (4-byte little endian)

Covenants

CHECKDATASIG covenants are a somewhat surprising development that came out after the opcode was initially specified. In essence, the idea is that you can make a script that uses the same signature and pubkey in both CHECKDATASIG and CHECKSIG; this forces the scriptSig to provide a full copy of the above sighash items, and therefore it means a script can be made aware of details from the transaction it's being spent in. The nominal idea of covenants is that a script can start enforcing rules on how it is spent (which output scripts are acceptable).

Publicly-generated covenant data with shared / arbitrary keys

If there are other signatures in a script that enforce ownership, the covenant can be done with a public key whose private key is known to all, for example the secp256k1 generator point (whose private key is the integer 1). By making the covenant shared in this way, it means that anyone can perform the work of providing the covenant data.

In fact the public key can even be supplied in the scriptSig. This which frees up precious space in a P2SH script (520 bytes).

Using covenants to generate partial sighashes

Here, we will be using the covenant to break apart the sighash into two pieces: a prefix, which is signed by shared covenant (i.e.,, signed by anyone), and the suffix, which has to be also signed by the UTXO 'owner'. Crucially, the suffix signed by the owner does not include prior transaction IDs, therefore anyone can modify the input transaction IDs just like with SIGHASH_NOINPUT.

We break apart the sighash serialization into two pieces: 1-7 (prefix), and 8-10 (suffix). The concatenation (prefix+suffix) will be used in the covenant (CHECKDATASIG + CHECKSIG), and then the suffix will be used in CHECKDATASIG alone.

Basic example -- single owner script

To demonstrate the idea, I'm going to show how one can build a single-owner script (analogous to a P2PK script). After I explain how this works, I'll explain how this can be easily generalized to arbitrarily complex scripts with a basic preamble and postamble.

Our script will take a number of items from scriptSig, pushed in this order:

<owner_sig>        - signature from owner_pubkey on suffix
<suffix>           - parts 8-10 from the sighash serialization above
<covenant_pubkey>  - arbitrary covenant pubkey
<covenant_sig>     - tx signature from the covenant key, less hashtype byte
<prefix>           - parts 1-7 from the sighash serialization above

The actual locking script looks like this:

// check covenant
3 OP_PICK              // grab a copy of the suffix
OP_2OVER               // grab a copy of covenant_pubkey and covenant_sig
PUSH 0x41              // push 0x41 hashtype byte on stack
OP_CAT                 // append hashtype byte to covenant_sig
OP_SWAP                // switch order to covenant_sig, covenant_pubkey
OP_CHECKSIGVERIFY      // check covenant tx signature
OP_CAT                 // concatenate prefix+suffix
OP_SHA256              // hash once to sync number of hashes
OP_ROT                 // change pubkey,sig,hash order to sig,hash,pubkey
OP_CHECKDATASIGVERIFY  // check covenant data signature

// now the stack only has <owner_sig>, <suffix>.

// owner enforcement -- like P2PK but it uses CHECKDATASIG
<owner_pubkey>         // push owner's pubkey
OP_CHECKDATASIG        // check owner's signature on suffix

How it works

1. When the owner makes a signature, he selects a list of outputs, and hashes this into hashOutputs. He then builds the 40-byte suffix using hashOutputs, locktime, and sighash mode 0x41 (ALL|FORKID). The owner then signs suffix using his key, to get the signature owner_sig. He then can share owner_sig, suffix, and the redeemscript.
2. Now some funds can be sent to the locking script. Note that in step 1, the owner did not need to know the input transaction ID to create owner_sig.
3. Now anyone who knows the redeemscript, the outputs list, suffix, and owner_sig can build a full transaction that spends the coin created in step 2. First they choose a random covenant key (or a known one) and sign the transaction using the same sighash mode as in suffix. Then, they break apart the sighash digest into prefix and suffix, where the suffix must match the owner's suffix identically.
4. If the input transaction ID gets malleated for some reason, anyone can again come and produce a new covenant signature using the new prefix.

Advanced example -- conditional script

Now I'm going to show how the above can be modified for a fairly common case: a conditional script with two clauses.

<script_data>      - to be used by the 'inner' script
<owner_sig>        - signature from owner_pubkey on suffix
<suffix>           - parts 8-10 from the sighash serialization above
<which_path>       - boolean value that chooses which script to execute
<covenant_pubkey>  - arbitrary covenant pubkey
<covenant_sig>     - tx signature from the covenant key, less hashtype byte
<prefix>           - parts 1-7 from the sighash serialization above

The locking script from above gets modified like so:

// check covenant
3 OP_PICK              // grab a copy of the suffix
OP_2OVER               // grab a copy of covenant_pubkey and covenant_sig
PUSH 0x41              // push 0x41 hashtype byte on stack
OP_CAT                 // append hashtype byte to covenant_sig
OP_SWAP                // switch order to covenant_sig, covenant_pubkey
OP_CHECKSIGVERIFY      // check covenant tx signature
OP_CAT                 // concatenate prefix+suffix
OP_SHA256              // hash once to sync number of hashes
OP_ROT                 // change pubkey,sig,hash order to sig,hash,pubkey
OP_CHECKDATASIGVERIFY  // check covenant data signature

// now the stack has <script_data>,<owner_sig>,<suffix>,<which_path>.
// custom script starts here
OP_IF                  // decide execution path based on which_path
    <clause1_pubkey>
    OP_CHECKDATASIGVERIFY
    ... (do stuff with script_data)
OP_ELSE
    <clause0_pubkey>
    OP_CHECKDATASIGVERIFY
    ... (do stuff with script_data)
OP_ENDIF

Now, the owner_sig can be provided by either clause1_pubkey or clause0_pubkey. All the usual things can go inside the clauses, for example script_data could contain the secret for a hash lock.

Variations

Finer locking --- The script can be made more elaborate by combining more pieces. For example, the owner may only want to sign the hashOutputs but not locktime. Or, it is desired that the hashtype byte can be made flexible (maybe an option to use SIGHASH_SINGLE is desired). When this is done, the script should take additional care that pieces coming after the hashOutputs are checked to have the correct size, to avoid some kinds of exploit where the signature data might be shifted out.

Additional data -- The owner can also sign additional data that is not part of the transaction serialization. This would be concatenated into the data signed by the owner, but not concatenated into the covenant. Again, some thought should be put into carefully size-checking components to avoid exploits here. Using such additional data, we can do Eltoo contracts that don't rely on the locktime trick.

Expanding size limit -- Since the size of a stack item is limited to 520 bytes, and prefix+suffix must fit in that amount, this means that the scriptCode is limited to be a total of 361 bytes long. Normally, scriptCode is the entire locking script, so this prevents the locking script from being the full 520 byte length. This can however be fixed using OP_CODESEPARATOR. The covenant CHECKDATASIGVERIFY occurs in a preamble block, leaving data on the alt stack. Then at the very end of the script, the covenant is completed by running CHECKSIG on those stored items, just after OP_CODESEPARATOR.

Limitations

Unlike SIGHASH_NOINPUT, this can't be used on a regular multisig input. This means the usual constructions of things like Lighting / Eltoo need to be modified to use this script (containing multisig) in place of bare multisigs.

My last gist about BIP62 and Schnorr had a theme of using P2PKH malleability fixes and P2PKH aggregated signatures, to keep complicated scripts like this OFF the chain, so that privacy is maintained in the case of a collaborative closure. I believe that idea can be combined with this one, but I think it will be significantly more complicated than one might expect.

An inefficient Spedn equivalent:

contract NoInput(PubKey clause0Pubkey, PubKey clause1Pubkey) {
    challenge spend(DataSig ownerSig, bin suffix, PubKey covenantPubkey, DataSig covenantSig, bin prefix, bool whichPath) {
        verify checkSig(Sig(covenantSig . 0x41), covenantPubkey);
        verify checkDataSig(covenantSig, sha256(prefix . suffix), covenantPubkey);

        if (whichPath) {
            verify checkDataSig(ownerSig, suffix, clause1Pubkey);
        } else {
            verify checkDataSig(ownerSig, suffix, clause0Pubkey);
        }
    }
}