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
next prev parent 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 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$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=vjudeu@gazeta$(echo .)pl \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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