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
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gmaxwell@gmail.com>) id 1W3bfs-0000ov-6d
for bitcoin-development@lists.sourceforge.net;
Thu, 16 Jan 2014 01:23:12 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.215.49 as permitted sender)
client-ip=209.85.215.49; envelope-from=gmaxwell@gmail.com;
helo=mail-la0-f49.google.com;
Received: from mail-la0-f49.google.com ([209.85.215.49])
by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1W3bfr-0002ZJ-CM
for bitcoin-development@lists.sourceforge.net;
Thu, 16 Jan 2014 01:23:12 +0000
Received: by mail-la0-f49.google.com with SMTP id y1so1986587lam.22
for <bitcoin-development@lists.sourceforge.net>;
Wed, 15 Jan 2014 17:23:04 -0800 (PST)
MIME-Version: 1.0
X-Received: by 10.112.52.6 with SMTP id p6mr37521lbo.67.1389835384660; Wed, 15
Jan 2014 17:23:04 -0800 (PST)
Received: by 10.112.198.65 with HTTP; Wed, 15 Jan 2014 17:23:04 -0800 (PST)
Date: Wed, 15 Jan 2014 17:23:04 -0800
Message-ID: <CAAS2fgQmsxjkQFSiCdeMoVMaqq5720KpUpdkKZOE+XytHsWw0w@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: -1.6 (-)
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
(gmaxwell[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
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: 1W3bfr-0002ZJ-CM
Subject: [Bitcoin-development] Bait for reusable addresses
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: Thu, 16 Jan 2014 01:23:12 -0000
One challenge with reusable addresses is that while they result in a
small constant overhead for full nodes in searching for their own
transactions they create large overheads for SPV nodes.
One way to address this is for the SPV nodes to hand their servers
their blinding private key so that the server may test addresses on
their behalf. The primary problem with this is that it is
non-reputable: If I show you a blinding private key and say a set of
transactions are related you will be utterly convinced of it, the
transactions really are related. This makes the privacy brittle.
It also has a downside of not being indexable for the server, the
server must do O(clients * reusable-address-txn) work and the work
includes an ECC multiply.
An idea that Adam Back had originally proposed was including optional
"bloom bait", a small token=E2=80=94 say 8 bits=E2=80=94 that distinguished
transactions which allowed an anonymity set vs filtering trade off.
Such a bait would be indexable, enabling faster lookup too.
But bloom bait has privacy problems more severe than the current SPV
bloom filtering. While you leak information to your SPV servers today
if you use bloom filtering the leak usually goes no further. So a
compromise requires both a statistical attack _and_ using SPV servers
that log data against your interest. With bloom bait the whole
network can see the relation. That is unfortunate.
I suggest instead that with optional bait is included in an address
that the sender compute H(nonce-pubkey) and then pick one byte at
random out of the first 16 and xor it with the specified bait and
store the result in the transaction. An SPV server can now index the
bait as it comes in by extracting 16 8-bit keys from each transaction
(the 16 bytes xored with the bait in the transaction). When the
client wants to search for transactions it can give the server a list
of keys its interested in=E2=80=94 including their real key and number of
random number of cover keys.
ObTechnicalWank: This is a specific simple instance of a general
class of solutions which are related to locally decodable error
correcting codes: E.g. the transaction data represents a codeword in a
vector-space and the degree of freedom provided by the adjustable
prefix is used to ensure that codeword is never more than a certain
distance from a specified point. The point isn't made public in the
transaction and it's hidden from the server by providing several
points. There is still an information leak here=E2=80=94 as if someone
believes a set of transactions are related they can intersect their
radiuses and test if the intersection is empty, and if it's not assume
that they found the secret bait=E2=80=94 but it is substantially lower an
information leak than the prefix case.
I didn't give any though into the parameters 8-bits and 16 dimensions.
Some reasoning should be done to fix the parameters in order to make
them the most useful: e.g.
Systems derived from more complex linear codes might give better
performance, e.g. two secret bloom baits, two prefixes in the
transaction bait0^random_char[0-8], bait1^random_char[0-8], server
extracts 16 keys.. and returns to the client transactions which have
at least two key matches with their list.
Obviously whatever is used needs to be easy to implement, but schemes
loosely based on fountain codes should only require picking some
things and xoring... so they should be simple enough.
|
