Skip to content

Instantly share code, notes, and snippets.

@RobinLinus
Last active February 19, 2024 01:30
Show Gist options
  • Save RobinLinus/9a69f5552be94d13170ec79bf34d5e85 to your computer and use it in GitHub Desktop.
Save RobinLinus/9a69f5552be94d13170ec79bf34d5e85 to your computer and use it in GitHub Desktop.
Emulate covenants using only OP_CAT and ECDSA signatures

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.

@nyonson
Copy link

nyonson commented Feb 17, 2024

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?

@RobinLinus
Copy link
Author

RobinLinus commented Feb 18, 2024

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.

@nyonson
Copy link

nyonson commented Feb 18, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment