MIME-Version: 1.0
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
Subject: [bitcoin-dev] For discussion: limit transaction size to mitigate
	CVE-2013-2292
Precedence: list

--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 &lt;<a href=3D"mailto:gavinandresen@gmail.com">gavina=
ndresen@gmail.com</a>&gt;</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&#39;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 &quot;non-stan=
dard&quot;</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&#39;t re-hash variations o=
f the transaction&#39;s data.</div><div>This is the &quot;most correct&quot=
; 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&#39;s original report</div><div><br></div><div><=
br></div><div class=3D"gmail_signature"><br></div>
</div>

--001a11347d2c4af458051b534a21--