Is Bitcoin Vulnerable On Asynchornous Networks?

Forget all the hubbub about who Satoshi Nakamoto is in person(s), something much more interesting has come up this week: a possible attack on the principle behind the technology underlying Bitcoin.

Nakamoto's blockchain is intended to enable consensus to be reached in a permissionless setting.
Although anyone can join or leave the protocol, the protocol should prevent “sybil attacks”.  To do this it relies upon solving a computational puzzles: the so called proof of work.  However, the assumption behind proving that this is sufficient to prevent attacks has always been that the network on which it operates is synchronous, something that is not quite true in the real world.  Likewise possible attacks have typically made the same assumption, such as those analysed by Yonatan Sompolinsky and Aviv Zohar.

Not surprising then that I was interested when a paper was published entitled Analysis of the Blockchain Protocol in Asynchronous Network.  Thankfully for all the Bitcoin fans it shows a degree of robustness in networks with limited delays, but outside of certain bounds it also demonstrates a simple attack which shows that the proof of work needs to be made harder.

The Trouble With Anonymity

There is an old adage that on the Internet no one knows you're a dog. It accompanied a cartoon in The New Yorker in 1993, which eons in Internet evolutionary terms, but issues with identity remains as problematic today as ever.  This holds true for system to system communications as well as those from person to person.  One attack that has become well known in forging identities in peer to peer networks is the Sybil attack.

The essence of a Sybil attack is simple: you subvert the reputation of a system in a peer to peer network by setting up a large number of pseudonymous identities and thereby gain an undue influence allowing you to, for example, gather data that you would not otherwise be able to do.  The ease with which a Sybil attack can be mounted is largely a factor of how cheaply identities can be generated.

In the last 10 years much work has been done on how to defend against Sybil attacks in particular contexts, such as, social networks and peer to peer (P2P) networks.  All such defences basically rely on one approach: having a trusted agency certify identities.  Researchers showed as far back as 2002 that without a logically centralised authority Sybil attacks were always possible unless you make unrealistic assumptions about networked resources.