Decentralized Consensus, Cryptocurrencies, and Game Theory
Vitalik Buterin’s Blog Post on Consensus-by-Bet
The recent development of cryptocurrencies and decentralized blockchains is a gold mine for economic models and game theory analysis: the entire security of such systems rely on a solid incentive model for participants. In the linked blog post, Vitalik Buterin, co-founder of the highly successful Ethereum cryptocurrency, provides a general overview of the consensus-by-bet paradigm to reach consensus of a blockchain’s state. In general, the problem is this: we have a public decentralized blockchain (an ordered sequence of blocks, with each block containing some financial or other transactions), and we want to add another block (recording some new transactions) onto the end of the blockchain (in effect, allowing these transactions to have “happened”). However, since the blockchain is decentralized, we need some way for all the participants to reach consensus of which block to add to the blockchain next. Additionally, the participants do not trust each other, the only thing they can rely on to reach consensus are using the rules and rewards laid out by the protocol.
There are several approaches that cryptocurrencies have used to solve this issue. The most common is called Proof-of-Work. This is what Satoshi Nakamoto presented with the original release of Bitcoin in 2009, and virtually every major cryptocurrency (including the current version of Ethereum) uses some variation of it. The Proof-of-Work approach works as follows: create a mathematical problem that requires a large amount of work to find a solution, but is extremely easy to prove a solution is correct. We also tie each solution to a block, so that a solution implies a specific block is to be added to the blockchain next. Since the problem is really hard (that is, impossible in any practical sense) to solve directly, the best way to find a solution is to just guess random values and hope to find a valid solution. Participants can then decide on which block they want to support, and guess potential solutions that would result in that block being chosen to be added next. This approach basically choses a random participant to generate a block (but weighted towards participants that put in more work), but they can be chosen once they have committed to selecting a particular block. Overall this does solve the initial problem, as a valid solution from any participant results in a specific block being chosen to add to the blockchain next; however, there are still edge cases that need to be fleshed out, such as if two participants generate a valid solution at the same time, delay in communication between participants, etc. (If you are interested, YouTube user 3Blue1Brown has a good introduction to blockchains and proof of work here.)
One criticism of Proof-of-Work is that it forces participants to expend resources solving “useless” mathematical problems. Because of this (among other issues with Proof-of-Work), another general approach called Proof-of-Stake has been developed. In the simplest versions of Proof-of-Stake, participants all enter a deposit, and then a participant is chosen at random to select which block to generate next. The deposit is to prevent a “Sybil Attack” (where one participant pretends they are many participants, giving them a higher chance of being chosen) by making such an attack require a large amount of money. Note that this is rather insecure, however, for the following reason: if the participant selected is malicious, they have complete control to stop the protocol by, for example, refusing to choose a block. We can mitigate such an attacker by destroying their deposit if they fail to make a decision, but since it could be that the participant is not malevolent but temporarily offline, that also does not seem like a good solution. (This issue, along with a few other possible attacks, stem from the fact that a participant commits to a block after they have been selected, rather than having already committed to a block before being selected as in Proof-of-Work.) Ideally, we would want some random subset of the participants, or the entire group, to decide together what block to add next, so we don’t concentrate all the power onto a potential attacker; however, this is just returns us back to our original problem, and we haven’t solved anything.
We can improve upon the basic Proof-of-Stake algorithm using consensus-by-bet. The basic idea behind consensus-by-bet is that each participant bets on which block they think the group will choose, and the block that is chosen is whichever block has the most money bet on it. This seems rather circular, and can be illustrated better with an example, formatted like the game theory examples given in class: let us consider we have 3 participants that need to decided between blocks X and Y. We can then describe one round of consensus-by-bet using the payoff matrix below, with r=1.
The format is different than those presented in class because this is a 3 player game, and so it should be read as follows: if A chooses X, B chooses X, and C chooses Y, then the payoffs are given directly under those choices (in this case the second column), and so A and B get payoff 1, and C gets payoff -1. The first interesting fact about this game is that the game is completely symmetric between players A, B, and C, and also between the block choices X and Y; that is, there is no advantage to any player, no a preference towards block X or Y. Additionally, there are many more 1s than -1s in the matrix, as getting a -1 means both of the other players must have chosen the opposite block. Given all of this, we find that if the players cannot communicate before making their move (that is, no player can signal their block preference), the best strategy is to choose randomly with 50% probability between X and Y. This may seem like the we have not accomplished much, since the block that is chosen ends up being random. However, let us make modify this game to have two rounds, both with payoff matrix described above, the first round with r=0.01, the second with r=1. In this case, the players can all signal their preferred block on the first round with very little penalty imposed by the protocol (not included in the matrix in our example is the external preference for a block by the players, but the r is chosen to be small on the first round so that the players preference dominates that decision), and then for the second round, the player in the minority can switch to match the majority in the second round, and thus still gain the maximum reward.
One observation from this example is that it seems to be equivalent to a simple majority vote, and this is true. In a certain sense, all decentralized consensus algorithms must come to some form of majority vote, because if a majority of the participants accept a different result, then that other result has more consensus than the “chooses” but disagreed with result. However, our case presented above is very literally a simple majority vote because of three assumptions: first, we assume there are discrete rounds, second, we assume that every participant votes in every round, and third, we assume that there are only two blocks to choose between. In the consensus-by-bet as presented in Buterin’s blog post, neither of these are assumed. Rather, each participant can choose to bet or not bet at any point in time. This greatly complicates the analysis of the algorithm and optimal participant strategy. However, this also means that a participant can go offline with little consequence for block selection (so an attacker cannot stop the protocol by simply not responding). Additionally, Buterin’s formulation also allows for any participant to propose a block for consideration, rather than assuming there are two blocks to choose between. Overall, our example simply demonstrates the a very basic version of consensus-by-bet to illustrate the underlying idea.
If you are interested, please check out Buterin’s blog post for a full introduction to consensus-by-bet, including a rigorous game theoretic evaluation of the protocol, as well as a security against attackers, and cryptographically verifying the actions of other participants.