summaryrefslogtreecommitdiff
path: root/b2/fb580b9c6f47b4fc6b96e5afe28bfe66667bab
blob: 730fac56cdb0f86ed78f0d8ab43f3832ddd213f8 (plain)
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
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
Return-Path: <fresheneesz@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id A9B7DC0012
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 14:57:50 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 9F48360A68
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 14:57:50 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id iuUt1Ojl_zm1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 14:57:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com
 [IPv6:2a00:1450:4864:20::52b])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 349456060A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 14:57:48 +0000 (UTC)
Received: by mail-ed1-x52b.google.com with SMTP id b24so21005568edu.10
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 07:57:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=0yuS3HSpC4DNQYwP50JDMm98zpRO3/8Tp3D+40I37aw=;
 b=fd/gMzS5HMNXgjA2hR3j0BOLgmZfTESvb+eWKDDeWZHPfvSFt+EvH1X6dIsfmmCsfW
 YvAAHn0/iM6S6wKdl+fieDxp60LLIfq32rpc4leClll0hcgNNdv8WH9J0v5Z8BkdFlSe
 09mvnW0jTxZNumV7lAP52t3MBi+HNwEYcJsWhbmr6TGSRMFqDD5CyVFerIPoujgbLdM4
 /erjOdmOFh/nGicUxc2QwuQ5Q2mvdz6oLLj+SgfcR1CzSrf6iAMA1t8sT7E7JZu2Gk4B
 1xY5qwVC/KD5arPXV5/heZD6JEsBC3I+USJdOyj2ylO3Tu7nghZdbswXvQgpt4IRoIjx
 XaxA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to;
 bh=0yuS3HSpC4DNQYwP50JDMm98zpRO3/8Tp3D+40I37aw=;
 b=02pG7AtMAVhbGOq/sZF76AvjUnwhu1rmNPMsoOJUiXrxCTK4XF1S9wFQhhnw9VJEme
 jTplAV06L3863nICB2uVgZ/54dv4GDy7e1Nook6HXw06EZ/UgxHTQWQ0bzUTojPoE2qH
 +OtSkL4NzZEzcf4r6MWFCKeyC/RnYH++JPd0LfdtVmRmX45TZA0agU99tGn7tagyDKfd
 0jrfyD9yqfSSajgQDpVP+VXeylOj1ERwc/kkoW46n/Mq9lVrCyP3kltxvho4VGghQVNg
 JWVfiEPREBSYSOKWWaAXDwJyMp0lZf7/DIgP59i3iurewowQSCKe3fIJFH915QVoz9dU
 nvOw==
X-Gm-Message-State: AOAM5313azfWMRBUkqW5A7M/05yY2ObsqWGeolzPxgrENJyhU4MnA8/b
 sOfs4Utb33jocB0yAslTlgSNhsbIhfowqkh7xfczXY74
X-Google-Smtp-Source: ABdhPJyhOzXAPRhLpU9OMS/SzmXbsSCDFjiSA/AjxZdjP9sI7H7HpGrb3nM9GxHpsDJ8B5Dfl1v63xs7yfdeOS2BXVg=
X-Received: by 2002:a50:ec94:0:b0:419:75fa:f695 with SMTP id
 e20-20020a50ec94000000b0041975faf695mr5052338edr.355.1648565865942; Tue, 29
 Mar 2022 07:57:45 -0700 (PDT)
MIME-Version: 1.0
References: <CAPv7TjbXm953U2h+-12MfJ24YqOM5Kcq77_xFTjVK+R2nf-nYg@mail.gmail.com>
In-Reply-To: <CAPv7TjbXm953U2h+-12MfJ24YqOM5Kcq77_xFTjVK+R2nf-nYg@mail.gmail.com>
From: Billy <fresheneesz@gmail.com>
Date: Tue, 29 Mar 2022 09:57:33 -0500
Message-ID: <CAGpPWDa1QfN53a_-9Dhee58T6_zk3S0bZJhZbiDpXndzzv0nTA@mail.gmail.com>
To: Ruben Somsen <rsomsen@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000d4110305db5ca628"
X-Mailman-Approved-At: Tue, 29 Mar 2022 15:37:28 +0000
Subject: Re: [bitcoin-dev]
	=?utf-8?q?Silent_Payments_=E2=80=93_Non-interactive?=
	=?utf-8?q?_private_payments_with_no_on-chain_overhead?=
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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: Tue, 29 Mar 2022 14:57:50 -0000

--000000000000d4110305db5ca628
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Ruben,

Very interesting protocol. This reminds me of how monero stealth addresses
work, which gives monero the same downsides regarding light clients (among
other things). I was a bit confused by the following:

> without requiring any interaction or on-chain overhead

After reading through, I have to assume it was rather misleading to say "no
on-chain overhead". This still requires an on-chain transaction to be sent
to the tweaked address, I believe. Maybe it would have been more accurate
to say no *extra* on chain overhead (over a normal transaction)?

It seems the primary benefit of this is privacy for the recipient. To that
end, it seems like a pretty useful protocol. It's definitely a level of
privacy one would only care about if they might receive a lot money related
to that address. However of course someone might not know they'll receive
an amount of money they want to be private until they receive it. So the
inability to easily do this without a full node is slightly less than
ideal. But it's another good reason to run a full node.

Perhaps there could be a standard that can identify tweaked address, such
that only those addresses can be downloaded and checked by light clients.
It reduces the anonymity set a bit, but it would probably still be
sufficient.



On Mon, Mar 28, 2022, 10:29 Ruben Somsen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi all,
>
> I'm publishing a new scheme for private non-interactive address generatio=
n
> without on-chain overhead. It has upsides as well as downsides, so I
> suspect the main discussion will revolve around whether this is worth
> pursuing or not. There is a list of open questions at the end.
>
> I added the full write-up in plain text below, though I recommend reading
> the gist for improved formatting and in order to benefit from potential
> future edits:
> https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8
>
> Cheers,
> Ruben
>
>
>
> Silent Payments
>
> Receive private payments from anyone on a single static address without
> requiring any interaction or on-chain overhead
>
>
>
> OVERVIEW
>
>
> The recipient generates a so-called silent payment address and makes it
> publicly known. The sender then takes a public key from one of their chos=
en
> inputs for the payment, and uses it to derive a shared secret that is the=
n
> used to tweak the silent payment address. The recipient detects the payme=
nt
> by scanning every transaction in the blockchain.
>
> Compared to previous schemes[1], this scheme avoids using the Bitcoin
> blockchain as a messaging layer[2] and requires no interaction between
> sender and recipient[3] (other than needing to know the silent payment
> address). The main downsides are the scanning requirement, the lack of
> light client support, and the requirement to control your own input(s). A=
n
> example use case would be private one-time donations.
>
> While most of the individual parts of this idea aren=E2=80=99t novel, the
> resulting protocol has never been seriously considered and may be
> reasonably viable, particularly if we limit ourselves to detecting only
> unspent payments by scanning the UTXO set. We=E2=80=99ll start by describ=
ing a
> basic scheme, and then introduce a few improvements.
>
>
>
> BASIC SCHEME
>
>
> The recipient publishes their silent payment address, a single 32 byte
> public key:
> X =3D x*G
>
> The sender picks an input containing a public key:
> I =3D i*G
>
> The sender tweaks the silent payment address with the public key of their
> input:
> X' =3D hash(i*X)*G + X
>
> Since i*X =3D=3D x*I (Diffie-Hellman Key Exchange), the recipient can det=
ect
> the payment by calculating hash(x*I)*G + X for each input key I in the
> blockchain and seeing if it matches an output in the corresponding
> transaction.
>
>
>
> IMPROVEMENTS
>
>
> UTXO set scanning
>
> If we forgo detection of historic transactions and only focus on the
> current balance, we can limit the protocol to only scanning the
> transactions that are part of the UTXO set when restoring from backup,
> which may be faster.
>
> Jonas Nick was kind enough to go through the numbers and run a benchmark
> of hash(x*I)*G + X on his 3.9GHz Intel=C2=AE Core=E2=84=A2 i7-7820HQ CPU,=
 which took
> roughly 72 microseconds per calculation on a single core. The UTXO set
> currently has 80 million entries, the average transaction has 2.3 inputs,
> which puts us at 2.3*80000000*72/1000/1000/60 =3D 221 minutes for a singl=
e
> core (under 2 hours for two cores).
>
> What these numbers do not take into account is database lookups. We need
> to fetch the transaction of every UTXO, as well as every transaction for
> every subsequent input in order to extract the relevant public key,
> resulting in (1+2.3)*80000000 =3D 264 million lookups. How slow this is a=
nd
> what can be done to improve it is an open question.
>
> Once we=E2=80=99re at the tip, every new unspent output will have to be s=
canned.
> It=E2=80=99s theoretically possible to scan e.g. once a day and skip tran=
sactions
> with fully spent outputs, but that would probably not be worth the added
> complexity. If we only scan transactions with taproot outputs, we can
> further limit our efforts, but this advantage is expected to dissipate on=
ce
> taproot use becomes more common.
>
>
> Variant using all inputs
>
> Instead of tweaking the silent payment address with one input, we could
> instead tweak it with the combination of all input keys of a transaction.
> The benefit is that this further lowers the scanning cost, since now we
> only need to calculate one tweak per transaction, instead of one tweak pe=
r
> input, which is roughly half the work, though database lookups remain
> unaffected.
>
> The downside is that if you want to combine your inputs with those of
> others (i.e. coinjoin), every participant has to be willing to assist you
> in following the Silent Payment protocol in order to let you make your
> payment. There are also privacy considerations which are discussed in the
> =E2=80=9CPreventing input linkage=E2=80=9D section.
>
> Concretely, if there are three inputs (I1, I2, I3), the scheme becomes:
> hash(i1*X + i2*X + i3*X)*G + X =3D=3D hash(x*(I1+I2+I3))*G + X.
>
>
> Scanning key
>
> We can extend the silent payment address with a scanning key, which allow=
s
> for separation of detecting and spending payments. We redefine the silent
> payment address as the concatenation of X_scan, X_spend, and derivation
> becomes X' =3D hash(i*X_scan)*G + X_spend. This allows your
> internet-connected node to hold the private key of X_scan to detect
> incoming payments, while your hardware wallet controls X_spend to make
> payments. If X_scan is compromised, privacy is lost, but your funds are n=
ot.
>
>
> Address reuse prevention
>
> If the sender sends more than one payment, and the chosen input has the
> same key due to address reuse, then the recipient address will also be th=
e
> same. To prevent this, we can hash the txid and index of the input, to
> ensure each address is unique, resulting in X' =3D hash(i*X,txid,index)*G=
 +
> X. Note this would make light client support harder.
>
>
>
> NOTEWORTHY DETAILS
>
>
> Light clients
>
> Light clients cannot easily be supported due to the need for scanning. Th=
e
> best we could do is give up on address reuse prevention (so we don=E2=80=
=99t
> require the txid and index), only consider unspent taproot outputs, and
> download a standardized list of relevant input keys for each block over
> wifi each night when charging. These input keys can then be tweaked, and
> the results can be matched against compact block filters. Possible, but n=
ot
> simple.
>
>
> Effect on BIP32 HD keys
>
> One side-benefit of silent payments is that BIP32 HD keys[4] won=E2=80=99=
t be
> needed for address generation, since every address will automatically be
> unique. This also means we won=E2=80=99t have to deal with a gap limit.
>
>
> Different inputs
>
> While the simplest thing would be to only support one input type (e.g.
> taproot key spend), this would also mean only a subset of users can make
> payments to silent addresses, so this seems undesirable. The protocol
> should ideally support any input containing at least one public key, and
> simply pick the first key if more than one is present.
>
> Pay-to-(witness-)public-key-hash inputs actually end up being easiest to
> scan, since the public key is present in the input script, instead of the
> output script of the previous transaction (which requires one extra
> transaction lookup).
>
>
> Signature nonce instead of input key
>
> Another consideration was to tweak the silent payment address with the
> signature nonce[5], but unfortunately this breaks compatibility with MuSi=
g2
> and MuSig-DN, since in those schemes the signature nonce changes dependin=
g
> on the transaction hash. If we let the output address depend on the nonce=
,
> then the transaction hash will change, causing a circular reference.
>
>
> Sending wallet compatibility
>
> Any wallet that wants to support making silent payments needs to support =
a
> new address format, pick inputs for the payment, tweak the silent payment
> address using the private key of one of the chosen inputs, and then proce=
ed
> to sign the transaction. The scanning requirement is not relevant to the
> sender, only the recipient.
>
>
>
> PREVENTING INPUT LINKAGE
>
>
> A potential weakness of Silent Payments is that the input is linked to th=
e
> output. A coinjoin transaction with multiple inputs from other users can
> normally obfuscate the sender input from the recipient, but Silent Paymen=
ts
> reveal that link. This weakness can be mitigated with the =E2=80=9Cvarian=
t using
> all inputs=E2=80=9D, but this variant introduces a different weakness =E2=
=80=93 you now
> require all other coinjoin users to tweak the silent payment address, whi=
ch
> means you=E2=80=99re revealing the intended recipient to them.
>
> Luckily, a blinding scheme[6] exists that allows us to hide the silent
> payment address from the other participants. Concretely, let=E2=80=99s sa=
y there
> are two inputs, I1 and I2, and the latter one is ours. We add a secret
> blinding factor to the silent payment address, X + blinding_factor*G =3D =
X',
> then we receive X1' =3D i1*X' (together with a DLEQ to prove correctness,=
 see
> full write-up[6]) from the owner of the first input and remove the blindi=
ng
> factor with X1' - blinding_factor*I1 =3D X1 (which is equal to i1*X).
> Finally, we calculate the tweaked address with hash(X1 + i2*X)*G + X. The
> recipient can simply recognize the payment with hash(x*(I1+I2))*G + X. No=
te
> that the owner of the first input cannot reconstruct the resulting addres=
s
> because they don=E2=80=99t know i2*X.
>
> The blinding protocol above solves our coinjoin privacy concerns (at the
> expense of more interaction complexity), but we=E2=80=99re left with one =
more issue
> =E2=80=93 what if you want to make a silent payment, but you control none=
 of the
> inputs (e.g. sending from an exchange)? In this scenario we can still
> utilize the blinding protocol, but now the third party sender can try to
> uncover the intended recipient by brute forcing their inputs on all known
> silent payment addresses (i.e. calculate hash(i*X)*G + X for every public=
ly
> known X). While this is computationally expensive, it=E2=80=99s by no mea=
ns
> impossible. No solution is known at this time, so as it stands this is a
> limitation of the protocol =E2=80=93 the sender must control one of the i=
nputs in
> order to be fully private.
>
>
>
> COMPARISON
>
>
> These are the most important protocols that provide similar functionality
> with slightly different tradeoffs. All of them provide fresh address
> generation and are compatible with one-time seed backups. The main benefi=
ts
> of the protocols listed below are that there is no scanning requirement,
> better light client support, and they don=E2=80=99t require control over =
the inputs
> of the transaction.
>
>
> Payment code sharing
>
> This is BIP47[2]. An OP_RETURN message is sent on-chain to the recipient
> to establish a shared secret prior to making payments. Using the blockcha=
in
> as a messaging layer like this is generally considered an inefficient use
> of on-chain resources. This concern can theoretically be alleviated by
> using other means of communicating, but data availability needs to be
> guaranteed to ensure the recipient doesn=E2=80=99t lose access to the fun=
ds.
> Another concern is that the input(s) used to establish the shared secret
> may leak privacy if not kept separate.
>
>
> Xpub sharing
>
> Upon first payment, hand out an xpub instead of an address in order to
> enable repeat payments. I believe Kixunil=E2=80=99s recently published sc=
heme[3] is
> equivalent to this and could be implemented with relative ease. It=E2=80=
=99s
> unclear how practical this protocol is, as it assumes sender and recipien=
t
> are able to interact once, yet subsequent interaction is impossible.
>
>
> Regular address sharing
>
> This is how Bitcoin is commonly used today and may therefore be obvious,
> but it does satisfy similar privacy requirements. The sender interacts wi=
th
> the recipient each time they want to make a payment, and requests a new
> address. The main downside is that it requires interaction for every sing=
le
> payment.
>
>
>
> OPEN QUESTIONS
>
>
> Exactly how slow are the required database lookups? Is there a better
> approach?
>
> Is there any way to make light client support more viable?
>
> What is preferred =E2=80=93 single input tweaking (revealing an input to =
the
> recipient) or using all inputs (increased coinjoin complexity)?
>
> Are there any security issues with the proposed cryptography?
>
> In general, compared to alternatives, is this scheme worth the added
> complexity?
>
>
>
> ACKNOWLEDGEMENTS
>
>
> Thanks to Kixunil, Calvin Kim, and Jonas Nick, holihawt and Lloyd Fournie=
r
> for their help/comments, as well as all the authors of previous schemes.
> Any mistakes are my own.
>
>
>
> REFERENCES
>
>
> [1] Stealth Payments, Peter Todd:
> https://github.com/genjix/bips/blob/master/bip-stealth.mediawiki =E2=86=
=A9=EF=B8=8E
>
> [2] BIP47 payment codes, Justus Ranvier:
> https://github.com/bitcoin/bips/blob/master/bip-0047.mediawiki
>
> [3] Reusable taproot addresses, Kixunil:
> https://gist.github.com/Kixunil/0ddb3a9cdec33342b97431e438252c0a
>
> [4] BIP32 HD keys, Pieter Wuille:
> https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
>
> [5] 2020-01-23 ##taproot-bip-review, starting at 18:25:
> https://gnusha.org/taproot-bip-review/2020-01-23.log
>
> [6] Blind Diffie-Hellman Key Exchange, David Wagner:
> https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000d4110305db5ca628
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div dir=3D"auto">Hi Ruben,=C2=A0</div><div dir=3D"auto">=
<br></div><div dir=3D"auto">Very interesting protocol. This reminds me of h=
ow monero stealth addresses work, which gives monero the same downsides reg=
arding light clients (among other things). I was a bit confused by the foll=
owing:</div><div dir=3D"auto"><br></div><div>&gt;=C2=A0<span style=3D"font-=
size:12.8px">without requiring any interaction or on-chain overhead</span><=
/div><div dir=3D"auto"><span style=3D"font-size:12.8px"><br></span></div><d=
iv dir=3D"auto">After reading through, I have to assume it was rather misle=
ading to say &quot;no on-chain overhead&quot;. This still requires an on-ch=
ain transaction to be sent to the tweaked address, I believe. Maybe it woul=
d have been more accurate to say no *extra* on chain overhead (over a norma=
l transaction)?</div><div dir=3D"auto"><br></div><div dir=3D"auto">It seems=
 the primary benefit of this is privacy for the recipient. To that end, it =
seems like a pretty useful protocol. It&#39;s definitely a level of privacy=
 one would only care about if they might receive a lot money related to tha=
t address. However of course someone might not know they&#39;ll receive an =
amount of money they want to be private until they receive it. So the inabi=
lity to easily do this without a full node is slightly less than ideal. But=
 it&#39;s another good reason to run a full node.</div><div dir=3D"auto"><b=
r></div><div dir=3D"auto">Perhaps there could be a standard that can identi=
fy tweaked address, such that only those addresses can be downloaded and ch=
ecked by light clients. It reduces the anonymity set a bit, but it would pr=
obably still be sufficient.=C2=A0</div><div dir=3D"auto"><br></div><div dir=
=3D"auto"><br><br><div class=3D"gmail_quote" dir=3D"auto"><div dir=3D"ltr" =
class=3D"gmail_attr">On Mon, Mar 28, 2022, 10:29 Ruben Somsen via bitcoin-d=
ev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_=
blank" rel=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wro=
te:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hi all,<br><br=
>I&#39;m publishing a new scheme for private non-interactive address genera=
tion without on-chain overhead. It has upsides as well as downsides, so I s=
uspect the main discussion will revolve around whether this is worth pursui=
ng or not. There is a list of open questions at the end.<br><br>I added the=
 full write-up in plain text below, though I recommend reading the gist for=
 improved formatting and in order to benefit from potential future edits: <=
a href=3D"https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb4=
6b8" rel=3D"noreferrer noreferrer" target=3D"_blank">https://gist.github.co=
m/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8</a><br><br>Cheers,<br>Ruben<=
br><br><br><br>Silent Payments<br><br>Receive private payments from anyone =
on a single static address without requiring any interaction or on-chain ov=
erhead<br><br><br><br>OVERVIEW<br><br><br>The recipient generates a so-call=
ed silent payment address and makes it publicly known. The sender then take=
s a public key from one of their chosen inputs for the payment, and uses it=
 to derive a shared secret that is then used to tweak the silent payment ad=
dress. The recipient detects the payment by scanning every transaction in t=
he blockchain.<br><br>Compared to previous schemes[1], this scheme avoids u=
sing the Bitcoin blockchain as a messaging layer[2] and requires no interac=
tion between sender and recipient[3] (other than needing to know the silent=
 payment address). The main downsides are the scanning requirement, the lac=
k of light client support, and the requirement to control your own input(s)=
. An example use case would be private one-time donations.<br><br>While mos=
t of the individual parts of this idea aren=E2=80=99t novel, the resulting =
protocol has never been seriously considered and may be reasonably viable, =
particularly if we limit ourselves to detecting only unspent payments by sc=
anning the UTXO set. We=E2=80=99ll start by describing a basic scheme, and =
then introduce a few improvements.<br><br><br><br>BASIC SCHEME<br><br><br>T=
he recipient publishes their silent payment address, a single 32 byte publi=
c key:<br>X =3D x*G<br><br>The sender picks an input containing a public ke=
y:<br>I =3D i*G<br><br>The sender tweaks the silent payment address with th=
e public key of their input: <br>X&#39; =3D hash(i*X)*G + X<br><br>Since i*=
X =3D=3D x*I (Diffie-Hellman Key Exchange), the recipient can detect the pa=
yment by calculating hash(x*I)*G + X for each input key I in the blockchain=
 and seeing if it matches an output in the corresponding transaction.<br><b=
r><br><br>IMPROVEMENTS<br><br><br>UTXO set scanning<br><br>If we forgo dete=
ction of historic transactions and only focus on the current balance, we ca=
n limit the protocol to only scanning the transactions that are part of the=
 UTXO set when restoring from backup, which may be faster.<br><br>Jonas Nic=
k was kind enough to go through the numbers and run a benchmark of hash(x*I=
)*G + X on his 3.9GHz Intel=C2=AE Core=E2=84=A2 i7-7820HQ CPU, which took r=
oughly 72 microseconds per calculation on a single core. The UTXO set curre=
ntly has 80 million entries, the average transaction has 2.3 inputs, which =
puts us at 2.3*80000000*72/1000/1000/60 =3D 221 minutes for a single core (=
under 2 hours for two cores).<br><br>What these numbers do not take into ac=
count is database lookups. We need to fetch the transaction of every UTXO, =
as well as every transaction for every subsequent input in order to extract=
 the relevant public key, resulting in (1+2.3)*80000000 =3D 264 million loo=
kups. How slow this is and what can be done to improve it is an open questi=
on.<br><br>Once we=E2=80=99re at the tip, every new unspent output will hav=
e to be scanned. It=E2=80=99s theoretically possible to scan e.g. once a da=
y and skip transactions with fully spent outputs, but that would probably n=
ot be worth the added complexity. If we only scan transactions with taproot=
 outputs, we can further limit our efforts, but this advantage is expected =
to dissipate once taproot use becomes more common.<br><br><br>Variant using=
 all inputs<br><br>Instead of tweaking the silent payment address with one =
input, we could instead tweak it with the combination of all input keys of =
a transaction. The benefit is that this further lowers the scanning cost, s=
ince now we only need to calculate one tweak per transaction, instead of on=
e tweak per input, which is roughly half the work, though database lookups =
remain unaffected.<br><br>The downside is that if you want to combine your =
inputs with those of others (i.e. coinjoin), every participant has to be wi=
lling to assist you in following the Silent Payment protocol in order to le=
t you make your payment. There are also privacy considerations which are di=
scussed in the =E2=80=9CPreventing input linkage=E2=80=9D section.<br><br>C=
oncretely, if there are three inputs (I1, I2, I3), the scheme becomes: hash=
(i1*X + i2*X + i3*X)*G + X =3D=3D hash(x*(I1+I2+I3))*G + X.<br><br><br>Scan=
ning key<br><br>We can extend the silent payment address with a scanning ke=
y, which allows for separation of detecting and spending payments. We redef=
ine the silent payment address as the concatenation of X_scan, X_spend, and=
 derivation becomes X&#39; =3D hash(i*X_scan)*G + X_spend. This allows your=
 internet-connected node to hold the private key of X_scan to detect incomi=
ng payments, while your hardware wallet controls X_spend to make payments. =
If X_scan is compromised, privacy is lost, but your funds are not.<br><br><=
br>Address reuse prevention<br><br>If the sender sends more than one paymen=
t, and the chosen input has the same key due to address reuse, then the rec=
ipient address will also be the same. To prevent this, we can hash the txid=
 and index of the input, to ensure each address is unique, resulting in X&#=
39; =3D hash(i*X,txid,index)*G + X. Note this would make light client suppo=
rt harder.<br><br><br><br>NOTEWORTHY DETAILS<br><br><br>Light clients<br><b=
r>Light clients cannot easily be supported due to the need for scanning. Th=
e best we could do is give up on address reuse prevention (so we don=E2=80=
=99t require the txid and index), only consider unspent taproot outputs, an=
d download a standardized list of relevant input keys for each block over w=
ifi each night when charging. These input keys can then be tweaked, and the=
 results can be matched against compact block filters. Possible, but not si=
mple.<br><br><br>Effect on BIP32 HD keys<br><br>One side-benefit of silent =
payments is that BIP32 HD keys[4] won=E2=80=99t be needed for address gener=
ation, since every address will automatically be unique. This also means we=
 won=E2=80=99t have to deal with a gap limit.<br><br><br>Different inputs<b=
r><br>While the simplest thing would be to only support one input type (e.g=
. taproot key spend), this would also mean only a subset of users can make =
payments to silent addresses, so this seems undesirable. The protocol shoul=
d ideally support any input containing at least one public key, and simply =
pick the first key if more than one is present.<br><br>Pay-to-(witness-)pub=
lic-key-hash inputs actually end up being easiest to scan, since the public=
 key is present in the input script, instead of the output script of the pr=
evious transaction (which requires one extra transaction lookup).<br><br><b=
r>Signature nonce instead of input key<br><br>Another consideration was to =
tweak the silent payment address with the signature nonce[5], but unfortuna=
tely this breaks compatibility with MuSig2 and MuSig-DN, since in those sch=
emes the signature nonce changes depending on the transaction hash. If we l=
et the output address depend on the nonce, then the transaction hash will c=
hange, causing a circular reference.<br><br><br>Sending wallet compatibilit=
y<br><br>Any wallet that wants to support making silent payments needs to s=
upport a new address format, pick inputs for the payment, tweak the silent =
payment address using the private key of one of the chosen inputs, and then=
 proceed to sign the transaction. The scanning requirement is not relevant =
to the sender, only the recipient.<br><br><br><br>PREVENTING INPUT LINKAGE<=
br><br><br>A potential weakness of Silent Payments is that the input is lin=
ked to the output. A coinjoin transaction with multiple inputs from other u=
sers can normally obfuscate the sender input from the recipient, but Silent=
 Payments reveal that link. This weakness can be mitigated with the =E2=80=
=9Cvariant using all inputs=E2=80=9D, but this variant introduces a differe=
nt weakness =E2=80=93 you now require all other coinjoin users to tweak the=
 silent payment address, which means you=E2=80=99re revealing the intended =
recipient to them.<br><br>Luckily, a blinding scheme[6] exists that allows =
us to hide the silent payment address from the other participants. Concrete=
ly, let=E2=80=99s say there are two inputs, I1 and I2, and the latter one i=
s ours. We add a secret blinding factor to the silent payment address, X + =
blinding_factor*G =3D X&#39;, then we receive X1&#39; =3D i1*X&#39; (togeth=
er with a DLEQ to prove correctness, see full write-up[6]) from the owner o=
f the first input and remove the blinding factor with X1&#39; - blinding_fa=
ctor*I1 =3D X1 (which is equal to i1*X). Finally, we calculate the tweaked =
address with hash(X1 + i2*X)*G + X. The recipient can simply recognize the =
payment with hash(x*(I1+I2))*G + X. Note that the owner of the first input =
cannot reconstruct the resulting address because they don=E2=80=99t know i2=
*X.<br><br>The blinding protocol above solves our coinjoin privacy concerns=
 (at the expense of more interaction complexity), but we=E2=80=99re left wi=
th one more issue =E2=80=93 what if you want to make a silent payment, but =
you control none of the inputs (e.g. sending from an exchange)? In this sce=
nario we can still utilize the blinding protocol, but now the third party s=
ender can try to uncover the intended recipient by brute forcing their inpu=
ts on all known silent payment addresses (i.e. calculate hash(i*X)*G + X fo=
r every publicly known X). While this is computationally expensive, it=E2=
=80=99s by no means impossible. No solution is known at this time, so as it=
 stands this is a limitation of the protocol =E2=80=93 the sender must cont=
rol one of the inputs in order to be fully private.<br><br><br><br>COMPARIS=
ON<br><br><br>These are the most important protocols that provide similar f=
unctionality with slightly different tradeoffs. All of them provide fresh a=
ddress generation and are compatible with one-time seed backups. The main b=
enefits of the protocols listed below are that there is no scanning require=
ment, better light client support, and they don=E2=80=99t require control o=
ver the inputs of the transaction.<br><br><br>Payment code sharing<br><br>T=
his is BIP47[2]. An OP_RETURN message is sent on-chain to the recipient to =
establish a shared secret prior to making payments. Using the blockchain as=
 a messaging layer like this is generally considered an inefficient use of =
on-chain resources. This concern can theoretically be alleviated by using o=
ther means of communicating, but data availability needs to be guaranteed t=
o ensure the recipient doesn=E2=80=99t lose access to the funds. Another co=
ncern is that the input(s) used to establish the shared secret may leak pri=
vacy if not kept separate.<br><br><br>Xpub sharing<br><br>Upon first paymen=
t, hand out an xpub instead of an address in order to enable repeat payment=
s. I believe Kixunil=E2=80=99s recently published scheme[3] is equivalent t=
o this and could be implemented with relative ease. It=E2=80=99s unclear ho=
w practical this protocol is, as it assumes sender and recipient are able t=
o interact once, yet subsequent interaction is impossible.<br><br><br>Regul=
ar address sharing<br><br>This is how Bitcoin is commonly used today and ma=
y therefore be obvious, but it does satisfy similar privacy requirements. T=
he sender interacts with the recipient each time they want to make a paymen=
t, and requests a new address. The main downside is that it requires intera=
ction for every single payment.<br><br><br><br>OPEN QUESTIONS<br><br><br>Ex=
actly how slow are the required database lookups? Is there a better approac=
h?<div><br>Is there any way to make light client support more viable?<br><b=
r>What is preferred =E2=80=93 single input tweaking (revealing an input to =
the recipient) or using all inputs (increased coinjoin complexity)?<br><br>=
Are there any security issues with the proposed cryptography?<br><br>In gen=
eral, compared to alternatives, is this scheme worth the added complexity?<=
br><br><br><br>ACKNOWLEDGEMENTS<br><br><br>Thanks to Kixunil, Calvin Kim, a=
nd Jonas Nick, holihawt and Lloyd Fournier for their help/comments, as well=
 as all the authors of previous schemes. Any mistakes are my own.<br><br><b=
r><br>REFERENCES<br><br><br>[1] Stealth Payments, Peter Todd: <a href=3D"ht=
tps://github.com/genjix/bips/blob/master/bip-stealth.mediawiki" rel=3D"nore=
ferrer noreferrer" target=3D"_blank">https://github.com/genjix/bips/blob/ma=
ster/bip-stealth.mediawiki</a> =E2=86=A9=EF=B8=8E<br><br>[2] BIP47 payment =
codes, Justus Ranvier: <a href=3D"https://github.com/bitcoin/bips/blob/mast=
er/bip-0047.mediawiki" rel=3D"noreferrer noreferrer" target=3D"_blank">http=
s://github.com/bitcoin/bips/blob/master/bip-0047.mediawiki</a><br><br>[3] R=
eusable taproot addresses, Kixunil: <a href=3D"https://gist.github.com/Kixu=
nil/0ddb3a9cdec33342b97431e438252c0a" rel=3D"noreferrer noreferrer" target=
=3D"_blank">https://gist.github.com/Kixunil/0ddb3a9cdec33342b97431e438252c0=
a</a><br><br>[4] BIP32 HD keys, Pieter Wuille: <a href=3D"https://github.co=
m/bitcoin/bips/blob/master/bip-0032.mediawiki" rel=3D"noreferrer noreferrer=
" target=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0032.me=
diawiki</a><br><br>[5] 2020-01-23 ##taproot-bip-review, starting at 18:25: =
<a href=3D"https://gnusha.org/taproot-bip-review/2020-01-23.log" rel=3D"nor=
eferrer noreferrer" target=3D"_blank">https://gnusha.org/taproot-bip-review=
/2020-01-23.log</a><br><br>[6] Blind Diffie-Hellman Key Exchange, David Wag=
ner: <a href=3D"https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67=
baf140406" rel=3D"noreferrer noreferrer" target=3D"_blank">https://gist.git=
hub.com/RubenSomsen/be7a4760dd4596d06963d67baf140406</a><br></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" rel=3D"noreferrer =
noreferrer" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">https://lists.li=
nuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div></div></div>

--000000000000d4110305db5ca628--