I may not understand this method correctly, but there seems to me to be an obvious way to generalize this method to work where the parties involved are not sending the same number of bitcoins. In their method, each person i with accounts A[i] to send bitcoins to the accounts B[i]. By using the sorted order of the public keys, the transaction from A[i] to B[i] is unique, guaranteeing that each person gets back the same number of bitcoins they sent. They also make use of a bitcoin transaction script to only let the transaction become valid if everyone involved signs the transactions they were supposed to. But why not just send any number of bitcoins, and distribute the bitcoins across the accounts in the appropriately sorted order? All that would be required is that each person announces not just their public keys, but also how many bitcoins they intend to send. Again, the bitcoins are sent using the sorted order of the public keys, except any time you are sending too many bitcoins to one address, you let the overflow go into the next address. Everyone would get back the same number of bitcoins, and it wouldn't be necessary for everyone to be sending the same number.
This doesn't work. If you know how many coins an output address is waiting to receive, all you need to do is look at which input address is submitting that many coins, and you have a matching.
I've realized there's a flaw in my method which is that it's not anonymous. If someone inputs X bitcoins, and no one else outputs X bitcoins, then whoever receives X bitcoins is the same as the person who submitted X bitcoins. It's necessary that all people send the same number of bitcoins so that the mixing creates anonymity.
There is a simple solution to this, though - You could submit one "donor" address giving X bitcoins, and submit X "recipient" addresses each receiving one bitcoin. Variations abound. As long as the recipient addresses you use are not used in a way that can be statistically linked with each other you're safe.
Of course, people might contribute too many recipient addresses trying to get free money, but this can never work - the transaction would be quickly aborted.
"Furthermore, honest participants will have picked their addresses uniformly at random, so the process of sorting automatically constructs a random permutation between these participants (dishonest participants must be excluded, since they can generate addresses from a skewed probability distributions)."
Wait... how do we exclude dishonest participants? We're trying to exchange bitcoins with random strangers on the internet here.
The sentence is a little unclear, but it is a little clearer if you consider things from the perspective of an organized attacker who controls some number of parties in the transaction. Even if the attacker messes around with the addresses of his keys, he doesn't learn anything about the addresses of the other participants: he can control the order of their keys relative to his, but not the relative order of keys among themselves.
Right. If you think you're dealing with 100 people, but it's actually 1 person with 100 addresses, then they can determine which output address is yours because it is the only one that isn't theirs.
So can you counter that by having everyone make multiple addresses explicitly (and only using some of them)?
Then you could have everyone ante 1/16th bitcoin or whatever minimum is sensible and dispense with the power of two thing, because everybody would have hundreds of wallets in the transaction.
Or does that just create a lot of correlations when those coins get consolidated?
It would seem harder to flood out the real traders if each person had to make tons of wallets. That would multiply the work required to have enough identities that you would end up trading only with them.
This is a really interesting idea, but I'm curious about how the transaction fees would affect things. Does the process of paying the fee reveal a match to an attacker? Regardless, it was an excellent read.
Yes, transaction fees are a big problem. One possibility is to not pay any fees: currently, there is a social convention that if all outputs are 0.01 BTC or larger, and so if we're not mixing too many addresses together, we can do the transaction for free. But once the intrinsic benefits of mining taper out, one would expect transaction costs to eventually become non-zero.
In this case, the transaction fee will have to be paid out of another wallet, not subtracted from the BTC involved in the transaction. Furthermore, this wallet must also be anonymous (e.g. to get anonymity, you must have some anonymity to begin with). But an important concern is how to pay for the transaction, when the size of Bitcoin you are anonymizing is about the same amount of the transaction cost anyway! One mitigating factor may be that it is really easy to find lots of participants willing to perform this mix, so a few benificient participants (who ostensibly want to be able to mix things) pay the entirety of the transaction fee for large, mini-mixes, and then uses the results of the mini-mix to pay for their bigger mixing.
I haven't fully thought this through, but why can't the protocol just be redefined so that the transaction incentive came out of each individual un-mixed input? Each party transferring a token would designate a fraction that goes towards the incentive. (Of course the quanta difference would would suck for multi-layer mixing, but I'd think some conventions could solve this)
BTW what are the specific resource requirements of SMP sort using currently accepted crypto primitives? I didn't get into digesting the linked paper just to see if they were working towards something feasible or if they required akin to one public key op per boolean gate.
You could this, but you would then be unable to mix any further, so the first mix must be sufficient to give you sufficient anonymity for the transaction you want to carry out.
The resource requirements are not well studied, since none of the literature attempts to handle sorting larger than 32-bit integers. However, on order of minutes would be my expectation.
