Bitcoin, Decentralization and the Nash Equilibrium

By Vitalik Buterin
Bitcoin Weekly
Saturday, July 23, 2011

http://bitcoinweekly.com/articles/bitcoin-decentralization-and-the-nash-equilibrium

Technological historians will for a long time see Bitcoin as a fundamental innovation in Internet technology. It's the first distributed electronic currency that enforces a prohibition on double spending, something which was earlier thought to be inherently impossible - it is inherent in the nature of data that it can be copied, and media companies have tried for a decade to find a way to prevent their products from being copied and have had only limited, transient success; every scheme they devise is eventually broken. Bitcoin may indeed become the world's great internet currency and overturn the world financial system. But even if Bitcoin fails, the concepts behind it are revolutionary by themselves. The idea of a cryptocurrency is not itself the innovation - it is merely one of the most obvious applications of a more fundamental advancement: for the first time, we have seen a computer network that prevents cheating not by being proprietary, but by the protocol itself being a Nash equilibrium - a state where no deviation from the equilibrium strategy (ie. the standard client software) can result in a gain for the deviant.

Nash equilibria are often used to describe situations of social cooperation - consider a situation where two people are exchanging goods, but both have the ability to cheat and not fulfill their side of the bargain. If both cooperate, the payout is (3,3) - both benefit from the exchange. If both cheat, neither will benefit - a (0,0) payout. So from the point of view of an outsider concerned with both parties' welfare, cheating is clearly harmful. But if one cheats, the payout becomes (5,-2) in favor of the cheater, so from a selfish perspective cheating is beneficial. The strategy of cooperation (3,3) is not a Nash equilibrium, since unilaterally deviating from the strategy is beneficial for the deviant. The only Nash equilibrium in the situation is that of both parties cheating - (0,0). Here, deviation from the strategy implies cooperation, which reduces the cooperator's payout to -2. Thus, cooperation is unstable, and we can see how this affects the real world, with the need for laws, reputations, web of trust systems, etc to penalize cheating and make cheating less profitable than cooperation.

To understand the significance of the Nash equilibrium concept for distributed computing, consider an example from a completely different field: massively multiplayer online games. An MMORPG is also a protocol - people move their characters and use attacks and spells, these actions change the state of the world, and the state of the world is transmitted to the other players. But there is, theoretically, the option of cheating - a player might decide to give himself ten thousand hit points and pass that on to the game. MMORPGs, to solve this problem, resort to a centralized server approach: the hit points are stored on a central server and the only form of interaction allowed with that server is through a preset category of actions - movement and spells. However even within that framework there can be cheating - a player might write a bot to allow him to gain experience or gold while sleeping, or write a script to play the game with essentially a zero reaction time, and from here the only solution is proprietary software - Blizzard, for example, has a program that routinely checks the player's computer for common forms of cheating, and the client is proprietary to prevent the player from rewriting the client in a way that would show the world in a way that would be more convenient for him to see it - showing enemies behind him or camouflaged behind bushes, for example. There is always some way for players to cheat, and centralized enforcement is the only way to prevent it. As another example, consider torrent downloading: torrents require people to seed them voluntarily with no compensation, which is, from a selfish point of view, not the optimal strategy, so the amount of files available for torrenting is less than what it could be if there was some mechanism to encourage people to seed everything they have. Some try to overcome this, once again, with proprietary software - having clients or servers that force something close to a 1:1 download to upload ratio, but open solutions are vastly preferred, since especially in applications which may attract unwanted government attention in some countries it is better not to have to trust any single party.

Now, let us see how the Bitcoin network enforces itself. There are two kinds of players: users and miners (all miners are also users, but not all users are miners so we will consider the two separately). Users have only one action available to them: send coins. To do this, they must have their private key and someone else's public key, so they must authenticate themselves to the miners to be able to send their coins just like an MMORPG player must authenticate himself to the server. However, the key difference between MMORPGs and the Bitcoin network is that Bitcoin servers (miners) are decentralized. Torrent users are also decentralized, but we can see how a torrent user can unilaterally benefit by deviating from the standard by downloading but not sharing. What options might Bitcoin miners have of cheating? They all fall into one or more of the following:

