path: root/23/fb5b6d468d2061992d198805288ebf6149ebb8

Return-Path: <laolu32@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 98CF1D0A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 22 May 2018 01:17:07 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f65.google.com (mail-wm0-f65.google.com [74.125.82.65])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5D035F3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 22 May 2018 01:17:05 +0000 (UTC)
Received: by mail-wm0-f65.google.com with SMTP id x12-v6so14039581wmc.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 21 May 2018 18:17:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to
	:cc; bh=cifVcp8iVLNyTFBMIw4vG8BbfDyatTpibI4P5ELqLoQ=;
	b=twCxahCiZ1TGoU+n9kN0rezvYaAAfajjOPg3ucqrlDWX0sd/PBf/8H0Q1ch+7jumvS
	hA9RDNsDQdje1PKtCLzdSWiQEkjKCWwi/pU8Xipisun0MHhn2LO0rE05RUBPfq5qq4z9
	IVG3gJ6uBCm8ZIgnv91EgpEtFmA9w4iLX9uGe8UiGQlAVdoCLpREPC6RkbcBE/ME9swb
	BO9CNotxgLnTbqSdprz+4Z81oQUHV3pwX9mJBsfHpEYrlcwpqGMVTG9OTTJ+q1GHU0oo
	HUPdeaYy9iQu1qrtLlNWjwifMkOygkr41f+l8EL3QETJ+YxjlSGob71lYADDO0nUrctV
	BZKw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:references:in-reply-to:from:date
	:message-id:subject:to:cc;
	bh=cifVcp8iVLNyTFBMIw4vG8BbfDyatTpibI4P5ELqLoQ=;
	b=Gs/XxKOdU4udBbH/ehUwRoYkEOg84tjYkTe6h/AF94e8tmqgDGIWdDQFio7Zfjm8W3
	RKfH5Za9rWDe31YcvomG92aAeasUZzexZp+oP14dJJEBbATtOz0/GbcLzfkJFCE4tHJZ
	Ev45WWan29czZOwNQRhoRWe5sykqEYI0I+f9WdtwTXejjY6GewBrCwHIAohn0BnoHD5O
	xRBIFqKglaUruJ0EoQd8+VvAQYBfCaeZejhX4UKYwKfsK8sW2vHImHDgvLjcEUOnsvWe
	qnofSURbCHVm5/bA4FXBtYAZsHkeb9zTCgwyjybJKxLfa3hTFaiWKCUwqRzUDyU0pVk7
	LGjQ==
X-Gm-Message-State: ALKqPwcf+uMXMQLWL7qnji2v6Sx88LVcyzqKlIsXyg5yk9zgYR6IAkoM
	79kHXKXQ22syOhkHZBb8bfUwhJ0iKadZv6KxGnA=
X-Google-Smtp-Source: AB8JxZpCHIwC7lLQSeU3tPa6UejuTCL3rWi50Nsd4QsCElSDlQhssVixcaVALgZngA6qzjiB0iCw8Y1IDn+dLcp3VdE=
X-Received: by 2002:aa7:c60a:: with SMTP id
	h10-v6mr25969614edq.151.1526951824003; 
	Mon, 21 May 2018 18:17:04 -0700 (PDT)
MIME-Version: 1.0
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>
	<c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
In-Reply-To: <c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Mon, 21 May 2018 18:16:52 -0700
Message-ID: <CAO3Pvs_MA4TtgCCu1NgCBjK2bZRN+rKnGQJN6m4yTrViBXRiPA@mail.gmail.com>
To: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000000f1609056cc12d60"
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
	HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
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: Tue, 22 May 2018 01:17:07 -0000

--0000000000000f1609056cc12d60
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

> What if instead of trying to decide up front which subset of elements wil=
l
> 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?

This is already the case. The current "track" is to add new service bits
(while we're in the uncommitted phase) to introduce new fitler types. Light
clients can then filter out nodes before even connecting to them.

-- Laolu

On Mon, May 21, 2018 at 1:35 AM Johan Tor=C3=A5s Halseth <johanth@gmail.com=
>
wrote:

> 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 wil=
l
> be most useful to include in the filters, and the size tradeoff, we let t=
he
> 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+outp=
oint)
> 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 ligh=
t
> client, but there are also some less obvious ones. We wouldn=E2=80=99t ha=
ve 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 default=
s
> 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 exp=
onential
> 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 par=
t
> 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
>
> _______________________________________________ bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

