Can we design the protocol, so that an address can only be used once as an output in a transaction?

Question

Most users reuse their addresses for deposits (ie. they receive money more than once on a given address).
Can the protocol be designed in such a way that an address can be used only once as an output in a transaction?
I guess there would need to be a way of quickly looking up if an address was already "used-up".
Also there would need to be a way to somehow to get "next address". For eg if an address is used for dividends and it can be used only once, the dividend payer should be able to automatically get a new address without the owner's (payee's) repeated input. (a one time set up of this, would be ok)
The point of this is to enhance privacy.

These are just thoughts, comments welcome.

Answer 1

Alice gets her computer hacked by Mallory, and she steals her wallet. Fortunately, Alice had encrypted it with a strong passphrase. Alice wants to sue Mallory for breaking into her computer, so she gets a lawyer, Bob.

• Alice's address, 10BTC --> Bob's address

Unfortunately for Alice, Mallory controls a node on the Bitcoin network, not too far from Alice, that quickly sees the transaction is from Alice (she has all her addresses), and instead relays, to hundreds of nodes at once, the transaction:

• Mallory's address, 1000 satoshis --> Bob's address

Which is incompatible with Alice's honest transaction.

Now, three things happen:

1) Alice tries to send the bitcoins to a different address given by Bob

2) Alice's nodes see her transaction as a double spend, and refuse to relay any transaction spending that coin to a different address

3) Mallory's transaction eventually gets mined. Back to trying to spend the coins to Bob.

Mallory can do other mischievous things with her position, such as allowing Alice to spend her bitcoin at a church fundraiser but not an abortion clinic (assuming she knows the address of both).

The main way people lose their privacy in bitcoin today is through heuristic analysis of the blockchain, not address reuse. Introducing a new network rule to protect users against their own stupidity will not significantly improve privacy (most wallets don't reuse addresses by default anyway), and opens up users to some interesting attacks.

Answer 2

I guess there would need to be a way of quickly looking up if an address was already "used-up".

There is, in Bitcoin. Just paste the address into the search box (not the one in the header) on https://blockchain.info.

Regarding your creation of a new address: Not only is this impossible in the way things are done currently, but it's furthermore contradictory to your goal of enhanced privacy.

First of all, let's talk about the current situation. Addresses are hashes of public keys (simplified). Those public keys are cryptographically associated with private keys which only the owner of them knows because knowing them enables one to spend the money which has been sent to the addresses associated with them. Hashes are one-way, meaning that you can determine the hash of something but not that something given only the hash. In order to pay to a different address belonging to the recipient, you either had to do a known function like incrementing by 1 on the private key – which is impossible not only because you can't find the public key given its hash but also because you can't find the private key given the public key – or somehow access a list of addresses of the recipient which would subvert the goal of increased privacy.

Now to all fictional situations, so all specifics of Bitcoin are dropped in this paragraph. If I'm the first one to pay to Mr. Smith's address 1e9Kp22 and you want to pay to that same address 5 minutes later, you have to get a new address. There can be either one or several addresses which can come after 1e9Kp22 but there certainly only is a small number of them so Mr. Smith can find the correct one. Let Φ(α) be the set of all addresses which are the possible next addresses after address α. In this general, fictional situation, we can't exclude the possibility of just being able to create new addresses belonging to Mr. Smith without undermining the exclusive right of the owner of coins the spend them. Since you can find a φ ∈ Φ(α) to pay to and know nothing more than me and ∀α∈Addreses : |Φ(α)| small, I can find your φ by just finding all elements of Φ(α) and examining which ones money has been paid to. Because we now both know that 1e9Kp22 belongs to Mr. Smith and I just learned that φ belongs to Mr. Smith, too, we both know that the address the other person used belongs to Mr. Smith.

The simple solution of this issue in practice is to just give a different address out for each expected payment, for example for each purchase in a web shop. Why would the shop owner give us both the same address in the first place? Addresses are completely free.