In 2012 Microsoft mathematicians wrote a paper called “On Bitcoin and Red Balloons”. In this paper they proved that any network architecture that requires 3 or more hops can be Sybil attacked.
In this article I will be breaking down how Microsoft determined these results and what exactly they mean. But first things first, let’s make sure we are all working on the same block.
Sybil Attack : An attack by which an attacker is able to overpower a network that is dependent on identities.
A Hop: The transmission of information from any arbitrary “station” or point (A) in a network to another to any arbitrary point (B) via the links between the two.
In the Centralized (a) model there are only 2 hops between any two connections as every communication passes through a central entity.
In both Decentralized (b) and Distributed © the number of hops is much greater than 3.
With these definitions hashed out, let’s examine the model that Microsoft used to arrive at their aforementioned conclusions regarding network topographies and sybil attacks.
The weather is unpredictable
During the 2009 DARPA Network Challenge, several teams of contestants were required to locate 10 red weather balloons that had been dispersed all across the USA. The strategy that ended up winning the challenge was devised by a student team from MIT. It was this strategy that the Microsoft researchers decided to deconstruct and outline an attack vector.
The strategy of the MIT team was to incentivise the spreading of information, so that they could search as wide an area as possible with as little resources as possible. To do this the team offered a $2000 reward per balloon, $1000 to the person that recruited the balloon finder, $500 reward to his recruiter and so on. Each individual participant had incentives to recruit their friends and anyone they could get in touch with, because doing so gave them a higher likelihood of claiming a prize. However, by recruiting more people the level of competition also increased. Once others were introduced into the network, there were more participants who themselves could also recruit others and claim a prize instead, reducing the amount the first recruiter would have received if the balloon was found within their own network.
This incentive mechanism creates an unintended incentive that helps malicious actors.
An attacker could create fake recruiters to claim maximum rewards for themselves. In the example of the DARPA Network Challenge, if an attacker creates fake identities that recruit one another in a chain and in that chain a genuine user finds a balloon the attackers reward is increased by a factor approaching 2.
Identities over powering a network: Sybil.
So what’s this got to do with Bitcoin and Cryptocurrencies?
These mathematicians were analysing the economic incentives of networks. That is exactly what underpins the security of every single cryptocurrency network, as an attacker attacks for profit. In a cryptocurrency network this is either done via double spends or manipulating the coin generation mechanism, both of which are dependent on identities.
Their conclusions were a simple set of guidelines stipulating that incentives of any Sybil resistant network must have the following features:
- An incentive to propagate information.
- No incentive for duplication of identities.
Their analysis of the bitcoin protocol is unique because they seem to have focused on a dynamic of the network that few even realize is relevant: the network topography.
The reason that bitcoin is Sybil resistant is because the identities are tied to the proof of work mechanism which cannot be faked.
The nodes within the network also learn where the proof of work is coming from and then allocate resources towards optimizing that connection. They do this so that they can receive the information as quickly as possible and begin working towards the next reward with a minimal waste in resources. This adaptive connection restructuring leads miners to form a small world network tending towards a complete graph, which has a total number of hops of less than 3.
Additionally the finder and every receiver of a block are both inherently incentivised to propagate it, if they wish to mine on top of it. If the rest of the network is working on a different block, there is a good chance that the block being worked on top of by our subject miner will be orphaned, thus wasting work.
Furthermore, duplicating oneself does not serve to increase reward.
Satoshi Nakamoto invented a Sybil proof network, with the first and most valuable application being cash. The model used within bitcoin takes the economic greed, inherent in every single one of us, and turns it into a mechanism to keep the participants from attacking.
If we take another cryptocurrency example like IOTA, we find that there are no incentives for information propagation other than a participant’s own transaction. Because of this there is an incentive for attackers to duplicate their identity if they wish to perform a double spend. Thus, IOTA fails both criteria set out by the Microsoft team for a Sybil proof network.
This is not up for debate. This is a mathematical problem. IOTA and a number of other cryptocurrencies are selling a non-solution. The architecture set out by IOTA specifically, will never work the way they have outlined. This is mathematically proven.