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.

RobinLinus/covenants_cat_ecdsa.md