1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
Return-Path: <admin@bitaps.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BD734B6C
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 Sep 2019 17:20:14 +0000 (UTC)
From: "admin@bitaps.com" <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 <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: 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 =
<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 =
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 =
<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
--Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; line-break: after-white-space;" class=3D"">Hello=
list, <div class=3D""><br class=3D""></div><span class=3D"">Here =
is a link for a draft of a BIP for compact probabilistic block =
filters alternative of BIP 158</span><div class=3D""><br =
class=3D""></div><div class=3D""><a =
href=3D"https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgk=
Eb_z0qSxv80ik/edit?usp=3Dsharing" =
class=3D"">https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZz=
mgkEb_z0qSxv80ik/edit?usp=3Dsharing</a></div><div class=3D""><br =
class=3D""></div><div class=3D"">Summary:</div><div class=3D""><br =
class=3D""></div><div class=3D""> - BIP 158 false positive =
rate is low, we can achieve lower bandwidth with higher false positive =
rate filter while sync blockchain</div><div class=3D""><br =
class=3D""></div><div class=3D""> - BIP 158 not do not support =
filter batching by design of used parameters for siphash and Golomb =
coding optimal parameters</div><div class=3D""><br class=3D""></div><div =
class=3D""> - 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.</div><div class=3D""> Second sequence have a =
lot of duplicates, compressed with 2 round of Huffman algorithm. =
(Effectivity about 98% vs Golomb with optimal parameters)</div><div =
class=3D""><br class=3D""></div><div class=3D""> - Block filters =
batching reduce filter size significantly</div><div class=3D""><br =
class=3D""></div><div class=3D"">- Separation of filters by address type =
allows lite client not to download redundant information without =
compromising privacy.</div><div class=3D""><br class=3D""></div><div =
class=3D"">- 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 </div><div class=3D""><br class=3D""></div><div =
class=3D"">Implementation (python): <a =
href=3D"https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/fi=
lters.py#L172" =
class=3D"">https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions=
/filters.py#L172</a></div><div class=3D""><br class=3D""></div><div =
class=3D"">Exactly information from mainnet about size for =
separated filters by address types and batch size will be added within =
few days.</div><div class=3D""><br class=3D""></div><div class=3D"">Thanks=
for any feedback.</div><div class=3D""> Aleksey =
Karpov</div><div class=3D""><div class=3D""><span class=3D""><br =
class=3D""></span></div></div></body></html>=
--Apple-Mail=_7A610AB8-382D-4393-BFD0-78FC0628F9F1--
|
