[bitcoin-dev] For discussion: limit transaction size to mitigate CVE-2013-2292

[Gavin Andresen via bitcoin-dev]

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 <***@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

[Tier Nolan via bitcoin-dev]

On Mon, Jul 20, 2015 at 8:10 PM, Gavin Andresen via bitcoin-dev <

Post by Gavin Andresen via bitcoin-dev
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.

[Gavin Andresen via bitcoin-dev]

On Mon, Jul 20, 2015 at 3:43 PM, Tier Nolan via bitcoin-dev <

Post by Tier Nolan via bitcoin-dev
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

[Ross Nicoll via bitcoin-dev]

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

Post by Gavin Andresen via bitcoin-dev
Draft BIP to prevent a potential CPU exhaustion attack if a
Title: Limit maximum transaction size
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==
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev

Post by Gavin Andresen via bitcoin-dev
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.

[Gavin Andresen via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev

Post by Gavin Andresen via bitcoin-dev
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...

[Jeremy Rubin via bitcoin-dev]

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 <

Post by Gavin Andresen via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev

Post by Gavin Andresen via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gavin Andresen via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev

Post by Gavin Andresen via bitcoin-dev
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?

[Gavin Andresen via bitcoin-dev]

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 <***@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

[odinn via bitcoin-dev]

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

Post by Gavin Andresen via bitcoin-dev
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.
https://github.com/gavinandresen/bitcoin-git/commits/count_hash_size
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.
BIP: ?? Title: Consensus rules to limit CPU time required to
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
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
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