From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 57D37408 for ; 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 ; Mon, 23 Sep 2019 05:20:44 +0000 (UTC) Received: by mail-lj1-f175.google.com with SMTP id e17so12235817ljf.13 for ; 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 Date: Mon, 23 Sep 2019 07:20:31 +0200 Message-ID: To: Tamas Blummer via bitcoin-dev 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" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Please also take a look at "Applying Private Informat= ion Retrieval to Lightweight Bitcoin Clients" Scaling Bitcoin talk. Th= e academics were not aware of BIP158 at all, yet came up with a similar sch= eme independently.

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

Yes, BIP158 uses the block hash to seed the hash= function, which makes distinct block filters non-aggregatable=C2=A0
<= div>for common values. Aggregate fiters on ranges of blocks would have to u= se some other seed and then=C2=A0
achive significant savings usin= g the same design.

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
not scanning over the entire chain, where aggregate filt= ers would help. I also suspect that whole chain=C2=A0
scans would= be better served with plain sequential reads in map-reduce style.

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
majority of history which is a bigger saving than any aggregate fi= lter.

I wish we get a filter committed as commitme= nt would unlock more utility than any marginal savings through
mo= re elaborate design.

Tamas Blummer

<= /div>
On Sep 19, 2019, at 19:20, ad= min--- via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wr= ote:

Hello list,=C2=A0

=
Here is a link for a draft of a BIP for =C2=A0compact probabili= stic block filters alternative of BIP 158

https://docs.google.com/docu= ment/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSxv80ik/edit?usp=3Dsharing<= /div>

Summary:

=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

=C2=A0- BIP 158 not do not support filter batching by design of used param= eters for siphash and Golomb coding optimal parameters

=
=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.
=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)

=C2=A0- Block filters batching re= duce filter size significantly

- Separation of fil= ters by address type allows lite client not to download redundant informati= on without compromising privacy.

- Lite client fil= ters download strategy: get biggest filter (smallest blocks/size rate) for = blocks range, in case positive test =C2=A0-> get medium filters to reduc= e blocks range -> =C2=A0get block filters for affected range -> downl= oad affected blocks over TOR=C2=A0


Exactly information from mainnet =C2=A0about size for separated fi= lters by address types and batch size will be added within few days.
<= div>
Thanks for any feedback.
=C2=A0 =C2=A0 =C2=A0 = Aleksey Karpov

__________= _____________________________________
bitcoin-dev mailing list
bitcoi= n-dev@lists.linuxfoundation.org
https://lists.linu= xfoundation.org/mailman/listinfo/bitcoin-dev

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev


--
Best,
=C3=81d= =C3=A1m
--000000000000cecf1a05933194be--