[bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[Ruben Somsen]

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

Hi all,

In short, this is yet another way to hand out addresses without interaction
between sender and recipient (Silent Payments, BIP47). The idea here is
that in non-ideal cases where you're already exposing your xpub to a server
(most light clients today, unfortunately), you might as well rely on them
to hand out addresses on your behalf.

Other than BTCPay Server, I am not aware of any serious attempts of
exploring this direction. Perhaps this is justified, due to the difficulty
of dealing with the gap limit, but it seems worth discussing nonetheless.

The write-up is available (and kept up-to-date) here as a gist:
https://gist.github.com/RubenSomsen/960ae7eb52b79cc826d5b6eaa61291f6

And here's a copy for the list:


### Introduction

Address reuse prevention generally requires interacting with the recipient
in order to receive a fresh address for each payment. There are various
protocols that ensure no interaction is required such as BIP47[^1] and
Silent Payments[^2], though neither is without downsides.

One area that is seemingly underexplored is that of outsourced interaction.
BTCPay Server[^3] is an example of this. The sender interacts with a
server, which acts on behalf of the recipient and hands out an address from
an xpub. The recipient controls and therefore trusts the server, so
malicious addresses won't be given out.

### Outsourcing and Malicious Keys

The vast majority of light clients today (even ones that support BIP47,
curiously) already control the user's xpub, so it seems logical to think
the interaction can be outsourced to them. However, unlike when running
your own server, a third party server *could* potentially hand out
malicious addresses (i.e. addresses that belong to someone other than you).

The solution to this is identity. As long as the sender knows a public key
by which the recipient can be identified, the recipient can sign the
addresses that are derived from their xpub[^4]. This way the sender can be
sure that the address it receives from the server belongs to the recipient.

### Gap Limit

One big remaining problem is the gap limit[^5]. When an adversary
repeatedly requests addresses from the server but then never uses them,
this could result in a large gap of unused addresses. This is a problem
because when recovering from backup the wallet stops looking for payments
when a large enough gap is encountered. Unfortunately there is no perfect
solution, but mitigations are still possible.

Whenever a sender wants to make their first payment, they could be expected
to obtain an address at a cost (solving captchas, paying over LN,
proof-of-burn[^6]). If the sender doesn't mind (or maybe even desires)
having their payments correlated by the recipient, a fresh xpub[^7] can be
handed out instead of an address in order to enable repeated payments. If
non-correlated payments are preferable, after each successful payment the
server could hand out a blind ecash[^8] token that entitles the sender to
another address.

An alternative mitigation (more user friendly, but more implementation
complexity) would be to require the sender to reveal their intended
transaction to the server prior to receiving the address[^9]. This is not a
privacy degradation, since the server could already learn this information
regardless. If the transaction doesn't end up getting sent, any subsequent
attempt to reuse one of the inputs should either be (temporarily)
blacklisted or responded to with the same address that was given out
earlier[^10].

If despite best efforts the gap limit is inadvertently reached anyway, the
recipient may have to be instructed to ensure they properly receive a
payment to bridge the gap before new addresses can be handed out. The
alternative is to forego privacy when this happens, but this seems unwise.

### Use Case

This protocol seems useful for users that a.) want to use light clients,
b.) accept the privacy degradation of handing out their xpub to a third
party, and c.) want to receive payments non-interactively. If any one of
these is not true, other protocols are likely to be a better choice[^11].
Finally, it should be acknowledged that this protocol introduces more
friction on the sender side due to the need for a gap limit mitigation
strategy.

-- Ruben Somsen


[^1]: BIP47: https://github.com/bitcoin/bips/blob/master/bip-0047.mediawiki

[^2]: Silent Payments:
https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8

[^3]: BTCPay Server https://btcpayserver.org/

[^4]: *Specifically, this could be a single signature on a merkle root, so
the amount of data that the recipient needs to send to the server can be
minimized and the server can just generate the same tree from the xpub and
hand out merkle proofs to senders. The order of the leaves should be
randomized so senders cannot learn how many payments were made.*

[^5]: Gap limit:
https://bitcoin.stackexchange.com/questions/111534/bitcoin-address-gap-limit

[^6]: Efficient Proof-of-Burn:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-July/020746.html

[^7]: Xpub sharing:
https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8#xpub-sharing

