Date: Wed, 11 May 2022 11:42:10 +0000
To: "vjudeu@gazeta.pl" <vjudeu@gazeta.pl>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <M80pb4TxcE1yCMCW4IboyTtx8MSvp8m9tphXe2EYvIvcrcf2Wzsn4ManJw8EP_ri-ohqtIOPrEaw7XkUcTO3lfVSLN4WMUwpromwzLm15Kc=@protonmail.com>
In-Reply-To: <161946014-482cdec305e2bd7a2c3fc4774c70239d@pmq1v.m5r2.onet>
References: <161946014-482cdec305e2bd7a2c3fc4774c70239d@pmq1v.m5r2.onet>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Precedence: list

Good morning vjudeu,


> > Looks like `OP_CAT` is not getting enabled until after we are reasonabl=
y 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 spli=
t 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 alw=
ays 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 toge=
ther, you instead pass in the two items to concatenate, and *then* the conc=
atenation.
Then you can synthesize a SCRIPT which checks that the supposed concatenati=
on 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 O=
R 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 i=
tself and that the complete SCRIPT contains its copy as an `OP_PUSH` and th=
e 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 o=
ur 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 re=
cursive covenants.

We cannot enable `OP_SUBSTR` either, unless we are reasonably sure that rec=
ursive 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 functiona=
l programming with codata.)

Regards,
ZmnSCPxj