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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
|
Return-Path: <tony991@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BBA1F3EE
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 Aug 2016 07:52:15 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f53.google.com (mail-wm0-f53.google.com [74.125.82.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 54BF58C
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 Aug 2016 07:52:14 +0000 (UTC)
Received: by mail-wm0-f53.google.com with SMTP id q128so76612850wma.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 10 Aug 2016 00:52:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:content-transfer-encoding;
bh=7rS01VPI8KZLAPiGSiFjE7drfAacFRE0SJ8Sm2k2VX0=;
b=YMwtqevwYRrIr005V3eQ1xmniZ8ncalazCl087VT7LHuZEeRWojH4/2Agc0p6mgRot
rSZyz8IjUL8Io6HA4Ex+WQE3EhxTkVfAERArpXgBNF+unlfoJ4YSe6i4YI90/zekSZ5T
PN/pj0lZuqegbeLGgV18BVA+4989s790n3cVhZW7VBPJbF08wLkM7w8tozNdvD3s6qPD
N32Mh4lrGoXhoUB2UWP/jOfMaJj7Y4dPtP5hNWzfyOLSIfFQvfabSvZZtijJjGk8pLdo
P1KrShkhY8NVicLTfuX7QsfNxHwHguohwCP6xh0Jfcw7ZxYvs7tCJAgqiVaM1KX6jPp3
vipA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:content-transfer-encoding;
bh=7rS01VPI8KZLAPiGSiFjE7drfAacFRE0SJ8Sm2k2VX0=;
b=IF1htG1aol3kanVamC6Km39e/ff2L3umnHHuQATf+NZYVhz94eXmhQLHkRlP9Sx0jz
hoQ7qz7/DafH3mTK+cZTPVmLln27hArjWL5lJSEgje6g1iH9yK1v6dIxbPymmuxE/FLY
GHyjUlgVEL5NF/LR4+E4C0Bsm3an6Uinb8PWp4VhrDW9ESgYw4taBdhVpt98IIj2jX6M
jNEWkQMYdvuhAzO7TmrDsJW71GBfQn6R5R9fcw9UrluOl9yHLcF9c8KObrjmK1fHbSXS
DFVkv+DoaDjf0CmjEsNgkfCv25ndVKAOuHAah+3eyZQEojP95K6jpMKN3GHCEHNMOA4R
fEbw==
X-Gm-Message-State: AEkoouvJSzeZSwwk5ZxugS4w6se0WJZeawRKDSoRcQW3mt3zcd3z2+28J/QHfuh3gL5xOr5n6JnuTzepxjCojw==
X-Received: by 10.28.44.193 with SMTP id s184mr1765085wms.73.1470815532515;
Wed, 10 Aug 2016 00:52:12 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.194.100.161 with HTTP; Wed, 10 Aug 2016 00:52:11 -0700 (PDT)
In-Reply-To: <CAL3p6zqj7bc=qrayBBK=O6p2b2PBNO3n5EMFf_1dR1oMq581hg@mail.gmail.com>
References: <CAL3p6zpADtYFQnQUr3Efk6V59+K+bB3tPQQMGT9weiafU=43zA@mail.gmail.com>
<20160808154707.GB2196@banane.informatik.uni-ulm.de>
<CAL3p6zo1xBEu90MDHSK4TNX0DL2QXxq5vC48a2cFnX0JCD=RvQ@mail.gmail.com>
<20160809072635.GA2178@banane.informatik.uni-ulm.de>
<CAL3p6zqj7bc=qrayBBK=O6p2b2PBNO3n5EMFf_1dR1oMq581hg@mail.gmail.com>
From: Tony Churyumoff <tony991@gmail.com>
Date: Wed, 10 Aug 2016 10:52:11 +0300
Message-ID: <CAL3p6zqZC-mqCJ+qryYiYBZ3yCS2KmYPUE37xyt2KWg3=Y4Ngw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,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: Wed, 10 Aug 2016 14:53:25 +0000
Subject: [bitcoin-dev] Fwd: Hiding entire content of on-chain transactions
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: Wed, 10 Aug 2016 07:52:15 -0000
> Instead of a hash function you may use a keyed hash function (HMAC) where
> the key is just the random string. They key needs to be stored in the
> history of the coin to allow for verification.
This is nearly equivalent. The sole purpose of the blinding factor is
to increase the search space and make preimaging of the output
impossible. While in many applications HMAC is superior to plain hash
of a concatenation of the input data and the key (key =3D blinding
factor in our case), its preimage resistance is the same as that of
the hash.
2016-08-09 10:26 GMT+03:00 Henning Kopp <henning.kopp@uni-ulm.de>:
>
> Hi Tony,
>
> > > Regarding the blinding factor, I think you could just use HMAC.
> > How exactly?
>
> I am not entirely sure if this works. You wrote:
>
> > There is one technical nuance that I omitted above to avoid distraction=
.
> > Unlike regular bitcoin transactions, every output in a private payment
> > must also include a blinding factor, which is just a random string. Wh=
en
> > the output is spent, the corresponding spend proof will therefore depen=
d on
> > this blinding factor (remember that spend proof is just a hash of the
> > output). Without a blinding factor, it would be feasible to pre-image =
the
> > spend proof and reveal the output being spent as the search space of al=
l
> > possible outputs is rather small.
>
> Instead of a hash function you may use a keyed hash function (HMAC) where
> the key is just the random string. They key needs to be stored in the
> history of the coin to allow for verification.
>
> Best
> Henning
>
> On Mon, Aug 08, 2016 at 07:03:28PM +0300, Tony Churyumoff wrote:
> > Hi Henning,
> >
> > 1. The fees are paid by the enclosing BTC transaction.
> > 2. The hash is encoded into an OP_RETURN.
> >
> > > Regarding the blinding factor, I think you could just use HMAC.
> > How exactly?
> >
> > Tony
> >
> >
> > 2016-08-08 18:47 GMT+03:00 Henning Kopp <henning.kopp@uni-ulm.de>:
> >
> > > Hi Tony,
> > >
> > > I see some issues in your protocol.
> > >
> > > 1. How are mining fees handled?
> > >
> > > 2. Assume Alice sends Bob some Coins together with their history and
> > > Bob checks that the history is correct. How does the hash of the txou=
t
> > > find its way into the blockchain?
> > >
> > > Regarding the blinding factor, I think you could just use HMAC.
> > >
> > > All the best
> > > Henning
> > >
> > >
> > > On Mon, Aug 08, 2016 at 06:30:21PM +0300, Tony Churyumoff via bitcoin=
-dev
> > > wrote:
> > > > This is a proposal about hiding the entire content of bitcoin
> > > > transactions. It goes farther than CoinJoin and ring signatures, w=
hich
> > > > only obfuscate the transaction graph, and Confidential Transactions=
,
> > > which
> > > > only hide the amounts.
> > > >
> > > > The central idea of the proposed design is to hide the entire input=
s and
> > > > outputs, and publish only the hash of inputs and outputs in the
> > > > blockchain. The hash can be published as OP_RETURN. The plaintext=
of
> > > > inputs and outputs is sent directly to the payee via a private mess=
age,
> > > and
> > > > never goes into the blockchain. The payee then calculates the hash=
and
> > > > looks it up in the blockchain to verify that the hash was indeed
> > > published
> > > > by the payer.
> > > >
> > > > Since the plaintext of the transaction is not published to the publ=
ic
> > > > blockchain, all validation work has to be done only by the user who
> > > > receives the payment.
> > > >
> > > > To protect against double-spends, the payer also has to publish ano=
ther
> > > > hash, which is the hash of the output being spent. We=E2=80=99ll c=
all this hash
> > > *spend
> > > > proof*. Since the spend proof depends solely on the output being s=
pent,
> > > > any attempt to spend the same output again will produce exactly the=
same
> > > > spend proof, and the payee will be able to see that, and will rejec=
t the
> > > > payment. If there are several outputs consumed by the same transac=
tion,
> > > > the payer has to publish several spend proofs.
> > > >
> > > > To prove that the outputs being spent are valid, the payer also has=
to
> > > send
> > > > the plaintexts of the earlier transaction(s) that produced them, th=
en the
> > > > plaintexts of even earlier transactions that produced the outputs s=
pent
> > > in
> > > > those transactions, and so on, up until the issue (similar to coinb=
ase)
> > > > transactions that created the initial private coins. Each new owne=
r of
> > > the
> > > > coin will have to store its entire history, and when he spends the =
coin,
> > > he
> > > > forwards the entire history to the next owner and extends it with h=
is own
> > > > transaction.
> > > >
> > > > If we apply the existing bitcoin design that allows multiple inputs=
and
> > > > multiple outputs per transaction, the history of ownership transfer=
s
> > > would
> > > > grow exponentially. Indeed, if we take any regular bitcoin output =
and
> > > try
> > > > to track its history back to coinbase, our history will branch ever=
y time
> > > > we see a transaction that has more than one input (which is not
> > > uncommon).
> > > > After such a transaction (remember, we are traveling back in time),=
we=E2=80=99ll
> > > > have to track two or more histories, for each respective input. Th=
ose
> > > > histories will branch again, and the total number of history entrie=
s
> > > grows
> > > > exponentially. For example, if every transaction had exactly two i=
nputs,
> > > > the size of history would grow as 2^N where N is the number of step=
s back
> > > > in history.
> > > >
> > > > To avoid such rapid growth of ownership history (which is not only
> > > > inconvenient to move, but also exposes too much private information=
about
> > > > previous owners of all the contributing coins), we will require eac=
h
> > > > private transaction to have exactly one input (i.e. to consume exac=
tly
> > > one
> > > > previous output). This means that when we track a coin=E2=80=99s h=
istory back in
> > > > time, it will no longer branch. It will grow linearly with the num=
ber of
> > > > transfers of ownership. If a user wants to combine several inputs,=
he
> > > will
> > > > have to send them as separate private transactions (technically, se=
veral
> > > > OP_RETURNs, which can be included in a single regular bitcoin
> > > transaction).
> > > >
> > > > Thus, we are now forbidding any coin merges but still allowing coin
> > > > splits. To avoid ultimate splitting into the dust, we will also re=
quire
> > > > that all private coins be issued in one of a small number of
> > > > denominations. Only integer number of =E2=80=9Cbanknotes=E2=80=9D =
can be transferred,
> > > the
> > > > input and output amounts must therefore be divisible by the denomin=
ation.
> > > > For example, an input of amount 700, denomination 100, can be split=
into
> > > > outputs 400 and 300, but not into 450 and 250. To send a payment, =
the
> > > > payer has to pick the unspent outputs of the highest denomination f=
irst,
> > > > then the second highest, and so on, like we already do when we pay =
in
> > > cash.
> > > >
> > > > With fixed denominations and one input per transaction, coin histor=
ies
> > > > still grow, but only linearly, which should not be a concern in reg=
ard to
> > > > scalability given that all relevant computing resources still grow
> > > > exponentially. The histories need to be stored only by the current=
owner
> > > > of the coin, not every bitcoin node. This is a fairer allocation o=
f
> > > > costs. Regarding privacy, coin histories do expose private transac=
tions
> > > > (or rather parts thereof, since a typical payment will likely consi=
st of
> > > > several transactions due to one-input-per-transaction rule) of past=
coin
> > > > owners to the future ones, and that exposure grows linearly with ti=
me,
> > > but
> > > > it is still much much better than having every transaction immediat=
ely on
> > > > the public blockchain. Also, the value of this information for pot=
ential
> > > > adversaries arguably decreases with time.
> > > >
> > > > There is one technical nuance that I omitted above to avoid distrac=
tion.
> > > > Unlike regular bitcoin transactions, every output in a private pay=
ment
> > > > must also include a blinding factor, which is just a random string.=
When
> > > > the output is spent, the corresponding spend proof will therefore d=
epend
> > > on
> > > > this blinding factor (remember that spend proof is just a hash of t=
he
> > > > output). Without a blinding factor, it would be feasible to pre-im=
age
> > > the
> > > > spend proof and reveal the output being spent as the search space o=
f all
> > > > possible outputs is rather small.
> > > >
> > > > To issue the new private coin, one can burn regular BTC by sending =
it to
> > > > one of several unspendable bitcoin addresses, one address per
> > > denomination.
> > > > Burning BTC would entitle one to an equal amount of the new privat=
e
> > > coin,
> > > > let=E2=80=99s call it *black bitcoin*, or *BBC*.
> > > >
> > > > Then BBC would be transferred from user to user by:
> > > > 1. creating a private transaction, which consists of one input and
> > > several
> > > > outputs;
> > > > 2. storing the hash of the transaction and the spend proof of the
> > > consumed
> > > > output into the blockchain in an OP_RETURN (the sender pays the
> > > > corresponding fees in regular BTC)
> > > > 3. sending the transaction, together with the history leading to it=
s
> > > input,
> > > > directly to the payee over a private communication channel. The fi=
rst
> > > > entry of the history must be a bitcoin transaction that burned BTC =
to
> > > issue
> > > > an equal amount of BCC.
> > > >
> > > > To verify the payment, the payee:
> > > > 1. makes sure that the amount of the input matches the sum of outpu=
ts,
> > > and
> > > > all are divisible by the denomination
> > > > 2. calculates the hash of the private transaction
> > > > 3. looks up an OP_RETURN that includes this hash and is signed by t=
he
> > > > payee. If there is more than one, the one that comes in the earlie=
r
> > > block
> > > > prevails.
> > > > 4. calculates the spend proof and makes sure that it is included in=
the
> > > > same OP_RETURN
> > > > 5. makes sure the same spend proof is not included anywhere in the =
same
> > > or
> > > > earlier blocks (that is, the coin was not spent before). Only
> > > transactions
> > > > by the same author are searched.
> > > > 6. repeats the same steps for every entry in the history, except th=
e
> > > first
> > > > entry, which should be a valid burning transaction.
> > > >
> > > > To facilitate exchange of private transaction data, the bitcoin net=
work
> > > > protocol can be extended with a new message type. Unfortunately, i=
t
> > > lacks
> > > > encryption, hence private payments are really private only when bit=
coin
> > > is
> > > > used over tor.
> > > >
> > > > There are a few limitations that ought to be mentioned:
> > > > 1. After user A sends a private payment to user B, user A will know=
what
> > > > the spend proof is going to be when B decides to spend the coin.
> > > > Therefore, A will know when the coin was spent by B, but nothing m=
ore.
> > > > Neither the new owner of the coin, nor its future movements will b=
e
> > > known
> > > > to A.
> > > > 2. Over time, larger outputs will likely be split into many smaller
> > > > outputs, whose amounts are not much greater than their denomination=
s.
> > > > You=E2=80=99ll have to combine more inputs to send the same amount.=
When you
> > > want
> > > > to send a very large amount that is much greater than the highest
> > > available
> > > > denomination, you=E2=80=99ll have to send a lot of private transact=
ions, your
> > > > bitcoin transaction with so many OP_RETURNs will stand out, and the=
ir
> > > > number will roughly indicate the total amount. This kind of privac=
y
> > > > leakage, however it applies to a small number of users, is easy to =
avoid
> > > by
> > > > using multiple addresses and storing a relatively small amount on e=
ach
> > > > address.
> > > > 3. Exchanges and large merchants will likely accumulate large coin
> > > > histories. Although fragmented, far from complete, and likely outd=
ated,
> > > it
> > > > is still something to bear in mind.
> > > >
> > > > No hard or soft fork is required, BBC is just a separate privacy
> > > preserving
> > > > currency on top of bitcoin blockchain, and the same private keys an=
d
> > > > addresses are used for both BBC and the base currency BTC. Every B=
CC
> > > > transaction must be enclosed into by a small BTC transaction that s=
tores
> > > > the OP_RETURNs and pays for the fees.
> > > >
> > > > Are there any flaws in this design?
> > > >
> > > > Originally posted to BCT https://bitcointalk.org/index.
> > > php?topic=3D1574508.0,
> > > > but got no feedback so far, apparently everybody was consumed with
> > > bitfinex
> > > > drama and now mimblewimble.
> > > >
> > > > Tony
> > >
> > > > _______________________________________________
> > > > bitcoin-dev mailing list
> > > > bitcoin-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > >
> > >
> > > --
> > > Henning Kopp
> > > Institute of Distributed Systems
> > > Ulm University, Germany
> > >
> > > Office: O27 - 3402
> > > Phone: +49 731 50-24138
> > > Web: http://www.uni-ulm.de/in/vs/~kopp
> > >
>
> --
> Henning Kopp
> Institute of Distributed Systems
> Ulm University, Germany
>
> Office: O27 - 3402
> Phone: +49 731 50-24138
> Web: http://www.uni-ulm.de/in/vs/~kopp
|