MIME-Version: 1.0
References: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com>
	<1ACE761E-A91B-45C7-A0EB-BD66FE3AD7BD@gmail.com>
In-Reply-To: <1ACE761E-A91B-45C7-A0EB-BD66FE3AD7BD@gmail.com>
From: nopara73 <adam.ficsor73@gmail.com>
Date: Mon, 23 Sep 2019 07:20:31 +0200
Message-ID: <CAEPKjgfO+YcmNcSp8=3bRJpxWvePdRC6Nne0soDdYAnLVVw5HA@mail.gmail.com>
To: Tamas Blummer via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000cecf1a05933194be"
Cc: "admin@bitaps.com" <admin@bitaps.com>
Subject: Re: [bitcoin-dev] Block Batch Filters for Light Clients
Precedence: list

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

Please also take a look at "Applying Private Information Retrieval to
Lightweight Bitcoin Clients" Scaling Bitcoin talk. The academics were not
aware of BIP158 at all, yet came up with a similar scheme independently.

On Sat, Sep 21, 2019 at 11:40 PM Tamas Blummer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Aleksey,
>
> Yes, BIP158 uses the block hash to seed the hash function, which makes
> distinct block filters non-aggregatable
> for common values. Aggregate fiters on ranges of blocks would have to use
> some other seed and then
> achive significant savings using the same design.
>
> I think that the most likely use of filters is to decide if a newly
> announced block should be downloaded and
> not scanning over the entire chain, where aggregate filters would help. I
> also suspect that whole chain
> scans would be better served with plain sequential reads in map-reduce
> style.
>
> Typical clients do not care of filters for blocks before the birth date o=
f
> their wallet=E2=80=99s keys, so they skip over the
> majority of history which is a bigger saving than any aggregate filter.
>
> I wish we get a filter committed as commitment would unlock more utility
> than any marginal savings through
> more elaborate design.
>
> Tamas Blummer
>
> On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Hello list,
>
> Here is a link for a draft of a BIP for  compact probabilistic block
> filters alternative of BIP 158
>
>
> https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qS=
xv80ik/edit?usp=3Dsharing
>
> Summary:
>
>  - BIP 158  false positive rate is low, we can achieve lower bandwidth
> with higher false positive rate filter while sync blockchain
>
>  - BIP 158 not do not support filter batching by design of used parameter=
s
> for siphash and Golomb coding optimal parameters
>
>  - Alternative compression with delta coding and splitting data to 2 bit
> string  sequences. First for data without prefixes, second one for
> information about  bit length written to first sequence.
>    Second sequence have a lot of duplicates,  compressed with 2 round of
> Huffman algorithm. (Effectivity about 98% vs Golomb with optimal paramete=
rs)
>
>  - Block filters batching reduce filter size significantly
>
> - Separation of filters by address type allows lite client not to downloa=
d
> redundant information without compromising privacy.
>
> - Lite client filters download strategy: get biggest filter (smallest
> blocks/size rate) for blocks range, in case positive test  -> get medium
> filters to reduce blocks range ->  get block filters for affected range -=
>
> download affected blocks over TOR
>
> Implementation (python):
> https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.p=
y#L172
>
> Exactly information from mainnet  about size for separated filters by
> address types and batch size will be added within few days.
>
> Thanks for any feedback.
>       Aleksey Karpov
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>


--=20
Best,
=C3=81d=C3=A1m

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

<div dir=3D"ltr">Please also take a look at &quot;Applying Private Informat=
ion Retrieval to Lightweight Bitcoin Clients&quot; Scaling Bitcoin talk. Th=
e academics were not aware of BIP158 at all, yet came up with a similar sch=
eme independently.</div><br><div class=3D"gmail_quote"><div dir=3D"ltr" cla=
ss=3D"gmail_attr">On Sat, Sep 21, 2019 at 11:40 PM Tamas Blummer via bitcoi=
n-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-=
dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"=
gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(20=
4,204,204);padding-left:1ex"><div style=3D"overflow-wrap: break-word;">Hi A=
leksey,<div><br></div><div>Yes, BIP158 uses the block hash to seed the hash=
 function, which makes distinct block filters non-aggregatable=C2=A0</div><=
div>for common values. Aggregate fiters on ranges of blocks would have to u=
se some other seed and then=C2=A0</div><div>achive significant savings usin=
g the same design.</div><div><br></div><div>I think that the most likely us=
e of filters is to decide if a newly announced block should be downloaded a=
nd=C2=A0</div><div>not scanning over the entire chain, where aggregate filt=
ers would help. I also suspect that whole chain=C2=A0</div><div>scans would=
 be better served with plain sequential reads in map-reduce style.</div><di=
v><br></div><div>Typical clients do not care of filters for blocks before t=
he birth date of their wallet=E2=80=99s keys, so they skip over the=C2=A0</=
div><div>majority of history which is a bigger saving than any aggregate fi=
lter.</div><div><br></div><div>I wish we get a filter committed as commitme=
nt would unlock more utility than any marginal savings through</div><div>mo=
re elaborate design.</div><div><br></div><div>Tamas Blummer</div><div><br><=
/div><div><div><blockquote type=3D"cite"><div>On Sep 19, 2019, at 19:20, ad=
min--- via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
ion.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wr=
ote:</div><br class=3D"gmail-m_8987343113371291965Apple-interchange-newline=
"><div><div style=3D"overflow-wrap: break-word;">Hello list,=C2=A0<div><br>=
</div><span>Here is a link for a draft of a BIP for =C2=A0compact probabili=
stic block filters alternative of BIP 158</span><div><br></div><div><a href=
=3D"https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0=
qSxv80ik/edit?usp=3Dsharing" target=3D"_blank">https://docs.google.com/docu=
ment/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=3Dsharing</a><=
/div><div><br></div><div>Summary:</div><div><br></div><div>=C2=A0- BIP 158 =
=C2=A0false positive rate is low, we can achieve lower bandwidth with highe=
r false positive rate filter while sync blockchain</div><div><br></div><div=
>=C2=A0- BIP 158 not do not support filter batching by design of used param=
eters for siphash and Golomb coding optimal parameters</div><div><br></div>=
<div>=C2=A0- Alternative compression with delta coding and splitting data t=
o 2 bit string =C2=A0sequences. First for data without prefixes, second one=
 for information about =C2=A0bit length written to first sequence.</div><di=
v>=C2=A0 =C2=A0Second sequence have a lot of duplicates, =C2=A0compressed w=
ith 2 round of Huffman algorithm. (Effectivity about 98% vs Golomb with opt=
imal parameters)</div><div><br></div><div>=C2=A0- Block filters batching re=
duce filter size significantly</div><div><br></div><div>- Separation of fil=
ters by address type allows lite client not to download redundant informati=
on without compromising privacy.</div><div><br></div><div>- Lite client fil=
ters download strategy: get biggest filter (smallest blocks/size rate) for =
blocks range, in case positive test =C2=A0-&gt; get medium filters to reduc=
e blocks range -&gt; =C2=A0get block filters for affected range -&gt; downl=
oad affected blocks over TOR=C2=A0</div><div><br></div><div>Implementation =
(python):=C2=A0<a href=3D"https://github.com/bitaps-com/pybtc/blob/bugfix/p=
ybtc/functions/filters.py#L172" target=3D"_blank">https://github.com/bitaps=
-com/pybtc/blob/bugfix/pybtc/functions/filters.py#L172</a></div><div><br></=
div><div>Exactly information from mainnet =C2=A0about size for separated fi=
lters by address types and batch size will be added within few days.</div><=
div><br></div><div>Thanks for any feedback.</div><div>=C2=A0 =C2=A0 =C2=A0 =
Aleksey Karpov</div><div><div><span><br></span></div></div></div>__________=
_____________________________________<br>bitcoin-dev mailing list<br><a hre=
f=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoi=
n-dev@lists.linuxfoundation.org</a><br><a href=3D"https://lists.linuxfounda=
tion.org/mailman/listinfo/bitcoin-dev" target=3D"_blank">https://lists.linu=
xfoundation.org/mailman/listinfo/bitcoin-dev</a><br></div></blockquote></di=
v><br></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><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
 class=3D"gmail_signature"><div dir=3D"ltr"><div><div dir=3D"ltr"><div><div=
 dir=3D"ltr"><div><div><span style=3D"font-size:13.3333px">Best,<br>=C3=81d=
=C3=A1m</span></div></div></div></div></div></div></div></div>

--000000000000cecf1a05933194be--