Author

Topic: Research Paper: Evaluating User Privacy in Bitcoin (Read 1978 times)

legendary
Activity: 1400
Merit: 1013
as long as the recipient has given you three requested outputs.
BIP 32 extended public keys would allow the sender to break the payment up into an arbitrary number of outputs without requiring any special effort on the part of the recipient.
legendary
Activity: 1526
Merit: 1134
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.rst

The 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.
hero member
Activity: 555
Merit: 654
Good paper.

There are two other heuristics that can be added to track users,

Let x = sum of the input amounts, minus the amount in the lowest input, minus the fee

1. the "change" address always receives less money than x
2. the "payee" address always receives more money than x
legendary
Activity: 2506
Merit: 1010
by Elli Androulaki, Ghassan Karame, Marc Roeschlin, Tobias Scherer and Srdjan Capkun
Evaluating User Privacy in Bitcoin

Presented at Financial Cryptography and Data Security 2013
Seventeenth International Conference, April 1–5, 2013, Okinawa, Japan

 - http://fc13.ifca.ai/proc/1-3.pdf
 - http://docs.google.com/viewer?url=http%3A%2F%2Ffc13.ifca.ai%2Fproc%2F1-3.pdf  <-- Web browser view using Google Docs

 - http://fc13.ifca.ai/slide/1-3.pdf
 - http://docs.google.com/viewer?url=http%3A%2F%2Ffc13.ifca.ai%2Fslide%2F1-3.pdf  <-- Web browser view using Google Docs


Quote
Abstract:
We evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that faith-fully mimics the use of Bitcoin within a university. In this setting, our results show that the profiles of almost 40% of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin.
Jump to: