Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id C51E5C0012 for ; Wed, 30 Mar 2022 16:09:45 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 9A853404AF for ; Wed, 30 Mar 2022 16:09:45 +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 hWSXb8uHoz6I for ; Wed, 30 Mar 2022 16:09:43 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com [IPv6:2a00:1450:4864:20::536]) by smtp2.osuosl.org (Postfix) with ESMTPS id A96954011C for ; Wed, 30 Mar 2022 16:09:42 +0000 (UTC) Received: by mail-ed1-x536.google.com with SMTP id y10so24989878edv.7 for ; Wed, 30 Mar 2022 09:09:42 -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=OtSGn87Sjg21T1bp+nfxLq/NHGVUcDp2xC4hb75fbP8=; b=aVGM6bQmkg0GS69wIu127KoO6jRJzDw98gkgTsaMve0wJqTxbFeI0eVws9lRan3L2J SsZnspuPp93XR6whLawg7ZJeSoWL0UPCYtVlV0mRltZaCLDbBr2Dp+05QqDlsEdd/30Y xfkUmvCOlvoA40uVsoNHqQ/tshkBhbdle8vh7dBtTBHnv8xfor1tkkWPj2pCTvBl53va wn6Z/FJ0oNFwFGub/eLvmjauBMxmLd8TuSbiNJOXeMmR2ISgAupz+uvYcVKKmNnbJhUP 74SxRyn96nmSNEO8TvOFbrugS5A+RgBp8bMLH7r2dVR4Q/fUcbi06yKKFwm/t4KJ0wgQ TszQ== 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=OtSGn87Sjg21T1bp+nfxLq/NHGVUcDp2xC4hb75fbP8=; b=SIvT18W9vJLuYFiR6VT3FgqrlLy4F5zdFayKorAcM19DlzgqBu25ivITjaHvj0uA9q f1kxrE+sGhasfdIhbty7Sq8PtDZ3SzKoGBhg2UiRinNlixcsDqE3YubyzHDCHWkh5b51 QaYCOE0H26nCx17vILm0cyuQtdDB/3ZsiPRogix2T3UKYL2ucuM5u6/I2RnIaUlfepbc CuDcYTLtaTn8Uuh5/luuaRwMmLgOI+HiBW7qkDn8A3YWcBKXR7k5nYIbhg2gLDVQLDOP 5mTgjTHSZq9lQacMiD3TAcQYNlVrvCXs73XtV4Kn4ynJYYdb4KYKoTH7pFkZRk9P/3Yj OaPg== X-Gm-Message-State: AOAM533MjQTOwoQ/QF8o92siC7Hj+fi31aW0Ydd9aT3W0LjRSILXlxMs kxqjEQDpTJSBfFqGsrFUmdLFbhEcseFLtDuG/95w2wrUMDY= X-Google-Smtp-Source: ABdhPJx2dEK846sphjAHl62UYk/m3F9aTpzRx/rmmM58qB0FSwMkw5UH5QL1yA6lxt4Q2+WKgr1bD6KnSZuMseiYV24= X-Received: by 2002:a05:6402:1742:b0:419:2707:747a with SMTP id v2-20020a056402174200b004192707747amr11654958edx.238.1648656580623; Wed, 30 Mar 2022 09:09:40 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Billy Date: Wed, 30 Mar 2022 11:09:22 -0500 Message-ID: To: Ruben Somsen Content-Type: multipart/alternative; boundary="000000000000d8423a05db71c502" X-Mailman-Approved-At: Wed, 30 Mar 2022 16:23:09 +0000 Cc: Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 30 Mar 2022 16:09:45 -0000 --000000000000d8423a05db71c502 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Ruben, After sending that last night, I realized the solution I had to deprivatizing the sender wouldn't work because it had the same problem of even divisibility in modulo N. And my math was incomplete I think. Also Marco D'Agostini pointed out other errors. And all this assumes that a modulus operator is defined for elliptic curve points in a way that makes these valid, which I'm not sure is true. But here's another try anyway: X' =3D X + i*X*hash((i*X)%N) =3D X + x*I*hash((x*I)%N) item =3D {recipient: X' % N, sender: I%N} // As before. Test for each filter item: (item.recipient - X) % N =3D=3D ( x*item.sender*hash((x*item.sender) % N) ) % N So to muse further about the properties of this, in a block full of taproot sends you might have an upper limit of something like 13,000 transactions. N=3D2^8 would I think mean an 18% collision rate (ie 20% false positive rat= e) because `(1-1/2^8)^13000 =3D 0.82...`. If we were to go with that, each ite= m is 4 bytes (1 byte per point component?) which would mean a 52kb filter without collisions, and an average of 43kb with 18% collisions (which can be removed as dupes). Maybe Golomb-Rice coding could help here as well like it does in the usual compact block filters. And since each collision with an address a client is watching on means downloading a whole block they don't need, maybe 18% collisions is too high, and we want to choose N =3D 2^10 or something to get down to 2% collisions. In any case, all this could be wrong if ECC modulus doesn't work this way. But was interesting to think about anyway. On Wed, Mar 30, 2022 at 12:58 AM Billy wrote: > > the sender can get in trouble too if they send money > > Good point. > > > how well this can be optimized without resorting to reducing anonymity > > Complete shot in the dark, but I wonder if something akin to compact bloc= k > filters could be done to support this case. If, for example, the tweaked > key were defined without hashing, I think something like that could be do= ne: > > X' =3D i*X*G + X =3D x*I*G + X > > Your compact-block-filter-like things could then store a set of each `ite= m > =3D {recipient: X' % N, sender: I%N}`, and a light client would download > this data and do the following to detect a likely payment for each filter > item: > > item.recipient - X%N =3D=3D x*item.sender*G > > You can then scale N to the proper tradeoff between filter size and false > positives. I suppose this might make it possible to deprivitize a tweaked > key by checking to see what non-tweaked keys evenly divide it. Perhaps > that's what hashing was being used to solve. What if we added the shared > diffie hellman secret modulo N to remove this correlation: > > X' =3D i*X*G + X + (i*X)%N =3D x*I*G + X + (x*I)%N > > Then for each `item =3D {recipient: X' % N, sender: I%N}`, we detect via > `item.recipient - X%N =3D=3D x*item.sender*(1+G)`. Is my math right here?= I'm > thinking this should work because (a+b%N)%N =3D=3D (a%N + b%N)%N. > > > > On Tue, Mar 29, 2022 at 10:36 AM Ruben Somsen wrote: > >> 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 wrote: >> >>> 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 lev= el >>> 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 i= t. >>> 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 stil= l 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 downsi= des, >>>> so I suspect the main discussion will revolve around whether this is w= orth >>>> 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 withou= t >>>> requiring any interaction or on-chain overhead >>>> >>>> >>>> >>>> OVERVIEW >>>> >>>> >>>> The recipient generates a so-called silent payment address and makes i= t >>>> publicly known. The sender then takes a public key from one of their c= hosen >>>> inputs for the payment, and uses it to derive a shared secret that is = then >>>> used to tweak the silent payment address. The recipient detects the pa= yment >>>> 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, = the >>>> resulting protocol has never been seriously considered and may be >>>> reasonably viable, particularly if we limit ourselves to detecting onl= y >>>> unspent payments by scanning the UTXO set. We=E2=80=99ll start by desc= ribing 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 >>>> detect 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 i= 7-7820HQ CPU, >>>> which took roughly 72 microseconds per calculation on a single core. T= he >>>> 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 >>>> single 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 transact= ion >>>> 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 i= s 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 b= e >>>> scanned. It=E2=80=99s theoretically possible to scan e.g. once a day a= nd skip >>>> transactions with fully spent outputs, but that would probably not be = worth >>>> the added complexity. If we only scan transactions with taproot output= s, we >>>> can further limit our efforts, but this advantage is expected to dissi= pate >>>> once taproot use becomes more common. >>>> >>>> >>>> Variant using all inputs >>>> >>>> Instead of tweaking the silent payment address with one input, we coul= d >>>> instead tweak it with the combination of all input keys of a transacti= on. >>>> The benefit is that this further lowers the scanning cost, since now w= e >>>> only need to calculate one tweak per transaction, instead of one tweak= per >>>> 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 >>>> 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' =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 ar= e not. >>>> >>>> >>>> Address reuse prevention >>>> >>>> If the sender sends more than one payment, and the chosen input has th= e >>>> same key due to address reuse, then the 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 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, an= d >>>> download a standardized list of relevant input keys for each block ove= r >>>> wifi each night when charging. These input keys can then be tweaked, a= nd >>>> the results can be matched against compact block filters. Possible, bu= t 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 ma= ke >>>> payments to silent addresses, so this seems undesirable. The protocol >>>> should ideally support any input containing at least one public key, a= nd >>>> 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 extr= a >>>> 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 M= uSig2 >>>> and MuSig-DN, since in those schemes the signature nonce changes depen= ding >>>> on the transaction hash. If we let the output address depend on the no= nce, >>>> 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 s= ilent >>>> payment address using the private key of one of the chosen inputs, and= then >>>> proceed to sign the transaction. The scanning requirement is not relev= ant >>>> 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 use= rs >>>> 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 wea= kness =E2=80=93 you >>>> now require all other coinjoin users to tweak the silent payment addre= ss, >>>> 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= 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', >>>> then we receive X1' =3D i1*X' (together with a DLEQ to prove correctne= ss, see >>>> full write-up[6]) from the owner of the first input and remove the bli= nding >>>> 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.= Note >>>> that the owner of the first input cannot reconstruct the resulting add= ress >>>> 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 wi= th one more >>>> issue =E2=80=93 what if you want to make a silent payment, but you con= trol none of >>>> the inputs (e.g. sending from an exchange)? In this scenario we can st= ill >>>> utilize the blinding protocol, but now the third party sender can try = to >>>> uncover the intended recipient by brute forcing their inputs on all kn= own >>>> silent payment addresses (i.e. calculate hash(i*X)*G + X for every pub= licly >>>> 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 control one of th= e inputs 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 f= resh >>>> address generation and are compatible with one-time seed backups. The = main >>>> benefits of the protocols listed below are that there is no scanning >>>> requirement, better light client support, and they don=E2=80=99t requi= re 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 >>>> 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 other means of communicating, but data availabilit= y >>>> needs to be guaranteed to ensure the recipient doesn=E2=80=99t lose ac= cess to the >>>> funds. Another concern is that the input(s) used to establish the shar= ed >>>> 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= scheme[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 recip= ient >>>> 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 with the recipient each time they want to make a payment, an= d >>>> requests a new address. The main downside is that it requires interact= ion >>>> for every single 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 previo= us >>>> 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 >>>> >>> --000000000000d8423a05db71c502 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Ruben,

