path: root/8f/51b673e8ea1c46f1816c772a7a52080abd9761

Return-Path: <adam.ficsor73@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 57D37408
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 23 Sep 2019 05:20:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lj1-f175.google.com (mail-lj1-f175.google.com
	[209.85.208.175])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0C9B7844
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 23 Sep 2019 05:20:44 +0000 (UTC)
Received: by mail-lj1-f175.google.com with SMTP id e17so12235817ljf.13
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 22 Sep 2019 22:20:44 -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=QZuGR4q6i0jQTFYqhQDCFNDgSzZlII+4VRlt64OLm0Y=;
	b=KcUzNyzgnsktZRXZFUxzZyVFMbR+kiyp3SfzqevFyKxzLumgLVZ3n2vL5wTv00hERv
	lR2tNHFsB3CbUA/zSog6LEK32+sL2VOfIzTOc8nsVHiiA9LMfBz0EGdIM8qaGftuXTv9
	P0/cWjsIq3u6J552LWQlr8Fl+Gusm6YyoD0Mz6tgBF1XNImVbqFzSEPh1PzDF0T+POcK
	BNp5V1fAIFZXncad7TwqLp78IJx4iSicDej2BmY5sKwtZv4cfaTOcQyFfuTGoIQnrDW1
	8bMKdY5rsxwhnfU9jKK9uLsiPCEW3KV/z++Iy4ua8yTUkM0X7i60sH4kGCQser7t8F6a
	4qqQ==
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=QZuGR4q6i0jQTFYqhQDCFNDgSzZlII+4VRlt64OLm0Y=;
	b=gKYGiDnlGR4RDmn2v4kCb82VXFtBiWirecvx7BSAfbSjWbpUanj3GTB4R7tr+5lgzI
	weXWfdec28F1nfVmZeYWdtFLCz2g+3SwNWTdm7exjlaQsyzj683OH0wpgrDfMY8FoOdK
	td4w7wTDbqHNSCqsxs00anXb3Eh01Cc80RitapnfxGYTrLxiLpB2WHOoQ6y4jL7S99PJ
	XmxNwJULR8lNIx1IZobKwszWuocN2NNrDS/i/Tqc5zJ3+TD+KcKkb57MnwzaPJT+xqlu
	uPrPmSZsULY22V8a0jR1A999NR8ODEZggHdx9bqeSLprV/Qy0ILHHUiIhacbw/+2TTDj
	Z5og==
X-Gm-Message-State: APjAAAVeuLOP+Mvc0jnO2vRy5kf4FQqYnqJBttJgg74FN7tRZ3W1AyT7
	nDonXL5Dv03wxAPxQuLefOrjCDJWqKuUQaWLah0bZCZV2qw=
X-Google-Smtp-Source: APXvYqyoag1H/MMJ+zsVzCIxMv0xTsIHH8sl0avsbRBEsD7xp2vCocqWUfYCqoleYrH0f2YDNGXubWb0AcIgmlzCtcw=
X-Received: by 2002:a05:651c:154:: with SMTP id
	c20mr15503146ljd.83.1569216042813; 
	Sun, 22 Sep 2019 22:20:42 -0700 (PDT)
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"
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
X-Mailman-Approved-At: Mon, 23 Sep 2019 05:57:48 +0000
Cc: "admin@bitaps.com" <admin@bitaps.com>
Subject: Re: [bitcoin-dev] Block Batch Filters for Light Clients
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, 23 Sep 2019 05:20:47 -0000

--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--