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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <adam@cypherspace.org>) id 1W9yxQ-0006qI-Df
for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 15:27:40 +0000
X-ACL-Warn:
Received: from mout.perfora.net ([74.208.4.195])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1W9yxO-00042m-Gh
for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 15:27:40 +0000
Received: from netbook (c186-45.i02-7.onvol.net [213.165.186.45])
by mrelay.perfora.net (node=mrus3) with ESMTP (Nemesis)
id 0LwacZ-1VBGuH1TyB-018F99; Sun, 02 Feb 2014 10:26:35 -0500
Received: by netbook (Postfix, from userid 1000)
id CB9FE2E4A67; Sun, 2 Feb 2014 16:26:27 +0100 (CET)
Received: by flare (hashcash-sendmail, from uid 1000);
Sun, 2 Feb 2014 16:26:24 +0100
Date: Sun, 2 Feb 2014 16:26:24 +0100
From: Adam Back <adam@cypherspace.org>
To: Peter Todd <pete@petertodd.org>
Message-ID: <20140202152624.GA22093@netbook.cypherspace.org>
References: <CAAS2fgQmsxjkQFSiCdeMoVMaqq5720KpUpdkKZOE+XytHsWw0w@mail.gmail.com>
<20140124090218.GA15398@savin>
<CANEZrP0MnXr4xjaMPg7v7vTiDQr-y7esvEBE=xk=Y0BUGXak9A@mail.gmail.com>
<20140124154235.GA3741@netbook.cypherspace.org>
<20140124161330.GA31233@petertodd.org>
<20140125161901.GA17457@netbook.cypherspace.org>
<20140202023651.GA18666@savin> <op.xanddiq6yldrnw@laptop-air>
<20140202122610.GA22329@savin>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <20140202122610.GA22329@savin>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:140202:pete@petertodd.org::abnTlfOq0o4b1KmY:0000000000000000000
0000000000000000000000000B5X
X-Hashcash: 1:20:140202:jeremy@taplink.co::O5B4YXYtonFlZ0El:00000000000000000000
00000000000000000000000029td
X-Hashcash: 1:20:140202:bitcoin-development@lists.sourceforge.net::BmLmqyZvsWEa1
Kee:00000000000000000000D+ma
X-Hashcash: 1:20:140202:adam@cypherspace.org::LqK2RNx8jdTPBV7j:00000000000000000
00000000000000000000000076JG
X-Provags-ID: V02:K0:LK1OzrCITqAxAiQSVFzuZvLCtSKWsXjoZOqmC0RQFIy
x1JYKAqZjqyNETlzeFijLq+6ooJLIZPzhtJre024yj0/fK5/fv
7a8rM/M7UXfX0xGyUFp1tWesuAQdY6Tm2oNoMxcKEPNTpWV/bC
ATeV7WfKvbDu9tGh4/fWTdhhG4unHX8I/MRrNgxYvQBl+n5t7M
KMmrczCEkfBD/3yz4Hao4qM+W2+W7nWPVidCQW7QQaI/LYf95X
yL7PkPq0t43lApaduTD/7yRmq5F5qQjXhUFiNKcxkWozWtnyyj
jaTWlj0E58wiuL+ALthbuIh+KHMF6rRcSzu7+h62PNHSh7SzdJ
luu6xXgcC8C8DRz9sdzBDnZGisMSd5oxrEvvP77x0
X-Spam-Score: -0.0 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
no trust [74.208.4.195 listed in list.dnswl.org]
-0.0 SPF_HELO_PASS SPF: HELO matches SPF record
X-Headers-End: 1W9yxO-00042m-Gh
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] (space) efficient reusable addr via weil
pairing IBE (Re: 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: Sun, 02 Feb 2014 15:27:40 -0000
I think you Peter & Jeremy figured it out - dont disagree with the
explanation details.
And it seems better explained between the two posts than I did. I think
Peter is right that you do not need an explicit prefix, the prefix after
decryption can be a chosen number of leading 0s and this gives a tunable
amount of false positives. You already have privacy becaue the query is
only revealed to the semi-trusted full node, and its query scope is limited
to one or a chosen batch of blocks. But you can if desired add additional
ambiguity as Peter described by reducing the number of bits of 0 in the
decrypted block. There is no need for matching a specific prefix as its
already a recipient specific calculation. (It means the actual encrypted
value where it is chosen would have to mimic false positives: random with
n-bits of trailing 0s and expected probability distribution).
It should be compatible for combining with sharding or public prefixes, as
Peter mentioned but for short public prefixes those still has some (reduced)
blockchain ledger logged possibility to reduce anonymity set when combined
with flow analysis.
Maybe you could vary a public prefix per block. Eg the public prefix for a
given user is the LSBits of the per block IBE derived pubic key for a given
user. I am not sure if that helps or hinders. Maybe it hurts anonymity set
because the analyst (Eve) is given multiple chances over time to exclude an
analysed flow candidate.
It would desirable to find a non-IBE way to do this. (And more
computationally efficient / precomputable / indexable)
Or you could use different address types depending on the circumstance:
one-use, stealth, or IBE. Kind of difficult to automate that (to know what
the user is planning to do with it) and avoid user confusion. Clearly users
are quite confused and the convenient and understandable thing is to have a
(safely) reusable address.
Adam
On Sun, Feb 02, 2014 at 07:26:10AM -0500, Peter Todd wrote:
>On Sun, Feb 02, 2014 at 01:16:20AM -0800, Jeremy Spilman wrote:
>> >
>> >Consequently you can now securely and very network/space efficiently
>> >securely delegate searching a block by computing the private key for the
>> >IBE pub key that any sender would use for that block, and sending it as
>> >a query to a random (or node-capture defended random selected node).
>> >The node can decrypt the encrypted bloom baits with it, but remains
>> >powerless to correlate with bloom baits to other payments received by
>> >the same user in bother blocks.
>> >
>>
>> I'm not sure I've fully wrapped my head around it.
>>
>> d/Q - Identity key
>> E - Generate an epoch-pubkey: E = Q * H1(epoch)
>> r/P - Ephemeral privkey/pubkey, or discoverable from inputs
>> S = r * K - Shared secret (ECDE)
>
>There needs to be two separate payor pubkeys, which I called elsewhere
>the "Filter" and "Recover" pubkeys - the latter I think corresponds to
>what you meant by identity key. From those two pubkeys two separate
>shared secrets are derived.
>
>The key idea is that you can encrypt a short string of zeros with the
>"Filter" pubkey using ECDH and place the resulting "filter bait" in the
>transaction. This lets the payor give the secret key corresponding to
>that pubkey to a semi-trusted third party. That third party can then
>trial decrypt all filter bait seen in transactions in the blockchain,
>and every time the decrypted string has a sufficient number of zeros
>it's considered a filter pass and the transaction is given to the payor.
>For n zero bits one in 2^n transactions will match at random, which sets
>your false positive rate.
>
>Basically think of it as a way to outsource the work required for
>zero-prefix stealth addresses, but with (less) of a sacrifice of
>anonymity compared to just giving the third-party your recovery pubkey.
>Identity-based encryption only comes into it because it's nice to be
>able to further limit what transactions the server knows about to
>specific time intervals rather than forver into the future.
>
>Interestingly both schemes can be used at once - a short public prefix
>combined with a second private filter. What's interesting there is that
>the public prefix can do a first-pass filtering, with the second private
>filter relatively long but still providing plausible deniability - you
>can always claim 100% of the matching transactions were false positives
>because you didn't receive any funds!
>
>> The full node then uses this privkey to decrypt the same byte in all
>> the transactions in that epoch/block which match the expected
>> layout/template, e.g. given a certain length OP_RETURN, pull the
>> specific byte and decrypt.
>>
>> This decrypted byte is then in turn used as bloom bait which may or
>> may not cause the transaction to be sent back to the SPV client.
>
>There's no bloom filters involved; as I said before "bloom bait" is a
>misleading name. "Filter bait" is a better term given it's a generic
>concept.
>
>> What encryption scheme is being used here?
>
>XOR with the ECDH-calculated nonce is fine. (run the nonce though a hash
>function first)
>
>--
>'peter'[:-1]@petertodd.org
>000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0
|
