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

--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&#39;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,&#39;Liberation Mono&#39;,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&#39;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&#39;s sighash-creation code (&#39;openssl speed sha256&#39; 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&#39;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&quot; 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 &lt;<a href=
=3D"mailto:gavinandresen@gmail.com">gavinandresen@gmail.com</a>&gt;</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&#39;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 &quot;non-standard&quot;</div><div>(they are not relayed or mined by de=
fault) for years, and a block full of</div><div>&quot;standard&quot; 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&#39;t re-hash variations of</div><div>the transacti=
on&#39;s data. This is the &quot;most correct&quot; 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&#39;s original report</div><div>=
<br></div><div class=3D"gmail_extra"><div class=3D"gmail_signature"><br></d=
iv>
</div></div>

--089e0160bd704d14ad051ba54898--