2024.02 Vol.3

Little ol’ OP_CAT

Bitcoin’s original OP_CAT opcode was simple. It took two items off the stack, concatenated them together, and placed the new item on the stack. Despite its simplicity, it was disabled by Satoshi himself way back in the day. But he had a pretty good reason to do so, it was one of a handful of opcodes that had some serious DOS issues. It was straight forward for an attacker to create a script which put some data on the stack and ran OP_DUP OP_CAT (duplicate concatenate) again and again and again until a validating node’s memory exploded. There was no limit on the size of things being concatenated. Satoshi must not of had a good enough reason to try and keep OP_CAT, so he just disabled it.

Kinda interesting, but what does that have to do with covenants and abstract algebra?

Well it turns out that re-enabling OP_CAT (with a new memory restriction) and adding a pinch of algebra, enables covenants on bitcoin. But how can something as simple as “push two data items together” enable offchain contract patterns like vaults? The best person to explain this is not me, that would be Andrew Poelstra, who wrote the Cat and Schnorr Tricks blog post. Andrew is great at walking through really complex things in simple terms. But with that said, I had to re-read that post like five times and let it sink in over a day before it started to click. I’ll now try to lock it in by re-describing it here in a less digestible form.

To start, how does an output script enforce a covenant? A covenant constrains the spending transaction, but bitcoin has no script opcodes to introspect a spending transaction. In other words, how can an output script enforce something like “all outputs of the spending transaction are less than 100000 sats” if it can’t even see those spending transaction outputs? Well, a way for a script to get any data is to have it be passed through the witness. In the common cases the witness data is just a signature which satisfies the output script, but an output script can ask for pretty much anything from the spender. It could even ask for the spending transaction!

Let’s say the spender complies and puts the spending transaction data in the witness stack. Now the output script can run its validation checks (e.g. outputs less than 100000) and fail if the spending transaction doesn’t follow the covenant rules. The only obvious problem here is that the spender can pass any data to the output script in order to satisfy it, there is nothing enforcing that this is the actual spending transaction being passed in. As in, the spender could lie! Ideally, Script had some opcode that could verify witness data matches the actual spending transaction.

There have been proposals to add a new opcode to bitcoin called OP_CHECKSIGFROMSTACK which would help out here. It would be similar to the exisiting OP_CHECKSIG except the signed data would come from the witness stack instead of implicitly from the spending transaction. OP_CHECKSIGFROMSTACK combo’d with OP_CAT would be a relatively clean way to validate witness data. The script could take the transaction data as input on the witness stack, concatenate it all together with OP_CAT, hash it (OP_SHA256), and then check the message against the given signature with OP_CHECKSIGFROMSTACK. It would then use that same signature and call OP_CHECKSIG. If both check out, the script knows this data is what exists in the actual spending transaction (the same message was used in both) and can perform further validation on the transaction components.

Is OP_CHECKSIGFROMSTACK a requirement for covenants? Hmmm…I think now is a good time to quickly refresh on the Schnorr signature scheme and the OP_CHECKSIG opcode.

sG = hash(R||P||m)*P + R
^    ^                 ^   
|    |                 |
|    |                 |
s  = hash(R||P||m)*d + k 

Schnorr scheme used to create and verify a signature, R||s. In a bitcoin transaction, the message m contains the spending transaction data.

The OP_CHECKSIG opcode expects two items on the stack, the public key P and the signature R||s. That is enough to verify that the private key holder authorized the transaction because the message m is implicit. OP_CHECKSIG is a unique opcode because it has limited introspective power which it uses to build m with the spending transaction data itself (in taproot-land, there are a few more constants in here that I am ignoring for now). Can these introspection powers, however limited, be leveraged for covenants?

OP_CHECKSIG is doing two jobs at once, it verifies that the signer owns the private key and that they committed to the message (a.k.a. the spending transaction). A covenant implementation doesn’t much care for the “signer”, it just wants to verify the message data somehow. What if the secret elements are “fixed” to 1 instead of the usual big random numbers (private key and nonce). The signature scheme starts to look way simpler, maybe even calculable…

sG = hash(G||G||m)*G  + G
^    ^                  ^   
|    |                  |
|    |                  |
s  = hash(G||G||m)*1  + 1  

