Oh good, it's out. Will have to discuss this with Elli next time I see her.
The paper can be summarized as follows. Bitcoin leaks private information today in various ways. It is possible to measure this and run statistical clustering algorithms on the block chain. There are a variety of possible solutions, though the paper and presentation is pessimistic on this point.
Actually I'm much more optimistic. Nothing in this research is news to us and the seeds of solutions are already planted. I insisted the payment protocol support specification of multiple outputs in a payment and multiple transactions during the design phase for exactly this reason - it means when people transact they can request payments to multiple keys made in unrelated transactions:
https://github.com/gavinandresen/paymentrequest/blob/master/spec.rstThe recipient can then broadcast the set of received transactions with some jitter, though at high traffic rates you probably don't need to jitter their broadcast very much to make them unlinkable. Wallets can attempt to target particular coin sizes to minimise the amount of linkability. For instance if you want to pay 30 bitcoins and you have 5, 15 and 10 coin outputs in three different transactions, you can create and sign over 3 transactions that move those outputs independently, without leakage, as long as the recipient has given you three requested outputs. They may ask for more or less, depending on their own coin size targeting algorithm, but over time somewhat regular coin sizes would coverge.
With regards to mixing, p2p mixing is possible and designs for it were already proposed on this forum. So their claim that mixing requires centralisation isn't really correct. It would be a nice enhancement to the system in future.
