public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
@ 2022-03-28 15:27 Ruben Somsen
  2022-03-29 14:57 ` Billy
  0 siblings, 1 reply; 9+ messages in thread
From: Ruben Somsen @ 2022-03-28 15:27 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 12907 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 13729 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-03-28 15:27 [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead Ruben Somsen
@ 2022-03-29 14:57 ` Billy
  2022-03-29 15:36   ` Ruben Somsen
  0 siblings, 1 reply; 9+ messages in thread
From: Billy @ 2022-03-29 14:57 UTC (permalink / raw)
  To: Ruben Somsen, Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 15059 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 16583 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-03-29 14:57 ` Billy
@ 2022-03-29 15:36   ` Ruben Somsen
  2022-03-30  5:58     ` Billy
  0 siblings, 1 reply; 9+ messages in thread
From: Ruben Somsen @ 2022-03-29 15:36 UTC (permalink / raw)
  To: Billy; +Cc: Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 16349 bytes --]

Hi Billy,

Thanks for taking a look.

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

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

>primary benefit of this is privacy for the recipient

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

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

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

Cheers,
Ruben



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

> Hi Ruben,
>
> Very interesting protocol. This reminds me of how monero stealth 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
>>
>

[-- Attachment #2: Type: text/html, Size: 18011 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-03-29 15:36   ` Ruben Somsen
@ 2022-03-30  5:58     ` Billy
  2022-03-30 16:09       ` Billy
  0 siblings, 1 reply; 9+ messages in thread
From: Billy @ 2022-03-30  5:58 UTC (permalink / raw)
  To: Ruben Somsen; +Cc: Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 18141 bytes --]

>  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 <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 for the recipient
>
> Fair, but just wanted to note the sender can get in trouble too if they
> send money to e.g. blacklisted addresses.
>
> >there could be a standard that [...] reduces the anonymity set a bit
>
> This has occurred to me but I am reluctant to make that trade-off. It
> seems best to first see how well this can be optimized without resorting to
> reducing anonymity, and it's hard to analyze exactly how impactful the
> anonymity degradation is (I suspect it's worse than you think because it
> can help strengthen existing heuristics about output ownership).
>
> Cheers,
> Ruben
>
>
>
> On Tue, Mar 29, 2022 at 4:57 PM Billy <fresheneesz@gmail.com> wrote:
>
>> Hi Ruben,
>>
>> Very interesting protocol. This reminds me of how monero stealth
>> 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
>>>
>>

[-- Attachment #2: Type: text/html, Size: 20443 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-03-30  5:58     ` Billy
@ 2022-03-30 16:09       ` Billy
  2022-03-31 10:48         ` Ruben Somsen
  0 siblings, 1 reply; 9+ messages in thread
From: Billy @ 2022-03-30 16:09 UTC (permalink / raw)
  To: Ruben Somsen; +Cc: Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 20254 bytes --]

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' = X + i*X*hash((i*X)%N) =  X + x*I*hash((x*I)%N)

item = {recipient: X' % N, sender: I%N} // As before.

Test for each filter item: (item.recipient - X) % N == (
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=2^8 would I think mean an 18% collision rate (ie 20% false positive rate)
because `(1-1/2^8)^13000 = 0.82...`. If we were to go with 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% 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 =
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 <fresheneesz@gmail.com> 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 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 <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 for the recipient
>>
>> Fair, but just wanted to note the sender can get in trouble too if they
>> send money to e.g. blacklisted addresses.
>>
>> >there could be a standard that [...] reduces the anonymity set a bit
>>
>> This has occurred to me but I am reluctant to make that trade-off. It
>> seems best to first see how well this can be optimized without resorting to
>> reducing anonymity, and it's hard to analyze exactly how impactful the
>> anonymity degradation is (I suspect it's worse than you think because it
>> can help strengthen existing heuristics about output ownership).
>>
>> Cheers,
>> Ruben
>>
>>
>>
>> On Tue, Mar 29, 2022 at 4:57 PM Billy <fresheneesz@gmail.com> wrote:
>>
>>> Hi Ruben,
>>>
>>> Very interesting protocol. This reminds me of how monero stealth
>>> 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
>>>>
>>>

[-- Attachment #2: Type: text/html, Size: 22773 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-03-30 16:09       ` Billy
@ 2022-03-31 10:48         ` Ruben Somsen
  0 siblings, 0 replies; 9+ messages in thread
From: Ruben Somsen @ 2022-03-31 10:48 UTC (permalink / raw)
  To: Billy; +Cc: Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 22865 bytes --]

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?permalink_comment_id=4113518#gistcomment-4113518

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 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' = X + i*X*hash((i*X)%N) =  X + x*I*hash((x*I)%N)
>
> item = {recipient: X' % N, sender: I%N} // As before.
>
> Test for each filter item: (item.recipient - X) % N == (
> 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=2^8 would I think mean an 18% collision rate (ie 20% false
> positive rate) because `(1-1/2^8)^13000 = 0.82...`. If we were to go with
> 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% 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 = 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 <fresheneesz@gmail.com> 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 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 <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 for the recipient
>>>
>>> Fair, but just wanted to note the sender can get in trouble too if they
>>> send money to e.g. blacklisted addresses.
>>>
>>> >there could be a standard that [...] reduces the anonymity set a bit
>>>
>>> This has occurred to me but I am reluctant to make that trade-off. It
>>> seems best to first see how well this can be optimized without resorting to
>>> reducing anonymity, and it's hard to analyze exactly how impactful the
>>> anonymity degradation is (I suspect it's worse than you think because it
>>> can help strengthen existing heuristics about output ownership).
>>>
>>> Cheers,
>>> Ruben
>>>
>>>
>>>
>>> On Tue, Mar 29, 2022 at 4:57 PM Billy <fresheneesz@gmail.com> wrote:
>>>
>>>> Hi Ruben,
>>>>
>>>> Very interesting protocol. This reminds me of how monero stealth
>>>> 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
>>>>>
>>>>

[-- Attachment #2: Type: text/html, Size: 25641 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-05-24 13:49 ` alicexbt
@ 2022-05-25 13:13   ` Erik Aronesty
  0 siblings, 0 replies; 9+ messages in thread
From: Erik Aronesty @ 2022-05-25 13:13 UTC (permalink / raw)
  To: alicexbt, Bitcoin Protocol Discussion

[-- Attachment #1: Type: text/plain, Size: 1985 bytes --]

i like the  00 || X_spend || X_scan + mandate address reuse prevention.

might as well start with something strict

easy to loosen it later - if needed - harder to tighten it later because of
back-compatibility with addresses in-use


On Tue, May 24, 2022 at 11:02 AM alicexbt via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi woltx,
>
> Thanks for implementing silent payments in Bitcoin Core. I tried the steps
> shared in tutorial and everything works as expected.
>
> I have updated the silent payment address (signet) as TXT record for
> domain alice.silentbitco.in
>
> $ dig -t txt alice.silentbitco.in +short
> "tb1px3kma8e8y8z9l7e640v0x2chzrzww9cu06mqvwyrz805ffletu3s067sgh"
>
> I have also added basic information about silent payments proposal,
> implementation and tutorial on https://silentbitco.in
>
> I had no issues with performance of the UTXO Set and the blocks scan. I
> don't mind using flag but a new address/descriptor format should be a
> better approach. I could not review the code in detail or test edge cases
> however these suggestions by Pavol Rusnak make sense:
> https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8?permalink_comment_id=4177027#gistcomment-4177027
>
>
> /dev/fd0
>
> Sent with ProtonMail <https://protonmail.com/> secure email.
>
> ------- Original Message -------
> On Tuesday, May 24th, 2022 at 7:01 AM, woltx via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> I created a short and simple tutorial on how to make silent payments on
> signet.
> https://gist.github.com/w0xlt/72390ded95dd797594f80baba5d2e6ee
>
> In this tutorial, the user will generate an address, publish it, receive
> and spend coins from it and still no transactions are shown from this
> address in a blockchain explorer.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5549 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead
  2022-05-24  1:31 woltx
@ 2022-05-24 13:49 ` alicexbt
  2022-05-25 13:13   ` Erik Aronesty
  0 siblings, 1 reply; 9+ messages in thread
From: alicexbt @ 2022-05-24 13:49 UTC (permalink / raw)
  To: woltx; +Cc: bitcoin-dev

[-- Attachment #1: Type: text/plain, Size: 1397 bytes --]

Hi woltx,

Thanks for implementing silent payments in Bitcoin Core. I tried the steps shared in tutorial and everything works as expected.

I have updated the silent payment address (signet) as TXT record for domain alice.silentbitco.in

$ dig -t txt alice.silentbitco.in +short
"tb1px3kma8e8y8z9l7e640v0x2chzrzww9cu06mqvwyrz805ffletu3s067sgh"

I have also added basic information about silent payments proposal, implementation and tutorial on https://silentbitco.in

I had no issues with performance of the UTXO Set and the blocks scan. I don't mind using flag but a new address/descriptor format should be a better approach. I could not review the code in detail or test edge cases however these suggestions by Pavol Rusnak make sense: https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8?permalink_comment_id=4177027#gistcomment-4177027

/dev/fd0

Sent with [ProtonMail](https://protonmail.com/) secure email.

------- Original Message -------
On Tuesday, May 24th, 2022 at 7:01 AM, woltx via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> I created a short and simple tutorial on how to make silent payments on signet.
> https://gist.github.com/w0xlt/72390ded95dd797594f80baba5d2e6ee
> In this tutorial, the user will generate an address, publish it, receive and spend coins from it and still no transactions are shown from this address in a blockchain explorer.

[-- Attachment #2: Type: text/html, Size: 4220 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* [bitcoin-dev]  Silent Payments – Non-interactive private payments with no on-chain overhead
@ 2022-05-24  1:31 woltx
  2022-05-24 13:49 ` alicexbt
  0 siblings, 1 reply; 9+ messages in thread
From: woltx @ 2022-05-24  1:31 UTC (permalink / raw)
  To: bitcoin-dev

[-- Attachment #1: Type: text/plain, Size: 319 bytes --]

I created a short and simple tutorial on how to make silent payments on signet.
https://gist.github.com/w0xlt/72390ded95dd797594f80baba5d2e6ee
In this tutorial, the user will generate an address, publish it, receive and spend coins from it and still no transactions are shown from this address in a blockchain explorer.

[-- Attachment #2: Type: text/html, Size: 534 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2022-05-25 13:13 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-03-28 15:27 [bitcoin-dev] Silent Payments – Non-interactive private payments with no on-chain overhead Ruben Somsen
2022-03-29 14:57 ` Billy
2022-03-29 15:36   ` Ruben Somsen
2022-03-30  5:58     ` Billy
2022-03-30 16:09       ` Billy
2022-03-31 10:48         ` Ruben Somsen
2022-05-24  1:31 woltx
2022-05-24 13:49 ` alicexbt
2022-05-25 13:13   ` Erik Aronesty

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox