Date: Sat, 2 Jun 2018 08:41:57 -0400
From: "David A. Harding" <dave@dtrt.org>
To: Jim Posen <jim.posen@gmail.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20180602124157.744x7j4u7dqtaa43@email>
References: <7E4FA664-BBAF-421F-8C37-D7CE3AA5310A@gmail.com>
	<F87D7069-0FDC-4572-B02B-398A2A455935@gmail.com>
	<CAAS2fgT716PiP0ucoASxryM9y+s9H2z06Z0ToaP1xT3BozAtNw@mail.gmail.com>
	<CADZtCSguto2z6Z9CykymxnCokqo1G=sW0Ov0ht+KcD+KMnYyow@mail.gmail.com>
	<CAO3Pvs-YDzfRqmyJ85wTH0ciccjCvkm5stGyP_tVGGna=PMv3A@mail.gmail.com>
	<CAO3Pvs9p5COiS_7Jbj1r2iAKTEdXUcnVTRzL27c3=CeuB9WDTQ@mail.gmail.com>
	<CAAS2fgSyVi0d_ixp-auRPPzPfFeffN=hsWhWT5=EzDO3O+Ue1g@mail.gmail.com>
	<CAO3Pvs_0qCZbRCfL8EJw6gzWjZeXWcJrtg27g_SJ7+PkYTHg6A@mail.gmail.com>
	<CAAS2fgTs+aKyiL8Kg_AZk=Mdh6896MEg=KHa6ANAZO7unsGEsg@mail.gmail.com>
	<CADZtCShyYbgKk2zsKzQniqDw--XKfYWTk3Hk3o50V=MgT6zeuQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="fzwwefg5shnzqbip"
Content-Disposition: inline
In-Reply-To: <CADZtCShyYbgKk2zsKzQniqDw--XKfYWTk3Hk3o50V=MgT6zeuQ@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Precedence: list


--fzwwefg5shnzqbip
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

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"

--fzwwefg5shnzqbip
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCAAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAlsSkJUACgkQ2dtBqWwi
adOfTw//XgeBJJ1v9sFcbfOn6KvcA3SrnRuyljoJwqcwt5VM7LTkuMC+pISuPXdc
feF8GiW2G7uY3kPwkDSniDTqZTgcT4iG0mg81WEMEweAQ9+3z31mOzqzJiCG5T8E
y+YdM2jDl9DD06qkReM1jJyBqN2eEtiwijVaakEfU7UguvyDPsWlXnYzelr6KBSc
7DzSmpn6GAVBBNnetu3C1BBghkcEm8EIj2UmK2hJxA1bJ7CdZXiYsF8kk76Vt2l6
sQ9jSF+mtOS4Ws8lkVKohh5nv7s55STpnJmcU/042BWr2ywctizSYmeIeDHJtdH+
PFbRYwE9wZZ6aTSjQlf8bdcq6DtJRlgQdYKo3gZ4brzNHiPZXId1qCKHFg0qZggc
AoJU9Eyy7oLSRYWxqT90kuLRyltmEtkrZgsVBwtpK9M126E0jtCRR/dnaGARhY2x
zZFIemNO6V84+Byi2S2tZhkzTDmlwvsYL+YVxw/crOUTlDWxV72m5nsodxd8adcs
Vt3H9MEAZulhGMj57q8XgzL0mJ3L2jeG9WGkDDZFkGkpxXkXc0hW02W16reKT+cY
YepTNiVqHaz3Fgr7cY5bC2Iuypmv5qO8mm0z5Fxe5/Mi8z0feF+aGtfhsutO3EsM
IKgcFrZr8ONQhP/iJvTLbhzEgtN4PaDYetf0maHiqAVJNG7eC7A=
=hptV
-----END PGP SIGNATURE-----

--fzwwefg5shnzqbip--