I had an idea on how to increase transaction privacy with something I was calling "enumerated addresses." About a week after I had the initial idea, this was posted:
https://bitcointalk.org/index.php?topic=130456.0. I also found
https://bitcointalk.org/index.php?topic=131243.0 and
http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/ as well. All of which essentially contain my idea, in one form or another, and all are much more fleshed out.
Even though others had the idea first, I figure summarizing my idea here is still worth a post.
The initial impetus came when reading the Satoshi paper. The paper discusses how addresses can become associated with each other: "Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner." That is, if all my addresses have less coin than I need to send, I will need to combine multiple addresses in the input. In general, this is a very strong indicator that the input addresses were owned by the same person.
We could instead send the coins in individual transactions. However, if we don't want the addresses associated with each other, the transactions would have to be spread out in time. Otherwise there would be a sequence of transactions sent to the same address at roughly the same time -- enough to associate the sending addresses again. (Albeit not as strongly.)
If each input could use a different output address, we wouldn't have to spread the transactions out in time. Thus, we need some way for the payee to send a list of addresses. It turns out that we can use the properties of public and private keys in ECDSA to generate this list of associated, or enumerated, keys.
All Bitcoin addresses are based on ECDSA over the elliptic curve secp256k1. We'll call the generator of the group associated with this curve 'G.' A private key is formed by choosing a 256-bit integer, 'a', and the public key is then constructed as 'aG' -- the generator added to itself 'a' times. It turns out that given 'a' it is easy to calculate 'aG' but when given 'aG' it is difficult to calculate 'a'. This disparity of difficulty is what allows us to define public-key cryptography on this group.
If we have a public key 'aG', we can define a collection of "enumerated keys," '{(a + n)G : n = 1, 2, ..., M}', simply by adding 'G' to the public key for every new address needed. Adding 'G' to the public key corresponds to adding '1' to the private key. Moreover, knowing that 'aG, (a + 1)G, ..., and (a + M)G' are all valid public keys does not help in finding 'a' -- not even if we are given valid signatures for each key. In this way the payee doesn't have to provide multiple addresses, he only has to provide one. When the transactions are sent, they aren't sent to the known payee address, but rather to the enumerated addresses. The payee simply checks '(a + 1)G, '(a + 2)G, ..., (a + M)G' until he finds an address with no funds sent to it at which point he knows he has enumerated all of the addresses.
Unfortunately, as long as this method is public, an analyst can also calculate the keys '(a + 1)G, (a + 2)G, ...' and thus still associate the input addresses with each other. So, simple enumeration doesn't work.
Instead, if we used some sort of keyed pseudo-random number generator, the keys could be enumerated only if you knew the secret. For example, given a shared secret, one could take the output of an HMAC as the next public key. That is, assume we have a shared secret, "password". Form the 256-bit number 's(n) = SHA256("password" || "n" || SHA256("password" || "n"))' and construct the public key as '(a + s(n))G'. (This isn't really what an HMAC is for, but it would work.) In this way multiple addresses can be formed from a single address and, as long as the shared secret stays secret, there is no way to guess the "enumerated" keys.
This ignores the fact that a Bitcoin address is not a public key, it is a hash of a public key. It is not feasible to figure out the public key corresponding to an address when all you have is the address. In fact, the public key corresponding to an address is normally only transmitted when coins are sent from that address. Therefore, if an address is to be used to generate enumerated addresses, that address must have previously appeared as an input to at least one transaction.
We need also need to transmit the secret. If we have the payee's public key, we can use it to encrypt the secret we want to share. However, that secret must be sent somehow. (It could be sent in the transaction somehow I guess. However I know using the block chain as a database is frowned upon.)
I'm implementing a proof-of-concept in the standard client for this if anyone else is interested.
