Decentralized coin mixing algorithm, using Namecoin and SIGHASH_ALL

[Qoheleth]

Here's the algorithm:

• Someone registers a K-V pair on the Namecoin network. The key is something like 'Melt:xxxxxxxxxxxx:0/3:1:InitialKey' - the xs are a randomly generated base58 round id (to distinguish from past and simultaneous swaps), the 0 is the id of the participant, the 3 is the number of bits of participants you're looking for (so, eight participants total, with ids 0-7), the 1 is the number of bitcoins that will be melted from each participant. The value assigned to this key will be your public key for communication with your fellow round participants.
• Other people chime in with their public keys at addresses like 'Melt:xxxxxxxxxxxx:5/3:1:InitialKey' (this guy would be claiming id 5 in the cabal's range 0-7).
• Each person posts their input and output addresses, encrypted with their binary-closest counterparty's private key. For instance, id 5 would post their input and output to 'Melt:xxxxxxxxxxxx:5/3:3:TxList', encrypted with the key at 'Melt:xxxxxxxxxxxx:4/3:1:InitialKey'.
• Each person posts the input and output addresses of their group of two, encrypted with the private key of that group's counterparties. For instance, id 5 would post his input and output, combined with those of id 4, to 'Melt:xxxxxxxxxxxx:5/3:2:TxList' - two copies would be posted there, the first encrypted with the key at 'Melt:xxxxxxxxxxxx:6/3:1:InitialKey', the second encrypted with the key at 'Melt:xxxxxxxxxxxx:7/3:1:InitialKey'.
• Things proceed. id 5 would post the combined inputs and outputs of ids 4-7 to 'Melt:xxxxxxxxxxxx:5/3:1:TxList', posting four copies: one each for ids 0-3 to read.
• Now everyone knows the transaction that will be submitted to the Bitcoin network. They all do so, requesting the transfer of their own coins, making finalization of the transaction contingent on everyone else's coins arriving, and setting the transaction to void itself if it is not finalized by some period from the earliest InitialKey registration time among those involved InitialKeys.

My playing through this algorithm as id 5 means that only the participant at id 4 knows the mapping of my coins from input to output. The participants at id 6 and 7 only know that my output belongs to "either id 4 or id 5". The participants at ids 0-4 only know that my output belongs to one of 0-4's inputs. Everyone else only knows that my output belongs to someone who participated.

The overhead of this method per round is however much it costs to do log2(n)+1 Namecoin registrations, where n is number of participants in the round. Obviously, you'd want to do more than one round, so that your closest counterparty isn't aware of the "true" input->output mapping, but only the mapping for that round.

Thoughts?

[1713428159]

1713428159

[1713428159]

1713428159

[1713428159]

1713428159

[1713428159]

1713428159

[1713428159]

1713428159

[iCEBREAKER]

Sounds good to me!

Reducing dependence on centralized coin mixers should be a priority.  This is the first step towards that goal.

Plus it helps the dot-bit project.  Win-win!

Question:  Would it be a good idea to first clean the Namecoins used in a recursive manner?   

[casascius]

Wow, excellent idea.

What if you enhanced it as follows:

1 - find some other way for the parties to communicate other than Namecoin.  What if all the mixing nodes (which are software bots, of course) just hooked up with one another in an IRC channel and communicated in real time?

2 - have three rounds so that the participants at the beginning of the round aren't disadvantaged.  During the first round, participants pass around bogus inputs and payout keys.  During the second round, participants add the real ones to the bogus data set, which will look indistinguishable from the bogus ones, which prevents the second participant from knowing which real keys belong to the first etc.  During the third round, participants remove the bogus data they added to the set.

So example:

Parties A,B,C,D,E,F get together in an IRC channel and all agree to start mixing.  They each generate an RSA keypair.  Let's assume the parties will speak in order, though ideally a simple deterministic hashing scheme based on their public keys could randomize the order (assuming they hash-commit to their public keys first).

All parties throw out their public key for everyone to see.  From then on, messages are encrypted for their intended recipient unless otherwise noted.

Party A chooses 100 random unspent txids from the block chain (that are probably not his), and generates 100 bitcoin addresses.  Basically he is creating a false claim that he wants to mix those coins to camouflage the coins he's going to add to the dataset in a future round.  At the same time, he creates a random mapping of how he'd supposedly like those 100 txids to be paid to his bitcoin addresses.  He sends the whole thing to B.  (Actually, he could add any number of each, but I'm using 100 for simplicity).

Party B does the same thing, adds his data to the set generated by party A, and sends it to party C.

Same thing, to party D, then E, then F.  When F sends it back to A, there should be 600 txids and 600 bitcoin addresses.

Round 2: party A adds the txids of the real coins he wants to mix, and new payout addresses to receive them, and sends them to B to do the same.  Then it goes to C, D, E, F, and back to A.

Round 3: Party A removes all of the bogus information he added in round 1, sends it to B.  Then C,D,E,F, and when it gets back to A, only the real information should remain.

Party A announces the proposed transaction publicly.  Each party confirms that the mixing will result in them getting the same number of coins they put in.

If all parties agree to the transaction, they generate the signatures.  They also generate a bunch of bogus placeholder signatures, so they can exchange signatures without divulging e.g. how many real signatures they are delivering.

To exchange the signatures, they encrypt them repeatedly, onion style (think Tor), so they must be passed back and forth among participants in multiple rounds to unpeel the layers.  They are passed back and forth in random order, so no participants can identify the originator of any particular signature.

If one party doesn't agree with the proposed transaction (for example it omits a payout and shortchanges him), he generates all bogus signatures and no real ones, so his refusal to sign doesn't identify him to the person who altered the transaction to withhold his payout.

Once somebody/anybody has all the signatures (and the bogus signatures thrown out), the transaction is signed and broadcast.

During all rounds, outputs can only be specified in the following amounts of BTC: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, etc.  Also, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01, 0.005, etc.... this uncouples the outputs from the inputs.  Otherwise, the guy who added 17.43233 BTC to the mix is probably the same guy with the 17.43233 BTC output.

[Gavin Andresen]

That sounds more complicated than it needs to be.

If you can assume some mixers are honest and won't disclose what they added to the mix, then just do a series of pair-wise mixes.

E.g.

A and B communicate securely and create a transaction that has 2 inputs and 2 outputs, all of the same amount of bitcoins (A and B might need to send-to-selves to get the right sized outputs).  The output order is randomized. They each sign their input (after checking to make sure their output goes to them).

A could then repeat with C, then D and, assuming B, C, and D aren't all actually the same person recording his IP address and the mixes, would have a coins linked to the wallets of A/B/C/D.  I believe after a few mixing steps a simple clustering analysis would think everybody who participated in the mix is sharing one big wallet (but I know very little about that stuff, and I wouldn't be surprised to find out there are more sophisticated clustering techniques that look at transaction times and overall transaction ordering that might be able to see through the fog and figure out who is who).

If all the other participants in the mixes are actually the same person (Sybil attack) then I believe no matter WHAT algorithm you use you're sunk.

My intuition is that if you can make the pairwise-mixing case work, then involving more than 2 people at once might be a useful optimization.  But you should start with the 2-person case and prove it is secure before getting more complicated.

[casascius]

I thought about my idea as presented further and realized much of it wouldn't work: the whole idea of selecting bogus transactions from the start is flawed because in the end, everyone is going to know which inputs never made it into the final transaction.

Here is another idea: what if a bitcoin client optionally swapped amounts with peers?  Let me refer to this as a dance.

On a random periodic basis, node A could say to randomly selected node B, "I got 25 BTC, want to trade?".  Node B could say, "Sure, here is a txid of mine worth 25 BTC and a new receiving address for me."  Node A would say, "Here is a transaction that combines our 25BTC and then pays us each 25BTC, signed by me."  Node B ensures that the transaction will cause him to remain with even money if executed, and if so, signs and broadcasts it.

After such a transaction completed, the two 25BTC outputs would be indistinguishable.  One would know that either output must have come from one of the two parties, which isn't a huge distraction.  But if, network wide, dances involving 25BTC were commonplace, and getting from point X to point Y potentially involved six or ten or more junctions that each cool the trail by a factor of 50%, then the 25BTC chunks will be extremely hard to follow after little more than a few dances.

Dancing probably works best if change doesn't have to be involved.  Keeping it to a few well-defined amounts systemwide would be important so that making change doesn't have to be considered and so nodes can plan on having txid's available that are worth exactly the amount of a dance.  So if a peer with say 123 BTC wants to dance, he first sendmany's himself to four of his addresses so they have 25,25,25,23 BTC.  The 25BTC chunks will periodically be involved in dances and the 23 will not.

If there were multiple standard dance amounts besides 25BTC, that would allow any size wallet to be accommodated.  The 23BTC in the prior example could be split into 23 chunks of 1BTC, each of which dance with other peers who have a 1BTC transaction handy.

Also, if instead of peer A asking peer B to swap coins, it could ask several of its peers simultaneously, and construct a transaction that combines four or five 25BTC chunks instead of two.