path: root/44/4fd76917556e9ad3af054de5fb47f669ee2be5

Return-Path: <tamas.blummer@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 14B3EA510
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue,  5 Feb 2019 20:10:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm1-f53.google.com (mail-wm1-f53.google.com
	[209.85.128.53])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D7AB9894
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue,  5 Feb 2019 20:10:18 +0000 (UTC)
Received: by mail-wm1-f53.google.com with SMTP id m22so277802wml.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 05 Feb 2019 12:10:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:subject:from:in-reply-to:date:cc
	:content-transfer-encoding:message-id:references:to;
	bh=ZTxhvnVQLeNoYIcxM2MxjLg5+hQb7RAX/ptighJ+cyA=;
	b=fDpptE5Zy2gxExaiANWtT3tjMm41TWjCBtqJt6rwoAtLgBmquMXsRzvFWgM3rsMHAo
	Fa3YjDaPS0K/6Zg1kuq4UgKUMWR6PueJHFd7fGaAB+6XY5Q8SK7S8riN9tfxu29uCMNZ
	dYERNmpjT38rDqu6+U05rAuOaXmCmkvH5EeBbMdgmu3VNMX6ef1vxj3HDuPSglBE7dZo
	diqHiQHJKO1GGEQ/YIaeNDe5yA1I8vlL64+mc9erk87FzBYkmURl4jy7iC/YZyJVHLzE
	iHjFMYEmGeNRj+aidLkBzl4M1UzannwoMRIlus8n5DNLMfLP5PLgDr02zdD/aaYnAzws
	/DNg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
	:content-transfer-encoding:message-id:references:to;
	bh=ZTxhvnVQLeNoYIcxM2MxjLg5+hQb7RAX/ptighJ+cyA=;
	b=qyB4T74b9MCHTmvQmZhi/ngF6ZUkRE9w4mwHU40ciIwViGSQ0U8t3v8vdy8tf2MUaV
	WqoOEsmd4y0amPNLvLn16JDD70d2xRzkI1WLtOUafnwRxBFXIWZ+PgNu0tArd0GVwyJA
	pWynzPbXLAcyzAkSgxfZfqYOFAk0r8ty9IrXIP9Ztelqm9+vQp7UpumhQ7TeJrvAXumu
	4PINnRZGOlUQZunF3pUGr9OnFztQGVITsMZYm4Fnq1/6DLMh+HaENBZxs3EMI5fS08SV
	+FX0FoKIHuLxrliqwsfie1ASSXGMi32Ynw9V9c3KfEGfO/yNTVik7Cuy7LkpqTfmiPiM
	yYZw==
X-Gm-Message-State: AHQUAuYRenJC8jL2dw2lpH1TgFQ6mSHX2fY+KIXt1Y1tWV/3RPR4533F
	pZQ8fVdtEbgoADvigeTa5qc=
X-Google-Smtp-Source: AHgI3IajL/QrE90ZZM9fPZMP9NAkQ4vox6VMPPHd/y5szU2kadpJvlxC1Tz7YMyq6oLKJ+9j98EYkA==
X-Received: by 2002:a7b:c84d:: with SMTP id c13mr322736wml.112.1549397417248; 
	Tue, 05 Feb 2019 12:10:17 -0800 (PST)
Received: from p200300dd672d1a0179a56fc96aad7f17.dip0.t-ipconnect.de
	([2003:dd:672d:1a01:79a5:6fc9:6aad:7f17])
	by smtp.gmail.com with ESMTPSA id z5sm482088wmi.15.2019.02.05.12.10.15
	(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
	Tue, 05 Feb 2019 12:10:16 -0800 (PST)
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>
X-Mailer: Apple Mail (2.3273)
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 06 Feb 2019 15:48:05 +0000
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 05 Feb 2019 20:10:20 -0000

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