GAME THEORY MEETS CRYPTO

In Game Theory Meets Crypto, keynote speaker Elaine Shi dives into a personal anecdote on how blockchain-inspired protocols can help unravel common real-world problems. In 2013, her research team faced a difficult decision: they had merged a paper with another group of researchers, and had to decide which team would present the paper at a cryptography conference. She derives a careful analysis on how Blum’s blockchain-based coin-toss protocol could help the researchers select a winning team. In Blum’s protocol, players post a commitment to the blockchain, then the commitments are revealed, and the winner takes it all, like a heads or tails game. Elaine uses game theory to determine whether the coin-toss protocol is fair. In the cryptography literature, the notion of strong fairness implies that even if some players are not honest, the outcome should still be unbiased. She finds that the coin-toss protocol achieves a weaker notion of fairness, also known as game-theoretic fairness, meaning that no matter what the corrupt player does, they cannot benefit themselves or harm the other player. In blockchain settings with multiple players, Elaine argues that it is unreasonable to assume an honest majority because individuals can make up pseudonyms to play a lottery contract, and a single player could have control over most pseudonyms. Even with a dishonest majority, Elaine shows that game theoretic fairness still prevails in multiple party coin-tosses, as players should not have incentives to deviate. She proves this in the context of lottery or leader election protocols, similar to proof-of-stake cryptocurrency mining, in which randomly elected individuals take turns providing services in exchange for rewards. Her research is fundamental to understanding consensus protocols for permissionless blockchains and the need to design protocols that are incentive compatible.