Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 81727BBC for ; Sat, 21 Sep 2019 21:16:31 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f51.google.com (mail-wr1-f51.google.com [209.85.221.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9ED83108 for ; Sat, 21 Sep 2019 21:16:30 +0000 (UTC) Received: by mail-wr1-f51.google.com with SMTP id b9so10121632wrs.0 for ; Sat, 21 Sep 2019 14:16:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:mime-version:subject:date:references:to:in-reply-to:message-id; bh=MASqr6PVxHzyo4ZLMZqjBjiuusAssUBmJKr4yUtHoM4=; b=Qc4c7RJamaECkRq/uxtPd5SaHRPMiW/XkrQ8T6ZtvamHKZmQLrnHV+9rXp1RP2b8Db nmgks4pFL42ToHxM9JLqKBwH286P9UIkY59lRvdxZDHVh2Igr9e6iDyx3g6RsasvV/5k LwdAhrNCaWlLUlnuw9wF257ajSaciOBBpGDfFj2GM+26Q4Yj1vPX4xN9Sa8fyBdVzh8i 0LGWP3+jesIAof9uYOj4u6RqCbG4Et2HjS/X8yJS3V4n2EvZ2ICEtQ36rwzHhfjlq2va AwYcZOUXggngJYWnW7vIC6yCbGYYvRxv5oxaN9UzWoCW94cpBQbkLcCNA15bxT2iNxg9 g3OQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:mime-version:subject:date:references:to :in-reply-to:message-id; bh=MASqr6PVxHzyo4ZLMZqjBjiuusAssUBmJKr4yUtHoM4=; b=IBYXOL4amBxMaVKGdGNeboqO+l5hwTrJzfh5fmOKIQSTO91cfg13TKclM5BKEDDVmz HqDa0fqaedS+cjBynan1mPKvfMHhBtTLUHIgSVv3lASZiPyAPhkXHGOKEHNVLt7YP4nU Gbk3dE9NuKZ3kLwbNGVEpGCARKKwAXqBOOqkCSrg/av0Y7KvOJ3GXvwL+qfxlgVo3o4g ZJf1sphaDO6wj2gSrwI+HGTkguKLMgGUQbE6Nca5svqYPhaKM2XDHqromRWw72s4jDUe 0STMg7FitcuYMsHvRKe+aTlZXdztojViEF4lZBr7zaFWARmBQXr+NKD2SKM3izJJVETX ql4A== X-Gm-Message-State: APjAAAWwNyOO+EHQW69Ll5f77yRQgQ/Thl/Iw2e8bp1R+sYwLM7BORqr yladXO0s+PP5H67TdK9vu3kLAoRJywY= X-Google-Smtp-Source: APXvYqx4oLCcfR7yWCsxeuuo5YMm+O8ibzCqWzc9h2K1sEr0jOkWRl/95eKy9kr8e/6BCZscGJGiLw== X-Received: by 2002:a5d:6704:: with SMTP id o4mr3942172wru.365.1569100588570; Sat, 21 Sep 2019 14:16:28 -0700 (PDT) Received: from p200300dd671264687411f8965abf20e0.dip0.t-ipconnect.de (p200300DD671264687411F8965ABF20E0.dip0.t-ipconnect.de. [2003:dd:6712:6468:7411:f896:5abf:20e0]) by smtp.gmail.com with ESMTPSA id v2sm12773894wmf.18.2019.09.21.14.16.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 21 Sep 2019 14:16:27 -0700 (PDT) From: Tamas Blummer Content-Type: multipart/alternative; boundary="Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89" Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Date: Sat, 21 Sep 2019 23:16:25 +0200 References: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com> To: "admin@bitaps.com" , Bitcoin Protocol Discussion In-Reply-To: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com> Message-Id: <1ACE761E-A91B-45C7-A0EB-BD66FE3AD7BD@gmail.com> X-Mailer: Apple Mail (2.3445.104.11) 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: Sat, 21 Sep 2019 21:39:42 +0000 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: Sat, 21 Sep 2019 21:16:31 -0000 --Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Hi Aleksey, Yes, BIP158 uses the block hash to seed the hash function, which makes = distinct block filters non-aggregatable=20 for common values. Aggregate fiters on ranges of blocks would have to = use some other seed and then=20 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=20 not scanning over the entire chain, where aggregate filters would help. = I also suspect that whole chain=20 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 = of their wallet=E2=80=99s keys, so they skip over the=20 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 = wrote: >=20 > Hello list,=20 >=20 > Here is a link for a draft of a BIP for compact probabilistic block = filters alternative of BIP 158 >=20 > = https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSx= v80ik/edit?usp=3Dsharing = >=20 > Summary: >=20 > - BIP 158 false positive rate is low, we can achieve lower bandwidth = with higher false positive rate filter while sync blockchain >=20 > - BIP 158 not do not support filter batching by design of used = parameters for siphash and Golomb coding optimal parameters >=20 > - 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 = parameters) >=20 > - Block filters batching reduce filter size significantly >=20 > - Separation of filters by address type allows lite client not to = download redundant information without compromising privacy. >=20 > - 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=20 >=20 > Implementation (python): = https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py= #L172 = >=20 > Exactly information from mainnet about size for separated filters by = address types and batch size will be added within few days. >=20 > Thanks for any feedback. > Aleksey Karpov >=20 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev --Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 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 of 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-kxfGuyNIIZz= mgkEb_z0qSxv80ik/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 parameters 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 parameters)

 - Block filters = batching reduce filter size significantly

- Separation of filters by address type = allows lite client not to download 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.py#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<= br class=3D"">

= --Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89--