Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: "vjudeu@gazeta•pl" <vjudeu@gazeta•pl>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Date: Wed, 11 May 2022 11:42:10 +0000	[thread overview]
Message-ID: <M80pb4TxcE1yCMCW4IboyTtx8MSvp8m9tphXe2EYvIvcrcf2Wzsn4ManJw8EP_ri-ohqtIOPrEaw7XkUcTO3lfVSLN4WMUwpromwzLm15Kc=@protonmail.com> (raw)
In-Reply-To: <161946014-482cdec305e2bd7a2c3fc4774c70239d@pmq1v.m5r2.onet>

Good morning vjudeu,

> > Looks like `OP_CAT` is not getting enabled until after we are reasonably sure that recursive covenants are not really unsafe.
>
> Maybe we should use OP_SUBSTR instead of OP_CAT. Or even better: OP_SPLIT. Then, we could have OP_SPLIT <n> <pos1> <pos2> ... <posN> that would split a string N times (so there will be N+1 pieces). Or we could have just OP_SPLIT <pos> to split one string into two. Or maybe OP_2SPLIT and OP_3SPLIT, just to split into two or three pieces (as we have OP_2DUP and OP_3DUP). I think OP_SUBSTR or OP_SPLIT is better than OP_CAT, because then things always get smaller and we can be always sure that we will have one byte as the smallest unit in our Script.

Unfortunately `OP_SUBSTR` can be used to synthesize an effective `OP_CAT`.

Instead of passing in two items on the witness stack to be `OP_CAT`ted together, you instead pass in the two items to concatenate, and *then* the concatenation.
Then you can synthesize a SCRIPT which checks that the supposed concatenation is indeed the two items to be concatenated.

Recursive covenants DO NOT arise from the increasing amounts of memory the trivial `OP_DUP OP_CAT OP_DUP OP_CAT` repetition allocates.

REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER RECURSIVE OR NOT.

Instead, `OP_CAT` enable recursive covenants (which we are not certain are safe) because `OP_CAT` allows quining to be done.
Quining is a technique to pass a SCRIPT with a copy of its code, so that it can then enforce that the output is passed to the exact same input SCRIPT.

`OP_SUBSTR` allows a SCRIPT to validate that it is being passed a copy of itself and that the complete SCRIPT contains its copy as an `OP_PUSH` and the rest of the SCRIPT as actual code.
This is done by `OP_SUBSTR` the appropriate parts of the supposed complete SCRIPT and comparing them to a reference value we have access to (because our own SCRIPT was passed to us inside an `OP_PUSH`).

   # Assume that the witness stack top is the concatenation of
   #   `OP_PUSH`, the SCRIPT below, then the`SCRIPT below.
   # Assume this SCRIPT is prepended with an OP_PUSH of our own code.
   OP_TOALTSTACK # save our reference
   OP_DUP 1 <scriptlength> OP_SUBSTR # Get the OP_PUSH argument
   OP_FROMALTSTACK OP_DUP OP_TOALTSTACK # Get our reference
   OP_EQUALVERIFY # check they are the same
   OP_DUP <1 + scriptlength> <scriptlength> OP_SUBSTR # Get the SCRIPT body
   OP_FROMALTSTACK # Get our reference
   OP_EQUALVERIFY # check they are the same
   # At this point, we have validated that the top of the witness stack
   # is the quine of this SCRIPT.
   # TODO: validate the `OP_PUSH` instruction, left as an exercise for the
   # reader.

Thus, `OP_SUBSTR` is enough to enable quining and is enough to implement recursive covenants.

We cannot enable `OP_SUBSTR` either, unless we are reasonably sure that recursive covenants are safe.

(FWIW recursive covenants are probably safe, as they are not in fact Turing-complete, they are a hair less powerful, equivalent to the total functional programming with codata.)

Regards,
ZmnSCPxj