1. Give themselves coins.
2. Take coins away from someone else.
3. Force a transaction from someone else to themselves.
4. Double spend their own coins.

Let's go through these case by case.

1. It is in fact agreed that miners are allowed to give themselves a specific number of coins (50 right now). However, if a miner tries to give himself more then 50, the block will be rejected by the other miners.
2. This can be done in three ways: (1) not including a transaction to that user in the miner's block, (2) erasing a transaction to that user from a previous block and (3) forcing a transaction from that user to another - see case 3. The first is definitely possible, but the signed transaction is still floating around and someone else will include it. The second will result in the hashes not matching, so the block will be rejected by the other miners.
3. A transaction where the private key does not match up will be rejected by any user that you try to send the coins to.
4. The block will be rejected by the other miners.

All of this makes sense - blocks which do not follow the rules exactly will be rejected by the other miners or users. But this is not enough for the system to be stable - what incentive is there for miners to participate in the punishment process? To solve this, second-order punishment - punishment of non-punishers - is needed. As an analogy, as this paper (PDF) describes in detail, property rights can be thought of as such a stable equilibrium - unilaterally deviating from the equilibrium strategy of everyone respecting private property is punished by the police, and the system of the police is itself upheld by second order punishment - if you don't participate in the punishment process (in our society indirectly by paying taxes) you are also punished by the very same system, and participation in this process of "second order punishment" is also enforced - some of your taxes go to support the government department that detects tax evasion, so the system is recursively stable. Everyone has the strategy of not stealing and of participating in every level of punishment, and every deviation from this strategy results in a net loss for the deviant due to the rest of the community's punishment. To prevent the government itself from deviating from this set of rules, we have democracy, which allows "the network" to reject bad government. This model is, of course, highly flawed in reality (whether better models of social cooperation exist is a hotly debated topic on the internet) since in practice there are so many ways for the government to slowly grab more and more power and for powerful interests to sink their claws into the government, but this is a practical weakness arising out of human inefficiency, not a theoretical one. The Bitcoin network is code, and in code theory is practice, so recursive infinite-order punishment is a perfectly stable model for Bitcoin to follow.

Second order punishment in Bitcoin is, in fact, very simple - if a miner creates a block that follows a previous bad block, then the next miner will notice that there is a bad block in the chain and both the original deviant and the careless miner will be rejected from the chain and they will have done all their computing work for nothing. If the miner two after the deviant does nothing, then the miner three after probably will, and so on - in this way it is recursive. Users are also encouraged to punish miners that put in transactions that were not signed with the correct private key - if they do not, they will be stuck with coins that no one else is willing to accept.

Thus, there is no conceivable deviation from the protocol that is not immediately corrected for and punished. There is the possibility of an attacker with more computing power than the entire network, but nothing can fully protect against that, much like no society can defend itself against a military attacker larger than all of them put together, although society can make the job difficult through guerrilla warfare and the Bitcoin protocol still limits the actions of such an attacker to double spending attacks. It is because of this that we now have a currency system that is both decentralized and open source - no centralization is necessary, and no proprietary client software is necessary. Thus, there is no single node that must be trusted for the system to function, and decentralization naturally creates more stable systems. To see why this is the case, one must realize that in centrally enforced systems the game is also a player - the central enforcer is itself subject to game theoretical motivations, and can itself unilaterally deviate from the rules for profit. The only reason why they do not is the punishment mechanism that we call the free market - people are not willing to buy into systems with an unreliable controller, so controllers have an incentive to maintain the game as it is (incidentally, the free market is also an infinitely recursive punishment system - the second order punishment, i.e. the punishment for those individuals that do not punish deviants by abandoning their services, is the crime itself). However, as we see with the example of government, partially centralized systems, although functional in theory, are flawed in practice, which is why decentralization is so important, and Bitcoin's innovation in setting up a Nash equilibrium that allows decentralization to take up more applications than ever before.

Reprinted with permission.