Trustless Address Server – Outsourcing handing out addresses to prevent reuse

Trustless_Address_Server.md

Trustless Address Server

Outsourcing handing out addresses to prevent address reuse

Also discussed on bitcoin-dev.

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¹ and Silent Payments², though neither is without downsides.

One area that is seemingly underexplored is that of outsourced interaction. BTCPay Server³ 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⁴. 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⁵. 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⁶). If the sender doesn't mind (or maybe even desires) having their payments correlated by the recipient, a fresh xpub⁷ 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⁸ 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⁹. 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¹⁰.

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¹¹. 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

Footnotes

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 ↩

I guess my point is that the majority of light clients use an approach that doesn't really lend itself to this proposal, and could be argued to actively lean away from it (for good reasons!). I raised it because I'm not sure if the approach used by the Electrum protocol is widely understood. Also, as an aside, connecting to your own Electrum server (rather than a public one) is increasingly becoming common given the popularity of packaged node projects.

the majority of light clients use an approach that doesn't really lend itself to this proposal, and could be argued to actively lean away from it

Sorry, I don't follow this logic. If you just share the next 100 addresses then the privacy implications are pretty much the same. At most you could argue you're unnecessarily sharing future addresses with the server, but this is a relatively minor concern and trivially solvable by simply never using those addresses if you ever move away from the server or even using a new derivation path to fully avoid any overlap.

connecting to your own Electrum server (rather than a public one) is increasingly becoming common

Yes, that is an excellent development and not a situation this protocol is designed for (specifically, it breaks points a and b). That said, it is of course also possible to host your own Trustless Address Server if you are okay with having your node being publicly available (and otherwise Silent Payments seem like a good fit).

If you just share the next 100 addresses then the privacy implications are pretty much the same.

Well, I for one would certainly be opposed to Electrum servers storing any request data - even personal ones. Handling wallet data ephemerally is a major feature, and this privacy tradeoff in my mind is definitely not worth it.

if you are okay with having your node being publicly available (and otherwise Silent Payments seem like a good fit).

Or we could use BIP47, which stands apart as being entirely compatible with the Electrum protocol :)

I for one would certainly be opposed to Electrum servers storing any request data - even personal ones. Handling wallet data ephemerally is a major feature

So in summary, this protocol can't forget the data until after it is confirmed on-chain, whereas Electrum can immediately forget the data after it is requested. In neither case can it be known whether the data was actually forgotten. Our conclusions on these facts differ insofar that I consider this difference largely inconsequential, while you consider it a major privacy tradeoff and thus not worth the benefits it could gain us (outsourcing handing out addresses).

I still can't say I understand why our conclusions are so divergent, but I appreciate the feedback nonetheless.

On bitcoin-dev @harding made an excellent suggestion about how to protect the gap limit against DoS by first supplying the server with a valid transaction to a (possibly) reused address and only then handing out a fresh address and letting the sender create the final transaction that gets sent to the network. This ensures we can more easily impose a cost to the sender, which seems like a clear improvement. Here's the post and my reply, which I recommend reading for details.

In neither case can it be known whether the data was actually forgotten.

I disagree on this point - certainly I can verify to a reasonable degree of certainty whether software I compile and run myself is doing something, or not doing it. And on a broader point, one can verify that no published implementation has the capability to store request data. Of course many users delegate, placing trust in their node package to do this work for them, but that's true for all the software in the package, including Bitcoin Core.

I still can't say I understand why our conclusions are so divergent

Perhaps because our threat models are different.

certainly I can verify to a reasonable degree of certainty whether software I compile and run myself is doing something, or not doing it[. M]any users delegate, placing trust in their node package to do this work for them

Of course we both agree that if you run your own Electrum server (even via a node package) you have a reasonable assurance of being fine, but the specific model I'm addressing here is one where you're remotely connecting to someone else's Electrum server. At that point all assurances go out the window.

no published implementation has the capability to store request data

I don't think there's much of an incentive for chain analysis companies to publish the source code of their modified data retaining variant of Electrum server, while there is an incentive for them to run as many of them as possible to gather data.

I hope that clarifies my threat model a little bit.