--0000000000000f1609056cc12d60
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>&gt; What if instead of trying to decide up front whi=
ch subset of elements will</div><div>&gt; be most useful to include in the =
filters, and the size tradeoff, we let the</div><div>&gt; full-node decide =
which subsets of elements it serves filters for?</div><div><br></div><div>T=
his is already the case. The current &quot;track&quot; is to add new servic=
e bits</div><div>(while we&#39;re in the uncommitted phase) to introduce ne=
w fitler types. Light</div><div>clients can then filter out nodes before ev=
en connecting to them.</div><div><br></div><div>-- Laolu</div><div><br></di=
v><div class=3D"gmail_quote"><div dir=3D"ltr">On Mon, May 21, 2018 at 1:35 =
AM Johan Tor=C3=A5s Halseth &lt;<a href=3D"mailto:johanth@gmail.com">johant=
h@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><img cla=
ss=3D"m_-8850601494583743300cloudmagic-smart-beacon" src=3D"https://tr.clou=
dmagic.com/h/v6/emailtag/tag/2.0/1526891728/b33cfe15f93c4412b9d3504fec67269=
7/2/b53988f48cda345112c1586d420d31cf/076962fa5a1f7737d8541e3d8681273b/903bb=
174d9946b90a95b4da487a91d69/newton.gif" style=3D"border:0;width:10px;height=
:10px" width=3D"10" height=3D"10" align=3D"right"><div dir=3D"auto"><span>H=
i all,</span><div><span><br></span></div><div><span>Most light wallets will=
 want to download the minimum amount of data required to operate, which mea=
ns they would ideally download the smallest possible filters containing the=
 subset of elements they need.=C2=A0</span></div><div><span><br></span></di=
v><div><span>What if instead of trying to decide up front which subset of e=
lements will be most useful to include in the filters, and the size tradeof=
f, 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 o=
nly), 011 (</span>script+outpoint) etc. A light client could then choose to=
 download the minimal filter type covering its needs.=C2=A0</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 filte=
r types grow organically, with full-node implementations coming with sane d=
efaults for served filter types (maybe even all possible types as long as t=
he number of elements is small), letting their operator add/remove types at=
 will.</div><div><br></div><div>The main disadvantage of this as I see it, =
is that there=E2=80=99s an exponential blowup in the number of possible fil=
ter 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 op=
erators just choose to serve the subsets corresponding to what now is calle=
d =E2=80=9Cregular=E2=80=9D + =E2=80=9Cextended=E2=80=9D filters anyway, re=
quiring 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 use=
ful in making the decision on what should be part of filters to eventually =
commit to in blocks.</div></div><div dir=3D"auto"><div><br></div><div>- Joh=
an</div></div><div dir=3D"auto"><div><div id=3D"m_-8850601494583743300cm_re=
plymail_content_wrap"><div class=3D"m_-8850601494583743300cm_replymail_cont=
ent_1526889092_wrapper">On Sat, May 19, 2018 at 5:12, Olaoluwa Osuntokun vi=
a bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br><=
/div></div></div></div><div dir=3D"auto"><div><div id=3D"m_-885060149458374=
3300cm_replymail_content_wrap"><div class=3D"m_-8850601494583743300cm_reply=
mail_content_1526889092_wrapper"><div id=3D"m_-8850601494583743300cm_replym=
ail_content_1526889092" style=3D"overflow:visible"><blockquote style=3D"mar=
gin:0;border-left:#d6d6d6 1px solid;padding-left:10px"><div dir=3D"ltr"><di=
v class=3D"gmail_quote"><div dir=3D"ltr">On Thu, May 17, 2018 at 2:44 PM Ji=
m 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"><=
div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #cc=
c solid;padding-left:1ex">Monitoring inputs by scriptPubkey vs input-txid a=
lso 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&#39;re watching block<b=
r>
 N+1 for based on the txids that paid you in N you can&#39;t filter them<br=
>
in parallel.<br></blockquote><div><br></div></div></div></div><div dir=3D"l=
tr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div>Yes, I&#39;l=
l grant that this is a benefit of your suggestion.</div></div></div></div><=
/blockquote><div><br></div><div>Yeah parallel filtering would be pretty nic=
e. We&#39;ve implemented a serial filtering for btcwallet [1] for the use-c=
ase of rescanning after a seed phrase import. Parallel filtering would help=
 here, but also we don&#39;t yet take advantage of batch querying for the f=
ilters 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 simp=
lifies the code, and we can leverage identical logic for btcd (which has RP=
Cs 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" =
target=3D"_blank">https://github.com/Roasbeef/btcwallet/blob/master/chain/n=
eutrino.go#L180</a> </div></div></div>
<br></blockquote></div></div></div></div></div><div dir=3D"auto"><div><div =
id=3D"m_-8850601494583743300cm_replymail_content_wrap"><div class=3D"m_-885=
0601494583743300cm_replymail_content_1526889092_wrapper"><div id=3D"m_-8850=
601494583743300cm_replymail_content_1526889092" style=3D"overflow:visible">=
<blockquote style=3D"margin:0;border-left:#d6d6d6 1px solid;padding-left:10=
px">_______________________________________________
bitcoin-dev mailing list
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
target=3D"_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoi=
n-dev</a>
</blockquote></div></div></div></div></div></blockquote></div></div>

--0000000000000f1609056cc12d60--