Instantly share code, notes, and snippets.

# RobinLinus/covenants_cat_ecdsa.md

Last active July 30, 2024 15:14
Show Gist options
• 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_CAT`and 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 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?

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 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.