Emulate covenants using only OP_CAT and ECDSA signatures

covenants_cat_ecdsa.md

Covenants with CAT and ECDSA

In his article, CAT and Schnorr Tricks I, Andrew Poelstra showed how to emulate OP_CHECKSIGFROMSTACK-like covenants using only OP_CATand Schnorr signatures.

Here, we show that a similar trick is possible to emulate covenants using only OP_CAT and ECDSA signatures.

The High-Level Idea

Recall the ECDSA Signature Equation

Given a secret key x and the corresponding public key P = xG. The signer chooses some random secret nonce k and computes public nonce R = kG. We call r the first coordinate of the point R. Then the signature equation for message hash H = Hash(message) is

s = ( H + r * x ) / k

Getting the Sighash onto the Stack

We get the sighash onto the stack by choosing k = 1 and x = 1/r, so the signature becomes s = H + 1.

We make the script require a signature from public key P = xG = 1/r G and require that signature to use public nonce R = kG = 1G = G. The nonce and the sighash are glued together (DER encoded) using OP_CAT into a ECDSA signature that can be verified using OP_CHECKSIGVERIFY.

So essentially, copying this signature before verifying it puts sighash + 1 onto the stack.

Further Details

Adding 1 to the Hash

Computing s = H + 1 is a bit tricky as there is no 256-bit arithmetic in Script. Either we can use Andrew's workaround

We just require the user grind her transaction data until the actual hash ends in the byte 01, which is pretty cheap (takes 256 tries on average, which at 250ns per shot would take 64 microseconds, comparable to the signing algorithm itself). Then her s value will end it 2, which we enforce by asking her to leave it off; we'll add it ourselves.

Alternatively, the unlocking script can contain H, chunked into 8 different 32-bit chunks. Then we can use regular 32-bit arithmetic to compute 1 + chunk_0 and finally, glue back together (1+chunk_0) | chunk_1 | ... | chunk_7 using OP_CAT.

Putting it all together to get a Covenant

The covenant works similar to OP_CHECKSIGFROMSTACK. However, it requires only a single signature check.

The locking script commits to prefix and postfix of the covenant TX. In the unlocking script is only the TXID of the prev TX to resolve the hash cycle. The locking script assembles the covenant TX using OP_CAT and computes its sighash by hashing it. (The covenant TX is serialized as for computing its sighash.)

Pseudocode:

cov_tx = <cov_tx_prefix> <txid> <cov_tx_postfix>

sighash = Hash256(cov_tx)

signature = (G, sighash + 1)

This computes the signature which is checked by OP_CHECKSIGVERIFY.

Stumbled upon your post trying to wrap my head around how the “+ 1” part of this algo is implemented. Do you know which parts of the transaction Andrew is referring to where the user “grinds” their transaction?

Your chunked up approach makes sense, but does that limit the output to matching an exact hash of a txn instead of enforcing certain conditions since the txn is pre-hashed?

where the user “grinds” their transaction

They grind the transaction's sighash (the hash of the TX, which is the message to be signed) such that it ends with the byte 01. That means sighash + 1 ends with the byte 02.

does that limit the output to matching an exact hash

For the covenant to work you have to commit in the unlocking script to a transaction (excluding the inputs so no hash-cycle is created). But there are no particular constrains on the hash.

They grind the transaction's sighash (the hash of the TX, which is the message to be signed) such that it ends with the byte 01. That means sighash + 1 ends with the byte 02.

That makes sense. I was also curious about what parts of the transaction exactly are grinded. I was checking out @rot13maxi's vault implementation and it looks like he uses the locktime or sequence depending on the context: https://github.com/taproot-wizards/purrfect_vault/blob/main/src/vault/signature_building.rs#L421

For the covenant to work you have to commit in the unlocking script to a transaction (excluding the inputs so no hash-cycle is create). But there are no particular constrains on the hash.

This took me a bit, but I think I get it now. For some reason I was assuming that your chunked transaction hash commitment was in the script, but it is actually in the input's witness. I was really hung up on why a supplied hash is required given the point of all this is to force the un-hashed transaction data into the witness and we can just hash that. But it is more like a means to an end to get to the signature. Calculated hash => supplied hash => signature => verify transaction.