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 BD734B6C for ; Thu, 19 Sep 2019 17:26:19 +0000 (UTC) X-Greylist: delayed 00:06:02 by SQLgrey-1.7.6 Received: from mail.bitaps.com (mail.bitaps.com [95.85.9.218]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id D7D5E876 for ; Thu, 19 Sep 2019 17:26:18 +0000 (UTC) Received: from [192.168.0.36] (unknown [109.195.21.38]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.bitaps.com (Postfix) with ESMTPSA id E2E71148766 for ; Thu, 19 Sep 2019 17:20:14 +0000 (UTC) From: "admin@bitaps.com" Content-Type: multipart/alternative; boundary="Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1" Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\)) Message-Id: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com> Date: Thu, 19 Sep 2019 21:20:13 +0400 To: bitcoin-dev@lists.linuxfoundation.org X-Mailer: Apple Mail (2.3445.100.39) X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE 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: Thu, 19 Sep 2019 19:15:04 +0000 Subject: [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: Thu, 19 Sep 2019 17:26:19 -0000 --Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Hello list,=20 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_z0qSx= v80ik/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=20 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 --Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii 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

= --Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1--