// Covenants and Recursion #Bitcoin
The Coins Must Flow…In A Finite State Machine
Covenant is a loose term in bitcoin-land because there are a handful of proposals out there which all satisfy some level of a covenant. Here is a relatively succinct description from the mailing list.
When the scriptPubKey of a UTXO restricts the scriptPubKey in the output(s) of a tx spending that UTXO.
– Anthony Towns
Time to muddle that up.
Covenants limit how bitcoin is moved, not just how it is locked. So spending a UTXO goes from “Hey, I own this private key” to “Hey, I own this private key and I am moving the bitcoin as specified”. An example of a covenant could be something like “Outputs of the spending transaction must be exactly 100,000 sats”.
This is a large departure from the original Script model which generally focuses on how coins are locked. There are some light covenant aspects like the OP_CHECKLOCKTIME opcode, which inspects the spending transaction to ensure its locktime is old enough. But these are very scoped, limited covenants. Next generation off-chain contracts will probably require more introspective covenants. Things like flow control where a user could limit any transaction paying out of an address to a certain number of coins. Or vaults, where a user could require coins to first move to staging address and wait for some time before moving to any other address. A use case I am curious about is joinpools which could horizontally scale the ownership of a UTXO, maybe making the last mile of Lightning Network onboarding less painful for new users.
With any new feature proposal for Bitcoin, the complexity concerns need to be weighed. Covenants are powerful and power can be kinda scary. They might be too powerful and expose a lurking bug which breaks all of Bitcoin. One of the original concerns with covenants is that they could be used to whitelist/blacklist coins, some sort of “coins can only be sent to these X addresses” breaking fungibility. This would definitely be possible, but I don’t think it is very relevant since there is already a much easier way to implement this in bitcoin: a simple multisig address where one party (e.g. evil government) would only sign a transaction if it is sending to a “whitelisted” address. I think the covenant version is “scarier” since it is covered by consensus, so more locked-in. But it would be more expensive to operate, so no reason an authority figure would do it that way over the existing multisig implementation.
A more interesting worry for covenants is recursive covenants. A covenant’s power correlates with how many transaction fields it can introspect. As mentioned above, there are some existing op codes with limited covenant power since they can introspect one field (e.g. locktime) of a spending transaction. On the other end of the spectrum would be an opcode which could introspect every field of a transaction. Closer to this end of the spectrum it becomes possible for a covenant to enforce that coins are spent to an output with the same covenant it is in. Coins can end up in an infinite recursive covenant, oh no! But it should be pointed out that recursive versus non-recursive covenants are not that different from a scary perspective. Someone could create a covenant output which restricts the spending output to a huge (like, thousands) chain of transactions. Not much difference from a user’s perspective and they probably just shouldn’t lock their coins in such a fashion.
With that said, how exactly are recursive covenants created? Gonna have to get into the nitty-gritty specifics to understand that, including expanding the definition from Towns at the top. And I think this is where this post turns into a somewhat rambling journey.
A covenant can restrict the general shape of the spending transaction, stuff like the number of inputs or outputs, or locktime. A more granular covenant, with deeper introspection, can restrict the scripts in the spending transaction’s outputs. Most modern UTXO scripts are some form of a hash commitment to a script, not the script itself like the old school pre-P2SH outputs. A commitment requires the data be known when created. If a covenant implementation only has the power to check if an output hash equals a given hash, it is much more limited than if it somehow had the power to check if the script itself matched a template of some sort.
|-Covenant TX-| |-Spending TX-| |--Future TX--|
I_C0 -+-+- O_C0 -- I_S0 -+-+- O_S0 -- I_F0 -+-+- O_F0
| |
I_C1 -+ +- O_C1
The Covenant transaction’s O_C0 output has a covenant which restricts the shape of its Spending transaction, possibly even the output script in O_S0 too. This could place a covenant on the Future transaction in the chain.
This is right around where the line is drawn between non-recursive and recursive covenants. A non-recursive covenant can simply commit to an equivalence check of the output hash. If the covenant is just for the next transaction, then it is clearly known when the covenant is defined. But what if the covenant is for a chain of transactions? Well, if it looks something like a Directed Acyclic Graph (DAG), where each transaction moves the coins to a new state (a.k.a node in the DAG), then it is also non-recursive. Since DAG’s are acyclic, no recursion, the whole thing can be described when the covenant is defined. So it is possible to commit to is just like a single transaction.
A recursive covenant adds a reference to itself somehow. The chain of transactions look more like a finite state machine instead of the DAG shape of non-recursive chains. I am guessing that a contract which could be described in a few states and their transitions could technically be copy/pasted a bunch into a huge DAG. But that seems complex and limiting. Ideally the states and their relationships could be coded up once and have no limits applied. That introduces some dynamic elements that cannot be known when the initial covenant is created. The circular dependencies make it impossible to commit to a hash like in the non-recursive case.
One way to codify a recursive finite state machine is with deeper introspection into the output script. The covenant needs to be able to enforce the requirement “this output script conforms to a certain template” (a.k.a. encumber the output). The looser template requirement (vs. a hash commitment) allows there to be some dynamic data per transaction.
A pattern to get this level of introspection is to require the covenant spender to put a copy of the output script on the witness stack. This has been described as quining on the mailing list, but I am not sure how often that term is used, it’s a fun word though. Anyways, the covenant can analyze the script and enforce it does what it needs to do. But it would then have to hash that script and compare it to the actual output’s scriptPubKey to confirm that the provided script is the same one in the output. At this time, this is not possible in Script since the tweaking is 256-bit arithmetic, we would need to softfork something in like Rusty Russell’s OP_KEYADDTWEAK idea or the OP_TWEAKVERIFY opcode on the Liquid chain.
Let’s say an opcode, or opcodes, are added which enabled deeper inspection of outputs and calculation of taproot public keys. No matter the implementation, some Script template will need to be passed in as data in order to validate it against the spending transaction’s output. How do we pass this data from output to output in order to enable recursive covenants? There is a bit of a bootstrapping, circular dependency issue. If a script wants to enforce that itself is present in the next output, it needs a serialized version of itself. And the serialization needs to be committed in the witness script, not the witness stack, since the spender controls the stack. But if it serializes itself into…itself, then it changes…and the forever cycle begins. Another way to see it, if Output_Script = (Verification Checks) && (Covenant on output with serialized Output_Script) what does Output_Script look like as opcodes?
I believe there are a few ways to break the cycle, but one is to generate the serialization at runtime. Randall Naar did a great deep dive on this which I’ll try to summarize here.
// Witness Script
<script_length | script> <internal_public_key> OP_OV
// Witness Stack
<parity> <output_index>
Witness script with a mythical covenant output opcode which forces an output to match a given script.
OK, let’s get the lay of the land.
OP_OVstands for “output verify”, a mythical opcode which takes a parity bit, output index, a serialized script, a public key, and verifies the spending transaction’s specified output. That parity thing is taproot public key encoding specific, so won’t dig into it here.- As is common in a lot of Bitcoin docs, the
<>brackets represent an implicit data push, where there would be a data push opcode before the element to get it on the stack. - The
<internal_public_key>is committed to in the witness script, not passed in on the stack, so that the covenant writer knows only the scriptpath spend (the covenant controlled output) is used. Otherwise, the spender could just keypath spend and skip the whole thing.
So the above script encumbers the spending transaction’s output by the shape <script_length | script>, which includes the script length to match the taproot encoding. But the goal of a recursive covenant is for the output script to execute like normal, and also somehow get itself on the stack as data in order to encumber the spending transaction’s output with the same script. The whole circular dependency issue.
If the witness script is simply WS = <S> S, this will load S on the stack and then executes S itself. If S uses the new OP_OV opcode to imprint the next output with a script template, that template will just be S since that is what is the argument initially loaded on the stack. To be recursive, the template needs to be <S> S, as in, the original witness script. So working backwards, we need to get <S> S on the stack, which would be <<S> S> in S. We can’t simply make the witness script WS = <<S> S> S because we run into the same issue where the imprinted template <S> S doesn’t equal the witness script, it isn’t recursive. We are losing a data push wrapper.
Thinking through the left-to-right nature of Script, opcodes in S can’t “bleed across” the <S> data push (the left side of <S>), because this would cause a circular dependency. S would reference itself. Whereas <S> S is just a copy/paste and a data push opcode, all static information. Opcodes can be to the left of <S>, but they are not part of the recursive S script. They would only apply to that iteration of the output. So the logic to generate the correct recursive template data (<S> S) needs to live on the right-side of <S> in S.
Can we get S to generate <S> S at execution time? It appears we need it to “add back” a data push wrapper somewhere, and the only place to add it is on the right side of <S>. We then need to perform some manipulation to get it “in front” of S, so it can act as the data push.
// S
<script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// Witness Script (<S> S)
<S> <script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// Witness Stack
<parity> <output_index> <witness_script_length>
Randall Naar’s design for recursive covenants. I really need to acquire more of an intuition for this “Forth-like” language!
Woah, what is going on here.
OP_CATis an old opcode which has been disabled, but may be re-enabled in the near future, which concatenates two items on the stack together.- If we concatenate
<script_length>and<script>we get<script_length | script>which is the same as<<script>>, a “doubly serialized” script. witness_script_lengthandscript_lengthare not equal,script_lengthis forSwhilewitness_script_lengthis for theWS = <S> S.
The last piece of information which I have been neglecting on this journey is the total witness script length, witness_script_length. The OP_OV opcode needs this to verify the taproot output. Should this be committed to in the witness script or left more flexible in the witness stack? For simplicity, I have it in the witness stack below, but I don’t think there is any technical reason it couldn’t be in the witness script and use the same OP_SWAP strategy to get it “in front” of the other elements.
// STEP 0: Empty stack and initial witness stack and script.
+-----------+
<parity> <output_index> <witness_script_length> <S> <script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 1: Load parity.
| p |
+-----------+
<output_index> <witness_script_length> <S> <script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 2: Load output index.
| oi |
| p |
+-----------+
<witness_script_length> <S> <script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 3: Load witness script length.
| wsl |
| oi |
| p |
+-----------+
<S> <script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 4: Load script S.
| S |
| wsl |
| oi |
| p |
+-----------+
<script_length> OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 5: Load script length.
| sl |
| S |
| wsl |
| oi |
| p |
+-----------+
OP_SWAP OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 6: Swap script length and script S to get the length in front to act as a data push.
| S |
| sl |
| wsl |
| oi |
| p |
+-----------+
OP_DUP OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 7: Duplicate script S.
| S |
| S |
| sl |
| wsl |
| oi |
| p |
+-----------+
OP_CAT OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 8: Concatenate the two S scripts.
| S|S |
| sl |
| wsl |
| oi |
| p |
+-----------+
OP_CAT OP_CAT <internal_public_key> OP_OV
// STEP 9: Concatenate the script length with the two S's. sl|S|S is equivalent to <S>|S (implicit data push).
| <S>|S |
| wsl |
| oi |
| p |
+-----------+
OP_CAT <internal_public_key> OP_OV
// STEP 10: Concatenate the witness script length with the ready to go witnes script <S> S.
| wsl|<S>|S |
| oi |
| p |
+-----------+
<internal_public_key> OP_OV
// STEP 11: Load the internal public key.
| ipk |
| wsl|<S>|S |
| oi |
| p |
+-----------+
OP_OV
// STEP 12: Finally verify the output with the four args on the stack.
Execution of the witness script to verify the spending transaction output matches the witness script <S> S.
This implementation depends on two lower level opcodes being enabled: OP_CAT and OP_TWEAKVERIFY. However, it is technically possible to get recursive covenants with just OP_CAT, but a new strategy is needed to get a script on the stack since there is no way to tweak it (256-bit math).
I’ll admit this alternate strategy bent my mind as much as the first. It is implemented in the purrfect vault proof of concept. This strategy only depends on a new OP_CAT, so there is no introspection of the output scripts themselves. So how does it recurse? The output script enforces a finite state machine by making sure outputs are sent to the same address, the same output script. The current “state” of the covenant is determined by the structure of the inputs into the UTXO. The script analyzes the inputs and can recognize which step it is in and what are the possible next steps. I believe this strategy is less flexible since all the logic needs to be stuffed into a single output script, but I haven’t really thought through the tradeoffs.
