Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 4860D102C for ; Tue, 12 Jun 2018 23:51:44 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f66.google.com (mail-wm0-f66.google.com [74.125.82.66]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 303D0EC for ; Tue, 12 Jun 2018 23:51:43 +0000 (UTC) Received: by mail-wm0-f66.google.com with SMTP id j15-v6so1912219wme.0 for ; Tue, 12 Jun 2018 16:51:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=44fI/zvMLUhS49iDkUFw/KBAMZRdXg8iTFjidfOlPVA=; b=Ai3FIfrfEFBU0nOiJ1LRA+0OD5kksBk3NKPW1jyWho366JfFQuj/QQh+MTRioDShNn lK+KHXdMNzmo5TCdPvvIUqvjqvV082HUVQGp5LLWZshrUdaPZTj5B6Lx1BDd7ML7ESf8 zrVBveNtOgPz03tJQNyxfq2kPTOCKw36d07BT1A3GsUX820eHNe6r/7i7E6PYqiDH/Bs oCWrx84iRFcNZtuWMY1ljWl3gr1DT6iKR50JFfRdAWcmTaEumkVWAwdjX73Kbz4vCNga wLkY0iwlhQ0Ls8BQDvZmRV0HpFewxS56O7RtHt87+n+4qo9rpWytPfQB4cXGazW+JVHE kwNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=44fI/zvMLUhS49iDkUFw/KBAMZRdXg8iTFjidfOlPVA=; b=Ibcn8de2jWNjQ9TXCQpZu8eT1LJV7TJ9DuN58umdTF65Zo7Vbk1DUwKuQQ7SIWkKrP B3PoRSMNzST1F4l8ndy/CIbP7hEqFBWCri+PUWJAdNk6ewDBI+gJWrC/wF7xo/54fHLd 29esR03Bqh0K3mgG7MuJRhVHKCRMh/5djMWEJEwDkg1IgbsDyDBmQX/trbZmXYoZAT6G MDpqkM9HwydhMiHVlUSNIt4Efv5iuSpqY8pHDUlaOxcHYplkv++rDTVClmmS97GRinx5 4iraRH+iR3yc/E1yWRYAy13RGBHmtXlpZHD7uNLbxioPDYPRxtkNOZ5uzaKgHW1bWsW9 JN4w== X-Gm-Message-State: APt69E0VCfMdV2F2RYMXUBUBtukMF/IrAM3zxXq+jsqedvIg3y3We1vJ /1htD1e5oQk+9Je2ubvOpQzd0DBT3x0qe1RYFb2Vxg== X-Google-Smtp-Source: ADUXVKIE7u+5Z9kwQhCLwDxI0SfP1/TJGj7GHz+JHHhJ64Hgm8KFUuYsNTVoOkp2VJYYFt8wHEL7rrbHaYFRo0AfvvA= X-Received: by 2002:a50:aba5:: with SMTP id u34-v6mr1519339edc.252.1528847501643; Tue, 12 Jun 2018 16:51:41 -0700 (PDT) MIME-Version: 1.0 References: <20180602124157.744x7j4u7dqtaa43@email> <343A3542-3103-42E9-95B7-640DFE958FFA@gmail.com> <37BECD1A-7515-4081-85AC-871B9FB57772@gmail.com> <20180609103445.alxrchjbbbxklkzt@email> In-Reply-To: <20180609103445.alxrchjbbbxklkzt@email> From: Olaoluwa Osuntokun Date: Tue, 12 Jun 2018 16:51:29 -0700 Message-ID: To: "David A. Harding" Content-Type: multipart/alternative; boundary="000000000000405741056e7a8cde" X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size 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: Tue, 12 Jun 2018 23:51:44 -0000 --000000000000405741056e7a8cde Content-Type: text/plain; charset="UTF-8" > 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 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 > --000000000000405741056e7a8cde Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> Doesn't the current BIP157 protocol have eac= h filter commit to the filter
> for the previous block?
<= div>
Yep!

> If that's the cas= e, 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 pre= ceeding blocks in
> the SPV trust model?

<= div>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 allow= s you to only validate a portion of the filter and requires other
added heuristics.=C2=A0

> In the case of prevo= ut+output filters, when a client receives advertisements
> for= different filters from different peers, it:

Alter= natively, they can decompress the filter and at least verify that
proper _output scripts_ have been included. Maybe this is "good enoug= h"
until its committed. If a command is added to fetch all t= he prev outs along
w/ a block (which would let you do another thi= ngs like verify fees), then
they'd be able to fully validate = the filter as well.

-- Laolu

<= br>
On Sat, Jun 9, 2018 at 3:35 = AM David A. Harding <dave@dtrt.org&= gt; wrote:
On Fri, Jun 08, 2018 at = 04:35:29PM -0700, Olaoluwa Osuntokun via bitcoin-dev wrote:
>=C2=A0 =C2=A02. Since the coinbase transaction is the first in a block,= it has the
>=C2=A0 =C2=A0 =C2=A0 longest merkle proof path. As a result, it may be = several hundred bytes
>=C2=A0 =C2=A0 =C2=A0 (and grows with future capacity increases) to pres= ent a proof to the
>=C2=A0 =C2=A0 =C2=A0 client.

I'm not sure why commitment proof size is a significant issue.=C2=A0 Do= esn't
the current BIP157 protocol have each filter commit to the filter for
the previous block?=C2=A0 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<= br> > allow.

I think those are unrelated points.=C2=A0 The gain from using a more
efficient filter is saved bytes.=C2=A0 The gain from using block commitment= s
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.=C2=A0 Yes, one uses more bytes than the other, but they're<= br> completely different security models and so there's no normative way fo= r
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 an= y
evidence for it.=C2=A0 The security model is "at least one of my peers= is
honest."=C2=A0 In the case of outpoint+output filters, when a client r= eceives
advertisements for different filters from different peers, it:

=C2=A0 =C2=A0 1. Downloads the corresponding block
=C2=A0 =C2=A0 2. Locally generates the filter for that block
=C2=A0 =C2=A0 3. Kicks any peers that advertised a different filter than wh= at it
=C2=A0 =C2=A0 =C2=A0 =C2=A0generated locally

This ensures that as long as the client has at least one honest peer, it will see every transaction affecting its wallet.=C2=A0 In the case of
prevout+output filters, when a client receives advertisements for
different filters from different peers, it:

=C2=A0 =C2=A0 1. Downloads the corresponding block and checks it for wallet=
=C2=A0 =C2=A0 =C2=A0 =C2=A0transactions 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.=C2=A0 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.=C2=A0 Neither protocol seems significantly more complicated than keeping an associative array recording the number of
false positive matches for each peer's filters.

-Dave
--000000000000405741056e7a8cde--