<div dir="ltr"><div>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.</div><div><br></div><div>The last two commits in this branch are an implementation:</div><div> <a href="https://github.com/gavinandresen/bitcoin-git/commits/count_hash_size">https://github.com/gavinandresen/bitcoin-git/commits/count_hash_size</a></div><div><br></div><div>From the commit message in the last commit:</div><div><br></div><div><pre style="overflow:visible;font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:13px;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-word;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: benchmark Core's sighash-creation code ('openssl speed sha256' reports something like 1GB per second on my machine).</div><div><br></div><div>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.</div><div><br></div><div><br></div><div>Draft BIP:</div><div><br></div><div> BIP: ??<br></div><div> Title: Consensus rules to limit CPU time required to validate blocks</div><div> Author: Gavin Andresen <<a href="mailto:gavinandresen@gmail.com">gavinandresen@gmail.com</a>></div><div> Status: Draft</div><div> Type: Standards Track</div><div> Created: 2015-07-24</div><div><br></div><div>==Abstract==</div><div><br></div><div>Mitigate potential CPU exhaustion denial-of-service attacks by limiting</div><div>the maximum number of ECDSA signature verfications done per block,</div><div>and limiting the number of bytes hashed to compute signature hashes.</div><div><br></div><div>==Motivation==</div><div><br></div><div>Sergio Demian Lerner reported that a maliciously constructed block could</div><div>take several minutes to validate, due to the way signature hashes are</div><div>computed for OP_CHECKSIG/OP_CHECKMULTISIG ([[<a href="https://bitcointalk.org/?topic=140078|CVE-2013-2292]]">https://bitcointalk.org/?topic=140078|CVE-2013-2292]]</a>).</div><div>Each signature validation can require hashing most of the transaction's</div><div>bytes, resulting in O(s*b) scaling (where s is the number of signature</div><div>operations and b is the number of bytes in the transaction, excluding</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 transactions larger than 100,000 bytes were not</div><div>relayed across the network or included in blocks. However, a miner</div><div>not following 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 to validate.</div><div><br></div><div>==Specification==</div><div><br></div><div>After deployment, the existing consensus rule for maximum number of</div><div>signature operations per block (20,000, counted in two different,</div><div>idiosyncratic, ad-hoc ways) shall be replaced by the following two rules:</div><div><br></div><div>1. The maximum number of ECDSA verify operations required to validate</div><div>all of the transactions in a block must be less than or equal to</div><div>the maximum block size in bytes divided by 100 (rounded 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 160.</div><div><br></div><div>==Compatibility==</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 considered "non-standard"</div><div>(they are not relayed or mined by default) for years, and a block full of</div><div>"standard" transactions will be well-under the limits.</div><div><br></div><div>Software that 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>==Deployment==</div><div><br></div><div>This change will be deployed with BIP 100 or BIP 101.</div><div><br></div><div>==Discussion==</div><div><br></div><div>Linking these consensus rules to the maximum 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 increases.</div><div><br></div><div>The constants are chosen to be maximally compatible with the existing consensus rule,</div><div>and to virtually eliminate the possibility that bitcoins could be lost if</div><div>somebody had locked some funds in a pre-signed, expensive-to-validate, locktime-in-the-future</div><div>transaction.</div><div><br></div><div>But they are chosen to put a reasonable upper bound on the CPU time required to validate</div><div>a maximum-sized block.</div><div><br></div><div>===Alternatives to this BIP:===</div><div><br></div><div>1. A simple limit on transaction size (e.g. any transaction in a block must be 100,000</div><div>bytes or smaller). </div><div><br></div><div>2. Fix the CHECKSIG/CHECKMULTISIG opcodes so they don't re-hash variations of</div><div>the transaction's data. This is the "most correct" solution, but would require</div><div>updating every piece of transaction-creating and transaction-validating software</div><div>to change how they compute the signature hash, and to avoid potential attacks would</div><div>still require some limit on how many such operations were permitted.</div><div><br></div><div>==References==</div><div><br></div><div>[[<a href="https://bitcointalk.org/?topic=140078|CVE-2013-2292]">https://bitcointalk.org/?topic=140078|CVE-2013-2292]</a>]: Sergio Demian Lerner's original report</div><div><br></div><div class="gmail_extra"><div class="gmail_signature"><br></div>
</div></div>