Topic: How to truly anonymously send coin to the Democratic Party - page 2. (Read 2319 times)

This was originally proposed by ByteCoin, and then I tried to expand on it in a super-complicated way that would reduce the how much of the blockchain would have to be searched for such transactions.  In the end, I think the idea ultimately works, but only if Bitcoin doesn't catch on... it's just way too costly when simple blockchain verification will be difficult to execute, much less additional ECDSA ops on each tx to look for a multitude of potential receiving addresses.

I think the idea is awesome and elegant and completely in the spirit of Bitcoin.  But it's not scalable  

By the way, the concept of a*(b*G) == b*(a*G) is also known as "Diffie-Hellman Shared Secret".  It is frequently used for key exchange:  you use each others' public keys to derive a shared secret which you then use as, say, an AES key for encrypting further communications.  There's actually a lot of cool and creative things you can do with DHSS, like creating pseudo-multi-signature addresses.

This is straight Diffie–Hellman key exchange. You each have a public key and generate a shared secret using your private key and the other's public key.  Nothing I invented.

Interesting idea. If I've interpreted it correctly, this looks like something a client could pretty easily implement. It could definitely get costly to check every transaction to see if an output is yours (which makes me wonder about how this would be done in some of the lighter clients), but there are definitely people who would be willing to sacrifice some time for complete anonymity. Also, I'm pretty surprised by the property aY=yA. I can imagine there's a lot of uses for a number which is specific to each pair of people, yet deterministically calculable by only themselves.

Let’s say you want to contribute but you’re embarrassed. Using Bitcoin today would still leave you exposed to being identified by analysis of the block chain. Checking the web of transactions we see:

     k1 (MtGox) -> k2 (Joe Smith) -> k3 -> k4 -> k5 (Democratic Party donation address)

Where the k(i)’s are transaction keys and some can be linked to real people and organizations. The Democratic Party one is obvious. It would be the donation key on their web site. k2 is tied to Joe Smith because he bought the coins on an exchange (which owns k1) and they have his name on file.

The current bloc chain is a web of transactions with anonymous nodes and well known nodes. Identifying who sent what to who is a hit and miss proposition of filling in the holes. The system will not, in general, secure your anonymity. That’s why we say Bitcoin is not truly anonymous.

The answer is to use Sender Generated Keys.

If the sender can generate a public key for the receiver such that:

1.   Only the receiver can generate the private part for it
2.   No third party can determine that the key in fact belongs to that receiver

Then we change the web of transaction map into something like this:

   k1 -> k2 -> k3 -> k4 -> k5

where each key is not associated with a principal (from a third party point of view). Separately, each principal has a certificate that is used by senders to generate new and truly anonymous transaction keys for each transaction.

   Cert(MtGox)    Cert(Joe Smith)    Cert(Democratic Party)

The certificate has a public key and any other information the owner wishes to add (or not).

In the current practice a receiver can generate anonymous keys at will. The problem is that the receiver organization would have to _publish_ them. Hence there is a map between organizations and these keys and they are no longer anonymous. Alternatively Joe could negotiate a private transfer of a key but that leaves a trail as well. (email etc.). In the current system you cannot escape the fact that identity is mixed in with some of the transaction keys lowering the anonymity of all keys.

Using principal certificates and sender generated keys gives Joe Smith much better anonymity than the current system.

-----------------------------------------------------------
This is how Sender Generated Keys work:

Let Alice publish a certificate with a public key. (This cert has a key that is NOT a transaction key. It cannot be used in a normal fashion by other clients to send to.) Let "a" be the cert private key.  The cert public key is "A" (A=aQ where Q is the basis point in the cryptographic curve).  A is available in the Cert created by Alice.

Also, let Bob have a wallet and it has coins under a public key "Y" so the bitcoin block chain has a transaction transferring coins to Y and Bob has the private key, "y", which corresponds to Y, but no one knows that Bob owns Y.

Bob wants to anonymously send some coins to Alice. He looks up the certificate for Alice and extracts A. Bob’s client generates a public key "X" from A, y, and "m" (m is randomness derived from parts of the transaction that transfers the coins).  X has the property that only Alice can derive the private key "x" and only Bob knows that Alice owns X. Alice can spend the coins in X by generating x and using it to sign a transaction spending the coins at some future time.

Bob generates X by first generating a shared secret, s, as follows:

     s=Hash(m,yA)     

     X = sA

(Note yA and sA are cryptographic multiplies in ECC). Only Bob and Alice can generate s.  Also, Bob cannot generate the private part of X but he can transfer coins to X.

Alice generates x, the private part of X, as follows:

     •   She obtains m and Y from the transaction

     •   She calculates the shared secret s=Hash(m,aY).   Note, aY = yA and only Bob and Alice can calculate them.

     •   Then x = sa (modulo a large prime determined by the ECC)

She can check that X = xQ. Also, X is derived from A but no one but Bob can prove Alice is the owner of X since only Alice and Bob know s.

“m” is chosen so that no two transactions produce the same s. Hence X will always be unique to that transaction. m would be a few bytes from the transaction that are unique to the transaction but are not dependent on X, the receiving key in the transaction. (This is important so we don’t have a circular definition for X).

Alice has a client that would have to check every new transaction for the property that s = Hash(m,aY) and X = sA to know to add the coins to the balance in the wallet. She can tell that she has received coins.

(Note this checking is expensive. We could save time by leaving a few bytes from Hash(s) in an available field of the transaction. That would save one of the two required ECC multiplies. The client would still have to calculate an s for each transaction but after that the Hash(s) is relatively cheap.)