After sending that last night= , I realized the solution I had to deprivatizing the sender wouldn't wo= rk because it had the same problem of even divisibility in modulo N. And my= math was incomplete I think. Also Marco D'Agostini pointed out other e= rrors. And all this assumes that a modulus operator is defined for elliptic= curve points in a way that makes these valid, which I'm not sure is tr= ue. But here's another try anyway:

X'=C2= =A0=3D=C2=A0X + i*X*hash((i*X)%N)=C2=A0=3D=C2=A0 X + x*I*hash((x*I)%N)

item=C2=A0=3D=C2=A0{rec= ipient: X' % N, sender: I%N} // As before.

Test for each filter item: (item.recipient - X)= % N=C2=A0=3D=3D=C2=A0( x*item.sender*hash((x*item.sender) % N= ) ) % N

So to muse further about the properties of= this, in a block full of taproot sends you might have an upper limit of so= mething like 13,000 transactions. N=3D2^8 would I think mean an 18% collisi= on rate (ie 20% false positive rate) because `(1-1/2^8)^13000 =3D 0.82...`.= If we were to go with that, each item is 4 bytes (1 byte per point compone= nt?) which would mean a 52kb filter without collisions, and an average of 4= 3kb with 18% collisions (which can be removed as dupes). Maybe Golomb-Rice = coding could help here as well like it does in the usual compact block filt= ers. And since each collision with an address a client is watching on means= downloading a whole block they don't need, maybe 18% collisions is too= high, and we want to choose N =3D 2^10 or something to get down to 2% coll= isions.=C2=A0

In any case, all this could be wrong= if ECC modulus doesn't work this way. But was interesting to think abo= ut anyway.=C2=A0

On Wed, Mar 30, 2022 at 12:58 AM Billy <fresheneesz@gmail.com> wrote:
>= =C2=A0 the sender can get in trouble too if they send money

Goo= d point.=C2=A0

> how well this can be optimized= without resorting to reducing anonymity

Complete = shot in the dark, but I wonder if something akin to compact block filters c= ould be done to support this case. If, for example, the tweaked key were de= fined without hashing, I think something like that could be done:

X'=C2=A0 =3D=C2=A0=C2=A0i*X*G + X=C2=A0 =3D=C2=A0 x*I*G=C2=A0+ X
<= div>
Your compact-block-filter-like things could then store a= set of each `item =3D {recipient: X' % = N, sender: I%N}`, and a light client would download this data and do the fo= llowing to detect a likely payment for each filter item:

item.recipient - X%N=C2=A0=3D=3D=C2=A0x*item.sender*G

You can then scale N to the proper tradeoff between= filter size and false positives. I suppose this might make it possible to = deprivitize a tweaked key by checking to see what non-tweaked keys evenly d= ivide it. Perhaps that's what hashing was being used to solve. What if = we added the shared diffie hellman secret modulo N to remove this correlati= on:

X' =3D i*X*= G + X=C2=A0+ (i*X)%N=C2=A0=3D=C2=A0 x*I*G=C2= =A0+ X=C2=A0+ (x*I)%N

Then for each `it= em=C2=A0=3D=C2=A0{recipient: X&= #39; % N, sender: I%N}`, we detect via `item.recipient - X%N=C2=A0=3D= =3D=C2=A0x*item.sender*(1+G)`. Is my math right here? I'm thinki= ng this should work because (a+b%N)%N=C2=A0=3D=3D=C2=A0(a%N=C2= =A0+ b%N)%N.=C2=A0



On Tue, Mar 29, 2022= at 10:36 AM Ruben Somsen <rsomsen@gmail.com> wrote:
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 f= or the recipient

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

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

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

Che= ers,
Ruben



On Tue, Mar 29, 202= 2 at 4:57 PM Billy <fresheneesz@gmail.com> wrote:
Hi Ruben,= =C2=A0

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:

= >=C2=A0without requiring any interactio= n 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 add= ress, I believe. Maybe it would have been more accurate to say no *extra* o= n chain overhead (over a normal transaction)?

It seems the primary benefit of this is privacy for t= he 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 rece= ive a lot money related to that address. However of course someone might no= t 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 n= ode.

Perhaps there could= be a standard that can identify tweaked address, such that only those addr= esses can be downloaded and checked by light clients. It reduces the anonym= ity set a bit, but it would probably still be sufficient.=C2=A0



On Mon, Mar 28, 2022, 10= :29 Ruben Somsen via bitcoin-dev <bitcoin-dev@lists.l= inuxfoundation.org> wrote:
Hi all,

I'm publishing a new = scheme for private non-interactive address generation without on-chain over= head. 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 te= xt below, though I recommend reading the gist for improved formatting and i= n order to benefit from potential future edits: https://gist.github.com/RubenSomsen/c43b79517e7c= b701ebf77eec6dbb46b8

Cheers,
Ruben



Silent Paym= ents

Receive private payments from anyone on a single static address= without requiring any interaction or on-chain overhead



OVER= VIEW


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 uses it to derive a shared secret= that is then used to tweak the silent payment address. The recipient detec= ts the payment by scanning every transaction in the blockchain.

Comp= ared to previous schemes[1], this scheme avoids using the Bitcoin blockchai= n as a messaging layer[2] and requires no interaction between sender and re= cipient[3] (other than needing to know the silent payment address). The mai= n downsides are the scanning requirement, the lack of light client support,= and the requirement to control your own input(s). An example use case woul= d 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 se= riously considered and may be reasonably viable, particularly if we limit o= urselves 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 impro= vements.



BASIC SCHEME


The recipient publishes the= ir 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 inpu= t:
X' =3D hash(i*X)*G + X

Since i*X =3D=3D x*I (Diffie-Hellm= an Key Exchange), the recipient can detect 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 transact= ions and only focus on the current balance, we can limit the protocol to on= ly scanning the transactions that are part of the UTXO set when restoring f= rom backup, which may be faster.

Jonas Nick was kind enough to go th= rough the numbers and run a benchmark of hash(x*I)*G + X on his 3.9GHz Inte= l=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 entrie= s, 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 core= s).

