For discussion: limit transaction size to mitigate CVE-2013-2292

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

On Mon, Jul 20, 2015 at 8:10 PM, Gavin Andresen via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> After deployment, the maximum serialized size of a transaction allowed
> in a block shall be 100,000 bytes.
>

This could render transactions with a locktime in the future as unspendable.

It is pretty low probability that someone has created a >100kB locked transaction though.

It violates the principle that no fork should render someone's coins unspendable.

At the cost of weakening the protection, the rule could be made to only apply to version 2 transactions.

*Specification*

    The transaction version is increased to version two.

    All coinbase transactions must be version two or higher.

    If any of its parent transactions are version two or higher
    then the transaction must be version two or higher.

    The maximum serialized size of a version two transactions allowed in
    a block is 100,000 bytes.

As time passes more and more of the UTXO set will be from version two transactions. To launch the attack, the attacker needs an historical UTXO entry.

Standard software would create version two transactions even if all inputs were version one.

The rule could be applied to all transactions most of the time, and have daily blocks that allow legacy transactions.

    This rule shall apply to version 1 transactions too unless the block
height is
    a multiple of 100.

At the risk of encouraging feature creep, if the transaction size is being limited, it would be useful to also limit the size of all its inputs.

This helps with fraud proofs and offline signing.

*Specification*
    The transaction version is increased to version two.

    All coinbase transactions must be version two or higher.

    If any of its parent transactions are version two or higher
    then the transaction must be version two or higher.

    The maximum serialized size of a version two transactions allowed in
    a block is 100,000 bytes.

    The maximum of the total serialized size of a version two transaction
and all
    of its parents allowed in a block shall be 200,000 bytes.

I take it there's no feasibility in suggesting the script execution code has run time maximums? I'm aware these would be much harder to have consensus on, but would seem like the better solution if at all possible.

Ross

On 20/07/2015 20:10, Gavin Andresen via bitcoin-dev wrote:

> 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
> <mailto: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]]
> <https://bitcointalk.org/?topic=140078%7CCVE-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]
> <https://bitcointalk.org/?topic=140078%7CCVE-2013-2292]>]: Sergio
> Demian Lerner's original report
>
>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

On Mon, Jul 20, 2015 at 3:43 PM, Tier Nolan via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> This could render transactions with a locktime in the future as
> unspendable.
>
> It is pretty low probability that someone has created a >100kB locked
> transaction though.
>
> It violates the principle that no fork should render someone's coins
> unspendable.
>

Mmmm.... you'd have to:

a) Have lost or thrown away the keys to the unspent transaction outputs b) Have created a locktime'd transaction with a lock time after the BIP100/101 switchover times that is more than 100,000 bytes big c) Have some special relationship with a miner that you trust to still be around when the transaction unlocks that would mine the bigger-than-standard transaction for you.

