path: root/fc/68bcd136b573095b0e7f1019fef94b0131b848

Return-Path: <riccardo.casatta@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 5495C86A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  6 Jun 2018 15:14:31 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f42.google.com (mail-it0-f42.google.com
	[209.85.214.42])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5015175A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  6 Jun 2018 15:14:30 +0000 (UTC)
Received: by mail-it0-f42.google.com with SMTP id 76-v6so8613605itx.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 06 Jun 2018 08:14:30 -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=bHOkZbN2eSEedICd+Vh0nAhmZxLc4+oyxGY9imO8an0=;
	b=YGciQQh8P4UTF6DjaZ3ga5HB2fDEVxANx+mAMy5amH1S5K1ddl6FBo2BiK3nZdrRZv
	S/Fhf/RlD45Bq3IpiwVn/ivMs1inLV/Wo6Aw9LGggcy8Q5o1m+OVxpgN01JVJ1FPgEDz
	yDPljiBGu4lddx1o4L80Rhs7r6ykb+s+4TFuHYIRW+3Sc9b2jSHRgvXe+Avm3ttXT4iD
	vaXZO6lrfMX0LXiEKTAe8k4SLdhYpfiZfGefDvf+JEahQWLmipU3Ktn65In7ubN5rSdi
	42S6bevNjtw7a7y5RmKPR7MWrEO6NRpng+lebvv8ZrFZ4yvc96VmfPijIa2jn9dtTW5g
	VM3g==
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=bHOkZbN2eSEedICd+Vh0nAhmZxLc4+oyxGY9imO8an0=;
	b=MR3FVsdLNSpA6towY3AwC0aThTdi6+M9OrEhA55UgUsu586yGhIxIxJk10Pw0UIeFJ
	MSaRL/PGvPSyYVgehjFn6ujrX0p5ad6Z8Kq6mOO+ahdJE3qdSLluTt3M00qFg3Wfhjjl
	fC1BPkVbwL3t/AP1ofh5NcAqYVd/vYd5nTjjkJ3XjIhUAkl4AYK0BiivZ98HMyyy5rR9
	TYSrhHoBT27t/0+l+kKbs5/mDGNFPKYHn9Fe+Te1lI+1SNzI3h+V0g6rpzn6Hd0EZu5X
	kV9V7M9q3wHM6Ko/EwXgmaCpTfAT4lieXDnXOZ+3O9qS253jDZtutnNRPq8qlqutv4kB
	bibA==
X-Gm-Message-State: APt69E3EcwgnBNTs5BpPTjEw23FVzoh9aGFA/pTcvbN2PNRYeSnHcOjK
	5fNv5ozp55E6eKyq+yNsJZrE7F1ShYU7K6lI3QVQXg==
X-Google-Smtp-Source: ADUXVKIRiOqc7UxFvLRPiWxmN215JaPer0/mVx3b3VOC4ZqnBFFIWA4f4/73PiIoR2xa+o8JdPpw900lZ/Z6amTvDVc=
X-Received: by 2002:a24:9f06:: with SMTP id
	c6-v6mr2731752ite.133.1528298069507; 
	Wed, 06 Jun 2018 08:14:29 -0700 (PDT)
MIME-Version: 1.0
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
	<CALJw2w7+VUYtMtdTexW6iE3mc0DsS9DME_ynP8skg_+-bv_tPA@mail.gmail.com>
	<CADabwBDG2_2syU0AnjbEfqTL=5ERRQkL6NOyVN7gAyJTAaf7UA@mail.gmail.com>
	<CAO3Pvs9tXte=_1UBPvLmrci+PD9QVbiKHu4R_6igpAEuQLJ3Wg@mail.gmail.com>
In-Reply-To: <CAO3Pvs9tXte=_1UBPvLmrci+PD9QVbiKHu4R_6igpAEuQLJ3Wg@mail.gmail.com>
From: Riccardo Casatta <riccardo.casatta@gmail.com>
Date: Wed, 6 Jun 2018 17:14:17 +0200
Message-ID: <CADabwBAvq8jG42ctFPGix6brKen+dZ+mBEHaOykuSTkKWW8HsQ@mail.gmail.com>
To: laolu32@gmail.com
Content-Type: multipart/alternative; boundary="0000000000008b4602056dfa9faf"
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: Wed, 06 Jun 2018 15:26:20 +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: Wed, 06 Jun 2018 15:14:31 -0000

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

Sorry if I continue on the subject even if
=E2=80=8Bcustom filter types are considered in BIP 157/158
.
I am doing it
 because
=E2=80=8B:
1)=E2=80=8B
with a fixed target FP=3D2^-20  (or 1/784931)
=E2=80=8B and the multi layer filtering maybe it's reasonable to consider l=
ess than
~20 bits for the golomb encoding of the per-block filter (one day committed
in the blockchain)
2) based on the answer received, privacy leak if downloading a subset of
filters doesn't look a concern
3)
As far as I know, anyone is considering to use a map instead of a filter
for the upper layers of the filter=E2=80=8B.

Simplistic example:
Suppose to have a 2 blocks blockchain, every block contains N items for the
filter:
1) In the current discussed filter we have 2 filters of 20N bits
2) In a two layer solution, we have 1 map of (10+1)2N bits and 2 filters of
10N bits
The additional bit in the map discriminate if the match is in the first or
in the second block.
Supposing to have 1 match in the two blocks, the filter size downloaded in
the first case is always 40N bits, while the expected downloaded size in
the second case is 22N+2^-10*10N+10N ~=3D 32N with the same FP because
independence.
This obviously isn't a full analysis of the methodology, the expected
downloaded size in the second case could go from the best case 22N bits to
the worst case of 42N bits...

@Gregory
> I don't know what portion of coins created are spent in the same 144 bloc=
k
window...

About 50%
source code <https://github.com/RCasatta/coincount>

From block 393216 to 458752  (still waiting for results on all the
blockchain)
Total outputs 264185587
size: 2 spent: 11791058 ratio:0.04463172322871649
size: 4 spent: 29846090 ratio:0.11297395266305728
size: 16 spent: 72543182 ratio:0.2745917475051355
size: 64 spent: 113168726 ratio:0.4283682818775424
size: 144 spent: 134294070 ratio:0.508332311103709
size: 256 spent: 148824781 ratio:0.5633342177747191
size: 1024 spent: 179345566 ratio:0.6788620379960395
size: 4096 spent: 205755628 ratio:0.7788298761355213
size: 16384 spent: 224448158 ratio:0.849585174379706

Another point to consider is that if we don't want the full transaction
history of our wallet but only the UTXO, the upper layer map could contain
only the item which are not already spent in the considered window. As we
can see from the previous result if the window is 16384 ~85% of the
elements are already spent suggesting a very high time locality. (apart
144, I choose power of 2 windows so there are an integer number of bits in
the map)

It's possible we need ~20 bits anyway for the per-block filters because
there are always connected wallets which one synced, always download the
last filter, anyway the upper layer map looks very promising for longer
sync.

Il giorno mer 6 giu 2018 alle ore 03:13 Olaoluwa Osuntokun <
laolu32@gmail.com> ha scritto:

