Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3A896B63 for ; Wed, 22 Mar 2017 21:51:15 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail.bluematt.me (mail.bluematt.me [192.241.179.72]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7371F124 for ; Wed, 22 Mar 2017 21:51:14 +0000 (UTC) Received: from [100.69.147.137] (unknown [172.56.16.130]) by mail.bluematt.me (Postfix) with ESMTPSA id 6AF571399F8; Wed, 22 Mar 2017 21:51:12 +0000 (UTC) Date: Wed, 22 Mar 2017 21:51:08 +0000 In-Reply-To: References: <201703220847.31303.luke@dashjr.org> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ" Content-Transfer-Encoding: 7bit To: Bram Cohen , Bitcoin Protocol Discussion , Bram Cohen via bitcoin-dev , Luke Dashjr From: Matt Corallo Message-ID: <30FB8B13-135D-4905-B1B4-76D79341CA02@mattcorallo.com> X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Fraud proofs for block size/weight X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Mar 2017 21:51:15 -0000 ------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable It works today and can be used to prove exact size: the key observation is = that all you need to show the length and hash of a transaction is the final= SHA256 midstate and chunk (max 64 bytes)=2E It also uses the observation t= hat a valid transaction must be at least 60 bytes long for compression (tho= ugh much of that compression possibility goes away if you're proving someth= ing other than "too large")=2E On March 22, 2017 1:49:08 PM PDT, Bram Cohen via bitcoin-dev wrote: >Some questions: > >Does this require information to be added to blocks, or can it work >today >on the existing format? > >Does this count number of transactions or their total length? The block >limit is in bytes rather than number of transactions, but transaction >number can be a reasonable proxy if you allow for some false negatives >but >want a basic sanity check=2E > >Does this allow for proofs of length in the positive direction, >demonstrating that a block is good, or does it only serve to show that >blocks are bad? Ideally we'd like an extension to SPV protocol so light >clients require proofs of blocks not being too big, given the credible >threat of there being an extremely large-scale attack on the network of >that form=2E > > >On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev < >bitcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote: > >> Despite the generalised case of fraud proofs being likely impossible, >there >> have recently been regular active proposals of miners attacking with >simply >> oversized blocks in an attempt to force a hardfork=2E This specific >attack >> can >> be proven, and reliably so, since the proof cannot be broken without >also >> breaking their attempted hardfork at the same time=2E >> >> While ideally all users ought to use their own full node for >validation >> (even >> when using a light client for their wallet), many bitcoin holders >still do >> not=2E As such, they are likely to need protection from these attacks, >to >> ensure >> they remain on the Bitcoin blockchain=2E >> >> I've written up a draft BIP for fraud proofs and how light clients >can >> detect >> blockchains that are simply invalid due to excess size and/or weight: >> >> =20 >https://github=2Ecom/luke-jr/bips/blob/bip-sizefp/bip-sizefp=2Emediawiki >> >> I believe this draft is probably ready for implementation already, >but if >> anyone has any idea on how it might first be improved, please feel >free to >> make suggestions=2E >> >> Luke >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists=2Elinuxfoundation=2Eorg >> https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev >> ------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable It works today and can be used to prove exact size= : the key observation is that all you need to show the length and hash of a= transaction is the final SHA256 midstate and chunk (max 64 bytes)=2E It al= so uses the observation that a valid transaction must be at least 60 bytes = long for compression (though much of that compression possibility goes away= if you're proving something other than "too large")=2E
On March 22, 2017 1:49:08 PM PDT, Bram Cohen v= ia bitcoin-dev <bitcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote:
Some questions:

Does this require in= formation to be added to blocks, or can it work today on the existing forma= t?

Does this count number of transactions or the= ir total length? The block limit is in bytes rather than number of transact= ions, but transaction number can be a reasonable proxy if you allow for som= e false negatives but want a basic sanity check=2E

Does this allow for proofs of length in the positive direction, demonstr= ating that a block is good, or does it only serve to show that blocks are b= ad? Ideally we'd like an extension to SPV protocol so light clients require= proofs of blocks not being too big, given the credible threat of there bei= ng an extremely large-scale attack on the network of that form=2E


On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists=2Elinuxfoundation=2Eorg> w= rote:
Despite the generalised case of= fraud proofs being likely impossible, there
have recently been regular active proposals of miners attacking with simpl= y
oversized blocks in an attempt to force a hardfork=2E This specific attack= can
be proven, and reliably so, since the proof cannot be broken without also<= br /> breaking their attempted hardfork at the same time=2E

While ideally all users ought to use their own full node for validation (e= ven
when using a light client for their wallet), many bitcoin holders still do=
not=2E As such, they are likely to need protection from these attacks, to = ensure
they remain on the Bitcoin blockchain=2E

I've written up a draft BIP for fraud proofs and how light clients can det= ect
blockchains that are simply invalid due to excess size and/or weight:

    https://githu= b=2Ecom/luke-jr/bips/blob/bip-sizefp/bip-sizefp=2Emediawiki

I believe this draft is probably ready for implementation already, but if<= br /> anyone has any idea on how it might first be improved, please feel free to=
make suggestions=2E

Luke
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@l= ists=2Elinuxfoundation=2Eorg
https://lists=2Elinuxfoundation= =2Eorg/mailman/listinfo/bitcoin-dev

------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ--