Paper 2022/308

Colordag: An Incentive-Compatible Blockchain

Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
ittay @ technion ac il
2022-03-07: received
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Danny Dolev and Ittay Eyal and Joseph Y.  Halpern},
      title = {Colordag: An Incentive-Compatible Blockchain},
      howpublished = {Cryptology ePrint Archive, Paper 2022/308},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.