1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
by lists.linuxfoundation.org (Postfix) with ESMTP id ABEFBC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2022 11:42:20 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id A9961828BA
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2022 11:42:20 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.601
X-Spam-Level:
X-Spam-Status: No, score=-1.601 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
FROM_LOCAL_NOVOWEL=0.5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: smtp1.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=protonmail.com
Received: from smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id x6lWV8qPi5b4
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2022 11:42:19 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-4319.protonmail.ch (mail-4319.protonmail.ch [185.70.43.19])
by smtp1.osuosl.org (Postfix) with ESMTPS id EE80681421
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2022 11:42:18 +0000 (UTC)
Date: Wed, 11 May 2022 11:42:10 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail2; t=1652269336;
bh=sWSw5CobOvhoeod5U3nMy88MJ9ji2Uf0DdAdJi64tg8=;
h=Date:To:From:Cc:Reply-To:Subject:Message-ID:In-Reply-To:
References:Feedback-ID:From:To:Cc:Date:Subject:Reply-To:
Feedback-ID:Message-ID;
b=Vb5raaq23zcbLNuLvwwePJOwctVvU8u7dRNkLZIuTSSF2EayNDlPUhu69jJAsVq5I
zX3cLDAUoi6x3qPLXNLP1ddVpyjzS3hkT+xidxG+ZcMmEDimB9uiR+gNfHT6/YAEY0
RcN5vrLPXAvWCnLNp89qp3sVCix8oFWJsV6RjC7zizjm0d92fiIIdq173RPqVsD4Hh
05c4BDgJWTynBSjamAfL7HbbHPnlfhs2Qx3vVAKuR+iaISpBqWDudOp95wVqy/7zH8
b4E/88Ond53N3/E4fOpMZu5oSpdEqNynRUq2gW0T/+TLtYCGFnLB+811HB7xo6x5+6
/kT+P2mRueIcA==
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)
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 11 May 2022 11:42:20 -0000
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
|
