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.
"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)."<p>Wait... how do we exclude dishonest participants? We're trying to exchange bitcoins with random strangers on the internet here.
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.