* [bitcoin-dev] Fraud proofs for block size/weight
@ 2017-03-22 8:47 Luke Dashjr
2017-03-22 20:49 ` Bram Cohen
0 siblings, 1 reply; 7+ messages in thread
From: Luke Dashjr @ 2017-03-22 8:47 UTC (permalink / raw)
To: bitcoin-dev
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. 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.
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. As such, they are likely to need protection from these attacks, to ensure
they remain on the Bitcoin blockchain.
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:
https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki
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.
Luke
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-22 8:47 [bitcoin-dev] Fraud proofs for block size/weight Luke Dashjr @ 2017-03-22 20:49 ` Bram Cohen 2017-03-22 21:51 ` Matt Corallo 0 siblings, 1 reply; 7+ messages in thread From: Bram Cohen @ 2017-03-22 20:49 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2087 bytes --] 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. 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. On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> 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. 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. > > 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. As such, they are likely to need protection from these attacks, to > ensure > they remain on the Bitcoin blockchain. > > 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: > > https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki > > 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. > > Luke > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 2879 bytes --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-22 20:49 ` Bram Cohen @ 2017-03-22 21:51 ` Matt Corallo 2017-03-23 18:27 ` Jorge Timón 0 siblings, 1 reply; 7+ messages in thread From: Matt Corallo @ 2017-03-22 21:51 UTC (permalink / raw) To: Bram Cohen, Bitcoin Protocol Discussion, Bram Cohen via bitcoin-dev, Luke Dashjr [-- Attachment #1: Type: text/plain, Size: 2729 bytes --] 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). It also 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"). On March 22, 2017 1:49:08 PM PDT, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> 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. > >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. > > >On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev < >bitcoin-dev@lists•linuxfoundation.org> 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. 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. >> >> 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. As such, they are likely to need protection from these attacks, >to >> ensure >> they remain on the Bitcoin blockchain. >> >> 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: >> >> >https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki >> >> 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. >> >> Luke >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> [-- Attachment #2: Type: text/html, Size: 3705 bytes --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-22 21:51 ` Matt Corallo @ 2017-03-23 18:27 ` Jorge Timón 2017-03-25 5:16 ` Luke Dashjr 0 siblings, 1 reply; 7+ messages in thread From: Jorge Timón @ 2017-03-23 18:27 UTC (permalink / raw) To: Matt Corallo, Bitcoin Protocol Discussion Great stuff, although the ordering of the sections seems a little bit confusing. I think it would be clearer to put the "Creation of proofs" section before "Proof verification", maybe even before "Proof format" if a high level defintion of "full tx size proof" is provided before. Also, in "For the full-size proof, each transaction should be assumed to be at a minimum the stripped-size rather than the fixed 60 bytes." it seems you are referring to a "full-size block proof" as opposed to a "full size tx proof", perhaps a better term could be "full-weight block proof" if what you are referring to is the proof of the weight instead of only the pre-segwit size. Perhaps some short definitions for "stripped-size proof", "full tx size proof", "full-size proof" and maybe also "size component" at the beginning would be enough. In "Network protocol", "It should not recheck blocks known to be valid, " does "known to be valid" include the blocks that the peer told us where valid (with their hash and 0 in the enumerated varint)? Those could be invalid too if the peer was lying, no? Do you mean "It should not recheck blocks known to be invalid,"? Why do you need to have at least one full tx size? In Rationale you have: " Why must a full tx size proof be included? This is necessary to establish that the claimed block transaction count is correct. " Why do you need to establish that? If you can establish that the number of transactions is at least N and that N * 60 bytes is greater than the size/weight limit, isn't it that enough? On Wed, Mar 22, 2017 at 10:51 PM, Matt Corallo via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > 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). It also 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"). > > > On March 22, 2017 1:49:08 PM PDT, Bram Cohen via bitcoin-dev > <bitcoin-dev@lists•linuxfoundation.org> 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. >> >> 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. >> >> >> On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev >> <bitcoin-dev@lists•linuxfoundation.org> 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. 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. >>> >>> 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. As such, they are likely to need protection from these attacks, to >>> ensure >>> they remain on the Bitcoin blockchain. >>> >>> 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: >>> >>> https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki >>> >>> 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. >>> >>> Luke >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists•linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >> > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-23 18:27 ` Jorge Timón @ 2017-03-25 5:16 ` Luke Dashjr 2017-03-26 14:16 ` Chris Pacia 2017-03-28 22:35 ` Matt Corallo 0 siblings, 2 replies; 7+ messages in thread From: Luke Dashjr @ 2017-03-25 5:16 UTC (permalink / raw) To: bitcoin-dev, Jorge Timón On Thursday, March 23, 2017 6:27:39 PM Jorge Timón via bitcoin-dev wrote: > I think it would be clearer to put the "Creation of proofs" section > before "Proof verification", maybe even before "Proof format" if a > high level defintion of "full tx size proof" is provided before. Creation of proofs isn't part of the spec itself. I've moved it out of the Specification section (but it's still below it). > Also, in "For the full-size proof, each transaction should be assumed > to be at a minimum the stripped-size rather than the fixed 60 bytes." > it seems you are referring to a "full-size block proof" as opposed to > a "full size tx proof", perhaps a better term could be "full-weight > block proof" if what you are referring to is the proof of the weight > instead of only the pre-segwit size. > > Perhaps some short definitions for "stripped-size proof", "full tx > size proof", "full-size proof" and maybe also "size component" at the > beginning would be enough. Added a definitions section above. > In "Network protocol", "It should not recheck blocks known to be > valid, " does "known to be valid" include the blocks that the peer > told us where valid (with their hash and 0 in the enumerated varint)? > Those could be invalid too if the peer was lying, no? > Do you mean "It should not recheck blocks known to be invalid,"? Right, fixed. > Why do you need to have at least one full tx size? > > In Rationale you have: > " > Why must a full tx size proof be included? > > This is necessary to establish that the claimed block transaction > count is correct. > " > > Why do you need to establish that? If you can establish that the > number of transactions is at least N and that N * 60 bytes is greater > than the size/weight limit, isn't it that enough? The only way to establish the number of transactions at all, is to show that a leaf is a parsable transaction. Which this doesn't actually show, so it's broken. :( Need to think on this. Any ideas? :/ Luke ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-25 5:16 ` Luke Dashjr @ 2017-03-26 14:16 ` Chris Pacia 2017-03-28 22:35 ` Matt Corallo 1 sibling, 0 replies; 7+ messages in thread From: Chris Pacia @ 2017-03-26 14:16 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 363 bytes --] On Mar 25, 2017 12:17 AM, "Luke Dashjr via bitcoin-dev" <bitcoin-dev@lists. linuxfoundation.org> wrote: Any ideas? :/ Can't the size be aggregated up the tree such that each midstate hash is the hash of branches below plus the agreegate of the sizes below. This would make the root hash(left + right + size/weight) and the proof would just be the preimage. [-- Attachment #2: Type: text/html, Size: 992 bytes --] ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bitcoin-dev] Fraud proofs for block size/weight 2017-03-25 5:16 ` Luke Dashjr 2017-03-26 14:16 ` Chris Pacia @ 2017-03-28 22:35 ` Matt Corallo 1 sibling, 0 replies; 7+ messages in thread From: Matt Corallo @ 2017-03-28 22:35 UTC (permalink / raw) To: Luke Dashjr, bitcoin-dev, Jorge Timón I dont think thats true? Sure, you have to assume the block is valid aside from a too-large size, but it seems sane. You don't strictly need to show that a leaf is a parseable transaction, as long as you can assume that the block is valid and that you cannot forge a SHA256 midstate which, when combined with data with a given length tag, would result in a hash of a given value (this is a pretty strong assumption, IMO, IIRC this was not a studied nor a claimed feature of SHA256). The only issue is that, since parts of the merkle tree are repeated, you need to be sure that the counting for minimum number of transactions is accurate, though I did not review your proposal text to check that. On 03/25/17 05:16, Luke Dashjr wrote: - snip - > The only way to establish the number of transactions at all, is to show that a > leaf is a parsable transaction. Which this doesn't actually show, so it's > broken. :( Need to think on this. Any ideas? :/ > > Luke > ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2017-03-28 22:36 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-03-22 8:47 [bitcoin-dev] Fraud proofs for block size/weight Luke Dashjr 2017-03-22 20:49 ` Bram Cohen 2017-03-22 21:51 ` Matt Corallo 2017-03-23 18:27 ` Jorge Timón 2017-03-25 5:16 ` Luke Dashjr 2017-03-26 14:16 ` Chris Pacia 2017-03-28 22:35 ` Matt Corallo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox