Paper 2022/308

Colordag: An Incentive-Compatible Blockchain

Abstract

We present $$, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than $$ of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an $$-Nash equilibrium as long as all miners have less than $$ of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call $$ and does not suffer from this problem. Because it is an $$-sure Nash equilibrium, Colordag is an $$-Nash equilibrium and with probability $$ is a best response.