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
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id B90BD25A
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 22 Nov 2018 22:10:24 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it1-f173.google.com (mail-it1-f173.google.com
[209.85.166.173])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 289695D4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 22 Nov 2018 22:10:23 +0000 (UTC)
Received: by mail-it1-f173.google.com with SMTP id i7so15952881iti.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 22 Nov 2018 14:10:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream.io; s=google;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=Z+FCY9qEN93e9BkC6UTVJnapMNBcvJJEddAH2G3k8ic=;
b=H3sdf7CpIIFd3jphK0LmyRPEuZdfMLIBm1HhOX44/5J+etZ1to4y4Z/VpULsd6fKxE
u5ypvtqx5unct+j5BcfwXGCRdwifLuyHJiRgtiwZ/T3yOxXeozNIFPAAiFHe2wfixjY9
bByS2tcurEX+/DxOXH3yswzBeBjX1Qii57tXc=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=Z+FCY9qEN93e9BkC6UTVJnapMNBcvJJEddAH2G3k8ic=;
b=mT7aikPlYu5mnFfA3Mx+DTvhjVTgbHw0O21SCE47pK4R8quwNT7SVO8V3bhtsx7bTY
7ympCHjPCWco3a6pR0fvkkr+ZT46dpI3R8UNOL6jXY0uq8wBasj6zeCkZlbpvObYshsX
sBK2rJ+YNZLwjAJokTDj2seyjZkekJT8qx1E9esYkB/iHsUoMNKYaenHGO0H24vHzQtQ
klUMntYaeq+/3+iig6OGiPg6LceAzbWTQiYoZJSA6jzQXxpWM5E19ULq+s9xNmjMNfF6
4xfi4UTgpWLTjzXYsmKzTpvlK4oK1qGniRYra2AwJ6RHEXVZSli3qtmATnMxjypLosiL
wAqw==
X-Gm-Message-State: AGRZ1gInEwS9D5lRm10ScT2lmMu1kbzFSgY7HibkXr0e1+FFmp07zWzX
XjlBzsug4X9A6iQoE5PYlXdmmdvNpJB8VRvUgY6+IA==
X-Google-Smtp-Source: AJdET5eoPbr98bcojJC0mHHCQs9F2aEB4sCmqXlJ5KUP2XHQm43gtbGy4eGwjNECEN1Csm1SXuypTHINc6ey6mKjF74=
X-Received: by 2002:a24:d4:: with SMTP id 203-v6mr10484474ita.26.1542924623189;
Thu, 22 Nov 2018 14:10:23 -0800 (PST)
MIME-Version: 1.0
References: <CAPg+sBhuPG-2GXc+Bp0yv5ywry2fk56LPLT4AY0Kcs+YEoz4FA@mail.gmail.com>
<CAMZUoK==Bdn73Lc=swgf2F5_mqE84TR1GRBFhrFkn7kab4jBaw@mail.gmail.com>
<64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk>
<CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
<8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
In-Reply-To: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 22 Nov 2018 17:10:11 -0500
Message-ID: <CAMZUoKkdjHYd8BR6PCae-UG_QRoujW36kYf8s4Gk2FVBeSJnrw@mail.gmail.com>
To: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/alternative; boundary="00000000000014b1a9057b482254"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 23 Nov 2018 04:04:44 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
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: Thu, 22 Nov 2018 22:10:24 -0000
--00000000000014b1a9057b482254
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau <jl2012@xbt.hk> wrote:
> Assuming a script size of 128 bytes (including SHA256 padding), 2^20
> scripts is 134MB. Double it to 268MB for the merkle branch hashes. With
> roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). However,
> memory use is not considered.
>
> >each call to this operation effectively takes O(script-size) time
> I=E2=80=99m not sure if this is correct. Actually,
> CTransactionSignatureSerializer() scans every script for OP_CODESEPARATOR=
.
> Scripts with and without OP_CODESEPARATOR should take exactly the same
> O(script-size) time (see https://github.com/bitcoin/bitcoin/pull/14786)
> Also, this is no longer a concern under segwit (BIP143), which
> CTransactionSignatureSerializer() is not used. Actually, OP_CODESEPARATOR
> under segwit is way simpler than the proposed OP_MASK. If one finds OP_MA=
SK
> acceptable, there should be no reason to reject OP_CODESEPARATOR.
>
Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair requires
recomputing a new #5. scriptCode from BIP 143, and hence computes a new
transaction digest. I understood that this issue was the main motivation
for wanting to deprecate OP_CODESEPARATOR and remove it from later versions
of script.
However, given that we are looking at a combinatorial explosion in SIGHASH
flag combinations already, coupled with existing SigOp limitations, maybe
the cost of recomputing scriptCode with OP_CODESEPARATOR isn't such a big
deal.
And even if we choose remove the behavior of OP_CODESEPARATOR in new
versions of Script, it seems more than 30 layers of sequential OP_IFs can
be MASTified, so there is no need to use OP_CODESEPARATOR within that limit=
.
>One suggestion I heard (I think I heard it from Pieter) to achieve the
above is to add an internal counter that increments on every control flow
operator,=E2=80=A6=E2=80=A6...
> If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator cou=
nting=E2=80=9D,
> I=E2=80=99d rather choose OP_CODESEPARATOR. At least we don=E2=80=99t nee=
d to add more
> lines to the consensus code, just for something that is mostly archivable
> with MAST.
>
--00000000000014b1a9057b482254
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu=
, Nov 22, 2018 at 3:53 PM Johnson Lau <<a href=3D"mailto:jl2012@xbt.hk">=
jl2012@xbt.hk</a>> wrote:<br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Assumi=
ng a script size of 128 bytes (including SHA256 padding), 2^20 scripts is 1=
34MB. Double it to 268MB for the merkle branch hashes. With roughly 100MB/s=
, this should take 2.5s (or 42min for 30 levels). However, memory use is no=
t considered.<br>
<br>
>each call to this operation effectively takes O(script-size) time<br>
I=E2=80=99m not sure if this is correct. Actually, CTransactionSignatureSer=
ializer() scans every script for OP_CODESEPARATOR. Scripts with and without=
OP_CODESEPARATOR should take exactly the same O(script-size) time (see <a =
href=3D"https://github.com/bitcoin/bitcoin/pull/14786" rel=3D"noreferrer" t=
arget=3D"_blank">https://github.com/bitcoin/bitcoin/pull/14786</a>)<br>
Also, this is no longer a concern under segwit (BIP143), which CTransaction=
SignatureSerializer() is not used. Actually, OP_CODESEPARATOR under segwit =
is way simpler than the proposed OP_MASK. If one finds OP_MASK acceptable, =
there should be no reason to reject OP_CODESEPARATOR.<br></blockquote><div>=
<br></div><div>Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair=
requires recomputing a new #5. scriptCode from BIP 143, and hence computes=
a new transaction digest.=C2=A0 I understood that this issue was the main =
motivation for wanting to deprecate OP_CODESEPARATOR and remove it from lat=
er versions of script.<br></div></div><div class=3D"gmail_quote"><div><br><=
/div><div>However, given that we are looking at a combinatorial explosion i=
n SIGHASH flag combinations already, coupled with existing SigOp limitation=
s, maybe the cost of recomputing scriptCode with OP_CODESEPARATOR isn't=
such a big deal.</div><div><br></div><div>And even if we choose remove the=
behavior of OP_CODESEPARATOR in new versions of Script, it seems more than=
30 layers of sequential OP_IFs can be MASTified, so there is no need to us=
e OP_CODESEPARATOR within that limit.<br></div><br></div><div class=3D"gmai=
l_quote">>One suggestion I heard (I think I heard it from Pieter) to ach=
ieve the above is to add an internal counter that increments on every contr=
ol flow operator,=E2=80=A6=E2=80=A6...<br><blockquote class=3D"gmail_quote"=
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator count=
ing=E2=80=9D, I=E2=80=99d rather choose OP_CODESEPARATOR. At least we don=
=E2=80=99t need to add more lines to the consensus code, just for something=
that is mostly archivable with MAST.<br></blockquote><br></div></div>
--00000000000014b1a9057b482254--
|
