public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
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


  reply	other threads:[~2022-05-11 11:42 UTC|newest]

Thread overview: 19+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-05-06 22:30 [bitcoin-dev] Speedy covenants (OP_CAT2) Jorge Timón
2022-05-07  3:06 ` ZmnSCPxj
2022-05-07  3:52   ` vjudeu
2022-05-07 13:31     ` Jorge Timón
2022-05-11 15:25     ` alicexbt
2022-05-11 16:03       ` vjudeu
2022-05-07 13:27   ` Jorge Timón
2022-05-07 14:08     ` ZmnSCPxj
     [not found]       ` <CABm2gDo1wTOoWcNgJ4mUgSB3KCtBSnjqe3nwVBSL+7=ziDJ==w@mail.gmail.com>
2022-05-07 22:28         ` ZmnSCPxj
2022-05-08  2:03       ` Nadav Ivgi
2022-05-08  2:19         ` ZmnSCPxj
2022-05-11 10:57           ` vjudeu
2022-05-11 11:42             ` ZmnSCPxj [this message]
2022-05-11 19:41               ` Russell O'Connor
2022-05-12  3:07                 ` ZmnSCPxj
2022-05-12 10:48                   ` Russell O'Connor
2022-05-13 21:43                     ` Anthony Towns
2022-05-13 23:33                       ` Russell O'Connor
2022-05-14 13:32                         ` Erik Aronesty

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='M80pb4TxcE1yCMCW4IboyTtx8MSvp8m9tphXe2EYvIvcrcf2Wzsn4ManJw8EP_ri-ohqtIOPrEaw7XkUcTO3lfVSLN4WMUwpromwzLm15Kc=@protonmail.com' \
    --to=zmnscpxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=vjudeu@gazeta.pl \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox