> 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 could be done: X' = i*X*G + X = x*I*G + X Your compact-block-filter-like things could then store a set of each `item = {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 == 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' = i*X*G + X + (i*X)%N = x*I*G + X + (x*I)%N Then for each `item = {recipient: X' % N, sender: I%N}`, we detect via `item.recipient - X%N == x*item.sender*(1+G)`. Is my math right here? I'm thinking this should work because (a+b%N)%N == (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 level >> of privacy one would only care about if they might receive a lot money >> related to that address. However of course someone might not know they'll >> receive an amount of money they want to be private until they receive it. >> So the inability to easily do this without a full node is slightly less >> than ideal. But it's another good reason to run a full node. >> >> Perhaps there could be a standard that can identify tweaked address, such >> that only those addresses can be downloaded and checked by light clients. >> It reduces the anonymity set a bit, but it would probably still be >> sufficient. >> >> >> >> On Mon, Mar 28, 2022, 10:29 Ruben Somsen via bitcoin-dev < >> bitcoin-dev@lists.linuxfoundation.org> wrote: >> >>> Hi all, >>> >>> I'm publishing a new scheme for private non-interactive address >>> generation without on-chain overhead. It has upsides as well as downsides, >>> so I suspect the main discussion will revolve around whether this is worth >>> pursuing or not. There is a list of open questions at the end. >>> >>> I added the full write-up in plain text below, though I recommend >>> reading the gist for improved formatting and in order to benefit from >>> potential future edits: >>> https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8 >>> >>> Cheers, >>> Ruben >>> >>> >>> >>> Silent Payments >>> >>> Receive private payments from anyone on a single static address without >>> requiring any interaction or on-chain overhead >>> >>> >>> >>> OVERVIEW >>> >>> >>> The recipient generates a so-called silent payment address and makes it >>> publicly known. The sender then takes a public key from one of their 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 detects 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 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’t novel, the >>> resulting protocol has never been seriously considered and may be >>> reasonably viable, particularly if we limit ourselves to detecting only >>> unspent payments by scanning the UTXO set. We’ll start by describing 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 = x*G >>> >>> The sender picks an input containing a public key: >>> I = i*G >>> >>> The sender tweaks the silent payment address with the public key of >>> their input: >>> X' = hash(i*X)*G + X >>> >>> Since i*X == 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® Core™ 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 = 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 transaction for >>> every subsequent input in order to extract the relevant public key, >>> resulting in (1+2.3)*80000000 = 264 million lookups. How slow this is and >>> what can be done to improve it is an open question. >>> >>> Once we’re at the tip, every new unspent output will have to be scanned. >>> It’s 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 outputs, we can >>> further limit our efforts, but this advantage is expected to dissipate 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 cost, 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 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 >>> “Preventing input linkage” section. >>> >>> Concretely, if there are three inputs (I1, I2, I3), the scheme becomes: >>> hash(i1*X + i2*X + i3*X)*G + X == 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' = 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 the >>> same. To prevent this, we can hash the txid and index of the input, to >>> ensure each address is unique, resulting in X' = 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’t >>> 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’t be >>> needed for address generation, since every address will automatically be >>> unique. This also means we won’t have to deal with a gap limit. >>> >>> >>> Different inputs >>> >>> While the simplest thing would be to only support one input type (e.g. >>> taproot key spend), this would also mean only a subset of users can make >>> payments to silent addresses, so this seems undesirable. The protocol >>> should ideally support any input containing at least one public key, and >>> simply pick the first key if more than one is present. >>> >>> Pay-to-(witness-)public-key-hash inputs actually end up being easiest to >>> scan, since the public key is present in the input script, instead of the >>> output script of the previous transaction (which requires one extra >>> transaction lookup). >>> >>> >>> Signature nonce instead of input key >>> >>> Another consideration was to tweak the silent payment address with the >>> signature nonce[5], but unfortunately this breaks compatibility with MuSig2 >>> and MuSig-DN, since in those schemes the signature nonce changes depending >>> on the transaction hash. If we let the output address depend on the nonce, >>> then the transaction hash will change, causing a circular reference. >>> >>> >>> Sending wallet compatibility >>> >>> Any wallet that wants to support making silent payments needs to support >>> a new address format, pick inputs for the payment, tweak the silent payment >>> address using the private key of one of the chosen inputs, and then proceed >>> 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 “variant >>> using all inputs”, but this variant introduces a different weakness – you >>> now require all other coinjoin users to tweak the silent payment address, >>> which means you’re 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’s 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 = X', >>> then we receive X1' = i1*X' (together with a DLEQ to prove correctness, see >>> full write-up[6]) from the owner of the first input and remove the blinding >>> factor with X1' - blinding_factor*I1 = X1 (which is equal to i1*X). >>> Finally, we calculate the tweaked address with hash(X1 + i2*X)*G + X. The >>> recipient can simply recognize the payment with hash(x*(I1+I2))*G + X. Note >>> that the owner of the first input cannot reconstruct the resulting address >>> because they don’t know i2*X. >>> >>> The blinding protocol above solves our coinjoin privacy concerns (at the >>> expense of more interaction complexity), but we’re left with one more issue >>> – what if you want to make a silent payment, but you control none of the >>> inputs (e.g. sending from an exchange)? In this scenario we can still >>> utilize the blinding protocol, but now the third party sender can try to >>> uncover the intended recipient by brute forcing their inputs on all known >>> silent payment addresses (i.e. calculate hash(i*X)*G + X for every publicly >>> known X). While this is computationally expensive, it’s by no means >>> impossible. No solution is known at this time, so as it stands this is a >>> limitation of the protocol – the sender must control one of the 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’t 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 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 availability needs to be >>> guaranteed to ensure the recipient doesn’t lose access to the funds. >>> 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’s recently published scheme[3] is >>> equivalent to this and could be implemented with relative ease. It’s >>> unclear how practical this protocol is, as it assumes sender and recipient >>> 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, and requests a new >>> address. 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 – 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 ↩︎ >>> >>> [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 >>> >>