Tuesday, January 14, 2014

Bitcoin : Anonymous...sort of....not really...eventually.

TL;DR version:

Real World Crypto New York 2014 first session was focused on Bitcoin. Bitcoin is not anonymous to the average user. Zerocoin isn't really an option at the moment. Zerocash may be an option soon. Bitcoin network is evolving fast and as profit margins are being squeezed, it is not entirely clear what/where the future of the network is.

Full version:

The focus for the first session at Real World Crypto (RWC) has it's sights set on Bitcoin and specifically the questions around anonymity followed by a brief debate about some of the more philosophical questions around the Bitcoin system.

The three speakers and their respective talks titles were as follows:

Arvind Narayanan -- Is Bitcoin anonymous?
Matthew Green -- Towards making Bitcoing anonymous.
Yifu Guo -- Avalon

Arvind steps up as the first speaker with a review on some of the problems facing the Bitcoin system with respect to the anonymity.

First, a bit of context on how the Bitcoin systems works with respect to transactions and how users verify the validity of transactions.

Consider two users, Alice and Bob. Alice owns 1 Bitcoin and would like to send it to Bob. Alice begins by generating a transaction which states that she would like to transfer 1 Bitcoin to Bob and signs the transaction using her private key. The transaction is broadcast to the network, verified and subsequently incorporated into the blockchain history.

The verification of a transaction checks the following:

-- the signature on the transaction corresponds to the spender (in this case Alice)
-- The source of the spend (Alice) owns sufficient funds to make the transaction
-- There has been no other valid transaction made to spend the same coins (no double spend)

All transactions are publicly available in a ledger at http://blockchain.info or http://blockexplorer.com

One important aspect of Bitcoin is the addressing scheme. It is trivial for a user to generate a new address each time they wish to carry out a transaction. An example of this is the donation page for wikileaks which generates a new address each time the page is loaded.

It may seem intuitive that if you want to keep your identity secret, simply use a new address for each transaction. Sounds easy enough. In practice though, this proves to be tricky. Consider an example where Alice owns 3 addresses X,Y and Z with the balance of 5, 3 and 6 Bitcoins respectively. Alice would like to purchase a product from Bob which costs 8 Bitcoins. Alice can combine the balance of X and Y to send 8 coins to Bob. Assuming that Bob is to receive all 8 coins at a single address, this now creates some link between the addresses X and Y. Someone wishing to analyse the network will notice the link and collapse the transaction to a single address or identifier. This was first attempted by F.Reid and M.Harrigan PASSAT 2011[5].

The focus of the paper tracked the transactions of a heist that saw 25,000 Bitcoins being stolen. The paper doesn't go as far as to reveal the real identity of the thieves but clusters the transactions believed to be associated with them.

This is all well and good, and so far reveals nothing (or very little) about the identity of the Bitcoin users. This model works well if Bitcoin is used independently from any other service, but of course this would also make it largely useless. Some ways in which this an users identity is revealed:

- A user openly claims to be the owner of an address. This turns out to be a fairly common occurrence and if you look through a few posts on Bitcointalk.org donation addresses are then linked to forum usernames and in some cases, real names.

- A Bitcoin user may wish to exchange Bitcoins for other conventional currency or visa versa. Signing up to an exchange often requires verification (e.g. as on mtGox) and although the user details are not public, a subpoena to the company holding the details will quickly reveal the users details (possibly a scanned copy of their passport!).

- Service providers and vendors which accept Bitcoin may still require a registration which again falls to a subpoena and possibly other avenues such as data sharing.

It is likely that many more exist but these cover quite a large range of possibilities. Remaining clear of the above scenarios require a particularly paranoid user that would have to go to fairly hefty measures to avoid leaking their identity (such as only ever exchanging Bitcoins using cash-in-hand or only using services with no identity checking).

Two papers [1][2] attempt to analyse the public address data in conjunction with the transaction linkability heuristics to analyse and paint a picture of the network transactions.

Backtracking a bit, I mentioned that a user may use a different address for each transaction and this helps keep some semblance of anonymity by making it difficult to link and track transactions to a single user. One difficulty with this is the notion of 'change' from a transaction.

Recall the running example where Alice wishes to transfer Bitcoins to Bob. Now let's assume that Alice wants to give 7.5 Bitcoins to Bob but has three addresses X, Y and Z in denominations of 3, 5 and 6 respectively. Using addresses X and Y to transfer 7.5 Bitcoins to Bob and receiving the 0.5 Bitcoins as 'change' in a new address C. If C is ever used in conjunction with Z then the two are linked and once again can be collapsed under a single entity address. A paper by Meiklejohn et al. [3] include the 'change' transactions in their analysis to present an up-to-date picture of the network. Perhaps a good observation from the paper is the high centralisation in the services currently running on Bitcoin. This shows that a large number of the Bitcoin network flow has at some point passed through a large service provider (such as Satoshi Dice or Mt.Gox). This falls back to the subpoena problem highlighted earlier.

This is not to say that the heuristics do not have their limitations. The 'change' address detection is fragile and can easily lead to the mis-characterisation of traffic. There exist services such as mixing pools which attempt to mix Bitcoins, in effect Bitcoin laundering, but the volume of transactions are often too small to have a clear impact.

Matthew Green presented next to address some of the anonymisation concerns through the use of Zerocoin[4] and a new system built out of this called Zerocash.

I will not go into too much detail about this but Matthew assured us that a Zerocash paper will be published soon (accompanied with an implementation). In short, Zerocoin was introduced as a Bitcoin add-on to facilitate anonymity over Bitcoin. Forbes' Andy Greenberg also wrote an article covering the talk here.

The Zerocoin implementation was found to be too cumbersome and was never fully adopted by the Bitcoin community/developers. Zerocash addresses many of the issues present in Zerocoin by making use of smaller zero-knowledge proofs and a trusted third party. But we'll find out more about this in their publication later this year.

The final talk (or rather -- discussion) was presented by Yifu Guo from Avalon[6]. This sparked more of a philosophical debate rather than a technical presentation. Some interesting points were discussed such as:

-- Consider the Bitcoin network as it stands today. Pooled mining has led us back to a centralised system where the pools are effectively banks. It no longer follows the decentralised model which Bitcoin was once praised for. Yifu suggests that Saitoshi (Bitcoin's creator) may have been aware of this feature (or flaw). So the question should be; Did he design it this way or is it a flaw which has grown well beyond his expectations.

-- Power vs Return. I suppose this is more of a moral dilemma, profit at the cost of electricity (and by extension the environment). The efficiency of mining technology is constantly evolving, pushing the hash/watt ratio to its limit (some companies going down to 20nm ASICs[7] where Intel's current 'state-of-the-art' processor is 14nm). This being said, the amount of mining rigs coming online is also growing. Bitcoin was designed such that as the network hash rate increases, mining becomes proportionally harder. In turn, as more people jump on the bandwagon, to invest in Bitcoin mining equipment, the energy footprint becomes alarmingly high. Yifu estimates that at today's values, the cost of running the network is somewhere around 10% of the return. This, of course, relies on you having a reasonably new and efficient mining rig. As time goes on, the mining rewards will halve and the profit will need to come out of the transaction fees. Currently the fees do not make it viable to mine but this can easily change based on a few factors; pool policies (to only accept transactions that pay a fee), value of Bitcoin, volume of transactions etc.

-- Use(less) computation. As it stands, the Bitcoin network doesn't actually compute on anything useful. Can you use the ASICs to break hashes? In short - no. As the name suggests Application Specific Integrated Circuit (ASIC) means that most mining rigs perform a double Sha-256 hash. There is no allowance for re-purposing the device. So we can already write-off the hardware in that respect. On the other hand, there has been some interest in trying to use the ledger in some way. For example, it is possible to encode data into the Bitcoin ledger. This may be used as a way to draw up contracts which are public and can not be modified (unless the network falls to an attack).

It is worth noting that Avalon originally entered the ASIC race to promote decentralisation. Unfortunately this didn't quite take off and resulted in adding to the problem (of the monopoly on pooled mining).


[1] http://eprint.iacr.org/2012/584.pdf
[2] http://eprint.iacr.org/2012/596.pdf
[3] http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
[4] http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf
[5] http://arxiv.org/pdf/1107.4524.pdf
[6] http://avalon-asics.com/
[7] https://www.kncminer.com/categories/miners

No comments:

Post a Comment