What these numbers do not take into account is database lookups.= We need to fetch the transaction of every UTXO, as well as every transacti= on 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 transaction= s with fully spent outputs, but that would probably not be worth the added = complexity. If we only scan transactions with taproot outputs, we can furth= er limit our efforts, but this advantage is expected to dissipate once tapr= oot use becomes more common.


Variant using all inputs

Ins= tead of tweaking the silent payment address with one input, we could instea= d tweak it with the combination of all input keys of a transaction. The ben= efit is that this further lowers the scanning cost, since now we only need = to calculate one tweak per transaction, instead of one tweak per input, whi= ch is roughly half the work, though database lookups remain unaffected.
=
The downside is that if you want to combine your inputs with those of o= thers (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 paymen= t. There are also privacy considerations which are discussed in the =E2=80= =9CPreventing input linkage=E2=80=9D section.

Concretely, if there a= re 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 ca= n extend the silent payment address with a scanning key, which allows for s= eparation of detecting and spending payments. We redefine the silent paymen= t 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 n= ode to hold the private key of X_scan to detect incoming payments, while yo= ur hardware wallet controls X_spend to make payments. If X_scan is compromi= sed, privacy is lost, but your funds are not.


Address reuse prev= ention

If the sender sends more than one payment, and the chosen inp= ut has the same key due to address reuse, then the recipient address will a= lso be the same. To prevent this, we can hash the txid and index of the inp= ut, 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 canno= t 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 standardi= zed list of relevant input keys for each block over wifi each night when ch= arging. These input keys can then be tweaked, and the results can be matche= d against compact block filters. Possible, but not simple.


Effec= t 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 add= ress will automatically be unique. This also means we won=E2=80=99t have to= deal with a gap limit.


Different inputs

While the simple= st 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 add= resses, 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 ac= tually 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 (wh= ich requires one extra transaction lookup).


Signature nonce inst= ead of input key

Another consideration was to tweak the silent payme= nt address with the signature nonce[5], but unfortunately this breaks compa= tibility with MuSig2 and MuSig-DN, since in those schemes the signature non= ce changes depending on the transaction hash. If we let the output address = depend on the nonce, then the transaction hash will change, causing a circu= lar reference.


Sending wallet compatibility

Any wallet th= at wants to support making silent payments needs to support a new address f= ormat, 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 t= ransaction. The scanning requirement is not relevant to the sender, only th= e recipient.



PREVENTING INPUT LINKAGE


A potential= weakness of Silent Payments is that the input is linked to the output. A c= oinjoin transaction with multiple inputs from other users can normally obfu= scate the sender input from the recipient, but Silent Payments reveal that = link. This weakness can be mitigated with the =E2=80=9Cvariant using all in= puts=E2=80=9D, but this variant introduces a different weakness =E2=80=93 y= ou 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>Luckily, a blinding scheme[6] exists that allows us to hide the silent p= ayment address from the other participants. Concretely, let=E2=80=99s say t= here 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 r= emove the blinding factor with X1' - blinding_factor*I1 =3D X1 (which i= s 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.

The blinding= protocol above solves our coinjoin privacy concerns (at the expense of mor= e 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 t= he inputs (e.g. sending from an exchange)? In this scenario we can still ut= ilize the blinding protocol, but now the third party sender can try to unco= ver the intended recipient by brute forcing their inputs on all known silen= t payment addresses (i.e. calculate hash(i*X)*G + X for every publicly know= n X). While this is computationally expensive, it=E2=80=99s by no means imp= ossible. No solution is known at this time, so as it stands this is a limit= ation of the protocol =E2=80=93 the sender must control one of the inputs i= n order to be fully private.



COMPARISON


These are= the most important protocols that provide similar functionality with sligh= tly different tradeoffs. All of them provide fresh address generation and a= re compatible with one-time seed backups. The main benefits of the protocol= s listed below are that there is no scanning requirement, better light clie= nt support, and they don=E2=80=99t require control over the inputs of the t= ransaction.


Payment code sharing

This is BIP47[2]. An OP_= RETURN message is sent on-chain to the recipient to establish a shared secr= et prior to making payments. Using the blockchain as a messaging layer like= this is generally considered an inefficient use of on-chain resources. Thi= s concern can theoretically be alleviated by using other means of communica= ting, but data availability needs to be guaranteed to ensure the recipient = doesn=E2=80=99t lose access to the funds. Another concern is that the input= (s) used to establish the shared secret may leak privacy if not kept separa= te.


Xpub sharing

Upon first payment, hand out an xpub ins= tead of an address in order to enable repeat payments. I believe Kixunil=E2= =80=99s recently published scheme[3] is equivalent to this and could be imp= lemented with relative ease. It=E2=80=99s unclear how practical this protoc= ol is, as it assumes sender and recipient are able to interact once, yet su= bsequent interaction is impossible.


Regular address sharing
<= br>This is how Bitcoin is commonly used today and may therefore be obvious,= but it does satisfy similar privacy requirements. The sender interacts wit= h the recipient each time they want to make a payment, and requests a new a= ddress. The main downside is that it requires interaction for every single = 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 alter= natives, is this scheme worth the added complexity?



ACKNOWLE= DGEMENTS


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.mediaw= iki =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 address= es, Kixunil: https://gist= .github.com/Kixunil/0ddb3a9cdec33342b97431e438252c0a

[4] BIP32 H= D keys, Pieter Wuille: http= s://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

[5] 2= 020-01-23 ##taproot-bip-review, starting at 18:25: https://gnusha.org/taproot-bip-review/2020-01-23.log
<= br>[6] Blind Diffie-Hellman Key Exchange, David Wagner: https://gist.github.com/RubenSomsen/be7a= 4760dd4596d06963d67baf140406
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.li= nuxfoundation.org/mailman/listinfo/bitcoin-dev
--000000000000d8423a05db71c502--