Paper 2022/308

Colordag: An Incentive-Compatible Blockchain

Abstract

We present $\textit{Colordag}$, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than $1/2$ 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 $\varepsilon$-Nash equilibrium as long as all miners have less than $1/2$ 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 $\varepsilon\textit{-sure Nash equilibrium}$ and does not suffer from this problem. Because it is an $\varepsilon$-sure Nash equilibrium, Colordag is an $\varepsilon$-Nash equilibrium and with probability $1-\varepsilon$ is a best response.