path: root/cb/106d4d7d348bc17c00c60e2d86b44a51115101

Return-Path: <rsomsen@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 5A641C0012
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 15:36:37 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 30B4940399
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 15:36:37 +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: smtp2.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id F7IH5ucPt3ct
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 15:36:35 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yb1-xb2c.google.com (mail-yb1-xb2c.google.com
 [IPv6:2607:f8b0:4864:20::b2c])
 by smtp2.osuosl.org (Postfix) with ESMTPS id CEEA84002B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 15:36:34 +0000 (UTC)
Received: by mail-yb1-xb2c.google.com with SMTP id x20so32073148ybi.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Mar 2022 08:36:34 -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
 :cc; bh=hoDKYuZFQWjs70v9rVDjEV+nsIYGK1Jo7jliabn1NqY=;
 b=lM8CFjNQaZX0inTtf/7GLhsLBYDaP0168LgiAqoVm2f0SZ5tl1MmoOHCR8BTpWb4sF
 Fdqabl3kZsCZkw11qC4Qv0BBkyLZBMzKIuYFZ6c5ktHCKW6QQK5IXXpmFz0aCxv5UyiT
 lurVwnd19nB0p0ponkXOtoSI5UMZgz/3QKwpF6t6GNxCxPtm0ENI10Bbm0YkIXchew14
 ibCLKef4MFXAguDsKZ6x4lQtvpjhZ+X+IYGO+cMLxV6CrKNNA2+L8wTCoK8xSnSvaP1Q
 VZK4T7xQWMITmv5dIV16qlv+FH/KdBQ4xxpn5FHHJIPuqtuJFYM28ZY9tFi4ggtmhsyf
 MS3Q==
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:cc;
 bh=hoDKYuZFQWjs70v9rVDjEV+nsIYGK1Jo7jliabn1NqY=;
 b=Va88bocs0FWklU5n9ZY/d79CpkqJJvdjWQikNEyDwB4YDfTkiqI3FUw4z/jhXcSJ8+
 pIi/1VVMlIRFtBNcWe60eu8sCj2hD47fe970gNjds1l8CbGnP63ecjd65w+Sn6V/enLP
 sB2rH23OEfy5SDFzeUJl61Oz8D7/jiYmn1dWHkMpHzzWc6D8uEdFLFRvecl8EHHLHcZE
 6LAd05FKGCL2LVsKnnS45YEP6cqZkmBz3OkW+Je17PFh8Wljc2ocDNScvj4JrNBQBeQZ
 0xGiwe9hrvCQCcXSOo5y0YGIlJDo0/hhDl52lk8AW/dTOc1CTDfuI+wntSE6Hrzdx7Tx
 yQiA==
X-Gm-Message-State: AOAM531WSTQGuT4lVpOWCmeGTxlOxEFHdbQUi/6CLljDqsMQoBfYU0ET
 tu0tQANY1+gd+Sd87Jl/SKzmXu1op2oeaCI2R+4=
X-Google-Smtp-Source: ABdhPJw9G527ROt4QY5PrmJxqsSke2Yj9hvxHwTVOMiEGyXiUFusg+Yzo1EotC5tcXaSVxTvT0GFJuKaoC8gI9dEjSY=
X-Received: by 2002:a25:b908:0:b0:61d:75f8:6eff with SMTP id
 x8-20020a25b908000000b0061d75f86effmr28295534ybj.641.1648568193301; Tue, 29
 Mar 2022 08:36:33 -0700 (PDT)
MIME-Version: 1.0
References: <CAPv7TjbXm953U2h+-12MfJ24YqOM5Kcq77_xFTjVK+R2nf-nYg@mail.gmail.com>
 <CAGpPWDa1QfN53a_-9Dhee58T6_zk3S0bZJhZbiDpXndzzv0nTA@mail.gmail.com>
In-Reply-To: <CAGpPWDa1QfN53a_-9Dhee58T6_zk3S0bZJhZbiDpXndzzv0nTA@mail.gmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Tue, 29 Mar 2022 17:36:13 +0200
Message-ID: <CAPv7TjZrFH6Hjm46N2ikWdoP0cAAQqu=jRKVA5iiSLJ50XNWDA@mail.gmail.com>
To: Billy <fresheneesz@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000008cc05805db5d3157"
X-Mailman-Approved-At: Tue, 29 Mar 2022 15:37:28 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 15:36:37 -0000

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

Hi Billy,

Thanks for taking a look.

>Maybe it would have been more accurate to say no *extra* on chain overhead

I can see how it can be misinterpreted. I updated the gist to be more
specific.

