Welcome to the resource topic for 2022/308
Title:
Colordag: An Incentive-Compatible Blockchain
Authors: Ittai Abraham, Danny Dolev, Ittay Eyal, Joseph Y. Halpern
Abstract:Proof-of-work blockchain protocols rely on incentive compatibility. System participants, called miners, generate blocks that form a directed acyclic graph (blockdag). The protocols aim to compensate miners based on their mining power, that is, the fraction of computational resources they control. The protocol designates rewards, striving to make the prescribed protocol be the miners’ best response. Nakamoto’s Bitcoin protocol achieves this for miners controlling up to almost 1/4 of the total mining power, and the Ethereum protocol does about the same. The state of the art in increasing this bound is Fruitchain, which works with a bound of 1/2. Fruitchain guarantees that miners can increase their revenue by only a negligible amount if they deviate. It is thus an epsilon-Nash equilibrium, for a small epsilon. However, Fruitchain’s mechanism allows a rational miner to deviate without penalty; we show that a simple practical deviation guarantees a miner a small increase in expected utility without any risk. This deviation results in a violation of the protocol desiderata. We conclude that, in our context, epsilon-Nash equilibrium is a rather fragile solution concept. We propose a more robust approach that we call epsilon-sure Nash equilibrium, in which each miner’s behavior is almost always a strict best response, and present Colordag, the first blockchain protocol that is an epsilon-sure Nash equilibrium for miners with less than 1/2 of the mining power. To achieve this, Colordag utilizes three techniques. First, it assigns blocks colors; rewards are assigned based on each color separately. By choosing sufficiently many colors, we can make sensitivity to network latency negligible. Second, Colordag penalizes forking—intentional bifurcation of the blockdag. Third, Colordag prevents miners from retroactively changing rewards. All this results in an epsilon-sure Nash equilibrium: Even when playing an extremely strong adversary with perfect knowledge of the future (specifically, when agents will generate blocks and when messages will arrive), correct behavior is a strict best response with high probability.
ePrint: https://eprint.iacr.org/2022/308
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .