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
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 952DF26C
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 08:57:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f52.google.com (mail-lf0-f52.google.com
[209.85.215.52])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3C4CC174
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 08:57:10 +0000 (UTC)
Received: by mail-lf0-f52.google.com with SMTP id u64so192935696lff.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 09 May 2016 01:57:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to:cc; bh=Qz3hKT6Xj8IHLZLm4c9xTV+oA3D1E/s1VfZApqVHCwA=;
b=XC4S7dTb+UaenbIezFREZOnDYr8PKDXxjngr/ATCuzUp6pCoMg33u7wX4i+dlZl0+K
i1XZ2eL+OBLlEUMLcsm0rjJGMMaoMvvWBPS9+XeGsJa6KqOvsB79U8iJ2pxiukWONCYa
RKlvl4y34pc+NHnK8zmSo1waSh527VKn1h/GgkkH+gCEML30NJOzot2JHo8wM13/1ef8
LUFB1yOFH4lcGmfk5RY2gPDPOYV/CJuIboAbZa6d01TdytY5MSLD2HblCq0yy4H02gFc
jFTnHkRGixEba11tb/WcEAjSk7dQO3wdUazn/VYKBNE9gvZ8gNtMGDJHVUOSsAen1uvy
xZIw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to:cc;
bh=Qz3hKT6Xj8IHLZLm4c9xTV+oA3D1E/s1VfZApqVHCwA=;
b=RYpnxpNoUbdSKte2wKrVr2iVe9bgSMpl0wROxqSj5xweG1E3g4BXoGLdsPp76MdNSG
vgwqmSNhwXx9y+qeyJujOFX4D05FVdVhVM0hZrF2ztmg5zuvWXEL+FAY/eZIkkGLPI50
CEpFuo8g3e5SRX57DN2ai+Q3Yec6oOn66ltEs+dzkg5/z8WTc7W6q/OQI2SjsM1Kpi7/
1XnLJOD4YtmvJIfT+GQRY7ZBFsyJxCKShRn0qhX4Un2W2DP5eOjMxWJ4xOxxYsb3K1q5
lJ6h/EBp3uG/NLVnqrnCHIALr6R+CScLoBe7HETFZGG5jJmPQSIDQykf6r7/ag8oVfx0
7BlQ==
X-Gm-Message-State: AOPr4FXi1LNFmZe3AIBEVQFvb9V7bd5px5kouoR01O1YFIMw/09Z75KqDHp+2MPydAwrW4FS9NRSynzZiM6FPQ==
MIME-Version: 1.0
X-Received: by 10.112.202.164 with SMTP id kj4mr14511365lbc.141.1462784228702;
Mon, 09 May 2016 01:57:08 -0700 (PDT)
Sender: gmaxwell@gmail.com
Received: by 10.112.65.108 with HTTP; Mon, 9 May 2016 01:57:08 -0700 (PDT)
In-Reply-To: <71d822e413ac457a530e1c367811cc24@cock.lu>
References: <71d822e413ac457a530e1c367811cc24@cock.lu>
Date: Mon, 9 May 2016 08:57:08 +0000
X-Google-Sender-Auth: PfbMDoFd7h9LnlewuYuIWnntc1E
Message-ID: <CAAS2fgTG6AKDVMMe6kZC5YbZhAkoNiYLh16mfodUR3=Pc_3AyA@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
To: bfd@cock.lu
Content-Type: text/plain; charset=UTF-8
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW 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: Mon, 09 May 2016 09:11:33 +0000
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Committed bloom filters for improved wallet
performance and SPV security
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 09 May 2016 08:57:14 -0000
On Mon, May 9, 2016 at 8:26 AM, bfd--- via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> We introduce several concepts that rework the lightweight Bitcoin
> client model in a manner which is secure, efficient and privacy
> compatible.
[...]
> A Bloom Filter Digest is deterministically created of every block
I think this is a fantastic idea.
Some napkin work shows that it has pretty good communications
bandwidth so long as you assume that the wallet has many keys (e.g.
more than the number of the outputs in the block)-- otherwise BIP37
uses less bandwidth, but you note its terrible privacy problems.
You should be aware that when the filter is transmitted but not
updated, as it is in these filtering applications, the bloom filter is
not the most communication efficient data structure.
The most efficient data structure is similar to a bloom filter, but
you use more bits and only one hash function. The result will be
mostly zero bits. Then you entropy code it using RLE+Rice coding or an
optimal binomial packer (e.g.
https://people.xiph.org/~greg/binomial_codec.c). This is about 45%
more space efficient than a bloom filter. ... it's just a PITA to
update, though that is inapplicable here. Entropy coding for this can
be quite fast, if many lookups are done the decompression could even
be faster than having to use two dozen hash functions for each lookup.
The intuition is that this kind of simple hash-bitmap is great, but
space inefficient if you don't have compression since most of the bits
are 0 you end up spending a bit to send less than a bit of
information. A bloom filter improve the situation by using the
multiple filters to increase the ones density to 50%, but the
increased collisions create overhead. This is important when its a
in-memory data-structure that you're updating often, but not here.
One thing to do with matching blocks is after finding the matches the
node could potentially consult some PIR to get the blocks it cares
about... thus preventing a leak of which blocks it was interested in,
but not taking PIR costs for the whole chain or requiring the
implementation of PIR tree search (which is theoretically simple but
in practice hard to implement).
|
