rich1.0npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3lhttps://nostr.ae/npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3lnjumphttps://nostr.ae📅 Original date posted:2022-02-23 📝 Original message:Subject: Turing-Completeness, And Its Enablement Of Drivechains Introduction ============ Recently, David Harding challenged those opposed to recursive covenants for *actual*, *concrete* reasons why recursive covenants are a Bad Thing (TM). Generally, it is accepted that recursive covenants, together with the ability to update loop variables, is sufficiently powerful to be considered Turing-complete. So, the question is: why is Turing-completness bad, if it requires *multiple* transactions in order to implement Turing-completeness? Surely the practical matter that fees must be paid for each transaction serves as a backstop against Turing-completeness? i.e. Fees end up being the "maximum number of steps", which prevents a language from becoming truly Turing-complete. I point out here that Drivechains is implementable on a Turing-complete language. And we have already rejected Drivechains, for the following reason: 1. Sidechain validators and mainchain miners have a strong incentive to merge their businesses. 2. Mainchain miners end up validating and commiting to sidechain blocks. 3. Ergo, sidechains on Drivechains become a block size increase. Also: 1. The sidechain-to-mainchain peg degrades the security of sidechain users from consensus "everyone must agree to the rules" to democracy "if enough enfranchised voters say so, they can beat you up and steal your money". In this write-up, I will demonstrate how recursive covenants, with loop variable update, is sufficient to implement a form Drivechains. Logically, if the construct is general enough to form Drivechains, and we rejected Drivechains, we should also reject the general construct. Digression: `OP_TLUV` And `OP_CAT` Implement Recursive Covenants ================================================================ Let me now do some delaying tactics and demonstrate how `OP_TLUV` and `OP_CAT` allow building recursive covenants by quining. `OP_TLUV` has a mode where the current Tapleaf is replaced, and the new address is synthesized. Then, an output of the transaction is validated to check that it has the newly-synthesized address. Let me sketch how a simple recursive covenant can be built. First, we split the covenant into three parts: 1. A hash. 2. A piece of script which validates that the first witness item hashes to the above given hash in part #1, and then pushes that item into the alt stack. 3. A piece of script which takes the item from the alt stack, hashes it, then concatenates a `OP_PUSH` of the hash to that item, then does a replace-mode `OP_TLUV`. Parts 1 and 2 must directly follow each other, but other SCRIPT logic can be put in between parts 2 and 3. Part 3 can even occur multiple times, in various `OP_IF` branches. In order to actually recurse, the top item in the witness stack must be the covenant script, *minus* the hash. This is supposed to be the quining argument. The convenant script part #2 then checks that the quining argument matches the hash that is hardcoded into the SCRIPT. This hash is the hash of the *rest* of the SCRIPT. If the quining argument matches, then it *is* the SCRIPT minus its hash, and we know that we can use that to recreate the original SCRIPT. It then pushes them out of the way into the alt stack. Part #3 then recovers the original SCRIPT from the alt stack, and resynthesizes the original SCRIPT. The `OP_TLUV` is then able to resynthesize the original address. Updating Loop Variables ----------------------- But repeating the same SCRIPT over and over is boring. What is much more interesting is to be able to *change* the SCRIPT on each iteration, such that certain values on the SCRIPT can be changed. Suppose our SCRIPT has a loop variable `i` that we want to change each time we execute our SCRIPT. We can simply put this loop variable after part 1 and before part 2. Then part 2 is modified to first push this loop variable onto the alt stack. The SCRIPT that gets checked is always starts from part 2. Thus, the SCRIPT, minus the loop variable, is always constant. The SCRIPT can then access the loop variable from the alt stack. Part 2 can be extended so that the loop variable is on top of the quined SCRIPT on the alt stack. This lets the SCRIPT easily access the loop variable. The SCRIPT can also update the loop variable by replacing the top of the alt stack with a different item. Then part 3 first pops the alt stack top (the loop variable), concatenates it with an appropriate push, then performs the hash-then-concatenate dance. This results in a SCRIPT that is the same as the original SCRIPT, but with the loop variable possibly changed. The SCRIPT can use multiple loop variables; it is simply a question of how hard it would be to access from the alt stack. Drivechains Over Recursive Covenants ==================================== Drivechains can be split into four parts: 1. A way to commit to the sidechain blocks. 2. A way to move funds from mainchain to sidechain. 3. A way to store sidechain funds. 4. A way to move funds from sidechain to mainchain. The first three can be easily implemented by a recursive covenant without a loop variable, together with an opcode to impose some restriction on amounts, such as `OP_IN_OUT_AMOUNT`. The technique we would use would be to put the entire sidechain funds into a single UTXO, protected by a recursive covenant. The recursive covenant ensures that it can store the sidechain funds. This covers part 3. The recursive covenant could, with the help of `OP_CAT` and `OP_CTV`, check that every transaction spending the UTXO has a second output that is an `OP_RETURN` with a commitment to the sidechain block. We can ensure that only one such transaction exists in each mainchain block by adding a `<1> OP_CSV`, ensuring that only one sidechain-commitment transaction can occur on each mainchain block. This covers part 1. Mainchain-to-sidechain pegs require the cooperation of a sidechain validator. The sidechain validator creates a block that instantiates the peg-in on the sidechain, then creates a transaction that commits to that sidechain block including the peg-in, and spending the current sidechain UTXO *and* the mainchain funds being transferred in. Then the entity requesting the peg-in checks the sidechain block and the commitment on the transaction, then signs the transaction. The value restriction on the recursive covenant should then be to allow the output to be equal, or larger, than the input. This covers part 2. The recursive sidechain covenant by itself has a constant SCRIPT, and thus has a constant address. The last part of Drivechains -- sidechain-to-mainchain peg --- is significantly more interesting. Digression: Hashes As Peano Naturals ------------------------------------ It is possible to represent natural numbers using the following Haskell data type: ```Haskell data Nat = Z | S Nat -- Z :: Nat -- S :: Nat -> Nat ``` We can represent naturals as: * `0` == `Z` * `1` == `S Z` * `2` == `S (S Z)` * `3` == `S (S (S Z))` * etc. How do we translate this into Bitcoin SCRIPT? * `Z` == Any arbitrary 160-bit number. * `S` == `OP_HASH160`. Thus: * `0` == `Z` * `1` == `hash160(Z)` * `2` == `hash160(hash160(Z))` * `3` == `hash160(hash160(hash160(Z)))` * etc. In particular: * We can increment a number by simply doing `OP_HASH160`. * We can decrement a number by having the supposed decrementation be supplied on the witness stack, then validating that it is indeed the next lower number by hashing the witness item and comparing it to the number we have. Note also that ***we do not need `OP_ADD` or `OP_SUB` for this***, though that would actually make it simpler. (But yeah, the whole point is that *BITCOIN IS A LOT MORE POWERFUL THAN YOU EXPECT*.) This is relevant to us due to how sidechain-to-mainchain pegs are implemented. Drivechain Peg-Out ------------------ In Drivechains, first somebody proposes to withdraw some amount of funds from the sidechain to a mainchain address. Then mainchain miners enter a voting period, during which they either agree to the withdrawal, or disagree. We can use the above schema to keep track of a running total number of votes. We define some numbers: * `Z` == `0` * `P` == some maximum time period. We then encode `Z`, `P / 2`, and `P` using the hashed-Peano encoding in the previous subsection. In order to allow withdrawals, we have an alternate branch, such as a different Tapleaf, for a withdrawal SCRIPT. This only requires that the first output has the same address as itself (i.e. the sidechain covenant), and the second output has a new recursive covenant, the peg-out covenant. The peg-out covenant has three loop variables: * `v`, initialized to `Z`. * This is the "validity level" of the peg-out. * Voters who want to vote "for validity" would *increment* this count. * Voters who want to vote "against validity" would *do nothing*. * `t`, initialized to `Z`. * This is the voting time period. * Each time the peg-out covenant is used, this loop variable is incremented. * Once it reaches `P`, voting ends and the voting branches of the peg-out covenant are disabled, * `a`, initialized to the peg-out address. * This is not actually changed in the covenant, but it is useful to keep it in the loop variable storage area. * With `OP_CTV` this can be an address that commits to any number of promised outputs. The peg-out covenant has these branches: * If `v` equals `P / 2`, then the UTXO can be spent to the address `a`. This is synthesized with an `OP_CTV` and `OP_CAT`. * If `t` equals `P`, then the UTXO can only be spent by being pegged into the sidechain covenant. If this branch is not entered, we increment `t`. * This implies an inter-recursion between the sidechain covenant and the peg-out covenant. * Check if the witness stack top is true or not: * If true, increment `v` and recurse ("vote-for" branch). * Else just recurse ("vote-against" branch). ### Fixing Inter-recursion We can observe that the inter-recursion between the sidechain covenant and the peg-out covenant is problematic: * `OP_CTV` requires that the hash of the output covenant is known. * `OP_TLUV` will only replace the same output index as the input index it is on. This prevents the inter-recursion between the sidechain covenant and the peg-out covenant. To fix this, we can observe that we can translate any set of inter-recursive functions, such as this: ```Haskell foo :: FooArg -> Result foo fa = bar (fooCode fa) bar :: BarArg -> Result bar ba = foo (barCode ba) ``` ...into a single self-recursive function: ```Haskell fooBar :: Either FooArg BarArg -> Result fooBar a = case a of Left fa -> fooBar (Right (fooCode fa)) Right ba -> fooBar (Left (barCode ba)) ``` Similarly, we can instead convert the inter-recursive sidechain and peg-out covenants into a single self-recursive covenant. This single covenant would have the same set of loop variables `v`, `t`, and `a` as the peg-out covenant described above. This time, `a` is not an address, but an entire output (i.e. `scriptPubKey` and `amount`). By default, `v`, `t`, and `a` are a number `0`. If so, then there is no pending peg-out being voted on. If there is no pending peg-out, then either we just commit to a sidechain block, or we commit to a sidechain block *and* start a new peg-out by filling in `a`, and initializing `v` and `t` to `Z`. If there is a pending peg-out, then either we just commit to a sidechain block (and implicitly downvote the pending peg-out) or commit to a sidechain block *and* indicate an upvote of the pending peg-out. If `v` has reached the limit then we require, using `OP_CTV`, that `a` appear on the second output, and that the same SCRIPT (with `v`, `t`, and `a` reseet to `0`) is on the first output, and do not impose any minimum value for the first output, and the sidechain commitment is now an `OP_RETURN` on the third output, and no other outputs. If `t` has reached the limit, then we require simply that the `v`, `t`, and `a` are reset to 0 and the sidechain commitment. With the above, all components of Drivechain are implementable with: * `OP_TLUV` * `OP_CAT` * `OP_CTV` * `OP_IN_OUT_AMOUNT` of some kind, including the ability to check the output amount is larger than the input amount (e.g. by `OP_EQUAL` or `OP_GREATER`). * Existing Bitcoin SCRIPT (`OP_ADD` **not** needed!). Conclusion ========== PH34R THE RECURSIVE COVENANT! PH34R!!!!!!!