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

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

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 2656 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3716 bytes --]

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

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2124 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 3027 bytes --]

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

[Ross Nicoll]

[-- Attachment #1: Type: text/plain, Size: 3440 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


[-- Attachment #2: Type: text/html, Size: 6277 bytes --]

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

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 1350 bytes --]

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


-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 2434 bytes --]

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

[Gregory Maxwell]

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.

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

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 1247 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1887 bytes --]

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

[Jeremy Rubin]

[-- Attachment #1: Type: text/plain, Size: 2131 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3397 bytes --]

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

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 2150 bytes --]

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?

-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 3384 bytes --]

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

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 5334 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 7270 bytes --]

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

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJVsty2AAoJEGxwq/inSG8ChnsH/1zvxxYlKE4LPdwx9PPdk4Pi
W9Vj1RAX+J57f+kxE6tVZRLkIVo0vpTPqDaNMAcvsDWPdlK1wQKrjzws1qN8UpiO
yoMHAu8TC+HMoV+wJZVHafXf/e+PitWMS2P2HMZFVSlh7m/nsZNvjkykgyBNgaoh
wf4SQOSoorCUr4HDDsw32lmMq5Sohaq3Z+WSXKik8awel6OcerVPDwAWkb79tXTC
THI+t3YjLhQjwXNvs3Iwn7z1iYSSUbZUoUlOpCwaeVx6tdtDgW4vzzohCOEl2VqO
z8K6TM60+01pHAbrsWv9ItOBus8wJWHEyUFcdshf71BaNq2NHfijyCy9dCxtgWg=
=speV
-----END PGP SIGNATURE-----