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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
|
Return-Path: <gavinandresen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 7F1DF40A
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Jul 2015 20:59:43 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f175.google.com (mail-lb0-f175.google.com
[209.85.217.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id EF55111E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Jul 2015 20:59:41 +0000 (UTC)
Received: by lbbyj8 with SMTP id yj8so22404368lbb.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Jul 2015 13:59:40 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-type; bh=XTPioaIz2oTuoHPRZBp/hIcQBzaA7S7vTX6jRxpe3OY=;
b=jAhfRCFx+CRbBeRNCVl+r9RKlL6DOVjYv3EK2c3oETKFsp+ptbxkqATzxVm1pcW6xS
yVvD9RLrp8j3HcSbWe9CtTzSE4q4qckhoMJM0vy7Dsl5iBprA9OmNHgxpYSZqpNygE4q
RCr2gRZVTS1S0xTrovi36BPGp3oUF2IFuHY7+Qi2Q2Am+VybQHE/jFSNcgtoRZZDodkj
odwvnFGjKAbm6XyPZ4PzTjsDKSnXjjg7ojspee0zXS34ACUn/FdeNi3VTamnUHlewhPd
P6KbFj70VrCrKAjlkBcaVfS3oaZyCtbnz6t27JM/KIOIW/G0kgPtXM6ylxeWbEBOMeW6
kyoQ==
MIME-Version: 1.0
X-Received: by 10.152.22.168 with SMTP id e8mr15546417laf.40.1437771580116;
Fri, 24 Jul 2015 13:59:40 -0700 (PDT)
Received: by 10.25.90.75 with HTTP; Fri, 24 Jul 2015 13:59:40 -0700 (PDT)
In-Reply-To: <CABsx9T3mEYPMFfxFbM-Jj7nADWsVg9HbvQOr0JZeEjC8gOvLZA@mail.gmail.com>
References: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>
<CAAS2fgRBa47ye-ouV2jDe16MJFCKxYh0zF0Jw4BTwzpXVKgwOg@mail.gmail.com>
<CABsx9T3mEYPMFfxFbM-Jj7nADWsVg9HbvQOr0JZeEjC8gOvLZA@mail.gmail.com>
Date: Fri, 24 Jul 2015 16:59:40 -0400
Message-ID: <CABsx9T2s3WaRZK8rEZLd9+FEVaUPxz=EmhL2JH=CnH-y6C1b0w@mail.gmail.com>
From: Gavin Andresen <gavinandresen@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=089e0160bd704d14ad051ba54898
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] For discussion: limit transaction size to
mitigate CVE-2013-2292
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 24 Jul 2015 20:59:43 -0000
--089e0160bd704d14ad051ba54898
Content-Type: text/plain; charset=UTF-8
After thinking about it, implementing it, and doing some benchmarking, I'm
convinced replacing the existing, messy, ad-hoc sigop-counting consensus
rules is the right thing to do.
The last two commits in this branch are an implementation:
https://github.com/gavinandresen/bitcoin-git/commits/count_hash_size
From the commit message in the last commit:
Summary of old rules / new rules:
Old rules: 20,000 inaccurately-counted-sigops for a 1MB block
New: 80,000 accurately-counted sigops for an 8MB block
A scan of the last 100,000 blocks for high-sigop blocks gets
a maximum of 7,350 sigops in block 364,773 (in a single, huge,
~1MB transaction).
For reference, Pieter Wuille's libsecp256k1 validation code
validates about 10,000 signatures per second on a single
2.7GHZ CPU core.
Old rules: no limit for number of bytes hashed to generate
signature hashes
New rule: 1.3gigabytes hashed per 8MB block to generate
signature hashes
Block 364,422 contains a single ~1MB transaction that requires
1.2GB of data hashed to generate signature hashes.
TODO: benchmark Core's sighash-creation code ('openssl speed sha256'
reports something like 1GB per second on my machine).
Note that in normal operation most validation work is done as transactions
are received from the network, and can be cached so it doesn't have to be
repeated when a new block is found. The limits described in this BIP are
intended, as the existing sigop limits are intended, to be an extra "belt
and suspenders" measure to mitigate any possible attack that involves
creating and broadcasting a very expensive-to-verify block.
Draft BIP:
BIP: ??
Title: Consensus rules to limit CPU time required to validate blocks
Author: Gavin Andresen <gavinandresen@gmail.com>
Status: Draft
Type: Standards Track
Created: 2015-07-24
==Abstract==
Mitigate potential CPU exhaustion denial-of-service attacks by limiting
the maximum number of ECDSA signature verfications done per block,
and limiting the number of bytes hashed to compute signature hashes.
==Motivation==
Sergio Demian Lerner reported that a maliciously constructed block could
take several minutes to validate, due to the way signature hashes are
computed for OP_CHECKSIG/OP_CHECKMULTISIG ([[
https://bitcointalk.org/?topic=140078|CVE-2013-2292]]).
Each signature validation can require hashing most of the transaction's
bytes, resulting in O(s*b) scaling (where s is the number of signature
operations and b is the number of bytes in the transaction, excluding
signatures). If there are no limits on s or b the result is O(n^2) scaling
(where n is a multiple of the number of bytes in the block).
This potential attack was mitigated by changing the default relay and
mining policies so transactions larger than 100,000 bytes were not
relayed across the network or included in blocks. However, a miner
not following the default policy could choose to include a
transaction that filled the entire one-megaybte block and took
a long time to validate.
==Specification==
After deployment, the existing consensus rule for maximum number of
signature operations per block (20,000, counted in two different,
idiosyncratic, ad-hoc ways) shall be replaced by the following two rules:
1. The maximum number of ECDSA verify operations required to validate
all of the transactions in a block must be less than or equal to
the maximum block size in bytes divided by 100 (rounded down).
2. The maximum number of bytes hashed to compute ECDSA signatures for
all transactions in a block must be less than or equal to the
maximum block size in bytes times 160.
==Compatibility==
This change is compatible with existing transaction-creation software,
because transactions larger than 100,000 bytes have been considered
"non-standard"
(they are not relayed or mined by default) for years, and a block full of
"standard" transactions will be well-under the limits.
Software that assembles transactions into blocks and software that validates
blocks must be updated to enforce the new consensus rules.
==Deployment==
This change will be deployed with BIP 100 or BIP 101.
==Discussion==
Linking these consensus rules to the maximum block size allows more
transactions
and/or transactions with more inputs or outputs to be included if the
maximum
block size increases.
The constants are chosen to be maximally compatible with the existing
consensus rule,
and to virtually eliminate the possibility that bitcoins could be lost if
somebody had locked some funds in a pre-signed, expensive-to-validate,
locktime-in-the-future
transaction.
But they are chosen to put a reasonable upper bound on the CPU time
required to validate
a maximum-sized block.
===Alternatives to this BIP:===
1. A simple limit on transaction size (e.g. any transaction in a block must
be 100,000
bytes or smaller).
2. Fix the CHECKSIG/CHECKMULTISIG opcodes so they don't re-hash variations
of
the transaction's data. This is the "most correct" solution, but would
require
updating every piece of transaction-creating and transaction-validating
software
to change how they compute the signature hash, and to avoid potential
attacks would
still require some limit on how many such operations were permitted.
==References==
[[https://bitcointalk.org/?topic=140078|CVE-2013-2292]]: Sergio Demian
Lerner's original report
--089e0160bd704d14ad051ba54898
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>After thinking about it, implementing it, and doing s=
ome benchmarking, I'm convinced replacing the existing, messy, ad-hoc s=
igop-counting consensus rules is the right thing to do.</div><div><br></div=
><div>The last two commits in this branch are an implementation:</div><div>=
=C2=A0 =C2=A0<a href=3D"https://github.com/gavinandresen/bitcoin-git/commit=
s/count_hash_size">https://github.com/gavinandresen/bitcoin-git/commits/cou=
nt_hash_size</a></div><div><br></div><div>From the commit message in the la=
st commit:</div><div><br></div><div><pre style=3D"overflow:visible;font-fam=
ily:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:13=
px;margin-top:10px;margin-bottom:10px;font-stretch:normal;line-height:1.45;=
max-width:100%;color:rgb(89,96,99);white-space:pre-wrap;word-wrap:break-wor=
d;background-color:rgb(230,241,246)">Summary of old rules / new rules:
Old rules: 20,000 inaccurately-counted-sigops for a 1MB block
New: 80,000 accurately-counted sigops for an 8MB block
A scan of the last 100,000 blocks for high-sigop blocks gets
a maximum of 7,350 sigops in block 364,773 (in a single, huge,
~1MB transaction).
For reference, Pieter Wuille's libsecp256k1 validation code
validates about 10,000 signatures per second on a single
2.7GHZ CPU core.
Old rules: no limit for number of bytes hashed to generate
signature hashes
New rule: 1.3gigabytes hashed per 8MB block to generate
signature hashes
Block 364,422 contains a single ~1MB transaction that requires
1.2GB of data hashed to generate signature hashes.</pre></div><div>TODO: be=
nchmark Core's sighash-creation code ('openssl speed sha256' re=
ports something like 1GB per second on my machine).</div><div><br></div><di=
v>Note that in normal operation most validation work is done as transaction=
s are received from the network, and can be cached so it doesn't have t=
o be repeated when a new block is found. The limits described in this BIP a=
re intended, as the existing sigop limits are intended, to be an extra &quo=
t;belt and suspenders" measure to mitigate any possible attack that in=
volves creating and broadcasting a very expensive-to-verify block.</div><di=
v><br></div><div><br></div><div>Draft BIP:</div><div><br></div><div>=C2=A0 =
BIP: ??<br></div><div>=C2=A0 Title: Consensus rules to limit CPU time requi=
red to validate blocks</div><div>=C2=A0 Author: Gavin Andresen <<a href=
=3D"mailto:gavinandresen@gmail.com">gavinandresen@gmail.com</a>></div><d=
iv>=C2=A0 Status: Draft</div><div>=C2=A0 Type: Standards Track</div><div>=
=C2=A0 Created: 2015-07-24</div><div><br></div><div>=3D=3DAbstract=3D=3D</d=
iv><div><br></div><div>Mitigate potential CPU exhaustion denial-of-service =
attacks by limiting</div><div>the maximum number of ECDSA signature verfica=
tions done per block,</div><div>and limiting the number of bytes hashed to =
compute signature hashes.</div><div><br></div><div>=3D=3DMotivation=3D=3D</=
div><div><br></div><div>Sergio Demian Lerner reported that a maliciously co=
nstructed block could</div><div>take several minutes to validate, due to th=
e way signature hashes are</div><div>computed for OP_CHECKSIG/OP_CHECKMULTI=
SIG ([[<a href=3D"https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]]">=
https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]]</a>).</div><div>Eac=
h signature validation can require hashing most of the transaction's</d=
iv><div>bytes, resulting in O(s*b) scaling (where s is the number of signat=
ure</div><div>operations and b is the number of bytes in the transaction, e=
xcluding</div><div>signatures). If there are no limits on s or b the result=
is O(n^2) scaling</div><div>(where n is a multiple of the number of bytes =
in the block).</div><div><br></div><div>This potential attack was mitigated=
by changing the default relay and</div><div>mining policies so transaction=
s larger than 100,000 bytes were not</div><div>relayed across the network o=
r included in blocks. However, a miner</div><div>not following the default =
policy could choose to include a</div><div>transaction that filled the enti=
re one-megaybte block and took</div><div>a long time to validate.</div><div=
><br></div><div>=3D=3DSpecification=3D=3D</div><div><br></div><div>After de=
ployment, the existing consensus rule for maximum number of</div><div>signa=
ture operations per block (20,000, counted in two different,</div><div>idio=
syncratic, ad-hoc ways) shall be replaced by the following two rules:</div>=
<div><br></div><div>1. The maximum number of ECDSA verify operations requir=
ed to validate</div><div>all of the transactions in a block must be less th=
an or equal to</div><div>the maximum block size in bytes divided by 100 (ro=
unded down).</div><div><br></div><div>2. The maximum number of bytes hashed=
to compute ECDSA signatures for</div><div>all transactions in a block must=
be less than or equal to the</div><div>maximum block size in bytes times 1=
60.</div><div><br></div><div>=3D=3DCompatibility=3D=3D</div><div><br></div>=
<div>This change is compatible with existing transaction-creation software,=
</div><div>because transactions larger than 100,000 bytes have been conside=
red "non-standard"</div><div>(they are not relayed or mined by de=
fault) for years, and a block full of</div><div>"standard" transa=
ctions will be well-under the limits.</div><div><br></div><div>Software tha=
t assembles transactions into blocks and software that validates</div><div>=
blocks must be updated to enforce the new consensus rules.</div><div><br></=
div><div>=3D=3DDeployment=3D=3D</div><div><br></div><div>This change will b=
e deployed with BIP 100 or BIP 101.</div><div><br></div><div>=3D=3DDiscussi=
on=3D=3D</div><div><br></div><div>Linking these consensus rules to the maxi=
mum block size allows more transactions</div><div>and/or transactions with =
more inputs or outputs to be included if the maximum</div><div>block size i=
ncreases.</div><div><br></div><div>The constants are chosen to be maximally=
compatible with the existing consensus rule,</div><div>and to virtually el=
iminate the possibility that bitcoins could be lost if</div><div>somebody h=
ad locked some funds in a pre-signed, expensive-to-validate, locktime-in-th=
e-future</div><div>transaction.</div><div><br></div><div>But they are chose=
n to put a reasonable upper bound on the CPU time required to validate</div=
><div>a maximum-sized block.</div><div><br></div><div>=3D=3D=3DAlternatives=
to this BIP:=3D=3D=3D</div><div><br></div><div>1. A simple limit on transa=
ction size (e.g. any transaction in a block must be 100,000</div><div>bytes=
or smaller).=C2=A0</div><div><br></div><div>2. Fix the CHECKSIG/CHECKMULTI=
SIG opcodes so they don't re-hash variations of</div><div>the transacti=
on's data. This is the "most correct" solution, but would req=
uire</div><div>updating every piece of transaction-creating and transaction=
-validating software</div><div>to change how they compute the signature has=
h, and to avoid potential attacks would</div><div>still require some limit =
on how many such operations were permitted.</div><div><br></div><div>=3D=3D=
References=3D=3D</div><div><br></div><div>[[<a href=3D"https://bitcointalk.=
org/?topic=3D140078|CVE-2013-2292]">https://bitcointalk.org/?topic=3D140078=
|CVE-2013-2292]</a>]: Sergio Demian Lerner's original report</div><div>=
<br></div><div class=3D"gmail_extra"><div class=3D"gmail_signature"><br></d=
iv>
</div></div>
--089e0160bd704d14ad051ba54898--
|