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

From: Ruben Somsen <rsomsen@gmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse
Date: Thu, 29 Sep 2022 17:39:18 +0200	[thread overview]
Message-ID: <CAPv7TjbOcH2mte8SWALc2o5aEKLO7qoZ-M_e1wHdGSp6EmMc2Q@mail.gmail.com> (raw)

[-- 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 --]