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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BC18FC46
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Sep 2017 05:13:14 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender-of-o52.zoho.com (sender-of-o52.zoho.com [135.84.80.217])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C6109D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Sep 2017 05:13:13 +0000 (UTC)
Received: from [192.168.1.139] (137.189.135.167 [137.189.135.167]) by
mx.zohomail.com with SMTPS id 1505884390337715.7435394716991;
Tue, 19 Sep 2017 22:13:10 -0700 (PDT)
From: Johnson Lau <jl2012@xbt.hk>
Message-Id: <B8C5E7EF-9062-4431-9B63-06FF855B1D78@xbt.hk>
Content-Type: multipart/alternative;
boundary="Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658"
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Wed, 20 Sep 2017 13:13:04 +0800
In-Reply-To: <201709190309.08669.luke@dashjr.org>
To: Luke Dashjr <luke@dashjr.org>,
bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
<C623794E-F061-4C7A-B05D-378798ED2BF7@friedenbach.org>
<201709190309.08669.luke@dashjr.org>
X-Mailer: Apple Mail (2.3273)
X-ZohoMailClient: External
X-Spam-Status: No, score=0.0 required=5.0 tests=HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] cleanstack alt stack & softfork improvements
(Was: Merkle branch verification & tail-call semantics for generalized
MAST)
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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, 20 Sep 2017 05:13:14 -0000
--Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
> On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> On Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via =
bitcoin-dev=20
> wrote:
>> After the main discussion session it was observed that tail-call =
semantics
>> could still be maintained if the alt stack is used for transferring
>> arguments to the policy script.
>=20
> Isn't this a bug in the cleanstack rule?
>=20
> (Unrelated...)
>=20
> Another thing that came up during the discussion was the idea of =
replacing all=20
> the NOPs and otherwise-unallocated opcodes with a new OP_RETURNTRUE=20
> implementation, in future versions of Script. This would immediately =
exit the=20
> program (perhaps performing some semantic checks on the remainder of =
the=20
> Script) with a successful outcome.
>=20
> This is similar to CVE-2010-5141 in a sense, but since signatures are =
no=20
> longer Scripts themselves, it shouldn't be exploitable.
>=20
> The benefit of this is that it allows softforking in ANY new opcode, =
not only=20
> the -VERIFY opcode variants we've been doing. That is, instead of =
merely=20
> terminating the Script with a failure, the new opcode can also remove =
or push=20
> stack items. This is because old nodes, upon encountering the =
undefined=20
> opcode, will always succeed immediately, allowing the new opcode to do=20=
> literally anything from that point onward.
>=20
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
I have implemented OP_RETURNTRUE in an earlier version of MAST (BIP114) =
but have given up the idea, for 2 reasons:
1. I=E2=80=99ve updated BIP114 to allow inclusion of scripts in witness, =
and require them to be signed. In this way users could add additional =
conditions for the validity of a signature. For example, with =
OP_CHECKBLOCKHASH, it is possible to make the transaction valid only in =
the specified chain. (More discussion in =
https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_sc=
ripts_in_witness =
<https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_s=
cripts_in_witness> )
2. OP_RETURNTRUE does not work well with signature aggregation. =
Signature aggregation will collect (pubkey, message) pairs in a tx, =
combine them, and verify with one signature. However, consider the =
following case:
OP_RETURNTRUE OP_IF <pubkey> OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE
For old nodes, the script terminates at OP_RETURNTRUE, and it will not =
collect the (pubkey, message) pair.
If we use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the =
number 17 to the stack), new nodes will collect the (pubkey, message) =
pair and try to aggregate with other pairs. This becomes a hardfork.
--------
Technically, we could create ANY op code with an OP_NOP. For example, if =
we want OP_MUL, we could have OP_MULVERIFY, which verifies if the 3rd =
stack item is the product of the top 2 stack items. Therefore, =
OP_MULVERIFY OP_2DROP is functionally same as OP_MUL, which removes the =
top 2 items and returns the product. The problem is it takes more =
witness space.
If we don=E2=80=99t want this ugliness, we could use a new script =
version for every new op code we add. In the new BIP114 (see link =
above), I suggest to move the script version to the witness, which is =
cheaper.
--Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=utf-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" =
class=3D""><br class=3D""><div><blockquote type=3D"cite" class=3D""><div =
class=3D"">On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev =
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:</div><br =
class=3D"Apple-interchange-newline"><div class=3D""><div class=3D"">On =
Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via bitcoin-dev =
<br class=3D"">wrote:<br class=3D""><blockquote type=3D"cite" =
class=3D"">After the main discussion session it was observed that =
tail-call semantics<br class=3D"">could still be maintained if the alt =
stack is used for transferring<br class=3D"">arguments to the policy =
script.<br class=3D""></blockquote><br class=3D"">Isn't this a bug in =
the cleanstack rule?<br class=3D""><br class=3D"">(Unrelated...)<br =
class=3D""><br class=3D"">Another thing that came up during the =
discussion was the idea of replacing all <br class=3D"">the NOPs and =
otherwise-unallocated opcodes with a new OP_RETURNTRUE <br =
class=3D"">implementation, in future versions of Script. This would =
immediately exit the <br class=3D"">program (perhaps performing some =
semantic checks on the remainder of the <br class=3D"">Script) with a =
successful outcome.<br class=3D""><br class=3D"">This is similar to =
CVE-2010-5141 in a sense, but since signatures are no <br =
class=3D"">longer Scripts themselves, it shouldn't be exploitable.<br =
class=3D""><br class=3D"">The benefit of this is that it allows =
softforking in ANY new opcode, not only <br class=3D"">the -VERIFY =
opcode variants we've been doing. That is, instead of merely <br =
class=3D"">terminating the Script with a failure, the new opcode can =
also remove or push <br class=3D"">stack items. This is because old =
nodes, upon encountering the undefined <br class=3D"">opcode, will =
always succeed immediately, allowing the new opcode to do <br =
class=3D"">literally anything from that point onward.<br class=3D""><br =
class=3D"">Luke<br =
class=3D"">_______________________________________________<br =
class=3D"">bitcoin-dev mailing list<br class=3D""><a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a><br =
class=3D"">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
br class=3D""></div></div></blockquote></div><br class=3D""><div =
class=3D"">I have implemented OP_RETURNTRUE in an earlier version of =
MAST (BIP114) but have given up the idea, for 2 reasons:</div><div =
class=3D""><br class=3D""></div><div class=3D"">1. I=E2=80=99ve updated =
BIP114 to allow inclusion of scripts in witness, and require them to be =
signed. In this way users could add additional conditions for the =
validity of a signature. For example, with OP_CHECKBLOCKHASH, it is =
possible to make the transaction valid only in the specified chain. =
(More discussion in <a =
href=3D"https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Addit=
ional_scripts_in_witness" =
class=3D"">https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Ad=
ditional_scripts_in_witness</a> )</div><div class=3D""><br =
class=3D""></div><div class=3D"">2. OP_RETURNTRUE does not work well =
with signature aggregation. Signature aggregation will collect (pubkey, =
message) pairs in a tx, combine them, and verify with one signature. =
However, consider the following case:</div><div class=3D""><br =
class=3D""></div><div class=3D"">OP_RETURNTRUE OP_IF <pubkey> =
OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE</div><div class=3D""><br =
class=3D""></div><div class=3D"">For old nodes, the script terminates at =
OP_RETURNTRUE, and it will not collect the (pubkey, message) =
pair.</div><div class=3D""><br class=3D""></div><div class=3D"">If we =
use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the number =
17 to the stack), new nodes will collect the (pubkey, message) pair and =
try to aggregate with other pairs. This becomes a hardfork.</div><div =
class=3D""><br class=3D""></div><div class=3D"">--------</div><div =
class=3D"">Technically, we could create ANY op code with an OP_NOP. For =
example, if we want OP_MUL, we could have OP_MULVERIFY, which verifies =
if the 3rd stack item is the product of the top 2 stack items. =
Therefore, OP_MULVERIFY OP_2DROP is functionally same as OP_MUL, which =
removes the top 2 items and returns the product. The problem is it takes =
more witness space.</div><div class=3D""><br class=3D""></div><div =
class=3D"">If we don=E2=80=99t want this ugliness, we could use a new =
script version for every new op code we add. In the new BIP114 (see link =
above), I suggest to move the script version to the witness, which is =
cheaper.</div><div class=3D""><br class=3D""></div><div class=3D""><br =
class=3D""></div></body></html>=
--Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658--
|
