ECDH in the payment protocol 

… or, how to solve the problems of stealth addresses


This article is about the stealth address technique, which recently popped up again due to being implemented in Dark Wallet.

I do not plan to implement stealth addresses in bitcoinj, although if someone else implementing sending to them I’d probably accept the patch. The reason is that the design has some problems and I think the same effect can be achieved in a better way.


What are stealth addresses?

Stealth addresses solve a basic problem: publishing a static Bitcoin address is convenient for receiving payments but has privacy leaks, because now your adversary can look up all the payments you received in the block chain.

One simple solution is to have a server that just iterates a BIP32 HD wallet branch you give it and vends the resulting addresses. By keeping the chain code hidden behind the server, we get unlinkability. But this is inconvenient for a few reasons:

  • You need a server that understands how to do this.
  • If the chain code ever leaks then all your payments become linkable.
  • More problematically, it doesn’t play well with signing in BIP70. To know who you are paying you want a signature from them, but then the server would have to be able to sign as you, which reduces security.

Why can’t you just publish the chain code and let the sender iterate the keys? Because the receipient of the money has to be able to find the payments, and that means they have to be able to enumerate all possible payment addresses. If the genuine recipient can enumerate them all, so can the adversary who wants to learn your income.

What’s needed is a way for a sender of money to generate a public key that they don’t own the private key for, such that the receiver can calculate the private key, and it’s impossible to link the payments together. This is what stealth addresses do.

How they work

The exact mechanism is well explained in this writeup by Peter Todd, although it’s worth noting the original idea of doing elliptic curve Diffie-Hellman is from ByteCoin in 2011. But at a very high level, the sender selects a large random number. This number is fed into a bunch of equations along with the published key and out pops what we need: a new public key (read: address) for which only the recipient can calculate the private part, and which can’t be linked to the original published key.

So far so good. Unfortunately it’s the conversion of this scheme into “stealth addresses” that is where the problems start. Let’s put aside the questionable name choice and look at the technology — to redeem the payment, the recipient needs the big random number. It can be public without causing problems, so the current stealth address scheme tags it onto the transaction using a new output.

First problem: stealth address usage bloats the block chain.

Second problem: stealth payments look different to regular payments.

Once such a tagged transaction is made, the recipient has to be able to find it. Normally a wallet does this by scanning the block chain looking for payments to addresses it generated. But in this case the address is brand new, and the tag is a random number. So the only way to find payments to your stealth address is to try all of them and see if any match. This scales very badly. There are attempts to hack around this problem in the original proposal, but they all assume big changes to the P2P protocol that nobody is implementing, and they work by simply sharding the anonymity set: you try some fraction of all possible payments, and the payer tries to make their payment fit by brute forcing the randomness to fit the requested fraction.

Third problem: stealth addresses and phones don’t mix

Of course by “phone” what I really mean is any CPU or battery constrained device, which these days is most of them.

Finally, the whole notion of an address is one we’re trying to get away from. Addresses can’t be easily extended with new features because it’s not backwards compatible. Wallets that don’t know about stealth addresses will just reject them, instead of successfully making a payment but with worse privacy — probably a popular option for deployment in the real world.

Fourth problem: stealth addresses are not backwards compatible.

There’s also a final issue that is is inherited from the notion of an address:

Fifth problem: you have no idea who sent you money or why.

Luckily there is an alternative design that fixes all these problems. It’s the one I plan to pursue long term.


ECDH in the payment protocol

BIP 70 is something I’ve talked about a lot, because it solves a lot of different problems. Once again it can help us out.

A BIP70 PaymentRequest message contains a list of requested outputs (think: list of addresses). We can extend the output message like this:

message Output {
optional uint64 amount = 1 [default = 0];
optional bytes script = 2;
optional boolean accept_ecdh = 3;
}

We add a third field that marks the output as accepting elliptic curve Diffie-Hellman (ECDH) payments. Old wallets don’t know about this field and will ignore it, resulting in a plain old pay-to-pubkey transaction. You don’t get the privacy, but you do get the money. If need be the protocol version can be optionally bumped for the case where you really would prefer to be private but poor.

Then we extend the Payment message to include a new, repeating ecdh_nonce field. Each nonce field (the big random number) is matched to the output in the directly submitted transactions:

message Payment {
optional bytes merchant_data = 1;
repeated bytes transactions = 2;
repeated Output refund_to = 3;
optional string memo = 4;
repeated bytes ecdh_nonces = 5;
}

Wallets that have been upgraded add in the nonces and don’t use the outputs that were actually requested: they’re modified to use the new derived keys.

Adding support to the payment protocol solves all the above problems at a stroke, by allowing you to include messages, keeping the nonces off the block chain, and submitting payments directly to the recipient thus avoiding expensive trial-and-error chain scanning and big P2P protocol changes.

However, it comes at a cost of a new problem.


Making person to person work

It’s not well known but Satoshi felt that a payment protocol was so important he implemented one in Bitcoin 0.1, the first version ever. It was initiated by typing the IP address of the recipient into the send money window. In his original vision addresses were kind of a quick hack, meant to be a fallback for when you couldn’t be sure you’d be online to receive the payment.

One reason it didn’t survive is that in the early days there weren’t any shops that accepted Bitcoin, so payments were always person to person and you could never really be sure someone would be online. Also IP addresses suck as a way to get data to someone. But the idea was sound.

BIP 70 works fine for shops. But because so many features either depend on BIP 70 or work better when it’s there, we need to solve the data transfer problem. Using the block chain as a scratchpad to store temporary data only one or two people care about is incredibly expensive and inefficient — people already complain about the bandwidth needed to serve the block chain, and stuffing data that doesn’t affect the consensus into it only makes that worse. If the block chain was the only way to do message transmission then it might be worth the cost. But it’s not the only way.

One of the next pieces of infrastructure we need is a simple network of store-and-forward servers. The original stealth address proposal discusses using BitMessage for this, but BitMessage has some very questionable design decisions in it and wouldn’t be suitable. What does a store and forward server need to do?

  1. Receive a PaymentRequest message, serve it via HTTP[S] GET on a unique URL.
  2. Accept Payment POSTs from wallets back to that URL, store them.
  3. Serve them back to the creator wallet and then delete them.

And that’s it. If this sounds very similar to email or instant messaging, that’s because it is. The original stealth address proposal writes off using a separate store-and-forward network on the assumption that it would be less reliable than just using Bitcoin, but there are plenty of reliable store-and-forward networks that people rely on every day, just as much as they rely on Bitcoin. Trying to abuse Bitcoin nodes to do store-and-forward results in bizarre hacks and crazy resource requirements: I assert that we can achieve better results by using a tool suited to the task.

What might such a system look like? It could be a little like email, where people explicitly pick a server and their wallet creates an account and either polls for new payments or just uses a hanging GET for immediate responsiveness. The “account” is just a unique HTTP URL on the server that accepts POST requests from wallets and GET requests when a password or key signature is presented. Once the Payment message is downloaded, the wallet takes responsibility for broadcasting it and showing the message (if any) to the user. People choose servers run by people they trust to provide reliable uptime, but no trust is needed beyond that — another BIP 70 extension can allow for encrypted Payment messages so the server is blind to their contents (using ECDH again).

Having to manually figure out who can be trusted to fix a server at 2am is kind of tedious though. That’s the kind of work computers are good at. So we could join these servers together into a Tor-like P2P network. Tor isn’t as decentralised as Bitcoin is: it sacrifices some decentralisation to make it work better. Tor nodes have their uptime and capabilities measured by “bandwidth authorities” which are trusted not to lie about what nodes can do. A coalition of wallet authors could likewise run uptime measurement servers that report back to wallets which ones are working well. The wallet app can then create an anonymous account, possibly paying a micropayment to do so, and then start vending its new URL in BIP 70 payment_url fields.

It would be convenient if the random URL could serve a simple web page when loaded by browsers instead of wallets, containing a bitcoin: QR code and a “Pay now” button, like what BitPay or Coinbase provide.

Long term, wallets could be augmented to test storage nodes and compile quality reports themselves, instead of relying on some third party services. Although this burns a bit of battery, the testing can be carried out at night when charging. Then if your wallet knows how to find your friends wallets, they could share such reports. This would result in a fully decentralised network for people who know other users already.

Once the above is implemented, it would be useful to define more BIP70 extensions to let people put (unauthenticated) names/pseudonyms, pictures and contact details into a payment request. People can then populate their wallets address books by loading up such files, and community run directory sites can make paying someone as easy as looking them up online. This does not require ECDH/stealth addresses of course because a wallet can always just constantly upload new versions of the payment request whenever a payment is received, but it does simplify things and avoids small amounts of reuse that could occur if a wallet was offline for a while.

The infrastructure I just talked about can be easily implemented by any reasonable programmer one step at a time, in layers. If you’re interested in experimenting with this, drop me a line: mike@plan99.net