public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Ross Nicoll <jrn@jrn•me.uk>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] For discussion: limit transaction size to mitigate CVE-2013-2292
Date: Mon, 20 Jul 2015 20:58:27 +0100	[thread overview]
Message-ID: <55AD52E3.3070306@jrn.me.uk> (raw)
In-Reply-To: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>

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

  parent reply	other threads:[~2015-07-20 19:58 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-07-20 19:10 Gavin Andresen
2015-07-20 19:43 ` Tier Nolan
2015-07-20 20:30   ` Gavin Andresen
2015-07-20 19:58 ` Ross Nicoll [this message]
2015-07-20 20:55 ` Gregory Maxwell
2015-07-21 18:09   ` Gavin Andresen
2015-07-21 18:18     ` Jeremy Rubin
2015-07-23 15:41   ` Gavin Andresen
2015-07-24 20:59     ` Gavin Andresen
2015-07-25  0:47       ` odinn

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=55AD52E3.3070306@jrn.me.uk \
    --to=jrn@jrn$(echo .)me.uk \
    --cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox