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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
|
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 6FA2011CD
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 16 Feb 2018 23:04:40 +0000 (UTC)
X-Greylist: delayed 00:15:03 by SQLgrey-1.7.6
Received: from sender-of-o51.zoho.com (sender-of-o51.zoho.com [135.84.80.216])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 84DD6124
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 16 Feb 2018 23:04:39 +0000 (UTC)
Received: from pn-206-101.itsc.cuhk.edu.hk (pn-206-101.itsc.cuhk.edu.hk
[137.189.206.101]) by mx.zohomail.com
with SMTPS id 1518821373199540.8463776892784;
Fri, 16 Feb 2018 14:49:33 -0800 (PST)
From: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/signed;
boundary="Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541";
protocol="application/pgp-signature"; micalg=pgp-sha512
Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\))
Message-Id: <0213B102-7595-4177-A76C-FE4E8D7F0EDF@xbt.hk>
Date: Fri, 16 Feb 2018 17:49:17 -0500
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.3445.5.20)
X-Zoho-Virus-Status: 1
X-ZohoMailClient: External
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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
Subject: [bitcoin-dev] Alternative way to count sigops
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: Fri, 16 Feb 2018 23:04:40 -0000
--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541
Content-Type: multipart/alternative;
boundary="Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15"
--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
Short history
----------------
Satoshi introduced sigops counting as a softfork to limit the number of =
signature operation in a block. He statically counted all =
OP_CHECK(MULTI)SIG(VERIFY) in both scriptSig and scriptPubKey, assumed a =
OP_CHECKMULTISIG is equivalent to 20 OP_CHECKSIG, and enforced a block =
limit of 20000 sigop. The counting is not contextual, i.e. one doesn=E2=80=
=99t need the UTXO set to determine the number of sigop. The counting =
was also static so one doesn=E2=80=99t need to execute a script in order =
to count sigop. However, this is completely wrong for few reasons: a) =
opcodes in scriptPubKey are not executed; b) scriptPubKey of spent UTXO, =
which are actually executed, are not counted at all; c) it greatly =
overestimate the cost of multi-sig; d) it counts sigop in unexecuted =
branch.
As P2SH was introduced, sigop counting also covered the sigop =
redeemScript. This is good because redeemScript is what being executed. =
It also improved the counting of OP_CHECKMULTISIG. If it is in certain =
canonical form, it would count the number of public keys instead of =
assuming it as 20. On the other hand, counting sigop becomes not =
possible without the UTXO set, since one needs UTXO to identify P2SH =
inputs. Also, the canonical OP_CHECKMULTISIG counting is not quite =
elegant and created more special cases in the code.
Segwit (BIP141) scaled the legacy sigop limit by 4x. So every legacy =
sigop becomes 4 new sigop, with a block limit of 80000 new sigop. P2WPKH =
is counted as 1 new sigop, and P2WSH is counted in the same way as P2SH.
Problem
------------
We now have multiple 2nd generation script proposals, such as BIP114, =
BIP117, taproot, etc. BIP114 and taproot allows static sigop counting, =
but not BIP117 as it requires execution to determine what would be run =
as script (like OP_EVAL). As we want to allow more complicated script =
functions, static sigop counting might not be easy. However, we still =
want to have a limit to avoid unexpected DoS attack.
Proposal
------------
Since we have a block weight limit of 4,000,000 and sigop limit of =
80,000, each sigop could not use more than 50 weight unit on average. =
For new script proposals we could count the actual number of sigop at =
execution (i.e. skip unexecuted sigop, skip 0-size signature, count the =
actual checksig operations in multi-sig), and make sure the number of =
executed sigop * 50 is not greater than the size of the input.
The minimal size of each input is 32 (prevout.hash) + 4 (prevout.n) + 4 =
(nSequence) + 1 (empty scriptSig) =3D 41 bytes or 164 weight unit. So =
the new rule would require that (164 + input witness size) >=3D =
(actual_sigop * 50). This is a per-input limit, as script validation is =
parallel.
Since a compressed key is 33 bytes and a normal compact signature is 64 =
bytes, the 1:50 ratio should be more than enough to allow any normal use =
of CHECKSIG, unless people are doing weird things like 2DUP 2DUP =
2DUP=E2=80=A6=E2=80=A6..CHECKSIG CHECKSIG CHECKSIG CHECKSIG , which =
would have many sigop with a relatively small witness. Interactive =
per-tx signature aggregation allows 64bytes/tx signature, and per-block =
non-interatcitve signature aggregation allows 32bytes/signature =
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.h=
tml =
<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.h=
tml>). In such cases, the 1:50 ratio might not be enough if many =
signatures are aggregated. Depends on the number of sigop we could =
tolerate, the 1:50 ratio might be reduced to 1:32 or lower to make sure =
legitimate use would never hit the limit. I think 32 is reasonable as it =
is about the size of a public key, which would guarantee each pubkey =
must get a sigop slot.
So a relay node could be certain that a tx won=E2=80=99t spend excessive =
CPU power by just looking at its size. If it spends too much, it is =
invalid and script execution could be terminated early.
--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15
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; line-break: after-white-space;" class=3D"">Short=
history<div class=3D"">----------------</div><div class=3D""><br =
class=3D""></div><div class=3D"">Satoshi introduced sigops counting as a =
softfork to limit the number of signature operation in a block. He =
statically counted all OP_CHECK(MULTI)SIG(VERIFY) in both scriptSig and =
scriptPubKey, assumed a OP_CHECKMULTISIG is equivalent to 20 =
OP_CHECKSIG, and enforced a block limit of 20000 sigop. The counting is =
not contextual, i.e. one doesn=E2=80=99t need the UTXO set to determine =
the number of sigop. The counting was also static so one doesn=E2=80=99t =
need to execute a script in order to count sigop. However, this is =
completely wrong for few reasons: a) opcodes in scriptPubKey are not =
executed; b) scriptPubKey of spent UTXO, which are actually executed, =
are not counted at all; c) it greatly overestimate the cost of =
multi-sig; d) it counts sigop in unexecuted branch.<div class=3D""><br =
class=3D""></div><div class=3D"">As P2SH was introduced, sigop counting =
also covered the sigop redeemScript. This is good because redeemScript =
is what being executed. It also improved the counting of =
OP_CHECKMULTISIG. If it is in certain canonical form, it would count the =
number of public keys instead of assuming it as 20. On the other hand, =
counting sigop becomes not possible without the UTXO set, since one =
needs UTXO to identify P2SH inputs. Also, the canonical OP_CHECKMULTISIG =
counting is not quite elegant and created more special cases in the =
code.</div><div class=3D""><br class=3D""></div><div class=3D"">Segwit =
(BIP141) scaled the legacy sigop limit by 4x. So every legacy sigop =
becomes 4 new sigop, with a block limit of 80000 new sigop. P2WPKH is =
counted as 1 new sigop, and P2WSH is counted in the same way as =
P2SH.</div><div class=3D""><br class=3D""></div><div class=3D""><br =
class=3D""></div></div><div class=3D""><br class=3D""></div><div =
class=3D"">Problem</div><div class=3D"">------------</div><div =
class=3D""><br class=3D""></div><div class=3D"">We now have multiple 2nd =
generation script proposals, such as BIP114, BIP117, taproot, etc. =
BIP114 and taproot allows static sigop counting, but not BIP117 as it =
requires execution to determine what would be run as script (like =
OP_EVAL). As we want to allow more complicated script functions, static =
sigop counting might not be easy. However, we still want to have a limit =
to avoid unexpected DoS attack.</div><div class=3D""><br =
class=3D""></div><div class=3D""><br class=3D""></div><div class=3D""><br =
class=3D""></div><div class=3D""><br class=3D""></div><div =
class=3D"">Proposal</div><div class=3D"">------------</div><div =
class=3D""><br class=3D""></div><div class=3D"">Since we have a block =
weight limit of 4,000,000 and sigop limit of 80,000, each sigop could =
not use more than 50 weight unit on average. For new script proposals we =
could count the actual number of sigop at execution (i.e. skip =
unexecuted sigop, skip 0-size signature, count the actual checksig =
operations in multi-sig), and make sure the number of executed sigop * =
50 is not greater than the size of the input.</div><div class=3D""><br =
class=3D""></div><div class=3D"">The minimal size of each input is 32 =
(prevout.hash) + 4 (prevout.n) + 4 (nSequence) + 1 (empty scriptSig) =3D =
41 bytes or 164 weight unit. So the new rule would require that (164 + =
input witness size) >=3D (actual_sigop * 50). This is a per-input =
limit, as script validation is parallel. </div><div class=3D""><br =
class=3D""></div><div class=3D"">Since a compressed key is 33 bytes and =
a normal compact signature is 64 bytes, the 1:50 ratio should be more =
than enough to allow any normal use of CHECKSIG, unless people are doing =
weird things like 2DUP 2DUP 2DUP=E2=80=A6=E2=80=A6..CHECKSIG CHECKSIG =
CHECKSIG CHECKSIG , which would have many sigop with a relatively small =
witness. Interactive per-tx signature aggregation allows 64bytes/tx =
signature, and per-block non-interatcitve signature aggregation allows =
32bytes/signature (<a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/0=
14272.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Ma=
y/014272.html</a>). In such cases, the 1:50 ratio might not be enough if =
many signatures are aggregated. Depends on the number of sigop we could =
tolerate, the 1:50 ratio might be reduced to 1:32 or lower to make sure =
legitimate use would never hit the limit. I think 32 is reasonable as it =
is about the size of a public key, which would guarantee each pubkey =
must get a sigop slot.</div><div class=3D""><br class=3D""></div><div =
class=3D"">So a relay node could be certain that a tx won=E2=80=99t =
spend excessive CPU power by just looking at its size. If it spends too =
much, it is invalid and script execution could be terminated =
early.</div></body></html>=
--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15--
--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename=signature.asc
Content-Type: application/pgp-signature;
name=signature.asc
Content-Description: Message signed with OpenPGP
-----BEGIN PGP SIGNATURE-----
iQGzBAEBCgAdFiEEKLhz7vf0beYGEpDt7p5VIDS+JNIFAlqHX+0ACgkQ7p5VIDS+
JNKc5wv/WfkEhNUxPAM9XmYGZeoBeF+SQM/tXl7PM7wkYRZ3WAyjS3rMg6HXryPc
SiRd80a/GDRnRHAOQY/9+xS+ITVgsmybFwWchxj+zJnzK7UI0knqjIYP6E1ATNOX
IhM2bJvzCWBp97CB/wBtbUYhUhlW/EhQkOCtiVqdVj49u97Up2QSWnQ07dGpajua
cVVnvYVG86bWTzWQc6gZuDEfvCatyIMnbmvToyc2cjGGBRvXdQKKI14PX0fC91Ln
yEVLI1STkABWu6BzeFZQhvMbBIv2EsZX7YlNffwb4Cq0/t9zSnoPH86knlsvGga7
2D8FI87jMPvtL4K61q8PB2lDgV0EdBLnY1emCxai/zzjlxk2VhPs+tRReYFiGEK2
i/sj6HT1b0ctj2VsEz8umVJPijYb9w4UjeQnSPD6LWdlUWU61Z+dv/3i68tTEtA7
lkbexBXzz6MK2U7mhsssKhega0P7JBZLAUBwgep58jwV++AlyreVa3bTTNoegUBE
MM53vvup
=5OT2
-----END PGP SIGNATURE-----
--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541--
|
