{"type":"rich","version":"1.0","author_name":"npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","author_url":"https://nostr.ae/npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-02-23\n📝 Original message:Subject: Turing-Completeness, And Its Enablement Of Drivechains\n\nIntroduction\n============\n\nRecently, David Harding challenged those opposed to recursive covenants\nfor *actual*, *concrete* reasons why recursive covenants are a Bad Thing\n(TM).\n\nGenerally, it is accepted that recursive covenants, together with the\nability to update loop variables, is sufficiently powerful to be\nconsidered Turing-complete.\nSo, the question is: why is Turing-completness bad, if it requires\n*multiple* transactions in order to implement Turing-completeness?\nSurely the practical matter that fees must be paid for each transaction\nserves as a backstop against Turing-completeness?\ni.e. Fees end up being the \"maximum number of steps\", which prevents a\nlanguage from becoming truly Turing-complete.\n\nI point out here that Drivechains is implementable on a Turing-complete\nlanguage.\nAnd we have already rejected Drivechains, for the following reason:\n\n1.  Sidechain validators and mainchain miners have a strong incentive to\n    merge their businesses.\n2.  Mainchain miners end up validating and commiting to sidechain blocks.\n3.  Ergo, sidechains on Drivechains become a block size increase.\n\nAlso:\n\n1.  The sidechain-to-mainchain peg degrades the security of sidechain\n    users from consensus \"everyone must agree to the rules\" to democracy\n    \"if enough enfranchised voters say so, they can beat you up and steal\n    your money\".\n\nIn this write-up, I will demonstrate how recursive covenants, with\nloop variable update, is sufficient to implement a form Drivechains.\nLogically, if the construct is general enough to form Drivechains, and\nwe rejected Drivechains, we should also reject the general construct.\n\nDigression: `OP_TLUV` And `OP_CAT` Implement Recursive Covenants\n================================================================\n\nLet me now do some delaying tactics and demonstrate how `OP_TLUV` and\n`OP_CAT` allow building recursive covenants by quining.\n\n`OP_TLUV` has a mode where the current Tapleaf is replaced, and the\nnew address is synthesized.\nThen, an output of the transaction is validated to check that it has\nthe newly-synthesized address.\n\nLet me sketch how a simple recursive covenant can be built.\nFirst, we split the covenant into three parts:\n\n1.  A hash.\n2.  A piece of script which validates that the first witness item\n    hashes to the above given hash in part #1, and then pushes that\n    item into the alt stack.\n3.  A piece of script which takes the item from the alt stack,\n    hashes it, then concatenates a `OP_PUSH` of the hash to that\n    item, then does a replace-mode `OP_TLUV`.\n\nParts 1 and 2 must directly follow each other, but other SCRIPT\nlogic can be put in between parts 2 and 3.\nPart 3 can even occur multiple times, in various `OP_IF` branches.\n\nIn order to actually recurse, the top item in the witness stack must\nbe the covenant script, *minus* the hash.\nThis is supposed to be the quining argument.\n\nThe convenant script part #2 then checks that the quining argument\nmatches the hash that is hardcoded into the SCRIPT.\nThis hash is the hash of the *rest* of the SCRIPT.\nIf the quining argument matches, then it *is* the SCRIPT minus its\nhash, and we know that we can use that to recreate the original SCRIPT.\nIt then pushes them out of the way into the alt stack.\n\nPart #3 then recovers the original SCRIPT from the alt stack, and\nresynthesizes the original SCRIPT.\nThe `OP_TLUV` is then able to resynthesize the original address.\n\nUpdating Loop Variables\n-----------------------\n\nBut repeating the same SCRIPT over and over is boring.\n\nWhat is much more interesting is to be able to *change* the SCRIPT\non each iteration, such that certain values on the SCRIPT can be\nchanged.\n\nSuppose our SCRIPT has a loop variable `i` that we want to change\neach time we execute our SCRIPT.\n\nWe can simply put this loop variable after part 1 and before part 2.\nThen part 2 is modified to first push this loop variable onto the\nalt stack.\n\nThe SCRIPT that gets checked is always starts from part 2.\nThus, the SCRIPT, minus the loop variable, is always constant.\nThe SCRIPT can then access the loop variable from the alt stack.\nPart 2 can be extended so that the loop variable is on top of the\nquined SCRIPT on the alt stack.\nThis lets the SCRIPT easily access the loop variable.\nThe SCRIPT can also update the loop variable by replacing the top\nof the alt stack with a different item.\n\nThen part 3 first pops the alt stack top (the loop variable),\nconcatenates it with an appropriate push, then performs the\nhash-then-concatenate dance.\nThis results in a SCRIPT that is the same as the original SCRIPT,\nbut with the loop variable possibly changed.\n\nThe SCRIPT can use multiple loop variables; it is simply a question\nof how hard it would be to access from the alt stack.\n\nDrivechains Over Recursive Covenants\n====================================\n\nDrivechains can be split into four parts:\n\n1.  A way to commit to the sidechain blocks.\n2.  A way to move funds from mainchain to sidechain.\n3.  A way to store sidechain funds.\n4.  A way to move funds from sidechain to mainchain.\n\nThe first three can be easily implemented by a recursive covenant\nwithout a loop variable, together with an opcode to impose some\nrestriction on amounts, such as `OP_IN_OUT_AMOUNT`.\n\nThe technique we would use would be to put the entire sidechain\nfunds into a single UTXO, protected by a recursive covenant.\nThe recursive covenant ensures that it can store the sidechain\nfunds.\nThis covers part 3.\n\nThe recursive covenant could, with the help of `OP_CAT` and\n`OP_CTV`, check that every transaction spending the UTXO has a\nsecond output that is an `OP_RETURN` with a commitment to the\nsidechain block.\nWe can ensure that only one such transaction exists in each\nmainchain block by adding a `\u003c1\u003e OP_CSV`, ensuring that only one\nsidechain-commitment transaction can occur on each mainchain\nblock.\nThis covers part 1.\n\nMainchain-to-sidechain pegs require the cooperation of a\nsidechain validator.\nThe sidechain validator creates a block that instantiates the\npeg-in on the sidechain, then creates a transaction that commits\nto that sidechain block including the peg-in, and spending the\ncurrent sidechain UTXO *and* the mainchain funds being transferred\nin.\nThen the entity requesting the peg-in checks the sidechain block\nand the commitment on the transaction, then signs the transaction.\nThe value restriction on the recursive covenant should then be to\nallow the output to be equal, or larger, than the input.\nThis covers part 2.\n\nThe recursive sidechain covenant by itself has a constant SCRIPT,\nand thus has a constant address.\n\nThe last part of Drivechains -- sidechain-to-mainchain peg ---\nis significantly more interesting.\n\nDigression: Hashes As Peano Naturals\n------------------------------------\n\nIt is possible to represent natural numbers using the following\nHaskell data type:\n\n```Haskell\ndata Nat = Z\n         | S Nat\n-- Z :: Nat\n-- S :: Nat -\u003e Nat\n```\n\nWe can represent naturals as:\n\n* `0` == `Z`\n* `1` == `S Z`\n* `2` == `S (S Z)`\n* `3` == `S (S (S Z))`\n* etc.\n\nHow do we translate this into Bitcoin SCRIPT?\n\n* `Z` == Any arbitrary 160-bit number.\n* `S` == `OP_HASH160`.\n\nThus:\n\n* `0` == `Z`\n* `1` == `hash160(Z)`\n* `2` == `hash160(hash160(Z))`\n* `3` == `hash160(hash160(hash160(Z)))`\n* etc.\n\nIn particular:\n\n* We can increment a number by simply doing `OP_HASH160`.\n* We can decrement a number by having the supposed\n  decrementation be supplied on the witness stack, then\n  validating that it is indeed the next lower number by\n  hashing the witness item and comparing it to the number\n  we have.\n\nNote also that ***we do not need `OP_ADD` or `OP_SUB` for\nthis***, though that would actually make it simpler.\n(But yeah, the whole point is that *BITCOIN IS A LOT MORE\nPOWERFUL THAN YOU EXPECT*.)\n\nThis is relevant to us due to how sidechain-to-mainchain\npegs are implemented.\n\nDrivechain Peg-Out\n------------------\n\nIn Drivechains, first somebody proposes to withdraw some\namount of funds from the sidechain to a mainchain address.\nThen mainchain miners enter a voting period, during\nwhich they either agree to the withdrawal, or disagree.\n\nWe can use the above schema to keep track of a running\ntotal number of votes.\n\nWe define some numbers:\n\n* `Z` == `0`\n* `P` == some maximum time period.\n\nWe then encode `Z`, `P / 2`, and `P` using the hashed-Peano\nencoding in the previous subsection.\n\nIn order to allow withdrawals, we have an alternate branch,\nsuch as a different Tapleaf, for a withdrawal SCRIPT.\nThis only requires that the first output has the same address\nas itself (i.e. the sidechain covenant), and the second output\nhas a new recursive covenant, the peg-out covenant.\n\nThe peg-out covenant has three loop variables:\n\n* `v`, initialized to `Z`.\n  * This is the \"validity level\" of the peg-out.\n  * Voters who want to vote \"for validity\" would *increment*\n    this count.\n  * Voters who want to vote \"against validity\" would\n    *do nothing*.\n* `t`, initialized to `Z`.\n  * This is the voting time period.\n  * Each time the peg-out covenant is used, this loop\n    variable is incremented.\n  * Once it reaches `P`, voting ends and the voting\n    branches of the peg-out covenant are disabled,\n* `a`, initialized to the peg-out address.\n  * This is not actually changed in the covenant, but\n    it is useful to keep it in the loop variable storage\n    area.\n  * With `OP_CTV` this can be an address that commits to\n    any number of promised outputs.\n\nThe peg-out covenant has these branches:\n\n* If `v` equals `P / 2`, then the UTXO can be spent to the\n  address `a`.\n  This is synthesized with an `OP_CTV` and `OP_CAT`.\n* If `t` equals `P`, then the UTXO can only be spent\n  by being pegged into the sidechain covenant.\n  If this branch is not entered, we increment `t`.\n  * This implies an inter-recursion between the sidechain\n    covenant and the peg-out covenant.\n* Check if the witness stack top is true or not:\n  * If true, increment `v` and recurse (\"vote-for\" branch).\n  * Else just recurse (\"vote-against\" branch).\n\n### Fixing Inter-recursion\n\nWe can observe that the inter-recursion between the sidechain\ncovenant and the peg-out covenant is problematic:\n\n* `OP_CTV` requires that the hash of the output covenant is\n  known.\n* `OP_TLUV` will only replace the same output index as the\n  input index it is on.\n\nThis prevents the inter-recursion between the sidechain\ncovenant and the peg-out covenant.\n\nTo fix this, we can observe that we can translate any set\nof inter-recursive functions, such as this:\n\n```Haskell\nfoo :: FooArg -\u003e Result\nfoo fa = bar (fooCode fa)\nbar :: BarArg -\u003e Result\nbar ba = foo (barCode ba)\n```\n\n...into a single self-recursive function:\n\n```Haskell\nfooBar :: Either FooArg BarArg -\u003e Result\nfooBar a = case a of\n             Left  fa -\u003e fooBar (Right (fooCode fa))\n             Right ba -\u003e fooBar (Left (barCode ba))\n```\n\nSimilarly, we can instead convert the inter-recursive\nsidechain and peg-out covenants into a single\nself-recursive covenant.\n\nThis single covenant would have the same set of loop\nvariables `v`, `t`, and `a` as the peg-out covenant\ndescribed above.\nThis time, `a` is not an address, but an entire output\n(i.e. `scriptPubKey` and `amount`).\n\nBy default, `v`, `t`, and `a` are a number `0`.\nIf so, then there is no pending peg-out being voted on.\n\nIf there is no pending peg-out, then either we just\ncommit to a sidechain block, or we commit to a sidechain\nblock *and* start a new peg-out by filling in `a`, and\ninitializing `v` and `t` to `Z`.\n\nIf there is a pending peg-out, then either we just commit\nto a sidechain block (and implicitly downvote the pending\npeg-out) or commit to a sidechain block *and* indicate an\nupvote of the pending peg-out.\n\nIf `v` has reached the limit then we require, using\n`OP_CTV`, that `a` appear on the second output, and that\nthe same SCRIPT (with `v`, `t`, and `a` reseet to `0`)\nis on the first output, and do not impose any minimum\nvalue for the first output, and the sidechain commitment\nis now an `OP_RETURN` on the third output, and no other\noutputs.\n\nIf `t` has reached the limit, then we require simply that\nthe `v`, `t`, and `a` are reset to 0 and the sidechain\ncommitment.\n\nWith the above, all components of Drivechain are implementable\nwith:\n\n* `OP_TLUV`\n* `OP_CAT`\n* `OP_CTV`\n* `OP_IN_OUT_AMOUNT` of some kind, including the ability to\n  check the output amount is larger than the input amount\n  (e.g. by `OP_EQUAL` or `OP_GREATER`).\n* Existing Bitcoin SCRIPT (`OP_ADD` **not** needed!).\n\nConclusion\n==========\n\nPH34R THE RECURSIVE COVENANT!\nPH34R!!!!!!!"}