> It isn't being discussed atm (but was discussed 1 year ago when the BIP
> draft was originally published), as we're in the process of removing item=
s
> or filters that aren't absolutely necessary. We're now at the point where
> there're no longer any items we can remove w/o making the filters less
> generally useful which signals a stopping point so we can begin widesprea=
d
> deployment.
>
> In terms of a future extension, BIP 158 already defines custom filter
> types,
> and BIP 157 allows filters to be fetched in batch based on the block heig=
ht
> and numerical range. The latter feature can later be modified to return a
> single composite filter rather than several individual filters.
>
> -- Laolu
>
>
> On Mon, Jun 4, 2018 at 7:28 AM Riccardo Casatta via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> I was wondering why this multi-layer multi-block filter proposal isn't
>> getting any comment,
>> is it because not asking all filters is leaking information?
>>
>> Thanks
>>
>> Il giorno ven 18 mag 2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev =
<
>> bitcoin-dev@lists.linuxfoundation.org> ha scritto:
>>
>>> On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev
>>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>>> > In general, I'm concerned about the size of the filters making existi=
ng
>>> > SPV clients less willing to adopt BIP 158 instead of the existing blo=
om
>>> > filter garbage and would like to see a further exploration of ways to
>>> > split out filters to make them less bandwidth intensive. Some further
>>> > ideas we should probably play with before finalizing moving forward i=
s
>>> > providing filters for certain script templates, eg being able to only
>>> > get outputs that are segwit version X or other similar ideas.
>>>
>>> There is also the idea of multi-block filters. The idea is that light
>>> clients would download a pair of filters for blocks X..X+255 and
>>> X+256..X+511, check if they have any matches and then grab pairs for
>>> any that matched, e.g. X..X+127 & X+128..X+255 if left matched, and
>>> iterate down until it ran out of hits-in-a-row or it got down to
>>> single-block level.
>>>
>>> This has an added benefit where you can accept a slightly higher false
>>> positive rate for bigger ranges, because the probability of a specific
>>> entry having a false positive in each filter is (empirically speaking)
>>> independent. I.e. with a FP probability of 1% in the 256 range block
>>> and a FP probability of 0.1% in the 128 range block would mean the
>>> probability is actually 0.001%.
>>>
>>> Wrote about this here: https://bc-2.jp/bfd-profile.pdf (but the filter
>>> type is different in my experiments)
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>>
>>
>> --
>> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

--=20
Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>

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

<div dir=3D"ltr">Sorry if I continue on the subject even if <div class=3D"g=
mail_default" style=3D"font-size:small;display:inline">=E2=80=8Bcustom filt=
er types are considered in BIP 157/158</div><div class=3D"gmail_default" st=
yle=3D"font-size:small;display:inline">.</div><div><div class=3D"gmail_defa=
ult" style=3D"font-size:small;display:inline">I am doing it</div>=C2=A0beca=
use<div class=3D"gmail_default" style=3D"font-size:small;display:inline">=
=E2=80=8B:</div></div><div><div class=3D"gmail_default" style=3D"font-size:=
small;display:inline">1)=E2=80=8B</div> with a fixed target FP=3D2^-20 =C2=
=A0(or 1/784931)<div class=3D"gmail_default" style=3D"font-size:small;displ=
ay:inline">=E2=80=8B and the multi layer filtering maybe it&#39;s reasonabl=
e to consider less than ~20 bits for the golomb encoding of the per-block f=
ilter (one day committed in the blockchain)=C2=A0</div></div><div><div clas=
s=3D"gmail_default" style=3D"font-size:small;display:inline">2) based on th=
e answer received, privacy leak if downloading a subset of filters doesn&#3=
9;t look a concern</div></div><div><div class=3D"gmail_default" style=3D"fo=
nt-size:small;display:inline">3)=C2=A0</div><span style=3D"font-size:small"=
>As far as I know, anyone is considering to use a map instead of a filter f=
or the upper layers of the filter=E2=80=8B.</span></div><div><div class=3D"=
gmail_default" style=3D"font-size:small"><br></div><div class=3D"gmail_defa=
ult"><font size=3D"2">Simplistic example:</font></div><div class=3D"gmail_d=
efault"><font size=3D"2">Suppose to have a 2 blocks blockchain, every block=
 contains N items for the filter:</font><br></div><div class=3D"gmail_defau=
lt" style=3D"font-size:small">1) In the current discussed filter we have 2 =
filters of 20N bits</div><div class=3D"gmail_default" style=3D"font-size:sm=
all">2) In a two <span style=3D"color:rgb(34,34,34);font-family:sans-serif;=
font-size:small;font-style:normal;font-variant-ligatures:normal;font-varian=
t-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-i=
ndent:0px;text-transform:none;white-space:normal;word-spacing:0px;backgroun=
d-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-colo=
r:initial;float:none;display:inline">layer</span> solution, we have 1 map o=
f (10+1)2N bits and 2 filters of 10N bits</div><div class=3D"gmail_default"=
 style=3D"font-size:small">The additional bit in the map discriminate if th=
e match is in the first or in the second block.</div></div><div class=3D"gm=
ail_default" style=3D"font-size:small">Supposing to have 1 match in the two=
 blocks, the filter size downloaded in the first case is always 40N bits, w=
hile the expected downloaded size in the second case is 22N+2^-10*10N+10N ~=
=3D 32N with the same FP because independence.</div><div class=3D"gmail_def=
ault" style=3D"font-size:small">This obviously isn&#39;t a full analysis of=
 the methodology, the expected downloaded size in the second case could go =
from the best case 22N bits to the worst case of 42N bits...</div><div clas=
s=3D"gmail_default" style=3D"font-size:small"></div><div><br></div><div><di=
v class=3D"gmail_default" style=3D"font-size:small">@Gregory<br></div></div=
><div class=3D"gmail_default" style=3D"font-size:small"><span style=3D"colo=
r:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;fon=
t-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-=
spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-s=
pace:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decorat=
ion-style:initial;text-decoration-color:initial;float:none;display:inline">=
&gt; I don&#39;t know=C2=A0</span><span style=3D"color:rgb(34,34,34);font-f=
amily:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:no=
rmal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-al=
ign:start;text-indent:0px;text-transform:none;white-space:normal;word-spaci=
ng:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text=
-decoration-color:initial;float:none;display:inline">what portion of coins =
created are spent in the same 144 block</span><br style=3D"color:rgb(34,34,=
34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-li=
gatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:norm=
al;text-align:start;text-indent:0px;text-transform:none;white-space:normal;=
word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:in=
itial;text-decoration-color:initial"><span style=3D"color:rgb(34,34,34);fon=
t-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures=
:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text=
-align:start;text-indent:0px;text-transform:none;white-space:normal;word-sp=
acing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;t=
ext-decoration-color:initial;float:none;display:inline">window...</span><br=
></div><div class=3D"gmail_default" style=3D"font-size:small"><span style=
=3D"color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:no=
rmal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400=
;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none=
;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text=
-decoration-style:initial;text-decoration-color:initial;float:none;display:=
inline"><br></span></div><div class=3D"gmail_default" style=3D"font-size:sm=
all"><span style=3D"color:rgb(34,34,34);font-family:sans-serif;font-size:13=
px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal=
;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;tex=
t-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(2=
55,255,255);text-decoration-style:initial;text-decoration-color:initial;flo=
at:none;display:inline">About 50%</span></div><div class=3D"gmail_default" =
style=3D"font-size:small"><span style=3D"color:rgb(34,34,34);font-family:sa=
ns-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;fon=
t-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:star=
t;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;b=
ackground-color:rgb(255,255,255);text-decoration-style:initial;text-decorat=
ion-color:initial;float:none;display:inline"><span style=3D"color:rgb(34,34=
,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-l=
igatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:nor=
mal;text-align:start;text-indent:0px;text-transform:none;white-space:normal=
;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:i=
nitial;text-decoration-color:initial;float:none;display:inline"><a href=3D"=
https://github.com/RCasatta/coincount" target=3D"_blank">source code</a></s=
pan><br></span></div><div class=3D"gmail_default" style=3D"font-size:small"=
><span style=3D"color:rgb(34,34,34);font-family:sans-serif;font-size:13px;f=
ont-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;fon=
t-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-tr=
ansform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,2=
55,255);text-decoration-style:initial;text-decoration-color:initial;float:n=
one;display:inline"><span style=3D"color:rgb(34,34,34);font-family:sans-ser=
if;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-vari=
ant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text=
-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;backgro=
und-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-co=
lor:initial;float:none;display:inline"><br></span></span></div><div class=
=3D"gmail_default" style=3D"font-size:small"><span style=3D"color:rgb(34,34=
,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-l=
igatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:nor=
mal;text-align:start;text-indent:0px;text-transform:none;white-space:normal=
;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:i=
nitial;text-decoration-color:initial;float:none;display:inline">From block =
393216 to 458752=C2=A0 (still waiting for results on all the blockchain)</s=
pan></div><div class=3D"gmail_default" style=3D"font-size:small"><span styl=
e=3D"color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:n=
ormal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:40=
0;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:non=
e;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);tex=
t-decoration-style:initial;text-decoration-color:initial;float:none;display=
:inline"><div class=3D"gmail_default" style=3D"font-size:small">Total outpu=
ts 264185587</div><div class=3D"gmail_default" style=3D"font-size:small">si=
ze: 2 spent: 11791058 ratio:0.04463172322871649</div><div class=3D"gmail_de=
fault" style=3D"font-size:small">size: 4 spent: 29846090 ratio:0.1129739526=
6305728</div><div class=3D"gmail_default" style=3D"font-size:small">size: 1=
6 spent: 72543182 ratio:0.2745917475051355</div><div class=3D"gmail_default=
" style=3D"font-size:small">size: 64 spent: 113168726 ratio:0.4283682818775=
424</div><div class=3D"gmail_default" style=3D"font-size:small">size: 144 s=
pent: 134294070 ratio:0.508332311103709</div><div class=3D"gmail_default" s=
tyle=3D"font-size:small">size: 256 spent: 148824781 ratio:0.563334217774719=
1</div><div class=3D"gmail_default" style=3D"font-size:small">size: 1024 sp=
ent: 179345566 ratio:0.6788620379960395</div><div class=3D"gmail_default" s=
tyle=3D"font-size:small">size: 4096 spent: 205755628 ratio:0.77882987613552=
13</div><div class=3D"gmail_default" style=3D"font-size:small">size: 16384 =
spent: 224448158 ratio:0.849585174379706</div><div class=3D"gmail_default" =
style=3D"font-size:small"><br></div><div class=3D"gmail_default" style=3D"f=
ont-size:small">Another point to consider is that if we don&#39;t want the =
full transaction history of our wallet but only the UTXO, the upper layer m=
ap could contain only the item which are not already spent in the considere=
d <span style=3D"color:rgb(34,34,34);font-family:sans-serif;font-size:small=
;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;f=
ont-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-=
transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255=
,255,255);text-decoration-style:initial;text-decoration-color:initial;float=
:none;display:inline">window</span>. As we can see from the previous result=
 if the window is 16384 ~85% of the elements are already spent suggesting a=
 very high time locality. (apart 144, I choose power of 2 windows so there =
are an integer number of bits in the map)</div><div class=3D"gmail_default"=
 style=3D"font-size:small"><br></div><div class=3D"gmail_default" style=3D"=
font-size:small">It&#39;s possible we need ~20 bits anyway for the per-bloc=
k filters because there are always connected wallets which one synced, alwa=
ys download the last filter, anyway the upper layer map looks very promisin=
g for longer sync.</div></span></div><div><div class=3D"gmail_default" styl=
e=3D"font-size:small;display:inline"></div></div><br><div class=3D"gmail_qu=
ote"><div dir=3D"ltr">Il giorno mer 6 giu 2018 alle ore 03:13 Olaoluwa Osun=
tokun &lt;<a href=3D"mailto:laolu32@gmail.com" target=3D"_blank">laolu32@gm=
ail.com</a>&gt; ha scritto:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div di=
r=3D"ltr"><div>It isn&#39;t being discussed atm (but was discussed 1 year a=
go when the BIP</div><div>draft was originally published), as we&#39;re in =
the process of removing items</div><div>or filters that aren&#39;t absolute=
ly necessary. We&#39;re now at the point where</div><div>there&#39;re no lo=
nger any items we can remove w/o making the filters less</div><div>generall=
y useful which signals a stopping point so we can begin widespread</div><di=
v>deployment.=C2=A0=C2=A0</div><div><br></div><div>In terms of a future ext=
ension, BIP 158 already defines custom filter types,</div><div>and BIP 157 =
allows filters to be fetched in batch based on the block height</div><div>a=
nd numerical range. The latter feature can later be modified to return a</d=
iv><div>single composite filter rather than several individual filters.</di=
v><div><br></div><div>-- Laolu</div><div><br></div><br><div class=3D"gmail_=
quote"><div dir=3D"ltr">On Mon, Jun 4, 2018 at 7:28 AM Riccardo Casatta via=
 bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" t=