>primary benefit of this is privacy for the recipient

Fair, but just wanted to note the sender can get in trouble too if they
send money to e.g. blacklisted addresses.

>there could be a standard that [...] reduces the anonymity set a bit

This has occurred to me but I am reluctant to make that trade-off. It seems
best to first see how well this can be optimized without resorting to
reducing anonymity, and it's hard to analyze exactly how impactful the
anonymity degradation is (I suspect it's worse than you think because it
can help strengthen existing heuristics about output ownership).

Cheers,
Ruben



On Tue, Mar 29, 2022 at 4:57 PM Billy <fresheneesz@gmail.com> wrote:

> Hi Ruben,
>
> Very interesting protocol. This reminds me of how monero stealth addresse=
s
> work, which gives monero the same downsides regarding light clients (amon=
g
> 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 tha=
t
> 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 relat=
ed
> 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
>> generation without on-chain overhead. It has upsides as well as downside=
s,
>> so I suspect the main discussion will revolve around whether this is wor=
th
>> 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 readin=
g
>> 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 cho=
sen
>> inputs for the payment, and uses it to derive a shared secret that is th=
en
>> used to tweak the silent payment address. The recipient detects the paym=
ent
>> 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). =
An
>> example use case would be private one-time donations.
>>
>> While most of the individual parts of this idea aren=E2=80=99t novel, th=
e
>> 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 descri=
bing 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 thei=
r
>> input:
>> X' =3D hash(i*X)*G + X
>>
>> Since i*X =3D=3D x*I (Diffie-Hellman Key Exchange), the recipient can de=
tect
>> 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 sing=
le
>> 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 =
and
>> 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 =
scanned.
>> It=E2=80=99s theoretically possible to scan e.g. once a day and skip tra=
nsactions
>> 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 o=
nce
>> 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 p=
er
>> 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 yo=
u
>> in following the Silent Payment protocol in order to let you make your
>> payment. There are also privacy considerations which are discussed in th=
e
>> =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
>> allows for separation of detecting and spending payments. We redefine th=
e
>> 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 =
not.
>>
>>
>> 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 t=
he
>> 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.
>> The 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 =
not
>> simple.
>>
>>
>> Effect on BIP32 HD keys
>>
>> One side-benefit of silent payments is that BIP32 HD keys[4] won=E2=80=
=99t 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 th=
e
>> 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 MuS=
ig2
>> and MuSig-DN, since in those schemes the signature nonce changes dependi=
ng
>> on the transaction hash. If we let the output address depend on the nonc=
e,
>> 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 paym=
ent
>> address using the private key of one of the chosen inputs, and then proc=
eed
>> 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
>> the output. A coinjoin transaction with multiple inputs from other users
>> 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 different weakn=
ess =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.
>>
>> Luckily, a blinding scheme[6] exists that allows us to hide the silent
>> payment address from the other participants. Concretely, let=E2=80=99s s=
ay 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 blind=
ing
>> 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. Th=
e
>> recipient can simply recognize the payment with hash(x*(I1+I2))*G + X. N=
ote
>> that the owner of the first input cannot reconstruct the resulting addre=
ss
>> 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 non=
e 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 know=
n
>> silent payment addresses (i.e. calculate hash(i*X)*G + X for every publi=
cly
>> known X). While this is computationally expensive, it=E2=80=99s by no me=
ans
>> 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 =
inputs in
>> order to be fully private.
>>
>>
>>
>> COMPARISON
>>
>>
>> These are the most important protocols that provide similar functionalit=
y
>> with slightly different tradeoffs. All of them provide fresh address
>> generation and are compatible with one-time seed backups. The main benef=
its
>> 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 blockch=
ain
>> as a messaging layer like this is generally considered an inefficient us=
e
>> 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 fu=
nds.
>> 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 s=
cheme[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 recipie=
nt
>> 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 w=
ith
>> 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 sin=
gle
>> 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
>> Fournier 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
>>
>

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

<div dir=3D"ltr">Hi Billy,<div><br></div><div>Thanks for taking a look.</di=
v><div><br></div><div>&gt;Maybe it would have been more accurate to say no =
*extra* on chain overhead</div><div><br></div><div>I can see how it can be =
misinterpreted. I updated the gist to be more specific.</div><div><br></div=
><div>&gt;primary benefit of this is privacy for the recipient</div><div><b=
r></div><div>Fair, but just wanted to note the sender can get in trouble to=
o if they send money=C2=A0to e.g. blacklisted addresses.</div><div><br></di=
v><div>&gt;there could be a standard that [...] reduces the anonymity set a=
 bit</div><div><br></div><div>This has occurred to me but I am reluctant to=
 make that trade-off. It seems best to first see how well this can be optim=
ized without resorting to reducing anonymity, and it&#39;s hard to analyze =
exactly how impactful the anonymity degradation is (I suspect it&#39;s wors=
e than you think because it can help strengthen existing heuristics about o=
utput ownership).</div><div><br></div><div>Cheers,</div><div>Ruben</div><di=
v><br></div><div><br></div></div><br><div class=3D"gmail_quote"><div dir=3D=
"ltr" class=3D"gmail_attr">On Tue, Mar 29, 2022 at 4:57 PM Billy &lt;<a hre=
f=3D"mailto:fresheneesz@gmail.com">fresheneesz@gmail.com</a>&gt; wrote:<br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left:1px solid rgb(204,204,204);padding-left:1ex"><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 how monero stealth =
addresses work, which gives monero the same downsides regarding light clien=
ts (among other things). I was a bit confused by the following:</div><div d=
ir=3D"auto"><br></div><div>&gt;=C2=A0<span style=3D"font-size:12.8px">witho=
ut requiring any interaction or on-chain overhead</span></div><div dir=3D"a=
uto"><span style=3D"font-size:12.8px"><br></span></div><div dir=3D"auto">Af=
ter reading through, I have to assume it was rather misleading to say &quot=
;no on-chain overhead&quot;. This still requires an on-chain transaction to=
 be sent to the tweaked address, I believe. Maybe it would have been more a=
ccurate to say no *extra* on chain overhead (over a normal transaction)?</d=
iv><div dir=3D"auto"><br></div><div dir=3D"auto">It seems the primary benef=
it of this is privacy for the recipient. To that end, it seems like a prett=
y useful protocol. It&#39;s definitely a level of privacy one would only ca=
re about if they might receive a lot money related to that address. However=
 of course someone might not know they&#39;ll receive an amount of money th=
ey 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&#39;s another =
good reason to run a full node.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">Perhaps there could be a standard that can identify tweaked addre=
ss, such that only those addresses can be downloaded and checked by light c=
lients. It reduces the anonymity set a bit, but it would probably still be =
sufficient.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto"><br><b=
r><div class=3D"gmail_quote" dir=3D"auto"><div dir=3D"ltr" class=3D"gmail_a=
ttr">On Mon, Mar 28, 2022, 10:29 Ruben Somsen via bitcoin-dev &lt;<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" rel=3D"noreferrer" target=
=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><=
blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l=
eft:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">Hi all,<b=
r><br>I&#39;m publishing a new scheme for private non-interactive address g=
eneration without on-chain overhead. It has upsides as well as downsides, s=
o I suspect the main discussion will revolve around whether this is worth p=
ursuing or not. There is a list of open questions at the end.<br><br>I adde=
d the full write-up in plain text below, though I recommend reading the gis=
t for improved formatting and in order to benefit from potential future edi=
ts: <a href=3D"https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec=
6dbb46b8" rel=3D"noreferrer noreferrer" target=3D"_blank">https://gist.gith=
ub.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8</a><br><br>Cheers,<br>R=
uben<br><br><br><br>Silent Payments<br><br>Receive private payments from an=
yone on a single static address without requiring any interaction or on-cha=
in overhead<br><br><br><br>OVERVIEW<br><br><br>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 chosen inputs for the payment, and us=
es it to derive a shared secret that is then used to tweak the silent payme=
nt address. The recipient detects the payment by scanning every transaction=
 in the blockchain.<br><br>Compared to previous schemes[1], this scheme avo=
ids using the Bitcoin blockchain as a messaging layer[2] and requires no in=
teraction between sender and recipient[3] (other than needing to know the s=
ilent payment address). The main downsides are the scanning requirement, th=
e lack of light client support, and the requirement to control your own inp=
ut(s). An example use case would be private one-time donations.<br><br>Whil=
e most of the individual parts of this idea aren=E2=80=99t novel, the resul=
ting protocol has never been seriously considered and may be reasonably via=
ble, particularly if we limit ourselves to detecting only unspent payments =
by scanning 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>The recipient publishes their silent payment address, a single 32 byte =
public key:<br>X =3D x*G<br><br>The sender picks an input containing a publ=
ic key:<br>I =3D i*G<br><br>The sender tweaks the silent payment address wi=
th the public key of their input: <br>X&#39; =3D hash(i*X)*G + X<br><br>Sin=
ce i*X =3D=3D x*I (Diffie-Hellman Key Exchange), the recipient can detect t=
he payment by calculating hash(x*I)*G + X for each input key I in the block=
chain and seeing if it matches an output in the corresponding transaction.<=
br><br><br><br>IMPROVEMENTS<br><br><br>UTXO set scanning<br><br>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 o=
f the UTXO set when restoring from backup, which may be faster.<br><br>Jona=
s Nick was kind enough to go through the numbers and run a benchmark of has=
h(x*I)*G + X on his 3.9GHz Intel=C2=AE Core=E2=84=A2 i7-7820HQ CPU, which t=
ook roughly 72 microseconds per calculation on a single core. The UTXO set =
currently has 80 million entries, the average transaction has 2.3 inputs, w=
hich puts us at 2.3*80000000*72/1000/1000/60 =3D 221 minutes for a single c=
ore (under 2 hours for two cores).<br><br>What these numbers do not take in=
to account is database lookups. We need to fetch the transaction of every U=
TXO, as well as every transaction for every subsequent input in order to ex=
tract the relevant public key, resulting in (1+2.3)*80000000 =3D 264 millio=
n lookups. How slow this is and what can be done to improve it is an open q=
uestion.<br><br>Once we=E2=80=99re at the tip, every new unspent output wil=
l have to be scanned. It=E2=80=99s theoretically possible to scan e.g. once=
 a day and skip transactions with fully spent outputs, but that would proba=
bly not be worth the added complexity. If we only scan transactions with ta=
proot outputs, we can further limit our efforts, but this advantage is expe=
cted 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 key=
s of a transaction. The benefit is that this further lowers the scanning co=
st, since now we only need to calculate one tweak per transaction, instead =
of one tweak per input, which is roughly half the work, though database loo=
kups 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 willing to assist you in following the Silent Payment protocol in order =
to let you make your payment. There are also privacy considerations which a=
re discussed in the =E2=80=9CPreventing input linkage=E2=80=9D section.<br>=
<br>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.<br><br><br=
>Scanning key<br><br>We can extend the silent payment address with a scanni=
ng key, which allows 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&#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 i=
ncoming payments, while your hardware wallet controls X_spend to make payme=
nts. 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 p=
ayment, and the chosen input has the same key due to address reuse, then th=
e recipient 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 i=
n X&#39; =3D hash(i*X,txid,index)*G + X. Note this would make light client =
support harder.<br><br><br><br>NOTEWORTHY DETAILS<br><br><br>Light clients<=
br><br>Light clients cannot easily be supported due to the need for scannin=
g. The 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 outpu=
ts, 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, a=
nd the results can be matched against compact block filters. Possible, but =
not simple.<br><br><br>Effect on BIP32 HD keys<br><br>One side-benefit of s=
ilent payments is that BIP32 HD keys[4] won=E2=80=99t be needed for address=
 generation, since every address will automatically be unique. This also me=
ans we won=E2=80=99t have to deal with a gap limit.<br><br><br>Different in=
puts<br><br>While the simplest thing would be to only support one input typ=
e (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 s=
imply pick the first key if more than one is present.<br><br>Pay-to-(witnes=
s-)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).<br>=
<br><br>Signature nonce instead of input key<br><br>Another consideration w=
as to tweak the silent payment address with the signature nonce[5], but unf=
ortunately this breaks compatibility with MuSig2 and MuSig-DN, since in tho=
se schemes the signature nonce changes depending on the transaction hash. I=
f we let the output address depend on the nonce, then the transaction hash =
will change, causing a circular reference.<br><br><br>Sending wallet compat=
ibility<br><br>Any wallet that wants to support making silent payments need=
s to support a new address format, pick inputs for the payment, tweak the s=
ilent payment address using the private key of one of the chosen inputs, an=
d then proceed to sign the transaction. The scanning requirement is not rel=
evant to the sender, only the recipient.<br><br><br><br>PREVENTING INPUT LI=
NKAGE<br><br><br>A potential weakness of Silent Payments is that the input =
is linked to the output. A coinjoin transaction with multiple inputs from o=
ther users 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 d=
ifferent weakness =E2=80=93 you now require all other coinjoin users to twe=
ak the silent payment address, which means you=E2=80=99re revealing the int=
ended recipient to them.<br><br>Luckily, a blinding scheme[6] exists that a=
llows us to hide the silent payment address from the other participants. Co=
ncretely, let=E2=80=99s say 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&#39;, then we receive X1&#39; =3D i1*X&#39; (=
together with a DLEQ to prove correctness, see full write-up[6]) from the o=
wner of the first input and remove the blinding factor with X1&#39; - blind=
ing_factor*I1 =3D X1 (which is equal to i1*X). Finally, we calculate the tw=
eaked address with hash(X1 + i2*X)*G + X. The recipient can simply recogniz=
e 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 k=
now i2*X.<br><br>The blinding protocol above solves our coinjoin privacy co=
ncerns (at the expense of more interaction complexity), but we=E2=80=99re l=
eft 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 th=
is scenario we can still utilize the blinding protocol, but now the third p=
arty sender can try to uncover the intended recipient by brute forcing thei=
r inputs on all known silent payment addresses (i.e. calculate hash(i*X)*G =
+ X for every publicly known X). While this is computationally expensive, i=
t=E2=80=99s by no means impossible. No solution is known at this time, so a=
s it stands this is a limitation of the protocol =E2=80=93 the sender must =
control one of the inputs in order to be fully private.<br><br><br><br>COMP=
ARISON<br><br><br>These are the most important protocols that provide simil=
ar functionality with slightly different tradeoffs. All of them provide fre=
sh address generation and are compatible with one-time seed backups. The ma=
in benefits of the protocols listed below are that there is no scanning req=
uirement, better light client support, and they don=E2=80=99t require contr=
ol over the inputs of the transaction.<br><br><br>Payment code sharing<br><=
br>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 blockchai=
n as a messaging layer like this is generally considered an inefficient use=
 of on-chain resources. This concern can theoretically be alleviated by usi=
ng other means of communicating, but data availability needs to be guarante=
ed to ensure the recipient doesn=E2=80=99t lose access to the funds. Anothe=
r concern is that the input(s) used to establish the shared secret may leak=
 privacy if not kept separate.<br><br><br>Xpub sharing<br><br>Upon first pa=
yment, hand out an xpub instead of an address in order to enable repeat pay=
ments. I believe Kixunil=E2=80=99s recently published scheme[3] is equivale=
nt to this and could be implemented with relative ease. It=E2=80=99s unclea=
r how practical this protocol is, as it assumes sender and recipient are ab=
le to interact once, yet subsequent interaction is impossible.<br><br><br>R=
egular address sharing<br><br>This is how Bitcoin is commonly used today an=
d may therefore be obvious, but it does satisfy similar privacy requirement=
s. The sender interacts with the recipient each time they want to make a pa=
yment, and requests a new address. The main downside is that it requires in=
teraction for every single payment.<br><br><br><br>OPEN QUESTIONS<br><br><b=
r>Exactly how slow are the required database lookups? Is there a better app=
roach?<div><br>Is there any way to make light client support more viable?<b=
r><br>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=
 general, compared to alternatives, is this scheme worth the added complexi=
ty?<br><br><br><br>ACKNOWLEDGEMENTS<br><br><br>Thanks to Kixunil, Calvin Ki=
m, and 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><b=
r><br><br>REFERENCES<br><br><br>[1] Stealth Payments, Peter Todd: <a href=
=3D"https://github.com/genjix/bips/blob/master/bip-stealth.mediawiki" rel=
=3D"noreferrer noreferrer" target=3D"_blank">https://github.com/genjix/bips=
/blob/master/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/b=
lob/master/bip-0047.mediawiki" rel=3D"noreferrer noreferrer" target=3D"_bla=
nk">https://github.com/bitcoin/bips/blob/master/bip-0047.mediawiki</a><br><=
br>[3] Reusable taproot addresses, Kixunil: <a href=3D"https://gist.github.=
com/Kixunil/0ddb3a9cdec33342b97431e438252c0a" rel=3D"noreferrer noreferrer"=
 target=3D"_blank">https://gist.github.com/Kixunil/0ddb3a9cdec33342b97431e4=
38252c0a</a><br><br>[4] BIP32 HD keys, Pieter Wuille: <a href=3D"https://gi=
thub.com/bitcoin/bips/blob/master/bip-0032.mediawiki" rel=3D"noreferrer nor=
eferrer" target=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-=
0032.mediawiki</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"noreferrer noreferrer" target=3D"_blank">https://gnusha.org/taproot-bip=
-review/2020-01-23.log</a><br><br>[6] Blind Diffie-Hellman Key Exchange, Da=
vid Wagner: <a href=3D"https://gist.github.com/RubenSomsen/be7a4760dd4596d0=
6963d67baf140406" rel=3D"noreferrer noreferrer" target=3D"_blank">https://g=
ist.github.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>
</blockquote></div>

--0000000000008cc05805db5d3157--