Date: Wed, 23 Feb 2022 11:28:36 +0000
To: "David A. Harding" <dave@dtrt.org>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <i710HUIxNHIqCNhkh07dzlShyDp9ZkoEokw9ZBezCFvsk05ZUy5fXK1xx_IQifLh4f3RYb8FJM_MFm7hAaQFaUM3Jy3E8QhfSzkaogAu1Gs=@protonmail.com>
In-Reply-To: <0100017ee6472e02-037d355d-4c16-43b0-81d2-4a82b580ba99-000000@email.amazonses.com>
References: <CAMZUoK=pkZuovtifBzdqhoyegzG+9hRTFEc7fG9nZPDK4KbU3w@mail.gmail.com>
 <87leymuiu8.fsf@rustcorp.com.au>
 <CAD5xwhgP2_51Dvar0f1tsMrCXZ61W9-HnLgR45D-54Oc7-X1ag@mail.gmail.com>
 <0100017ee6472e02-037d355d-4c16-43b0-81d2-4a82b580ba99-000000@email.amazonses.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Recursive covenant opposition,
	or the absence thereof,
	was Re: TXHASH + CHECKSIGFROMSTACKVERIFY in lieu of CTV and
	ANYPREVOUT
Precedence: list


Subject: Turing-Completeness, And Its Enablement Of Drivechains

Introduction
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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 =3D Z
         | S Nat
-- Z :: Nat
-- S :: Nat -> Nat
```

We can represent naturals as:

* `0` =3D=3D `Z`
* `1` =3D=3D `S Z`
* `2` =3D=3D `S (S Z)`
* `3` =3D=3D `S (S (S Z))`
* etc.

How do we translate this into Bitcoin SCRIPT?

* `Z` =3D=3D Any arbitrary 160-bit number.
* `S` =3D=3D `OP_HASH160`.

Thus:

* `0` =3D=3D `Z`
* `1` =3D=3D `hash160(Z)`
* `2` =3D=3D `hash160(hash160(Z))`
* `3` =3D=3D `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` =3D=3D `0`
* `P` =3D=3D 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 =3D bar (fooCode fa)
bar :: BarArg -> Result
bar ba =3D foo (barCode ba)
```

...into a single self-recursive function:

```Haskell
fooBar :: Either FooArg BarArg -> Result
fooBar a =3D 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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

PH34R THE RECURSIVE COVENANT!
PH34R!!!!!!!