To: bitcoin-dev@lists.linuxfoundation.org
References: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>
From: Ross Nicoll <jrn@jrn.me.uk>
Message-ID: <55AD52E3.3070306@jrn.me.uk>
Date: Mon, 20 Jul 2015 20:58:27 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:38.0) Gecko/20100101
	Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>
Content-Type: multipart/alternative;
	boundary="------------040908030201070401070706"
Subject: Re: [bitcoin-dev] For discussion: limit transaction size to
 mitigate CVE-2013-2292
Precedence: list

This is a multi-part message in MIME format.
--------------040908030201070401070706
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit

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


--------------040908030201070401070706
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

<html>
  <head>
    <meta content=3D"text/html; charset=3Dwindows-1252"
      http-equiv=3D"Content-Type">
  </head>
  <body bgcolor=3D"#FFFFFF" text=3D"#000000">
    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.<br>
    <br>
    Ross<br>
    <br>
    <div class=3D"moz-cite-prefix">On 20/07/2015 20:10, Gavin Andresen vi=
a
      bitcoin-dev wrote:<br>
    </div>
    <blockquote
cite=3D"mid:CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmai=
l.com"
      type=3D"cite">
      <div dir=3D"ltr">
        <div>Draft BIP to prevent a potential CPU exhaustion attack if a
          significantly larger maximum blocksize is adopted:</div>
        <div><br>
        </div>
        <div>=A0 Title: Limit maximum transaction size<br>
        </div>
        <div>=A0 Author: Gavin Andresen &lt;<a moz-do-not-send=3D"true"
            href=3D"mailto:gavinandresen@gmail.com">gavinandresen@gmail.c=
om</a>&gt;</div>
        <div>=A0 Status: Draft</div>
        <div>=A0 Type: Standards Track</div>
        <div>=A0 Created: 2015-07-17</div>
        <div><br>
        </div>
        <div>=3D=3DAbstract=3D=3D</div>
        <div><br>
        </div>
        <div>Mitigate a potential CPU exhaustion denial-of-service
          attack by limiting</div>
        <div>the maximum size of a transaction included in a block.</div>
        <div><br>
        </div>
        <div>=3D=3DMotivation=3D=3D</div>
        <div><br>
        </div>
        <div>Sergio Demian Lerner reported that a maliciously
          constructed block could</div>
        <div>take several minutes to validate, due to the way signature
          hashes are</div>
        <div>computed for OP_CHECKSIG/OP_CHECKMULTISIG ([[<a
            moz-do-not-send=3D"true"
            href=3D"https://bitcointalk.org/?topic=3D140078%7CCVE-2013-22=
92]]"><a class=3D"moz-txt-link-freetext" href=3D"https://bitcointalk.org/=
?topic=3D140078">https://bitcointalk.org/?topic=3D140078</a>|CVE-2013-229=
2]]</a>).</div>
        <div>Each signature validation can require hashing most of the
          transaction's</div>
        <div>bytes, resulting in O(s*b) scaling (where n is the number
          of signature</div>
        <div>operations and m is the number of bytes in the transaction,
          excluding</div>
        <div>signatures). If there are no limits on n or m the result is
          O(n^2) scaling.</div>
        <div><br>
        </div>
        <div>This potential attack was mitigated by changing the default
          relay and</div>
        <div>mining policies so transactions larger than 100,000 bytes
          were not</div>
        <div>relayed across the network or included in blocks. However,
          a miner</div>
        <div>not following the default policy could choose to include a</=
div>
        <div>transaction that filled the entire one-megaybte block and
          took</div>
        <div>a long time to validate.</div>
        <div><br>
        </div>
        <div>=3D=3DSpecification=3D=3D</div>
        <div><br>
        </div>
        <div>After deployment, the maximum serialized size of a
          transaction allowed</div>
        <div>in a block shall be 100,000 bytes.</div>
        <div><br>
        </div>
        <div>=3D=3DCompatibility=3D=3D</div>
        <div><br>
        </div>
        <div>This change should be compatible with existing
          transaction-creation software,</div>
        <div>because transactions larger than 100,000 bytes have been
          considered "non-standard"</div>
        <div>(they are not relayed or mined by default) for years.</div>
        <div><br>
        </div>
        <div>Software that assembles transactions into blocks and that
          validates blocks must be</div>
        <div>updated to reject oversize transactions.</div>
        <div><br>
        </div>
        <div>=3D=3DDeployment=3D=3D</div>
        <div><br>
        </div>
        <div>This change will be deployed with BIP 100 or BIP 101.</div>
        <div><br>
        </div>
        <div>=3D=3DDiscussion=3D=3D</div>
        <div><br>
        </div>
        <div>Alternatives to this BIP:</div>
        <div><br>
        </div>
        <div>1. A new consensus rule that limits the number of signature
          operations in a</div>
        <div>single transaction instead of limiting size. This might be
          more compatible with</div>
        <div>future opcodes that require larger-than-100,000-byte
          transactions, although</div>
        <div>any such future opcodes would likely require changes to the
          Script validation</div>
        <div>rules anyway (e.g. the 520-byte limit on data items).</div>
        <div><br>
        </div>
        <div>2. Fix the SIG opcodes so they don't re-hash variations of
          the transaction's data.</div>
        <div>This is the "most correct" solution, but would require
          updating every</div>
        <div>piece of transaction-creating and transaction-validating
          software to change how</div>
        <div>they compute the signature hash.</div>
        <div><br>
        </div>
        <div>=3D=3DReferences=3D=3D</div>
        <div><br>
        </div>
        <div>[[<a moz-do-not-send=3D"true"
            href=3D"https://bitcointalk.org/?topic=3D140078%7CCVE-2013-22=
92]">https://bitcointalk.org/?topic=3D140078|CVE-2013-2292]</a>]:
          Sergio Demian Lerner's original report</div>
        <div><br>
        </div>
        <div><br>
        </div>
        <div class=3D"gmail_signature"><br>
        </div>
      </div>
      <br>
      <fieldset class=3D"mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap=3D"">_______________________________________________
bitcoin-dev mailing list
<a class=3D"moz-txt-link-abbreviated" href=3D"mailto:bitcoin-dev@lists.li=
nuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>
<a class=3D"moz-txt-link-freetext" href=3D"https://lists.linuxfoundation.=
org/mailman/listinfo/bitcoin-dev">https://lists.linuxfoundation.org/mailm=
an/listinfo/bitcoin-dev</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>

--------------040908030201070401070706--