From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 7F1DF40A for ; 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 ; Fri, 24 Jul 2015 20:59:41 +0000 (UTC) Received: by lbbyj8 with SMTP id yj8so22404368lbb.0 for ; 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: References: Date: Fri, 24 Jul 2015 16:59:40 -0400 Message-ID: From: Gavin Andresen 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
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.

The last two commits in this branch are an implementation:

From the commit message in the la= st 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: be= nchmark Core's sighash-creation code ('openssl speed sha256' re= ports something like 1GB per second on my machine).

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.


Draft BIP:

=C2=A0 = BIP: ??
=C2=A0 Title: Consensus rules to limit CPU time requi= red to validate blocks
=C2=A0 Author: Gavin Andresen <gavinandresen@gmail.com>
=C2=A0 Status: Draft
=C2=A0 Type: Standards Track
= =C2=A0 Created: 2015-07-24

=3D=3DAbstract=3D=3D

Mitigate potential CPU exhaustion denial-of-service = attacks by limiting
the maximum number of ECDSA signature verfica= tions done per block,
and limiting the number of bytes hashed to = compute signature hashes.

=3D=3DMotivation=3D=3D

Sergio Demian Lerner reported that a maliciously co= nstructed block could
take several minutes to validate, due to th= e way signature hashes are
computed for OP_CHECKSIG/OP_CHECKMULTI= SIG ([[= https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]]).
Eac= h signature validation can require hashing most of the transaction's
bytes, resulting in O(s*b) scaling (where s is the number of signat= ure
operations and b is the number of bytes in the transaction, e= xcluding
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 transaction= s larger than 100,000 bytes were not
relayed across the network o= r included in blocks. However, a miner
not following the default = policy could choose to include a
transaction that filled the enti= re one-megaybte block and took
a long time to validate.

=3D=3DSpecification=3D=3D

After de= ployment, the existing consensus rule for maximum number of
signa= ture operations per block (20,000, counted in two different,
idio= syncratic, ad-hoc ways) shall be replaced by the following two rules:
=

1. The maximum number of ECDSA verify operations requir= ed to validate
all of the transactions in a block must be less th= an or equal to
the maximum block size in bytes divided by 100 (ro= unded 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 1= 60.

=3D=3DCompatibility=3D=3D

=
This change is compatible with existing transaction-creation software,=
because transactions larger than 100,000 bytes have been conside= red "non-standard"
(they are not relayed or mined by de= fault) for years, and a block full of
"standard" transa= ctions will be well-under the limits.

Software tha= t assembles transactions into blocks and software that validates
= blocks must be updated to enforce the new consensus rules.

=3D=3DDeployment=3D=3D

This change will b= e deployed with BIP 100 or BIP 101.

=3D=3DDiscussi= on=3D=3D

Linking these consensus rules to the maxi= mum block size allows more transactions
and/or transactions with = more inputs or outputs to be included if the maximum
block size i= ncreases.

The constants are chosen to be maximally= compatible with the existing consensus rule,
and to virtually el= iminate the possibility that bitcoins could be lost if
somebody h= ad locked some funds in a pre-signed, expensive-to-validate, locktime-in-th= e-future
transaction.

But they are chose= n to put a reasonable upper bound on the CPU time required to validate
a maximum-sized block.

=3D=3D=3DAlternatives= to this BIP:=3D=3D=3D

1. A simple limit on transa= ction size (e.g. any transaction in a block must be 100,000
bytes= or smaller).=C2=A0

2. Fix the CHECKSIG/CHECKMULTI= SIG opcodes so they don't re-hash variations of
the transacti= on's data. This is the "most correct" solution, but would req= uire
updating every piece of transaction-creating and transaction= -validating software
to change how they compute the signature has= h, and to avoid potential attacks would
still require some limit = on how many such operations were permitted.

=3D=3D= References=3D=3D

[[https://bitcointalk.org/?topic=3D140078= |CVE-2013-2292]]: Sergio Demian Lerner's original report
=

--089e0160bd704d14ad051ba54898--