How to truly anonymously send coin to the Democratic Party

[ffe]

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.)

[austonst]

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.

[ffe]

Also, I'm pretty surprised by the property aY=yA.

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.

[etotheipi]

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.

[austonst]

Also, I'm pretty surprised by the property aY=yA.

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.

I guess I was thinking more of point multiplication on elliptic curves and trying to visualize how the geometry would work out. Thinking of it as regular multiplication with modulus involved definitely helps out.

It's a shame it doesn't scale very well, and that much of the required computing power to scan transactions is on the receiver's side. I'd imagine a large company would have the processing power to check the whole blockchain, but it's mainly the individuals with their laptops and smartphones who would benefit from the anonymity.

[ffe]

There's actually a lot of cool and creative things you can do with DHSS, like creating pseudo-multi-signature addresses.

True.  See

[MoonShadow]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

[ffe]

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

Not true. Miners would not have to change to implement this.

This is independent of the current implementation in that the regular client does not have to change if this is implemented by some clients. Those clients willing to do the checking could implement this no problem.

[ffe]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

LOL - just joking. Didn't want to say Wiki-leaks or worse.

[MoonShadow]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

LOL - just joking. Didn't want to say Wiki-leaks or worse.

Worse than the Democratic Party?  What would that be, the Greens?

[ffe]

(which makes me wonder about how this would be done in some of the lighter clients)

Some deterministic wallet implementations have “light” clients talking to (untrusted) servers that handle the heavy work of scanning the bitcoin block chain and linking to multiple peers.

In that scenario the server should be able to check the ownership of a new transaction without being able to spend the coins in the transaction. However, allowing this would conflict with the stated property of privacy when using Bitcoin.

The following shows how you allow a server you choose to verify that you own a transaction without allowing the server to spend your coins or allowing the whole world to know which transactions are yours. It’s an intermediate level of trust that may not make sense to people who value strict privacy but is useful to people who value the light client deterministic single key property (for ease of multiple light client deployment, for example).

The Certificate master key is really a key doublet. The master private key is still "a" as above. However, now you generate a verifier private part “b”.  b = Hash(a). Let the public part of a be “A” and the public part of b be “B”.   A = aQ and B = bQ. The doublet “(A,B)” is published in the certificate for Alice. (A,B) and the private verifier b are given to the service(s) you are using to manage the block chain for you. With b the server can verify transaction ownership but not spend.

A sender would recover (A,B)  from Alice’s certificate. The sender then generates X as follows:

     s = Hash(m,yB)

     X = sA.

The sender sends coin to X.

A server holding verifier b would have to check every new transaction for the property that s = Hash(m,bY) and X = sA to know to add the coins to the balance in the wallet. (Note yB = bY). (As I mentioned above, this is expensive. We could save time by leaving a few bytes from Hash(s) in an available field of the transaction. The server would still have to calculate an s for each transaction but after that the Hash(s) is relatively cheap.)

Note the server can verify X belongs to Alice but cannot generate the private part of X.

The thin client Alice has generates x, the private part of X, as follows:  She is given m and Y from the transaction; then  s = Hash(m,bY);  x = sa (modulo a large prime determined by the ECC);  She can check that X = xQ.

The thin client can now sign a prepared transaction using x and return the signed transaction to the server when spending.

[etotheipi]

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

Not true. Miners would not have to change to implement this.

This is independent of the current implementation in that the regular client does not have to change if this is implemented by some clients. Those clients willing to do the checking could implement this no problem.

I didn't say it would have to be done by miners.  I implied that doing ECDSA-DHSS calculations on 1+ million transactions per hour is not feasible.  There's not 1 million tx/hour right now, but with any degree of success in the Bitcoin world, even having a single address which you know might be used for this kind of address extension will cause you to have to do at least 1 million ECDSA ops per hour.  That's a lot of electricity, just to find out if someone sent you money.

And that's only for one address.  Now you have to do one ECDSA-DHSS calculation for every address in your wallet on every tx, at least the ones that you suspect might be used for this kind of key extension.  For an organization like wikileaks which could post a single address once and dedicate a server to searching for incoming transactions, it makes sense.  But I don't see it working for regular users in the future...

[ffe]

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

Not true. Miners would not have to change to implement this.

This is independent of the current implementation in that the regular client does not have to change if this is implemented by some clients. Those clients willing to do the checking could implement this no problem.

I didn't say it would have to be done by miners.  I implied that doing ECDSA-DHSS calculations on 1+ million transactions per hour is not feasible.  There's not 1 million tx/hour right now, but with any degree of success in the Bitcoin world, even having a single address which you know might be used for this kind of address extension will cause you to have to do at least 1 million ECDSA ops per hour.  That's a lot of electricity, just to find out if someone sent you money.

And that's only for one address.  Now you have to do one ECDSA-DHSS calculation for every address in your wallet on every tx, at least the ones that you suspect might be used for this kind of key extension.  For an organization like wikileaks which could post a single address once and dedicate a server to searching for incoming transactions, it makes sense.  But I don't see it working for regular users in the future...

The server for thin clients (see my post above) would have to be scaled to deal with this problem, I agree.

My impression is processors can do 1,000's of ECDSA-DHSS per second today. I bet if you cared enough about this to dedicate processing to it, available processing power would keep up with total transactions.

As long as miners can keep up with regular transactions, Wikileaks should be able to deploy a server that can keep up as well.

[etotheipi]

The server for thin clients (see my post above) would have to be scaled to deal with this problem, I agree.

My impression is processors can do 1,000's of ECDSA-DHSS per second today. I bet if you cared enough about this to dedicate processing to it, available processing power would keep up with total transactions.

As long as miners can keep up with regular transactions, Wikileaks should be able to deploy a server that can keep up as well.

But my point was, that the usefulness of this solution is limited to isolated cases (which are still useful cases).  Sure you can do 1,000 ECDSA ops per second, but if there are 1,000 addresses in your wallet and any of them could be used in an address-extension like this, you're at 100% CPU just to check 1 tx per second.  And we know 1 tx per second is nothing compared to the desired adoptance of Bitcoin.  The math doesn't have to add up exactly (who has 1,000 addresses in their wallet?) but the point is it's entirely possible for network volume to overwhelm even powerful computers, which puts the whole idea on shaky grounds.

I actually really like the idea for wikileaks, political dissidents, or internet gambling, if they use a single public address and dedicate systems to it... but outside of that very niche market, I don't see it working.

[MoonShadow]

The server for thin clients (see my post above) would have to be scaled to deal with this problem, I agree.

My impression is processors can do 1,000's of ECDSA-DHSS per second today. I bet if you cared enough about this to dedicate processing to it, available processing power would keep up with total transactions.

As long as miners can keep up with regular transactions, Wikileaks should be able to deploy a server that can keep up as well.

But my point was, that the usefulness of this solution is limited to isolated cases (which are still useful cases).  Sure you can do 1,000 ECDSA ops per second, but if there are 1,000 addresses in your wallet and any of them could be used in an address-extension like this, you're at 100% CPU just to check 1 tx per second.  And we know 1 tx per second is nothing compared to the desired adoptance of Bitcoin.  The math doesn't have to add up exactly (who has 1,000 addresses in their wallet?) but the point is it's entirely possible for network volume to overwhelm even powerful computers, which puts the whole idea on shaky grounds.

I actually really like the idea for wikileaks, political dissidents, or internet gambling, if they use a single public address and dedicate systems to it... but outside of that very niche market, I don't see it working.

http://libdspace.uwaterloo.ca/bitstream/10012/855/1/jlutz2003.pdf

Dedicated hardware, sure.  Not unlikely if the market should arise.

[ripper234]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

Here it is - 1D5yADZsb1XGE15rbBRWhe2QkRDGSv3588

Edit: Propster admin wrote this:

I will be delivering this amount, and closing this Tip Jar.  Both democrats and republicans are against laissez-fair capitalism and are ultra-religious. This policy is described in the Howto, at the end.

[ffe]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

Here it is - 1D5yADZsb1XGE15rbBRWhe2QkRDGSv3588

Google search
-----------------------
Your search - 1D5yADZsb1XGE15rbBRWhe2QkRDGSv3588 - did not match any documents.

Suggestions:

Make sure all words are spelled correctly.
Try different keywords.
Try more general keywords.
-----------------------

Even Google doesn't want you contributing to them...

[MoonShadow]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

Here it is - 1D5yADZsb1XGE15rbBRWhe2QkRDGSv3588

You're the party treasurer, I take it?

[ripper234]

I'm curious.  What is the bitcoin donation address of the Democratic Party?

Here it is - 1D5yADZsb1XGE15rbBRWhe2QkRDGSv3588

You're the party treasurer, I take it?

Hell no, I just opened a tip jar on Propster for them.
It's a beautiful concept really.

Read the FAQ

[FreeMoney]

Noob question.

You cannot take an address and make a new address that the same private key can use, correct? But this is just because of the hashing going on, if we used pure public/private key pairs that would actually be possible?

Regarding identifying the sender generated keys. The sender could notify the receiver out of band, right?

I have a feeling like I'm missing something.