public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: "David A. Harding" <dave@dtrt.org>
To: Jim Posen <jim.posen@gmail.com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Date: Sat, 2 Jun 2018 08:41:57 -0400	[thread overview]
Message-ID: <20180602124157.744x7j4u7dqtaa43@email> (raw)
In-Reply-To: <CADZtCShyYbgKk2zsKzQniqDw--XKfYWTk3Hk3o50V=MgT6zeuQ@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 1780 bytes --]

On Fri, Jun 01, 2018 at 07:02:38PM -0700, Jim Posen via bitcoin-dev wrote:
> Without the ability to verify filter validity, a client would have to stop
> syncing altogether in the presence of just one malicious peer, which is
> unacceptable.

I'm confused about why this would be the case.  If Alice's node
generates filters accurately and Mallory's node generates filters
inaccurately, and they both send their filters to Bob, won't Bob be able
to download any blocks either filter indicates are relevant to his
wallet?

If Bob downloads a block that contains one of his transactions based on
Alice's filter indicating a possible match at a time when Mallory's
filter said there was no match, then this false negative is perfect
evidence of deceit on Mallory's part[1] and Bob can ban her.

If Bob downloads a block that doesn't contain any of his transactions
based on Mallory's filter indicating a match at a time when Alice's
filter said there was no match, then this false positive can be recorded
and Bob can eventually ban Mallory should the false positive rate
exceeds some threshold.

Until Mallory is eventually banned, it seems to me that the worst she
can do is waste Bob's bandwidth and that of any nodes serving him
accurate information, such as Alice's filters and the blocks Bob
is misled into downloading to check for matches.  The amount of
attacker:defender asymetry in the bandwidth wasted increases if
Mallory's filters become less accurate, but this also increases her
false positive rate and reduces the number of filters that need to be
seen before Bob bans her, so it seems to me (possibly naively) that this
is not a significant DoS vector.

-Dave

[1] Per BIP158 saying, "a Golomb-coded set (GCS), which matches all
items in the set with probability 1"

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

  reply	other threads:[~2018-06-02 13:16 UTC|newest]

Thread overview: 60+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-17 15:25 [bitcoin-dev] BIP 158 Flexibility and Filter Size 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 [this message]
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
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=20180602124157.744x7j4u7dqtaa43@email \
    --to=dave@dtrt.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=jim.posen@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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