From: Olaoluwa Osuntokun <laolu32@gmail•com>
To: "David A. Harding" <dave@dtrt•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Date: Tue, 12 Jun 2018 16:51:29 -0700 [thread overview]
Message-ID: <CAO3Pvs_GYnFAS-pM=+OYCbJaEw8TOo-opnv5GVCBiDEurLvjYg@mail.gmail.com> (raw)
In-Reply-To: <20180609103445.alxrchjbbbxklkzt@email>
[-- Attachment #1: Type: text/plain, Size: 4891 bytes --]
> Doesn't the current BIP157 protocol have each filter commit to the filter
> for the previous block?
Yep!
> If that's the case, shouldn't validating the commitment at the tip of the
> chain (or buried back whatever number of blocks that the SPV client
trusts)
> obliviate the need to validate the commitments for any preceeding blocks
in
> the SPV trust model?
Yeah, just that there'll be a gap between the p2p version, and when it's
ultimately committed.
> It seems like you're claiming better security here without providing any
> evidence for it.
What I mean is that one allows you to fully verify the filter, while the
other allows you to only validate a portion of the filter and requires other
added heuristics.
> In the case of prevout+output filters, when a client receives
advertisements
> for different filters from different peers, it:
Alternatively, they can decompress the filter and at least verify that
proper _output scripts_ have been included. Maybe this is "good enough"
until its committed. If a command is added to fetch all the prev outs along
w/ a block (which would let you do another things like verify fees), then
they'd be able to fully validate the filter as well.
-- Laolu
On Sat, Jun 9, 2018 at 3:35 AM David A. Harding <dave@dtrt•org> wrote:
> On Fri, Jun 08, 2018 at 04:35:29PM -0700, Olaoluwa Osuntokun via
> bitcoin-dev wrote:
> > 2. Since the coinbase transaction is the first in a block, it has the
> > longest merkle proof path. As a result, it may be several hundred
> bytes
> > (and grows with future capacity increases) to present a proof to the
> > client.
>
> I'm not sure why commitment proof size is a significant issue. Doesn't
> the current BIP157 protocol have each filter commit to the filter for
> the previous block? If that's the case, shouldn't validating the
> commitment at the tip of the chain (or buried back whatever number of
> blocks that the SPV client trusts) obliviate the need to validate the
> commitments for any preceeding blocks in the SPV trust model?
>
> > Depending on the composition of blocks, this may outweigh the gains
> > had from taking advantage of the additional compression the prev outs
> > allow.
>
> I think those are unrelated points. The gain from using a more
> efficient filter is saved bytes. The gain from using block commitments
> is SPV-level security---that attacks have a definite cost in terms of
> generating proof of work instead of the variable cost of network
> compromise (which is effectively free in many situations).
>
> Comparing the extra bytes used by block commitments to the reduced bytes
> saved by prevout+output filters is like comparing the extra bytes used
> to download all blocks for full validation to the reduced bytes saved by
> only checking headers and merkle inclusion proofs in simplified
> validation. Yes, one uses more bytes than the other, but they're
> completely different security models and so there's no normative way for
> one to "outweigh the gains" from the other.
>
> > So should we optimize for the ability to validate in a particular
> > model (better security), or lower bandwidth in this case?
>
> It seems like you're claiming better security here without providing any
> evidence for it. The security model is "at least one of my peers is
> honest." In the case of outpoint+output filters, when a client receives
> advertisements for different filters from different peers, it:
>
> 1. Downloads the corresponding block
> 2. Locally generates the filter for that block
> 3. Kicks any peers that advertised a different filter than what it
> generated locally
>
> This ensures that as long as the client has at least one honest peer, it
> will see every transaction affecting its wallet. In the case of
> prevout+output filters, when a client receives advertisements for
> different filters from different peers, it:
>
> 1. Downloads the corresponding block and checks it for wallet
> transactions as if there had been a filter match
>
> This also ensures that as long as the client has at least one honest
> peer, it will see every transaction affecting its wallet. This is
> equivilant security.
>
> In the second case, it's possible for the client to eventually
> probabalistically determine which peer(s) are dishonest and kick them.
> The most space efficient of these protocols may disclose some bits of
> evidence for what output scripts the client is looking for, but a
> slightly less space-efficient protocol simply uses randomly-selected
> outputs saved from previous blocks to make the probabalistic
> determination (rather than the client's own outputs) and so I think
> should be quite private. Neither protocol seems significantly more
> complicated than keeping an associative array recording the number of
> false positive matches for each peer's filters.
>
> -Dave
>
[-- Attachment #2: Type: text/html, Size: 5877 bytes --]
next prev parent reply other threads:[~2018-06-12 23:51 UTC|newest]
Thread overview: 60+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-17 15:25 Matt Corallo
2018-05-17 15:43 ` Peter Todd
2018-05-17 15:46 ` Matt Corallo
2018-05-17 16:36 ` Gregory Maxwell
2018-05-17 16:59 ` Matt Corallo
2018-05-17 18:34 ` Gregory Maxwell
2018-05-17 20:19 ` Jim Posen
2018-05-17 20:45 ` Gregory Maxwell
2018-05-17 21:27 ` Jim Posen
2018-05-19 3:12 ` Olaoluwa Osuntokun
2018-05-21 8:35 ` Johan Torås Halseth
2018-05-22 1:16 ` Olaoluwa Osuntokun
2018-05-22 9:23 ` Johan Torås Halseth
2018-05-23 0:42 ` Jim Posen
2018-05-23 7:38 ` Jim Posen
2018-05-23 8:16 ` Johan Torås Halseth
2018-05-23 17:28 ` Gregory Maxwell
2018-05-24 1:04 ` Conner Fromknecht
2018-05-24 3:48 ` Jim Posen
2018-05-28 18:18 ` Tamas Blummer
2018-05-28 18:28 ` Tamas Blummer
2018-05-28 19:24 ` Gregory Maxwell
2018-05-29 2:42 ` Jim Posen
2018-05-29 3:24 ` Gregory Maxwell
2018-05-29 4:01 ` Olaoluwa Osuntokun
2018-05-31 14:27 ` Tamas Blummer
2018-06-01 2:52 ` Olaoluwa Osuntokun
2018-06-01 4:15 ` Gregory Maxwell
[not found] ` <CAAS2fgSyVi0d_ixp-auRPPzPfFeffN=hsWhWT5=EzDO3O+Ue1g@mail.gmail.com>
2018-06-02 0:01 ` Olaoluwa Osuntokun
2018-06-02 0:22 ` Gregory Maxwell
2018-06-02 2:02 ` Jim Posen
2018-06-02 12:41 ` David A. Harding
2018-06-02 22:02 ` Tamas Blummer
2018-06-03 0:28 ` Gregory Maxwell
2018-06-03 5:14 ` Tamas Blummer
2018-06-03 6:11 ` Pieter Wuille
2018-06-03 16:44 ` Tamas Blummer
2018-06-03 16:50 ` Tamas Blummer
2018-06-08 5:03 ` Olaoluwa Osuntokun
2018-06-08 16:14 ` Gregory Maxwell
2018-06-08 23:35 ` Olaoluwa Osuntokun
2018-06-09 10:34 ` David A. Harding
2018-06-12 23:51 ` Olaoluwa Osuntokun [this message]
2018-06-09 15:45 ` Gregory Maxwell
2018-06-12 23:58 ` Olaoluwa Osuntokun
2018-05-17 18:34 ` Gregory Maxwell
2018-05-18 8:46 ` Riccardo Casatta
2018-05-19 3:08 ` Olaoluwa Osuntokun
2018-05-19 2:57 ` Olaoluwa Osuntokun
2018-05-19 3:06 ` Pieter Wuille
2018-05-22 1:15 ` Olaoluwa Osuntokun
2018-05-18 6:28 ` Karl-Johan Alm
2018-06-04 8:42 ` Riccardo Casatta
2018-06-05 1:08 ` Jim Posen
2018-06-05 4:33 ` Karl-Johan Alm
2018-06-05 17:22 ` Jim Posen
2018-06-05 17:52 ` Gregory Maxwell
2018-06-06 1:12 ` Olaoluwa Osuntokun
2018-06-06 15:14 ` Riccardo Casatta
2018-05-19 2:51 ` Olaoluwa Osuntokun
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='CAO3Pvs_GYnFAS-pM=+OYCbJaEw8TOo-opnv5GVCBiDEurLvjYg@mail.gmail.com' \
--to=laolu32@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=dave@dtrt$(echo .)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