path: root/fb/1145b3c176a7b3d33465b321f8eb84463057de

Return-Path: <johanth@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 3D5ECCC2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 21 May 2018 08:35:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qt0-f193.google.com (mail-qt0-f193.google.com
	[209.85.216.193])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F01C034E
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 21 May 2018 08:35:48 +0000 (UTC)
Received: by mail-qt0-f193.google.com with SMTP id m16-v6so17941051qtg.13
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 21 May 2018 01:35:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=from:to:cc:in-reply-to:references:subject:message-id:date
	:mime-version; bh=L+hkmMzDaN5Sfu8aBsmkrw5Xeg8rQFCtqHikS7ZyMnU=;
	b=qyGDlHANLxFUgoXUVBj4Tu7yCG1gyuiAxvqTg3rIBc4Bxtzqc/LAauIUQPtYN6Yv0N
	igNufAJzQ8R5LtdCxb39EmsMQhy7OhPiQ/vaHzn5lWA+jAIVENUanSzz9+tqulGJF4hl
	tJE4sy0TUwJtBxGWcGaW+6KejoJp0mKB+dra9Cs52yMYSWhhiQcHdC/zYJDzC00sCeoi
	n1OUMC5wfaHYxonrY7ePEGylXU5cgczUOOrotWMf+X3jpWxwNMvtZaI3O0mkTs1va2Wl
	ilohLUTW9/RLZjdZ9C8swh6ZtiUBuT3gD5o7Nv5fBxC6pT2K3sO7/3v8IG5yZhU/CDHo
	jNzA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:from:to:cc:in-reply-to:references:subject
	:message-id:date:mime-version;
	bh=L+hkmMzDaN5Sfu8aBsmkrw5Xeg8rQFCtqHikS7ZyMnU=;
	b=kjZzYVbqG9NZiq1mRa7KGYkEvcZiXdYJg/+EryuRpdxFXZvlVzqaFGKtUDhrhaRjw0
	XdcsKyfQhE/Hrn5+Iz+SSOxXiG4A3J29tiAYW1bdhO1KFzGWQl7lZJxPbBBNgpZ+AEcP
	eFaOI66G4aRt1iHM09w2apaW7NDUhvJAJEqELAz+xBQ6IOMW32KR10f9X0fxeUOm0Grn
	ejYeWD0RzRikUjbipIdmrbuZIJ0yX6xLnqgWMm4J60GyaK9tzs2RP3DugveqBUQG5mRW
	fW4EfoqtePfmCf6NLlXOEnfuYZXKph8x/rKaBSW7uLrNCWMem209G6mx7nIPbZvDdDNV
	3p0w==
X-Gm-Message-State: ALKqPwc1ebPSxZ1OXWgPbgU5C2qgWRFO9aTSYG7AiTB/DPHZDdpvJG8K
	qymUwRxx0ZRnR7xjvJ5F0ij4cj/A
X-Google-Smtp-Source: AB8JxZo5EMYphFlx7K1FOTv1O7WwvzwuRhMmXt7nzpcqAh2QwYZk6pem1GupV15BGhJzDWGZe4sDOA==
X-Received: by 2002:ac8:1766:: with SMTP id
	u35-v6mr17690424qtk.209.1526891747609; 
	Mon, 21 May 2018 01:35:47 -0700 (PDT)
Received: from [127.0.0.1] (ec2-54-210-254-132.compute-1.amazonaws.com.
	[54.210.254.132]) by smtp.gmail.com with ESMTPSA id
	b79-v6sm10440515qka.57.2018.05.21.01.35.46
	for <bitcoin-dev@lists.linuxfoundation.org>
	(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
	Mon, 21 May 2018 01:35:47 -0700 (PDT)
Content-Type: multipart/alternative;
	boundary="----sinikael-?=_1-15268917468760.3363917884416878"
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
To: Olaoluwa Osuntokun <laolu32@gmail.com>
In-Reply-To: <CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com>
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
	<CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com>
	<22d375c7-a032-8691-98dc-0e6ee87a4b08@mattcorallo.com>
	<CAAS2fgR3QRHeHEjjOS1ckEkL-h7=Na56G12hYW9Bmy9WEMduvg@mail.gmail.com>
	<CADZtCShLmH_k-UssNWahUNHgHvWQQ1y638LwaOfnJEipwjbiYg@mail.gmail.com>
	<CAAS2fgQLCN_cuZ-3QPjCLfYOtHfEk=SenTn5=y9LfGzJxLPR3Q@mail.gmail.com>
	<CADZtCSjYr6VMBVQ=rx44SgRWcFSXhVXUZJB=rHMh4X78Z2eY1A@mail.gmail.com>
	<CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com>
Message-Id: <c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
Date: Mon, 21 May 2018 10:35:28 +0200
X-Cm-Message-Id: 1526891729122305aed4c4dc8db302de96b91f53fea313b95b0284d11de711223906206
X-Cm-Draft-Id: WyJhIiwyLCJkcmFmdF9pZCIsIjE1MjY4OTE3MjgyMzkiLCJ2IiwxXQ==
X-Cm-Tracking-Code: 2.0/1526891728/b33cfe15f93c4412b9d3504fec672697/2/b53988f48cda345112c1586d420d31cf/076962fa5a1f7737d8541e3d8681273b/0f75828a92f1cf543e26ab700e98c693
X-Mailer: Newton
MIME-Version: 1.0
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	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: Mon, 21 May 2018 13:08:31 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <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: Mon, 21 May 2018 08:35:50 -0000

------sinikael-?=_1-15268917468760.3363917884416878
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Hi all,
Most light wallets will want to download the minimum amount of data=
 required to operate, which means they would ideally download the smallest =
possible filters containing the subset of elements they need.
What if instead of trying to decide up front which subset of elements will =
be most useful to include in the filters, and the size tradeoff, we let the=
 full-node decide which subsets of elements it serves filters for?

For instance, a full node would advertise that it could serve filters for =
the subsets 110 (txid+script+outpoint), 100 (txid only), 011 ( =
script+outpoint) etc. A light client could then choose to download the =
minimal filter type covering its needs.
The obvious benefit of this would =
be minimal bandwidth usage for the light client, but there are also some =
less obvious ones. We wouldn=E2=80=99t have to decide up front what each =
filter type should contain, only the possible elements a filter can contain=
 (more can be added later without breaking existing clients). This, I think=
, would let the most served filter types grow organically, with full-node =
implementations coming with sane defaults for served filter types (maybe =
even all possible types as long as the number of elements is small), =
letting their operator add/remove types at will.
The main disadvantage of =
this as I see it, is that there=E2=80=99s an exponential blowup in the =
number of possible filter types in the number of element types. However, =
this would let us start out small with only the elements we need, and in =
the worst case the node operators just choose to serve the subsets =
corresponding to what now is called =E2=80=9Cregular=E2=80=9D + =
=E2=80=9Cextended=E2=80=9D filters anyway, requiring no more resources.
This would also give us some data on what is the most widely used filter =
types, which could be useful in making the decision on what should be part =
of filters to eventually commit to in blocks.
- Johan On Sat, May 19, 2018 =
at 5:12, Olaoluwa Osuntokun via bitcoin-dev <bitcoin-dev@lists.=
linuxfoundation.org> wrote:
On Thu, May 17, 2018 at 2:44 PM Jim Posen via =
bitcoin-dev <bitcoin- Monitoring inputs by scriptPubkey vs input-txid also =
has a massive
advantage for parallel filtering: You can usually known your =
pubkeys
well in advance, but if you have to change what you're watching =
block
N+1 for based on the txids that paid you in N you can't filter them
in parallel.

Yes, I'll grant that this is a benefit of your suggestion.
Yeah parallel filtering would be pretty nice. We've implemented a serial =
filtering for btcwallet [1] for the use-case of rescanning after a seed =
phrase import. Parallel filtering would help here, but also we don't yet =
take advantage of batch querying for the filters themselves. This would =
speed up the scanning by quite a bit.
I really like the filtering model =
though, it really simplifies the code, and we can leverage identical logic =
for btcd (which has RPCs to fetch the filters) as well.
[1]: https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.=
go#L180 [https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.=
go#L180]
_______________________________________________ bitcoin-dev =
mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.=
linuxfoundation.org/mailman/listinfo/bitcoin-dev
------sinikael-?=_1-15268917468760.3363917884416878
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<img class=3D"cloudmagic-smart-beacon" src=3D"https://tr.cloudmagic.=
com/h/v6/emailtag/tag/2.0/1526891728/b33cfe15f93c4412b9d3504fec672697/2/b53=
988f48cda345112c1586d420d31cf/076962fa5a1f7737d8541e3d8681273b/0f75828a92f1=
cf543e26ab700e98c693/newton.gif" style=3D"border:0; width:10px; =
height:10px;" width=3D"10" height=3D"10" align=3D"right"><div =
dir=3D"auto"><span>Hi all,</span><div><span><br></span></div><div><span>Mos=
t light wallets will want to download the minimum amount of data required =
to operate, which means they would ideally download the smallest possible =
filters containing the subset of elements they need.=
&nbsp;</span></div><div><span><br></span></div><div><span>What if instead =
of trying to decide up front which subset of elements will be most useful =
to include in the filters, and the size tradeoff, we let the full-node =
decide which subsets of elements it serves filters for?=
<br></span><span><br>For instance, a full node would advertise that it =
could serve filters for the subsets 110 (txid+script+outpoint), 100 (txid =
only), 011 (</span>script+outpoint) etc. A light client could then choose =
to download the minimal filter type covering its needs.=
&nbsp;</div><div><br></div><div>The obvious benefit of this would be =
minimal bandwidth usage for the light client, but there are also some less =
obvious ones. We wouldn=E2=80=99t have to decide up front what each filter =
type should contain, only the possible elements a filter can contain (more =
can be added later without breaking existing clients). This, I think, would=
 let the most served filter types grow organically, with full-node =
implementations coming with sane defaults for served filter types (maybe =
even all possible types as long as the number of elements is small), =
letting their operator add/remove types at will.</div><div><br></div><div>T=
he main disadvantage of this as I see it, is that there=E2=80=99s an =
exponential blowup in the number of possible filter types in the number of =
element types. However, this would let us start out small with only the =
elements we need, and in the worst case the node operators just choose to =
serve the subsets corresponding to what now is called =
=E2=80=9Cregular=E2=80=9D + =E2=80=9Cextended=E2=80=9D filters anyway, =
requiring no more resources.</div><div><br></div><div>This would also give =
us some data on what is the most widely used filter types, which could be =
useful in making the decision on what should be part of filters to =
eventually commit to in blocks.</div><div><br></div><div>- =
Johan</div><div><div id=3D"cm_replymail_content_wrap"><div =
class=3D"cm_replymail_content_1526889092_wrapper">On Sat, May 19, 2018 at =
5:12, Olaoluwa Osuntokun via bitcoin-dev &lt;bitcoin-dev@lists.=
linuxfoundation.org&gt; wrote:<br><div id=3D"cm_replymail_content_152688909=
2" style=3D"overflow: visible;"><blockquote style=3D"margin:0;border-left: =
#D6D6D6 1px solid;padding-left: 10px;"><div dir=3D"ltr"><div =
class=3D"gmail_quote"><div dir=3D"ltr">On Thu, May 17, 2018 at 2:44 PM Jim =
Posen via bitcoin-dev &lt;bitcoin- </div><blockquote class=3D"gmail_quote" =
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><di=
v dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><blockq=
uote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc =
solid;padding-left:1ex">Monitoring inputs by scriptPubkey vs input-txid =
also has a massive<br>
advantage for parallel filtering:  You can usually =
known your pubkeys<br>
well in advance, but if you have to change what =
you're watching block<br>
 N+1 for based on the txids that paid you in N =
you can't filter them<br>
in parallel.<br></blockquote><div><br></div></div=
></div></div><div dir=3D"ltr"><div class=3D"gmail_extra"><div =
class=3D"gmail_quote"><div>Yes, I'll grant that this is a benefit of your =
suggestion.</div></div></div></div></blockquote><div><br></div><div>Yeah =
parallel filtering would be pretty nice. We've implemented a serial =
filtering for btcwallet [1] for the use-case of rescanning after a seed =
phrase import. Parallel filtering would help here, but also we don't yet =
take advantage of batch querying for the filters themselves. This would =
speed up the scanning by quite a bit. </div><div><br></div><div>I really =
like the filtering model though, it really simplifies the code, and we can =
leverage identical logic for btcd (which has RPCs to fetch the filters) as =
well. </div><div><br></div><div>[1]: <a href=3D"https://github.=
com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180">https://github.=
com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180</a> =
</div></div></div>
<br>_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
</blockquote></div></div></div></div></div>
------sinikael-?=_1-15268917468760.3363917884416878--