arget=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></=
div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div style=3D"font-size=
:small">I was wondering why this multi-layer multi-block filter proposal is=
n&#39;t getting any comment,</div><div style=3D"font-size:small">is it beca=
use not asking all filters is leaking information?</div><div style=3D"font-=
size:small"><br></div><div style=3D"font-size:small">Thanks</div></div><br>=
<div class=3D"gmail_quote"><div dir=3D"ltr">Il giorno ven 18 mag 2018 alle =
ore 08:29 Karl-Johan Alm via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@=
lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundat=
ion.org</a>&gt; ha scritto:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Fri,=
 May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev<br>
&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt; In general, I&#39;m concerned about the size of the filters making exi=
sting<br>
&gt; SPV clients less willing to adopt BIP 158 instead of the existing bloo=
m<br>
&gt; filter garbage and would like to see a further exploration of ways to<=
br>
&gt; split out filters to make them less bandwidth intensive. Some further<=
br>
&gt; ideas we should probably play with before finalizing moving forward is=
<br>
&gt; providing filters for certain script templates, eg being able to only<=
br>
&gt; get outputs that are segwit version X or other similar ideas.<br>
<br>
There is also the idea of multi-block filters. The idea is that light<br>
clients would download a pair of filters for blocks X..X+255 and<br>
X+256..X+511, check if they have any matches and then grab pairs for<br>
any that matched, e.g. X..X+127 &amp; X+128..X+255 if left matched, and<br>
iterate down until it ran out of hits-in-a-row or it got down to<br>
single-block level.<br>
<br>
This has an added benefit where you can accept a slightly higher false<br>
positive rate for bigger ranges, because the probability of a specific<br>
entry having a false positive in each filter is (empirically speaking)<br>
independent. I.e. with a FP probability of 1% in the 256 range block<br>
and a FP probability of 0.1% in the 128 range block would mean the<br>
probability is actually 0.001%.<br>
<br>
Wrote about this here: <a href=3D"https://bc-2.jp/bfd-profile.pdf" rel=3D"n=
oreferrer" target=3D"_blank">https://bc-2.jp/bfd-profile.pdf</a> (but the f=
ilter<br>
type is different in my experiments)<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
 class=3D"m_-6972841931057250559m_6246143091615729883m_-8470615826258348836=
m_1798458504075039611m_-7236474083222447233gmail_signature" data-smartmail=
=3D"gmail_signature"><div dir=3D"ltr">Riccardo Casatta - <a href=3D"https:/=
/twitter.com/RCasatta" target=3D"_blank">@RCasatta</a></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
 class=3D"m_-6972841931057250559m_6246143091615729883m_-8470615826258348836=
gmail_signature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr">Riccar=
do Casatta - <a href=3D"https://twitter.com/RCasatta" target=3D"_blank">@RC=
asatta</a></div></div></div>

--0000000000008b4602056dfa9faf--