Fix the secret scalars d and k to 1 since covenants don’t care about the signer verification part. Those 1’s scale up to the constant generator point G.

Now, admittedly, this is getting a little weird. You may start to think “Man, this feels really round-about!” and that…is because it is. But the goal here is the use the existing tools plus a new OP_CAT to get covenant functionality. Even if inefficiently.

With the secret elements “one’d-out”, the signature (R, s) boils down to (G, hash(G||G||m) + 1). If a script wanted to verify this signature with OP_CHECKSIG, it could pass the public key G (it too is fixed!) and the signature G||(hash(G||G||m) + 1). Look at all those constants. This means if all the transaction data is on the stack, the output script could leverage the OP_CHECKSIG introspection to verify the transaction data in a few steps:

1. Smash all the transaction data together to get m.
2. Smash that into G (constant generator point) twice.
3. Hash that.
4. Add one.
5. Smash that into G again, that’s s!
6. Pass G (the public key) and the calculated s to OP_CHECKSIG.

Bitcoin script already has the OP_SHA256 opcode, so the hash step is easy. Funny enough, that “add one” part is a little tricky, but more on that later. The big takeaway here is, dang, that’s a lot of concatenation! If only we some sort of OP_CAT…

OK, so there is a path here. Before moving on though, it is worth pointing out an opcode characteristic ol’ Mr. Poelstra mentioned on a podcast. OP_CAT concatenates two pieces of data, but it also gives scripts the ability to split data. If OP_CAT is in a script, the data starts as “split” and can be used before it is finally concat’d. The splitting is just being done “under the hood” by the creator of the witness. A delegation of sorts. The point here is that an opcode provides us with its operation and its reverse operation.

So back to verifying this data. Step #1, “Smash all the transaction data together to get m”, tosses a bunch of OP_CATs into the covenant script. This “splits up” the different parts of the transaction data (e.g. outputs, locktime, inputs, etc.) and allows the script to run custom validations (e.g. are the output amounts all less than 100000 sats?). Things then get concatenated together and verified in step #6 that it is truly what is in the transaction.

It appears OP_CAT enables covenants in output scripts…as long as the script can just add one to the hash, step #4, before running OP_CHECKSIG. I found this to be a deceptively tricky problem to think through. Since the “add one” is working in the “private” scalar part of the signature equation, it is 256-bit arithmetic. The script cannot simply use a <1> OP_ADD because it only supports 32-bit. So how does it add one?

The script can use a trick similar to splitting data with OP_CAT, but a little weirder. If it could somehow assume that the transaction hash ends with a 1, then it could also assume that the signature ends with a 2. It wouldn’t have to perform any 256-bit arithmetic, kinda side-stepping the issue. Can it ask this of the sender, similar to how it asks them to split the transaction data?

Making sure the transaction hash ends in a 1 isn’t as difficult as one might think. Obviously the sender can’t go from hash-to-data due to the discrete log problem, but they can “grind” the transaction data by tweaking it slightly and checking if it ends in 1. This is similar to bitcoin mining, but since only the last byte value matters, there are ton more “right” inputs. It should only take a blink of an eye to find one. Transaction fields like locktime and sequence are ripe for grinding since in a lot of contexts small changes to them won’t change the meaning of the transaction.

Once a sender has a hash that ends in 1, the output script requires them to “split” it (heyo OP_CAT!) and leave off that last byte. The output script itself can compute the transaction hash by concatenating a 1 or compute the signature by concatenating a 2.

                                +------------------+
      +------------------+      | Transaction Hash |
      | Transaction Data |      | Minus Last Byte  |
      +-------------+----+      +-+--------------+-+
                    |             |              |
                    | SHA256      | ||1          | ||2
INPUTS              |             |              |
--------------------+-------------+--------------+----------
COMPUTED            |             |              |
                    |             |              |
                 +--v-------------v-+       +----v------+
                 | Transaction Hash |       | Signature |
                 +------------------+       +-----------+

Operations on the provided spending transaction data and hash, using the new fancy OP_CAT.

This adds a bunch more complexity, but now the output script can enforce its covenant responsibilities. It has the transaction data on the stack, can validate it, verify the computed hash to the given hash hash_minus_last_byte||1, and then validate the signature hash_minus_last_byte||2 with the actual spending transaction. A covenant!