Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7CC2CC0012 for ; Thu, 31 Mar 2022 10:48:58 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 4DD5341B78 for ; Thu, 31 Mar 2022 10:48:58 +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: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id crygL9pSSbl8 for ; Thu, 31 Mar 2022 10:48:54 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-yb1-xb31.google.com (mail-yb1-xb31.google.com [IPv6:2607:f8b0:4864:20::b31]) by smtp4.osuosl.org (Postfix) with ESMTPS id 6838041B6A for ; Thu, 31 Mar 2022 10:48:54 +0000 (UTC) Received: by mail-yb1-xb31.google.com with SMTP id y142so41550362ybe.11 for ; Thu, 31 Mar 2022 03:48:54 -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=AM1n+uSzrY+izcD//UyZvRgFgFl6PhGuRiuwBgwreKc=; b=Sz/sW4VWQqZU49KXQZj6HVkQHCUbrDCaFoK7EZobTJyfOltYWbYzdIvMpfB41JRIhj oakUyhn72eUAq/VMOiWK5a2BVjoitB0/qaX/IerZork5lvdU/fbR1U31JG6ecKdQiXal k3XoLaI3M+qi/063Ql7keYWU37y+UztjbQY89AJSSkicBm9GErfUWuqTrTYH8V8WA1fj 5FTgAOdkCSTd+2aItWiOUx+jZLB+PReFO0vnAnLnB3bNXkik/ooBin7lnZBWJrOZGS3f L6jHimMsAxaNahlQLxX6mbZd/BNYwtOsjzCK7h8mpOWxw1QCOF7Ul16Tr4DREdhkXCqV q5zg== 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=AM1n+uSzrY+izcD//UyZvRgFgFl6PhGuRiuwBgwreKc=; b=LmmWwF1mTj6eZBtkf4miLf1kl+nROzCFV7EXolBdNyP8mrCUe8/d7cmr2DLviBmEJh NwGMyd1DJ6KPdknsHLNy6II2EgN9G4v1V32EQ1sKBossBjluFXDzIEu0sOqM3ehPBtS6 RNOReK8ZMhQOm5Kx5/46fbFKIoYB2Y1qfPKkxLNA1CbPnv6zBGBt4uLzz6m1XLk782sj Dzj926wwH68nnaNO++5sHUlRUlmq1Lhjy+7z2H5N9WAP5MktC0nawBGT0kc+jfZLXazB 1co4E49+yyf3aq31y6akNRPdVO/xpgZK+XZyNy97/E+0wdqzQjYwR2+qI0hGwlfJXkBl F8RA== X-Gm-Message-State: AOAM531DPQQ83m33YJqeZDpb9OmFuSNR2unqCMLIlzuwzF4XlYXaM2cM 0JxhA+/6Hj+4zm7SA+lDgRz4+BkEN4G5x/V0SmuqrHnUA34= X-Google-Smtp-Source: ABdhPJyKn1UI9oD8pJWaTiFHETzDbHEDEMsAJrDEMgL34K0zmZkT/367wlUXaZTiVEMRgOqlTyE8Ycd4LSLpdJjt1C0= X-Received: by 2002:a05:6902:1009:b0:636:eeb6:1d0d with SMTP id w9-20020a056902100900b00636eeb61d0dmr3689626ybt.297.1648723733194; Thu, 31 Mar 2022 03:48:53 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Ruben Somsen Date: Thu, 31 Mar 2022 12:48:41 +0200 Message-ID: To: Billy Content-Type: multipart/alternative; boundary="000000000000732b2205db816821" X-Mailman-Approved-At: Thu, 31 Mar 2022 10:49:38 +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: Thu, 31 Mar 2022 10:48:58 -0000 --000000000000732b2205db816821 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Billy, >i*X*G I believe you understand this now, but just to be clear, it's not possible to multiply a point by another point. At best you can take the x coordinate of i*X and multiply that by G. >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 I don't think I was 100% able to follow your math, but I assume your goal is to reduce the anonymity set by lowering the entropy using modulo. As you guessed, this won't work with curve points. I'm also not sure if we're on the same page with regards to my previous post: 1.) you can't reduce the scanning burden without also reducing the anonymity set, 2.) I'm hopeful the scanning requirement won't be so bad that we'd need to consider this tradeoff, and 3.) I'm concerned that the impact on anonymity is quite severe, even if you leak just a single bit and cut the anonymity set in half (e.g. you could figure out if a tx with a bunch of inputs are likely to originate from the same owner). >You can then scale N to the proper tradeoff between filter size and false positives Yes, the nice thing is that every person who follows this protocol has to scan the exact same number of potential keys per block, so it should be possible to create a custom block filter with the exact optimal false positive rate. So at a high level, the way I envision light clients working are as follows= : - The server derives a list of public keys from each block (~9MB per 144 blocks without cut-through) - The server also creates a block filter containing all taproot output keys (unsure what the size would be) - The client downloads both, performs Diffie-Hellman on the public keys, checks each result with the filter, and downloads relevant blocks You can find some more details about how this would work in one of my gist comments: https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8?permal= ink_comment_id=3D4113518#gistcomment-4113518 Cheers, Ruben On Wed, Mar 30, 2022 at 6:09 PM Billy wrote: > 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% fa= lse > positive rate) because `(1-1/2^8)^13000 =3D 0.82...`. If we were to go wi= th > that, each item is 4 bytes (1 byte per point component?) which would mean= a > 52kb filter without collisions, and an average of 43kb with 18% collision= s > (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 who= le > 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 >> block filters could be done to support this case. If, for example, the >> tweaked key were defined without hashing, I think something like that co= uld >> be done: >> >> X' =3D i*X*G + X =3D x*I*G + X >> >> 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 following to detect a likely payment for e= ach >> 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 fals= e >> positives. I suppose this might make it possible to deprivitize a tweake= d >> 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 resortin= g 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 i= t >>> 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 sa= y >>>> "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 transactio= n)? >>>> >>>> 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 le= vel >>>> 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 les= s >>>> 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 sti= ll 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 downs= ides, >>>>> 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 the= ir >>>>> 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. >>>>> >>>>> Compared to previous schemes[1], this scheme avoids using the Bitcoin >>>>> blockchain as a messaging layer[2] and requires no interaction betwee= n >>>>> sender and recipient[3] (other than needing to know the silent paymen= t >>>>> address). The main downsides are the scanning requirement, the lack o= f >>>>> 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 on= ly >>>>> unspent payments by scanning the UTXO set. We=E2=80=99ll start by des= cribing a >>>>> basic scheme, and then introduce a few improvements. >>>>> >>>>> >>>>> >>>>> BASIC SCHEME >>>>> >>>>> >>>>> The recipient publishes their silent payment address, a single 32 byt= e >>>>> 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 correspondin= g >>>>> 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 ha= s 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 transac= tion >>>>> for every subsequent input in order to extract the relevant public ke= y, >>>>> 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 >>>>> transactions with fully spent outputs, but that would probably not be= worth >>>>> the added complexity. If we only scan transactions with taproot outpu= ts, we >>>>> can further limit our efforts, but this advantage is expected to diss= ipate >>>>> once 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 cos= t, >>>>> since now we only need to calculate one tweak per transaction, instea= d 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 you= r >>>>> 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 you= r >>>>> internet-connected node to hold the private key of X_scan to detect >>>>> incoming payments, while your hardware wallet controls X_spend to mak= e >>>>> payments. If X_scan is compromised, privacy is lost, but your funds a= re 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 al= so be >>>>> the same. To prevent this, we can hash the txid and index of the inpu= t, to >>>>> ensure each address is unique, resulting in X' =3D hash(i*X,txid,inde= x)*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 do= n=E2=80=99t >>>>> require the txid and index), only consider unspent taproot outputs, a= nd >>>>> download a standardized list of relevant input keys for each block ov= er >>>>> wifi each night when charging. These input keys can then be tweaked, = and >>>>> the results can be matched against compact block filters. Possible, b= ut 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 limi= t. >>>>> >>>>> >>>>> 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 m= ake >>>>> 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 ext= ra >>>>> transaction lookup). >>>>> >>>>> >>>>> Signature nonce instead of input key >>>>> >>>>> Another consideration was to tweak the silent payment address with th= e >>>>> signature nonce[5], but unfortunately this breaks compatibility with = MuSig2 >>>>> and MuSig-DN, since in those schemes the signature nonce changes depe= nding >>>>> on the transaction hash. If we let the output address depend on the n= once, >>>>> 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, an= d then >>>>> proceed to sign the transaction. The scanning requirement is not rele= vant >>>>> to the sender, only the recipient. >>>>> >>>>> >>>>> >>>>> PREVENTING INPUT LINKAGE >>>>> >>>>> >>>>> A potential weakness of Silent Payments is that the input is linked t= o >>>>> the output. A coinjoin transaction with multiple inputs from other us= ers >>>>> can normally obfuscate the sender input from the recipient, but Silen= t >>>>> 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 we= akness =E2=80=93 you >>>>> now require all other coinjoin users to tweak the silent payment addr= ess, >>>>> which means you=E2=80=99re revealing the intended recipient to them. >>>>> >>>>> Luckily, a blinding scheme[6] exists that allows us to hide the silen= t >>>>> payment address from the other participants. Concretely, let=E2=80=99= s say there >>>>> are two inputs, I1 and I2, and the latter one is ours. We add a secre= t >>>>> 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 correctn= ess, see >>>>> full write-up[6]) from the owner of the first input and remove the bl= inding >>>>> 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 ad= dress >>>>> 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 w= ith one more >>>>> issue =E2=80=93 what if you want to make a silent payment, but you co= ntrol none of >>>>> the inputs (e.g. sending from an exchange)? In this scenario we can s= till >>>>> utilize the blinding protocol, but now the third party sender can try= to >>>>> uncover the intended recipient by brute forcing their inputs on all k= nown >>>>> silent payment addresses (i.e. calculate hash(i*X)*G + X for every pu= blicly >>>>> 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 i= s a >>>>> limitation of the protocol =E2=80=93 the sender must control one of t= he 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 = fresh >>>>> 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 requ= ire 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. Usin= g 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 availabili= ty >>>>> needs to be guaranteed to ensure the recipient doesn=E2=80=99t lose a= ccess to the >>>>> funds. Another concern is that the input(s) used to establish the sha= red >>>>> secret may leak privacy if not kept separate. >>>>> >>>>> >>>>> Xpub sharing >>>>> >>>>> Upon first payment, hand out an xpub instead of an address in order t= o >>>>> enable repeat payments. I believe Kixunil=E2=80=99s recently publishe= d 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 reci= pient >>>>> 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, a= nd >>>>> requests a new address. The main downside is that it requires interac= tion >>>>> 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 previ= ous >>>>> 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 >>>>> >>>> --000000000000732b2205db816821 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Billy,

