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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <adam.back@gmail.com>) id 1YOrr4-0008RB-0i
for bitcoin-development@lists.sourceforge.net;
Fri, 20 Feb 2015 17:59:10 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.216.47 as permitted sender)
client-ip=209.85.216.47; envelope-from=adam.back@gmail.com;
helo=mail-qa0-f47.google.com;
Received: from mail-qa0-f47.google.com ([209.85.216.47])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1YOrr2-0000ye-UV
for bitcoin-development@lists.sourceforge.net;
Fri, 20 Feb 2015 17:59:10 +0000
Received: by mail-qa0-f47.google.com with SMTP id v10so13503019qac.6
for <bitcoin-development@lists.sourceforge.net>;
Fri, 20 Feb 2015 09:59:03 -0800 (PST)
MIME-Version: 1.0
X-Received: by 10.140.31.246 with SMTP id f109mr24859263qgf.23.1424455143476;
Fri, 20 Feb 2015 09:59:03 -0800 (PST)
Sender: adam.back@gmail.com
Received: by 10.96.150.233 with HTTP; Fri, 20 Feb 2015 09:59:03 -0800 (PST)
In-Reply-To: <CANEZrP0cOY5Wt_mvBSdGGmi4NfZi04SQ7d6GLpnRxmqvXNArGA@mail.gmail.com>
References: <CALqxMTE2doZjbsUxd-e09+euiG6bt_J=_BwKY_Ni3MNK6BiW1Q@mail.gmail.com>
<CANEZrP32M-hSU-a1DA5aTQXsx-6425sTeKW-m-cSUuXCYf+zuQ@mail.gmail.com>
<CALqxMTFNdtUup5MB2Dc_AmQ827sM-t5yx7WQubbfOEd_bO_Ong@mail.gmail.com>
<CANEZrP0cOY5Wt_mvBSdGGmi4NfZi04SQ7d6GLpnRxmqvXNArGA@mail.gmail.com>
Date: Fri, 20 Feb 2015 17:59:03 +0000
X-Google-Sender-Auth: 2qUdiw_elDBwqlla0EWnybh3wbw
Message-ID: <CALqxMTE1OANaMAvqrcOLuKtYd_jmqYp5GcB4CX77S8+fR05=jg@mail.gmail.com>
From: Adam Back <adam@cypherspace.org>
To: Mike Hearn <mike@plan99.net>
Content-Type: text/plain; charset=UTF-8
X-Spam-Score: -1.5 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(adam.back[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1YOrr2-0000ye-UV
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] bloom filtering, privacy
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Fri, 20 Feb 2015 17:59:10 -0000
The idea is not mine, some random guy appeared in #bitcoin-wizards one
day and said something about it, and lots of people reacted, wow why
didnt we think about that before.
It goes something like each block contains a commitment to a bloom
filter that has all of the addresses in the block stored in it.
Now the user downloads the headers and bloom data for all blocks. The
know the bloom data is correct in an SPV sense because of the
commitment. They can scan it offline and locally by searching for
addresses from their wallet in it. Not sure off hand what is the most
efficient strategy, probably its pretty fast locally anyway.
Now they know (modulo false positives) which addresses of theirs maybe
in the block.
So now they ask a full node for merkle paths + transactions for the
addresses from the UTXO set from the block(s) that it was found in.
Separately UTXO commitments could optionally be combined to improve
security in two ways:
- the normal SPV increase that you can also see that the transaction
is actually in the last blocks UTXO set.
- to avoid withholding by the full node, if the UTXO commitment is a
trie (sorted) they can expect a merkle path to lexically adjacent
nodes either side of where the claimed missing address would be as a
proof that there really are no transactions for that address in the
block. (Distinguishing false positive from node withholding)
Adam
On 20 February 2015 at 17:43, Mike Hearn <mike@plan99.net> wrote:
> Ah, I see, I didn't catch that this scheme relies on UTXO commitments
> (presumably with Mark's PATRICIA tree system?).
>
> If you're doing a binary search over block contents then does that imply
> multiple protocol round trips per synced block? I'm still having trouble
> visualising how this works. Perhaps you could write down an example run for
> me.
>
> How does it interact with the need to download chains rather than individual
> transactions, and do so without round-tripping to the remote node for each
> block? Bloom filtering currently pulls down blocks in batches without much
> client/server interaction and that is useful for performance.
>
> Like I said, I'd rather just junk the whole notion of chain scanning and get
> to a point where clients are only syncing headers. If nodes were calculating
> a script->(outpoint, merkle branch) map in LevelDB and allowing range
> queries over it, then you could quickly pull down relevant UTXOs along with
> the paths that indicated they did at one point exist. Nodes can still
> withhold evidence that those outputs were spent, but the same is true today
> and in practice this doesn't seem to be an issue.
>
> The primary advantage of that approach is it does not require a change to
> the consensus rules. But there are lots of unanswered questions about how it
> interacts with HD lookahead and so on.
>
|
