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
|
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 41E8825A
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Jul 2015 19:10:29 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f178.google.com (mail-lb0-f178.google.com
[209.85.217.178])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 06EC8DE
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Jul 2015 19:10:27 +0000 (UTC)
Received: by lbbzr7 with SMTP id zr7so101295709lbb.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Jul 2015 12:10:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to:content-type;
bh=JxuRSG4bg1S0HxjR/AN0LG0tqa2VfYKNt1w6XksYGhs=;
b=C9kXpXgxYFmjubZiauc1KyWO/FxYIJWzxZ0SJEeIIP8RY11gdw/OrhKa33fT9ePQcZ
V78BQGwIkdA0oOGuITMCIosjd8z564fjm5DWoIct4+fg3W/DpEx00OvDXSDYh0aR/X+H
pwKrCEyOkPyPlb/tsaVd0LNH3DnlY/1jFwmZdFSsPxN9nEUaEUZANkwlnCuFOyQFKEdN
Ye4DbM2AMPjhQZCVeyXwcQH1JerPeEgCoi0SyMG5WD5JizcUmSF27oMTyjNNJ8Qprh3B
mXD/AvBCHrM6H1EeqgYphrg1DinN9iFT+bRLohOTVLXMLf/xE3yaggmyMuAcSYJyVz7g
IKJg==
MIME-Version: 1.0
X-Received: by 10.113.10.135 with SMTP id ea7mr29173441lbd.65.1437419426213;
Mon, 20 Jul 2015 12:10:26 -0700 (PDT)
Received: by 10.25.90.75 with HTTP; Mon, 20 Jul 2015 12:10:26 -0700 (PDT)
Date: Mon, 20 Jul 2015 15:10:26 -0400
Message-ID: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>
From: Gavin Andresen <gavinandresen@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a11347d2c4af458051b534a21
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: [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: Mon, 20 Jul 2015 19:10:29 -0000
--001a11347d2c4af458051b534a21
Content-Type: text/plain; charset=UTF-8
Draft BIP to prevent a potential CPU exhaustion attack if a significantly
larger maximum blocksize is adopted:
Title: Limit maximum transaction size
Author: Gavin Andresen <gavinandresen@gmail.com>
Status: Draft
Type: Standards Track
Created: 2015-07-17
==Abstract==
Mitigate a potential CPU exhaustion denial-of-service attack by limiting
the maximum size of a transaction included in a block.
==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 n is the number of signature
operations and m is the number of bytes in the transaction, excluding
signatures). If there are no limits on n or m the result is O(n^2) scaling.
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 maximum serialized size of a transaction allowed
in a block shall be 100,000 bytes.
==Compatibility==
This change should be 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.
Software that assembles transactions into blocks and that validates blocks
must be
updated to reject oversize transactions.
==Deployment==
This change will be deployed with BIP 100 or BIP 101.
==Discussion==
Alternatives to this BIP:
1. A new consensus rule that limits the number of signature operations in a
single transaction instead of limiting size. This might be more compatible
with
future opcodes that require larger-than-100,000-byte transactions, although
any such future opcodes would likely require changes to the Script
validation
rules anyway (e.g. the 520-byte limit on data items).
2. Fix the SIG 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.
==References==
[[https://bitcointalk.org/?topic=140078|CVE-2013-2292]]: Sergio Demian
Lerner's original report
--001a11347d2c4af458051b534a21
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Draft BIP to prevent a potential CPU exhaustion attac=
k if a significantly larger maximum blocksize is adopted:</div><div><br></d=
iv><div>=C2=A0 Title: Limit maximum transaction size<br></div><div>=C2=A0 A=
uthor: Gavin Andresen <<a href=3D"mailto:gavinandresen@gmail.com">gavina=
ndresen@gmail.com</a>></div><div>=C2=A0 Status: Draft</div><div>=C2=A0 T=
ype: Standards Track</div><div>=C2=A0 Created: 2015-07-17</div><div><br></d=
iv><div>=3D=3DAbstract=3D=3D</div><div><br></div><div>Mitigate a potential =
CPU exhaustion denial-of-service attack by limiting</div><div>the maximum s=
ize of a transaction included in a block.</div><div><br></div><div>=3D=3DMo=
tivation=3D=3D</div><div><br></div><div>Sergio Demian Lerner reported that =
a maliciously constructed block could</div><div>take several minutes to val=
idate, due to the way signature hashes are</div><div>computed for OP_CHECKS=
IG/OP_CHECKMULTISIG ([[<a href=3D"https://bitcointalk.org/?topic=3D140078|C=
VE-2013-2292]]">https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]]</a>=
).</div><div>Each signature validation can require hashing most of the tran=
saction's</div><div>bytes, resulting in O(s*b) scaling (where n is the =
number of signature</div><div>operations and m is the number of bytes in th=
e transaction, excluding</div><div>signatures). If there are no limits on n=
or m the result is O(n^2) scaling.</div><div><br></div><div>This potential=
attack was mitigated by changing the default relay and</div><div>mining po=
licies so transactions larger than 100,000 bytes were not</div><div>relayed=
across the network or included in blocks. However, a miner</div><div>not f=
ollowing the default policy could choose to include a</div><div>transaction=
that filled the entire one-megaybte block and took</div><div>a long time t=
o validate.</div><div><br></div><div>=3D=3DSpecification=3D=3D</div><div><b=
r></div><div>After deployment, the maximum serialized size of a transaction=
allowed</div><div>in a block shall be 100,000 bytes.</div><div><br></div><=
div>=3D=3DCompatibility=3D=3D</div><div><br></div><div>This change should b=
e compatible with existing transaction-creation software,</div><div>because=
transactions larger than 100,000 bytes have been considered "non-stan=
dard"</div><div>(they are not relayed or mined by default) for years.<=
/div><div><br></div><div>Software that assembles transactions into blocks a=
nd that validates blocks must be</div><div>updated to reject oversize trans=
actions.</div><div><br></div><div>=3D=3DDeployment=3D=3D</div><div><br></di=
v><div>This change will be deployed with BIP 100 or BIP 101.</div><div><br>=
</div><div>=3D=3DDiscussion=3D=3D</div><div><br></div><div>Alternatives to =
this BIP:</div><div><br></div><div>1. A new consensus rule that limits the =
number of signature operations in a</div><div>single transaction instead of=
limiting size. This might be more compatible with</div><div>future opcodes=
that require larger-than-100,000-byte transactions, although</div><div>any=
such future opcodes would likely require changes to the Script validation<=
/div><div>rules anyway (e.g. the 520-byte limit on data items).</div><div><=
br></div><div>2. Fix the SIG opcodes so they don't re-hash variations o=
f the transaction's data.</div><div>This is the "most correct"=
; solution, but would require updating every</div><div>piece of transaction=
-creating and transaction-validating software to change how</div><div>they =
compute the signature hash.</div><div><br></div><div>=3D=3DReferences=3D=3D=
</div><div><br></div><div>[[<a href=3D"https://bitcointalk.org/?topic=3D140=
078|CVE-2013-2292]">https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]<=
/a>]: Sergio Demian Lerner's original report</div><div><br></div><div><=
br></div><div class=3D"gmail_signature"><br></div>
</div>
--001a11347d2c4af458051b534a21--
|