>i*X*G

I believe you understand this now, but just to be clear, it's not= possible to multiply a point by another point. At best you can take the x = coordinate of i*X and multiply that by G.

>all = this assumes that a modulus operator is defined for elliptic curve points i= n a way that makes these valid, which I'm not sure is true
I don't think I was 100% able to follow your math, but I a= ssume your goal is to reduce the anonymity set by lowering the entropy usin= g modulo. As you guessed, this won't work with curve points.
=
I'm also not sure if we're on the same page with reg= ards to my previous post: 1.) you can't reduce the scanning burden with= out also reducing the anonymity set, 2.) I'm hopeful the scanning requi= rement won't be so bad that we'd need to consider this tradeoff, an= d 3.) I'm concerned that the impact on anonymity is quite severe, even = if you leak just a single bit and cut the anonymity set in half (e.g. you c= ould figure out if a tx with a bunch of inputs are likely to originate from= the same owner).

>You can then scale N to the = proper tradeoff between filter size and false positives

Yes, the nice thing is that every person who follows this protocol ha= s to scan the exact same number of potential keys per block, so it should b= e possible to create a custom block filter with the exact optimal false pos= itive rate.

So at a high level, the way I envision= light clients working are as follows:
- The server derives a lis= t of public keys from each block (~9MB per 144 blocks without cut-through)<= /div>
- The server also creates a block filter containing all taproot o= utput keys (unsure what the size would be)
- The client downloads= =C2=A0both, performs Diffie-Hellman on the public keys, checks each result = with the filter, and downloads relevant blocks

You= can find some more details about how this would work in one of my gist com= ments:

Cheers,
Ruben





On Wed, Mar 30, 2022 at 6:09 PM Billy <fresheneesz@gmail.com> wrote:
Hi Ruben,
After sending that last night, I realized the solution I ha= d to deprivatizing the sender wouldn't work because it had the same pro= blem 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 th= at a modulus operator is defined for elliptic curve points in a way that ma= kes these valid, which I'm not sure is true. 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{recipient: 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 o= f this, in a block full of taproot sends you might have an upper limit of s= omething like 13,000 transactions. N=3D2^8 would I think mean an 18% collis= ion 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 compon= ent?) 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 fil= ters. And since each collision with an address a client is watching on mean= s downloading a whole block they don't need, maybe 18% collisions is to= o high, and we want to choose N =3D 2^10 or something to get down to 2% col= lisions.=C2=A0

In any case, all this could be wron= g if ECC modulus doesn't work this way. But was interesting to think ab= out 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:

<= div>

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
--000000000000732b2205db816821--