[^8]: Blind ecash:
https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406

[^9]: *This would essentially look like an incomplete but signed
transaction where the output address is still missing.*

[^10]: *Keep in mind the edge case where e.g. two inputs are presented but
not used, followed by two separate transactions which each use one of the
priorly presented inputs.*

[^11]: Protocol considerations:
https://twitter.com/SomsenRuben/status/1530096037414707200

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

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[David A. Harding]

On 2022-09-29 05:39, Ruben Somsen via bitcoin-dev wrote:
> An alternative mitigation (more user friendly, but more implementation
> complexity) would be to require the sender to reveal their intended
> transaction to the server prior to receiving the address[^9]. This is
> not a privacy degradation, since the server could already learn this
> information regardless. If the transaction doesn't end up getting
> sent, any subsequent attempt to reuse one of the inputs should either
> be (temporarily) blacklisted or responded to with the same address
> that was given out earlier
> [...]
> [^9]: *This would essentially look like an incomplete but signed
> transaction where the output address is still missing.*

Hi Ruben,

Instead of maintaining a database of inputs that should be blocked or 
mapped to addresses, have the spender submit to you (but not the 
network) a valid transaction paying a placeholder address and in return 
give them a guaranteed unique address.  They can then broadcast a 
transaction using the same inputs to pay the guaranteed unique address.  
If you don't see that transaction within a reasonable amount of time, 
broadcast the transaction paying the placeholder address.  This makes it 
cost the same to them whether they use the unique address or not.  By 
placeholder address, I mean an address of yours that's never received a 
payment but which may have been provided in a previous invoice (e.g. to 
prevent exceeding the gap limit).

In short, what I think I've described is the BIP78 payjoin protocol 
without any payjoining going on (which is allowed by BIP78).  BTCPay 
already implements BIP78, as do several wallets, and I think it 
satisfies all the design constraints you've described.

-Dave

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[Ruben Somsen]

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

Hi David,

Thanks for the excellent suggestion, that makes the protocol much more
elegant and actually increases my optimism about its practicality. Also,
interesting observation that there is overlap with BIP78. From the
perspective of the recipient it does mean there's a potential privacy
reduction when a placeholder transaction goes through (these should perhaps
be marked in the wallet?), but I suppose this is still better than no
payment at all. I also like your point that it doubles as a way to
potentially bridge gaps.

Cheers,
Ruben







On Mon, Oct 3, 2022 at 12:48 AM David A. Harding <dave@dtrt.org> wrote:

> On 2022-09-29 05:39, Ruben Somsen via bitcoin-dev wrote:
> > An alternative mitigation (more user friendly, but more implementation
> > complexity) would be to require the sender to reveal their intended
> > transaction to the server prior to receiving the address[^9]. This is
> > not a privacy degradation, since the server could already learn this
> > information regardless. If the transaction doesn't end up getting
> > sent, any subsequent attempt to reuse one of the inputs should either
> > be (temporarily) blacklisted or responded to with the same address
> > that was given out earlier
> > [...]
> > [^9]: *This would essentially look like an incomplete but signed
> > transaction where the output address is still missing.*
>
> Hi Ruben,
>
> Instead of maintaining a database of inputs that should be blocked or
> mapped to addresses, have the spender submit to you (but not the
> network) a valid transaction paying a placeholder address and in return
> give them a guaranteed unique address.  They can then broadcast a
> transaction using the same inputs to pay the guaranteed unique address.
> If you don't see that transaction within a reasonable amount of time,
> broadcast the transaction paying the placeholder address.  This makes it
> cost the same to them whether they use the unique address or not.  By
> placeholder address, I mean an address of yours that's never received a
> payment but which may have been provided in a previous invoice (e.g. to
> prevent exceeding the gap limit).
>
> In short, what I think I've described is the BIP78 payjoin protocol
> without any payjoining going on (which is allowed by BIP78).  BTCPay
> already implements BIP78, as do several wallets, and I think it
> satisfies all the design constraints you've described.
>
> -Dave
>

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

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[rot13maxi]

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

Hi all,

I'm working on a light wallet and have been kicking around a really similar idea (we already have a hosted component that knows the user's xpub, why not provide an endpoint that can vend fresh receive addresses to senders and try to make the easy-path for sending bitcoin to our users also be the more private one). I wanted to throw in another thing you can build with this setup: address authentication.

Bitcoin addresses don't (generally) carry any semantic information that humans can use at-a-glance to distinguish legitimate addresses from illegitimate addresses. There have been instances of clipboard-hijacking malware that have used this fact to steal bitcoin -- a user goes to a webpage (or email, or IM or whatever), copies an address, and then pastes it into their bitcoin wallet. Unbeknownst to them, the clipboard contents have been replaced with an address controlled by some bad actor. The wallet just builds the transaction to whatever addresses the "user" supplied, and the user is none-the-wiser until after the funds have left their wallet.

Now imagine instead that the wallet has some address book with a pubkey for each recipient the user wants to send bitcoin to. Alice wants to pay Bob, so she clicks "Bob" in her transaction UI. Her wallet goes and asks the address server for an address for Bob. The address server picks an unused address, and has it signed (depending on the setup, this could be that the address server also has the Address Authentication privkey for bob, or it could be that bob gets some callback or notification, or that bob has pre-signed a batch of addresses. it will depend on the implementation). The address server sends a signed blob back to alice that contains an address and a signature proving that the address is in fact Bob's. Now Alice's wallet can tell whether or not the address it's putting in the transaction output belongs to Bob, even if that data was intercepted between the address server and the wallet (this doesn't help if the address server is malicious or has been compromised, but that's a different problem).

It would be really nice to have a protocol here that can make wallets interoperable in fetching fresh addresses from Address Servers and in the return schema that can include signatures and other metadata (like optimistic expirations, maybe other invoice data?).

Love the conversation so far. Happy to dig into this further with anyone else interested :)

Cheers,
rijndael

------- Original Message -------
On Monday, October 3rd, 2022 at 7:01 PM, Ruben Somsen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi David,
>
> Thanks for the excellent suggestion, that makes the protocol much more elegant and actually increases my optimism about its practicality. Also, interesting observation that there is overlap with BIP78. From the perspective of the recipient it does mean there's a potential privacy reduction when a placeholder transaction goes through (these should perhaps be marked in the wallet?), but I suppose this is still better than no payment at all. I also like your point that it doubles as a way to potentially bridge gaps.
>
> Cheers,
> Ruben
>
> On Mon, Oct 3, 2022 at 12:48 AM David A. Harding <dave@dtrt.org> wrote:
>
>> On 2022-09-29 05:39, Ruben Somsen via bitcoin-dev wrote:
>>> An alternative mitigation (more user friendly, but more implementation
>>> complexity) would be to require the sender to reveal their intended
>>> transaction to the server prior to receiving the address[^9]. This is
>>> not a privacy degradation, since the server could already learn this
>>> information regardless. If the transaction doesn't end up getting
>>> sent, any subsequent attempt to reuse one of the inputs should either
>>> be (temporarily) blacklisted or responded to with the same address
>>> that was given out earlier
>>> [...]
>>> [^9]: *This would essentially look like an incomplete but signed
>>> transaction where the output address is still missing.*
>>
>> Hi Ruben,
>>
>> Instead of maintaining a database of inputs that should be blocked or
>> mapped to addresses, have the spender submit to you (but not the
>> network) a valid transaction paying a placeholder address and in return
>> give them a guaranteed unique address. They can then broadcast a
>> transaction using the same inputs to pay the guaranteed unique address.
>> If you don't see that transaction within a reasonable amount of time,
>> broadcast the transaction paying the placeholder address. This makes it
>> cost the same to them whether they use the unique address or not. By
>> placeholder address, I mean an address of yours that's never received a
>> payment but which may have been provided in a previous invoice (e.g. to
>> prevent exceeding the gap limit).
>>
>> In short, what I think I've described is the BIP78 payjoin protocol
>> without any payjoining going on (which is allowed by BIP78). BTCPay
>> already implements BIP78, as do several wallets, and I think it
>> satisfies all the design constraints you've described.
>>
>> -Dave

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

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[Bryan Bishop]

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

On Mon, Oct 17, 2022 at 7:05 PM rot13maxi via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Unbeknownst to them, the clipboard contents have been replaced with an
> address controlled by some bad actor.
>
[snip]

> Now imagine instead that the wallet has some address book with a pubkey
> for each recipient the user wants to send bitcoin to.
>

Isn't this the same problem but now for copy-pasting pubkeys instead of an
address?

- Bryan
https://twitter.com/kanzure

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

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[Ruben Somsen]

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

Hi Rijndael,

I think your thoughts are pretty much compatible with this proposal, as
what I'm describing (the recipient signing their keys) is also essentially
a form of authentication.

It's a good observation that in general this makes the communication of
addresses more secure. I do wish to re-emphasize Bryan's remark that you
still need to ensure the pubkey itself is securely communicated.

>depending on the setup, this could be that the address server also has the
Address Authentication privkey for bob, or it could be that bob gets some
callback or notification, or that bob has pre-signed a batch of addresses

In my opinion the only meaningful distinction is whether Bob runs the
Trustless Address Server himself (full privacy) or not. In either case I
see no reason to diverge from the model where Bob deposits a batch of
signed keys to the server, ensuring that no malicious addresses can be
handed out.

Note I discussed the Trustless Address Server design in the first 20
minutes of this podcast:
https://twitter.com/bitcoinoptech/status/1580573594656333825

And I also brought it up in my presentation at Tabconf last Saturday, but
that video isn't online yet.

Cheers,
Ruben



On Tue, Oct 18, 2022 at 2:07 AM Bryan Bishop via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Mon, Oct 17, 2022 at 7:05 PM rot13maxi via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Unbeknownst to them, the clipboard contents have been replaced with an
>> address controlled by some bad actor.
>>
> [snip]
>
>> Now imagine instead that the wallet has some address book with a pubkey
>> for each recipient the user wants to send bitcoin to.
>>
>
> Isn't this the same problem but now for copy-pasting pubkeys instead of an
> address?
>
> - Bryan
> https://twitter.com/kanzure
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[Andrew Poelstra]

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

On Mon, Oct 17, 2022 at 07:07:07PM -0500, Bryan Bishop via bitcoin-dev wrote:
> 
> Isn't this the same problem but now for copy-pasting pubkeys instead of an
> address?
>

No, as I understand the proposal, the "public key" held by the wallet is simply
a signing key used to authenticate addresses, and never leaves the wallet. Yes,
if the wallet's own memory is compromised, it can be tricked into accepting bad
addresses, but this is much much harder than compromising data on the clipboard,
which basically any application can do without any "real" exploits or special
permissions.

As an extreme, this proposal could be run on a hardware wallet which had some
out-of-band way to obtain and authenticate public keys (similar to Signal QR
codes).

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[rot13maxi]

Hello Andrew and Bryan,

> No, as I understand the proposal, the "public key" held by the wallet is simply
> a signing key used to authenticate addresses, and never leaves the wallet. 

That's right (or at least, that's the intent). Think of importing someone's GPG key and then using it to validate future signed messages from them. In this case, the public key stays in your "address book" entry for a person and then whenever you need to fetch a fresh address for them from the Address Server, your wallet can validate that it's for their wallet. 

Making sure that you import a legitimate/authentic public key is a problem, but you only need to do it once per recipient, instead of doing it every time you need to transact with that person. Maybe that's something you solve in UI (i.e. Signal has you compare strings with your counter-party), or something you can solve through other metadata (GPG had WoT, or if you're already using an address server maybe there's some PKI scheme that's appropriate, etc.). 


Rubin, I think you responded on another branch of the thread, but thanks for the podcast link. I'll check it out!

Cheers,

Rijndael

------- Original Message -------
On Tuesday, October 18th, 2022 at 8:42 AM, Andrew Poelstra <apoelstra@wpsoftware.net> wrote:


> On Mon, Oct 17, 2022 at 07:07:07PM -0500, Bryan Bishop via bitcoin-dev wrote:
>
> > Isn't this the same problem but now for copy-pasting pubkeys instead of an
> > address?
>
>
> No, as I understand the proposal, the "public key" held by the wallet is simply
> a signing key used to authenticate addresses, and never leaves the wallet. Yes,
> if the wallet's own memory is compromised, it can be tricked into accepting bad
> addresses, but this is much much harder than compromising data on the clipboard,
> which basically any application can do without any "real" exploits or special
> permissions.
>
> As an extreme, this proposal could be run on a hardware wallet which had some
> out-of-band way to obtain and authenticate public keys (similar to Signal QR
> codes).
>
> --
> Andrew Poelstra
> Director of Research, Blockstream
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster