[PROPOSAL] Untrackable addresses

[abacabadabacaba]

Currently, if someone publishes his Bitcoin address (to receive donations, for example), anyone can see how much money he got. I propose a protocol which can be used to receive donations without revealing all payments to everyone. A person who wishes to receive money would generate 3 keys:
1. Public key can be used to send money to the person, but not to see when others send money to him.
2. Semi-private key can be used to see all incoming transactions, but not spend them.
3. Private key is necessary to spend the money.
It is expected that the user will publish his public key, keep hist semi-private key on his online computer, and keep his private key offline.

Implementation
I will use lower case letters to denote ECDSA private keys and corresponding upper case letters to denote corresponding public keys.
Creating an address: to create an address, a user generates to pairs of ECDSA keys. Let's call them (a, A) and (b, B). Then, (A, B) is a public key, (a, B) is a semi-private key, and (a, b) is a private key.
Sending money: suppose that someone wants to send money to key (A, B), and some of it is currently owned by key C. He performs Diffie–Hellman key exchange between keys A and C to generate a shared secret d=A*c. Then he uses a type 2 key derivation function (used in type 2 deterministic wallets) to generate a new public key E from B and d. He than sends money to an address generated from E. Note that C must appear in one of the inputs.
Receiving money: on the receiving side, the user scans all transactions to see if they match his semi-private key (a, B). To do so, he iterates over all inputs that match send-to-address template. Let C be a key that appears in one of such inputs. He computes d=C*a and E. If E matches the address the money was sent to, then this money was sent to him.
Spending money: to generate private key e, the user generates d as before and derives e from b and d.

Why this is useful?
It would be able to publish an address such that no one would be able to see how much money was received.
If someone wants to send money owned by multiple keys, he can send it in multiple transactions that can't be linked to each other.
Finally, users won't need to have many addresses. They can send change to themselves using the same procedure.

[cunicula]

Interesting. Txns recorded in the blockchain would then have a unique addresses for each sender-recipient pair. Is that correct?

[abacabadabacaba]

If everyone uses this scheme, then it would appear that each address ever received at most one transaction. Every transactions would have a unique address. However, if someone sends money twice from the same normal address to the same proposed address, then destination normal address will also be the same. But these coins are tied to each other anyway.

[Sergio_Demian_Lerner]

Destination Address Randomization (DAR) solves this problem.

See http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

The simple idea is to send the money to a multiple of the public key, and send the factor privately.

[abacabadabacaba]

My proposal doesn't require sending anything privately. All the necessary information is contained in the transaction itself. At the same time, the transaction looks exactly like the ordinary send-to-address transaction.

[Sergio_Demian_Lerner]

My proposal doesn't require sending anything privately. All the necessary information is contained in the transaction itself. At the same time, the transaction looks exactly like the ordinary send-to-address transaction.

You can also send the factor encrypted with the recipient public key, embedded in the input script. This way it works exactly like your proposal.

[Pieter Wuille]

How about just using unique addresses for every transaction from the start? Using a payment protocol (such as the one being developed), the problem of address reuse goes away entirely.

I agree that for some cases, like anonymous donations, where you don't want any out-of-band communication to occur a scheme such as this would be nice.

[abacabadabacaba]

My proposal doesn't require sending anything privately. All the necessary information is contained in the transaction itself. At the same time, the transaction looks exactly like the ordinary send-to-address transaction.

You can also send the factor encrypted with the recipient public key, embedded in the input script. This way it works exactly like your proposal.

Not exactly. Everyone would be able to see that something is embedded in the input script. In my proposal, nothing reveals that the transaction is in any way different from an ordinary pay-to-address transaction.

I agree that for some cases, like anonymous donations, where you don't want any out-of-band communication to occur a scheme such as this would be nice.

That's the whole point. A person who wants to receive donations doesn't have to set up a server for out-of-band communication. He only needs to publish an address. This also means that it won't be necessary to keep multiple keys in a wallet. One key would be enough.

[cunicula]

Destination Address Randomization (DAR) solves this problem.

See http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

The simple idea is to send the money to a multiple of the public key, and send the factor privately.

Couldn't you then decrypt this by testing all known public keys against each message?

The proposed method seems stronger to me.

[Sergio_Demian_Lerner]

Destination Address Randomization (DAR) solves this problem.

See http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

The simple idea is to send the money to a multiple of the public key, and send the factor privately.

Couldn't you then decrypt this by testing all known public keys against each message?

The proposed method seems stronger to me.

Yes, each user should have two different keypairs. And so a pubkey specifically published for encryption.

[cunicula]

Destination Address Randomization (DAR) solves this problem.

See http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

The simple idea is to send the money to a multiple of the public key, and send the factor privately.

Couldn't you then decrypt this by testing all known public keys against each message?

The proposed method seems stronger to me.

Yes, each user should have two different keypairs. And so a pubkey specifically published for encryption.

But then you are back to communicating the public key privately, right?

[kjj]

Currently, if someone publishes his Bitcoin address (to receive donations, for example), anyone can see how much money he got. I propose a protocol which can be used to receive donations without revealing all payments to everyone. A person who wishes to receive money would generate 3 keys:
1. Public key can be used to send money to the person, but not to see when others send money to him.
2. Semi-private key can be used to see all incoming transactions, but not spend them.
3. Private key is necessary to spend the money.
It is expected that the user will publish his public key, keep hist semi-private key on his online computer, and keep his private key offline.

Implementation
I will use lower case letters to denote ECDSA private keys and corresponding upper case letters to denote corresponding public keys.
Creating an address: to create an address, a user generates to pairs of ECDSA keys. Let's call them (a, A) and (b, B). Then, (A, B) is a public key, (a, B) is a semi-private key, and (a, b) is a private key.
Sending money: suppose that someone wants to send money to key (A, B), and some of it is currently owned by key C. He performs Diffie–Hellman key exchange between keys A and C to generate a shared secret d=A*c. Then he uses a type 2 key derivation function (used in type 2 deterministic wallets) to generate a new public key E from B and d. He than sends money to an address generated from E. Note that C must appear in one of the inputs.
Receiving money: on the receiving side, the user scans all transactions to see if they match his semi-private key (a, B). To do so, he iterates over all inputs that match send-to-address template. Let C be a key that appears in one of such inputs. He computes d=C*a and E. If E matches the address the money was sent to, then this money was sent to him.
Spending money: to generate private key e, the user generates d as before and derives e from b and d.

Why this is useful?
It would be able to publish an address such that no one would be able to see how much money was received.
If someone wants to send money owned by multiple keys, he can send it in multiple transactions that can't be linked to each other.
Finally, users won't need to have many addresses. They can send change to themselves using the same procedure.

Erm.  What exactly is stopping an attacker from doing the same math between the pubkey of each input and the list of known public keys to recover all of the transactions?

A, B and C are all publicly known, which means that d is known, which means that E is known.  The attacker still can't spend them because b is unknown, but he can sure see them.

P.S.  Diffie-Hellman is an online protocol.  It requires (bidirectional) active participation from both parties.

[Rudd-O]

I want to see this developed further.

[abacabadabacaba]

Erm.  What exactly is stopping an attacker from doing the same math between the pubkey of each input and the list of known public keys to recover all of the transactions?

A, B and C are all publicly known, which means that d is known, which means that E is known.  The attacker still can't spend them because b is unknown, but he can sure see them.

P.S.  Diffie-Hellman is an online protocol.  It requires (bidirectional) active participation from both parties.

To compute d an attacker would need to know either a or c. None of them is public.
I define d=A*c=C*a. The fact that it's hard to compute d from A and C is the basis of Diffie–Hellman key agreement protocol.

[prezbo]

How can you compute d=C*a, when d and a are integers, and C is an EC point? "d" should probably be market as "D", "E" could be "B+D" but then how can you calculate "e" from "b" and "D"?

[abacabadabacaba]

Well, d is an EC point hashed to an integer. So it can be implemented this way:

d=hash(A*c)=hash(C*a)
E=B+G*d
e=b+d

Here, hash is any hash function, and G is the base point.
Alternatively, a different key derivation function can be used:

E=B*d
e=b*d

I hope it's clearer now.

[prezbo]

Well, d is an EC point hashed to an integer. So it can be implemented this way:

d=hash(A*c)=hash(C*a)
E=B+G*d
e=b+d

Here, hash is any hash function, and G is the base point.
Alternatively, a different key derivation function can be used:

E=B*d
e=b*d

I hope it's clearer now.

ok, that would work, thanks for explaining. Haven't thought of just using an (encoded) ec point as an integer, stupid of me

[kjj]

Erm.  What exactly is stopping an attacker from doing the same math between the pubkey of each input and the list of known public keys to recover all of the transactions?

A, B and C are all publicly known, which means that d is known, which means that E is known.  The attacker still can't spend them because b is unknown, but he can sure see them.

P.S.  Diffie-Hellman is an online protocol.  It requires (bidirectional) active participation from both parties.

To compute d an attacker would need to know either a or c. None of them is public.
I define d=A*c=C*a. The fact that it's hard to compute d from A and C is the basis of Diffie–Hellman key agreement protocol.

Ahh, I missed that it was A*c and a*C.  To make this easier for non-cryptographers:

g is the basis point (x,y) of the curve we are using.  a and c are a secret 256 bit integers.  (Keep in mind that in EC math, a point multiplied by an integer is a point.)

A = a * g
C = c * g
A * c = a * g * c
C * a = c * g * a

EC multiplication is commutative, so A*c = a*g*c = c*g*a = C*a = E

[Mike Hearn]

That's very neat, thanks. I suggest we write this up on the wiki somewhere so it isn't lost. Chris Raggio was wanting to develop NFC-based "tip jars". Stefan and I brainstormed some protocols for this at the airport on the way back from the London conference but didn't come up with anything as neat as this.

Do you plan to implement it? The biggest challenge I see is scalability. Your algorithm requires running the computation for every input in order to find payments. That is a lot of EC math. I am skeptical it would be pleasant to receive such payments on a smartphone. It'd probably be OK on a desktop/laptop at current traffic levels with a good parallel implementation on an SPV client. I suppose you could have a semi-trusted third party identify the transactions for you (eg, a node).

If you want to integrate your scheme with bitcoinj I am happy to advise and do code review.

[thanke]

Cool idea!

However, if someone sends money twice from the same normal address to the same proposed address, then destination normal address will also be the same.

You can replace d by d*txid before deriving E, to get a unique address for each transaction even when resending from the same A.
Here txin is the hash of the output owned by A that is used as input for the transaction. The receiver sees txin as he iterates over all inputs.

Well, d is an EC point hashed to an integer. So it can be implemented this way:

d=hash(A*c)=hash(C*a)
E=B+G*d
e=b+d

Here, hash is any hash function, and G is the base point.

Practically, d would just be the x-coordinate of the point A*c, no need for a "real hash".

A remark, just to inform the readers of this paper (which was posted in this thread):
Your proposal makes a very nice substitution for the "signalling protocol" described in section IV.D of that paper, which is sub-optimal because it requires the private key to detect and monitor incoming payment. Your proposal invents the "semi-private" key and thereby allows to detect and monitor incoming payments without having to have the private key at hand. Taking A=B, hence private key=semi-private key, would give the old protocol.