Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Tamas Blummer <tamas.blummer@gmail.com>
In-Reply-To: <CAO3Pvs_gvYy99Bch=7RwVszM_0PFTKUyqDVok=xfm4OOcqwaaQ@mail.gmail.com>
Date: Tue, 5 Feb 2019 21:10:09 +0100
Content-Transfer-Encoding: quoted-printable
Message-Id: <6D36035C-A675-4845-9292-3BC16CD19B41@gmail.com>
References: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
	<CADZtCSgKu1LvjePNPT=0C0UYQvb47Ca0YN+B_AfgVNTpcOno4w@mail.gmail.com>
	<CDAFC2F7-A0AD-460B-B5B1-A717F7EC700E@gmail.com>
	<CAO3Pvs_gvYy99Bch=7RwVszM_0PFTKUyqDVok=xfm4OOcqwaaQ@mail.gmail.com>
To: Olaoluwa Osuntokun <laolu32@gmail.com>
Cc: Jim Posen <jimpo@coinbase.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Interrogating a BIP157 server,
 BIP158 change proposal
Precedence: list

Hi Laolu,

The only advantage I see in the current design choice is filter size, =
but even that is less
impressive in recent history and going forward, as address re-use is =
much less frequent nowadays
than it was Bitcoin=E2=80=99s early days.

I calculated total filter sizes since block 500,000:

input script + output script (current BIP): 1.09 GB=20
spent outpoint + output script: 1.26 GB

Both filters are equally useful for a wallet to discover relevant =
transactions, but the current design
choice seriously limits, practically disables a light client, to prove =
that the filter is correct.=20

Clear advantages of moving to spent outpoint + output script filter:

1. Filter correctness can be proven by downloading the block in question =
only.
2. Calculation of the filter on server side does not need UTXO.
3. Spent outpoints in the filter enable light clients to do further =
probabilistic checks and even more if committed.

The current design choice offers lower security than now attainable. =
This certainly improves with=20
a commitment, but that is not even on the roadmap yet, or is it?

Should a filter be committed that contains spent outpoints, then such =
filter would be even more useful:
A client could decide on availability of spent coins of a transaction =
without maintaining the UTXO set, by=20
checking the filters if the coin was spent after its origin proven in an =
SPV manner, evtl. eliminating false positives=20
with a block download. This would be slower than having UTXO but require =
only immutable store, no unwinds and=20
only download of a few blocks.

Since Bitcoin Core is not yet serving any filters, I do not think this =
discussion is too late.

Tamas Blummer


> On Feb 5, 2019, at 02:42, Olaoluwa Osuntokun <laolu32@gmail.com> =
wrote:
>=20
> Hi Tamas,=20
>=20
> This is how the filter worked before the switch over to optimize for a
> filter containing the minimal items needed for a regular wallet to =
function.
> When this was proposed, I had already implemented the entire proposal =
from
> wallet to full-node. At that point, we all more or less decided that =
the
> space savings (along with intra-block compression) were worthwhile, we
> weren't cutting off any anticipated application level use cases (at =
that
> point we had already comprehensively integrated both filters into =
lnd), and
> that once committed the security loss would disappear.
>=20
> I think it's too late into the current deployment of the BIPs to =
change
> things around yet again. Instead, the BIP already has measures in =
place for
> adding _new_ filter types in the future. This along with a few other =
filter
> types may be worthwhile additions as new filter types.
>=20
> -- Laolu
>=20
> On Mon, Feb 4, 2019 at 12:59 PM Tamas Blummer =
<tamas.blummer@gmail.com> wrote:
> I participated in that discussion in 2018, but have not had the =
insight gathered by now though writing both client and server =
implementation of BIP157/158
>=20
> Pieter Wuille considered the design choice I am now suggesting here as =
alternative (a) in: =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016064.h=
tml
> In his evaluation he recognized that a filter having spent output and =
output scripts would allow decision on filter correctness by knowing the =
block only.
> He did not evaluate the usefulness in the context of checkpoints, =
which I think are an important shortcut here.
>=20
> Yes, a filter that is collecting input and output scripts is shorter =
if script re-use is frequent, but I showed back in 2018 in the same =
thread that this saving is not that significant in recent history as =
address reuse is no longer that frequent.
>=20
> A filter on spent outpoint is just as useful for wallets as is one on =
spent script, since they naturally scan the blockchain forward and =
thereby learn about their coins by the output script before they need to =
check spends of those outpoints.
>=20
> It seems to me that implementing an interrogation by evtl. downloading =
blocks at checkpoints is much simpler than following multiple possible =
filter paths.
>=20
> A spent outpoint filter allows us to decide on coin availability based =
on immutable store, without updated and eventually rolled back UTXO =
store. The availability could be decided by following the filter path to =
current tip to genesis and
> check is the outpoint was spent earlier. False positives can be sorted =
out with a block download. Murmel implements this if running in server =
mode, where blocks are already there.
>=20
> Therefore I ask for a BIP change based on better insight gained =
through implementation.
>=20
> Tamas Blummer
>=20
>> On Feb 4, 2019, at 21:18, Jim Posen <jim.posen@gmail.com> wrote:
>>=20
>> Please see the thread "BIP 158 Flexibility and Filter Size" from 2018 =
regarding the decision to remove outpoints from the filter [1].
>>=20
>> Thanks for bringing this up though, because more discussion is needed =
on the client protocol given that clients cannot reliably determine the =
integrity of a block filter in a bandwidth-efficient manner (due to the =
inclusion of input scripts).
>>=20
>> I see three possibilities:
>> 1) Introduce a new P2P message to retrieve all prev-outputs for a =
given block (essentially the undo data in Core), and verify the scripts =
against the block by executing them. While this permits some forms of =
input script malleability (and thus cannot discriminate between all =
valid and invalid filters), it restricts what an attacker can do. This =
was proposed by Laolu AFAIK, and I believe this is how btcd is =
proceeding.
>> 2) Clients track multiple possible filter header chains and =
essentially consider the union of their matches. So if any filter =
received for a particular block header matches, the client downloads the =
block. The client can ban a peer if they 1) ever return a filter =
omitting some data that is observed in the downloaded block, 2) =
repeatedly serve filters that trigger false positive block downloads =
where such a number of false positives is statistically unlikely, or 3) =
repeatedly serves filters that are significantly larger than the =
expected size (essentially padding the actual filters with garbage to =
waste bandwidth). I have not done the analysis yet, but we should be =
able to come up with some fairly simple banning heuristics using =
Chernoff bounds. The main downside is that the client logic to track =
multiple possible filter chains and filters per block is more complex =
and bandwidth increases if connected to a malicious server. I first =
heard about this idea from David Harding.
>> 3) Rush straight to committing the filters into the chain (via =
witness reserved value or coinbase OP_RETURN) and give up on the =
pre-softfork BIP 157 P2P mode.
>>=20
>> I'm in favor of option #2 despite the downsides since it requires the =
smallest number of changes and is supported by the BIP 157 P2P protocol =
as currently written. (Though the recommended client protocol in the BIP =
needs to be updated to account for this). Another benefit of it is that =
it removes some synchronicity assumptions where a peer with the correct =
filters keeps timing out and is assumed to be dishonest, while the =
dishonest peer is assumed to be OK because it is responsive.
>>=20
>> If anyone has other ideas, I'd love to hear them.
>>=20
>> -jimpo
>>=20
>> [1] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.h=
tml
>>=20
>>=20
>>=20
>> On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>> TLDR: a change to BIP158 would allow decision on which filter chain =
is correct at lower bandwith use
>>=20
>> Assume there is a BIP157 client that learned a filter header chain =
earlier and is now offered an alternate reality by a newly connected =
BIP157 server.
>>=20
>> The client notices the alternate reality by routinely asking for =
filter chain checkpoints after connecting to a new BIP157 server. A =
divergence at a checkpoint means that the server disagrees the client's =
history at or before the first diverging checkpoint. The client would =
then request the filter headers between the last matching and first =
divergent checkpoint, and quickly figure which block=E2=80=99s filter is =
the first that does not match previous assumption, and request that =
filter from the server.
>>=20
>> The client downloads the corresponding block, checks that its header =
fits the PoW secured best header chain, re-calculates merkle root of its =
transaction list to know that it is complete and queries the filter to =
see if every output script of every transaction is contained in there, =
if not the server is lying, the case is closed, the server disconnected.
>>=20
>> Having all output scripts in the filter does not however guarantee =
that the filter is correct since it might omit input scripts. Inputs =
scripts are not part of the downloaded block, but are in some blocks =
before that. Checking those are out of reach for lightweight client with =
tools given by the current BIP.
>>=20
>> A remedy here would be an other filter chain on created and spent =
outpoints as is implemented currently by Murmel. The outpoint filter =
chain must offer a match for every spent output of the block with the =
divergent filter, otherwise the interrogated server is lying since a PoW =
secured block can not spend coins out of nowhere. Doing this check would =
already force the client to download the outpoint filter history up-to =
the point of divergence. Then the client would have to download and PoW =
check every block that shows a match in outpoints until it figures that =
one of the spent outputs has a script that was not in the server=E2=80=99s=
 filter, in which case the server is lying. If everything checks out =
then the previous assumption on filter history was incorrect and should =
be replaced by the history offered by the interrogated server.=20
>>=20
>> As you see the interrogation works with this added filter but is =
highly ineffective. A really light client should not be forced to =
download lots of blocks just to uncover a lying filter server. This =
would actually be an easy DoS on light BIP157 clients.
>>=20
>> A better solution is a change to BIP158 such that the only filter =
contains created scripts and spent outpoints. It appears to me that this =
would serve well both wallets and interrogation of filter servers well:
>>=20
>> Wallets would recognize payments to their addresses by the filter as =
output scripts are included, spends from the wallet would be recognized =
as a wallet already knows outpoints of its previously received coins, so =
it can query the filters for them.
>>=20
>> Interrogation of a filter server also simplifies, since the filter of =
the block can be checked entirely against the contents of the same =
block. The decision on filter correctness does not require more bandwith =
then download of a block at the mismatching checkpoint. The client could =
only be forced at max. to download 1/1000 th of the blockchain in =
addition to the filter header history.
>>=20
>> Therefore I suggest to change BIP158 to have a base filter, defined =
as:
>>=20
>> A basic filter MUST contain exactly the following items for each =
transaction in a block:
>>         =E2=80=A2 Spent outpoints
>>         =E2=80=A2 The scriptPubKey of each output, aside from all =
OP_RETURN output scripts.
>>=20
>> Tamas Blummer
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20