I don't think adding extra complexity to consensus-critical code to support such an incredibly unlikely scenario is the right decision here. I think it is more likely that the extra complexity would trigger a bug that causes a loss of bitcoin greater than the amount of bitcoin tied up in locktime'ed transactions (because I think there are approximately zero BTC tied up in >100K locktime'ed transactions).

RE: limit size of transaction+parents: Feature creep, belongs in another BIP in my opinion. This one is focused on fixing CVE-2013-2292

On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:

> Mitigate a potential CPU exhaustion denial-of-service attack by limiting
> the maximum size of a transaction included in a block.

This seems like a fairly indirect approach. The resource being watched for is not the size (otherwise two transactions for 200k would be strictly worse than one 200k transactions) but the potential of N^2 costs related to repeated hashing in checksig; which this ignores.

The cost of the indirection is forclosing future applications which involve larger signatures but have no quadratic component and are thus fast to verify-- or requring yet another hard fork to remove the limit, or a kludgy soft fork that splits the same data across two "transactions" which get processed as a unit... all would be unfortunate.

Alternative 1 sounds more attractive to be for this reason as it's more direct.

On Mon, Jul 20, 2015 at 4:55 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote:

> On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation•org> wrote:
> > Mitigate a potential CPU exhaustion denial-of-service attack by limiting
> > the maximum size of a transaction included in a block.
>
> This seems like a fairly indirect approach. The resource being watched
> for is not the size (otherwise two transactions for 200k would be
> strictly worse than one 200k transactions) but the potential of N^2
> costs related to repeated hashing in checksig; which this ignores.
>

Yes. The tradeoff is implementation complexity: it is trivial to check transaction size, not as trivial to count signature operations, because number-of-bytes-in-transaction doesn't require any context.

But I would REALLY hate myself if in ten years a future version of me was struggling to get consensus to move away from some stupid 100,000 byte transaction size limit I imposed to mitigate a potential DoS attack.

So I agree, a limit on sigops is the right way to go. And if that is being changed, might as well accurately count exactly how many sigops a transaction actually requires to be validated...

I think it's not a horrible idea to just add a field into the transaction metadata for N_SIG_OPS in the script_sig

It is much simpler in implementation if the concern is complexity (once a transaction goes above N_SIG_OPS it could be considered invalid, number computed must be equal). It wouldn't even need to be stored permanently as it can be pruned easily and recomputed later (hashes would protect against buggy complicated sig counting code).

Furthermore, it would differentiate a branch with different counts well.

On Wed, Jul 22, 2015 at 2:09 AM, Gavin Andresen via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> On Mon, Jul 20, 2015 at 4:55 PM, Gregory Maxwell <gmaxwell@gmail•com>
> wrote:
>
>> On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev
>> <bitcoin-dev@lists•linuxfoundation•org> wrote:
>> > Mitigate a potential CPU exhaustion denial-of-service attack by limiting
>> > the maximum size of a transaction included in a block.
>>
>> This seems like a fairly indirect approach. The resource being watched
>> for is not the size (otherwise two transactions for 200k would be
>> strictly worse than one 200k transactions) but the potential of N^2
>> costs related to repeated hashing in checksig; which this ignores.
>>
>
> Yes.  The tradeoff is implementation complexity: it is trivial to check
> transaction size,
> not as trivial to count signature operations, because
> number-of-bytes-in-transaction
> doesn't require any context.
>
> But I would REALLY hate myself if in ten years a future version of me was
> struggling to
> get consensus to move away from some stupid 100,000 byte transaction size
> limit
> I imposed to mitigate a potential DoS attack.
>
> So I agree, a limit on sigops is the right way to go. And if that is being
> changed,
> might as well accurately count exactly how many sigops a transaction
> actually
> requires to be validated...
>
> --
> --
> Gavin Andresen
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

On Mon, Jul 20, 2015 at 4:55 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote:

> On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation•org> wrote:
> > Mitigate a potential CPU exhaustion denial-of-service attack by limiting
> > the maximum size of a transaction included in a block.
>
> This seems like a fairly indirect approach. The resource being watched
> for is not the size (otherwise two transactions for 200k would be
> strictly worse than one 200k transactions) but the potential of N^2
> costs related to repeated hashing in checksig; which this ignores.
>

To get a feeling for the implementation complexity / correctness tradeoff, I implemented changes to Core to count exactly how many signature operations are performed and how many bytes are hashed to compute sighashes:

https://github.com/gavinandresen/bitcoin-git/commit/08ecd6f67d977271faa92bc1890b8f94b15c2792

I haven't benchmarked how much keeping track of the counts affects performance (but I expect it to be minimal compared to ECDSA signature validation, accessing inputs from the UTXO, etc).

I like the idea of a consensus rule that directly addresses the attack-- e.g. "validating a transaction must not require more than X megabytes hashed to compute signature hashes." (or: "validating a block must not require more than X megabytes hashed..." which is more symmetric with the current "maximum number of sigops allowed per block")

Thinking about this and looking at block 364,292, I think I see a simple optimization that would speed up validation for transactions with lots of inputs: use SIGHASH_ANYONECANPAY for all of the inputs instead of SIGHASH_ALL.

(which would make the transaction malleable-- if that's a concern, then make one of the inputs SIGHASH_ALL and the rest SIGHASH_ANYONECANPAY-- I think this is a change that should be made to Core and other wallets should make).

---

I'd like to hear from maintainers of other full implementations: how hard would it be for you to keep track of the number of bytes hashed to validate a transaction or block, and use it as a consensus rule?

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

Interesting, so this basically would merge into an already existing BIP (Jeff Garzik's). However, it proposes some changes.

OK

CVE-2013-2292 is a severity thingy of "high" which is described as

"bitcoind and Bitcoin-Qt 0.8.0 and earlier allow remote attackers to cause a denial of service (electricity consumption) by mining a block to create a nonstandard Bitcoin transaction containing multiple OP_CHECKSIG script opcodes."

(munches popcorn)

I do appreciate seeing the effort toward working something toward / into Garzik's proposal. The general idea that I suggested before - to work some new ideas (not XT-related), into a BIP, and to work with Jeff Garzik on getting something done, seems to be the direction that you are taking... so I'm hopeful that continues.

- -O

On 07/24/2015 01:59 PM, Gavin Andresen via bitcoin-dev wrote:

> 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
> <mailto: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
>
>
>
>
> _______________________________________________ bitcoin-dev mailing
> list bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

- -- http://abis.io ~ "a protocol concept to enable decentralization and expansion of a giving economy, and a new social good" https://keybase.io/odinn