Paper 2020/1262

On (multi-stage) Proof-of-Work blockchain protocols

Paolo D'Arco and Francesco Mogavero

Abstract

In this paper, we analyze permissionless blockchain protocols, whose distributed consensus algorithm lies on a Proof-of-Work composed of $k \geq 1$ sequential hash-puzzles. We put our focus in a restricted scenario, widely used in the blockchain literature, in which the number of miners, their hash rates, and the difficulty values of the hash-puzzles are constant throughout time. Our main contribution is a closed-form expression for the mining probability of a miner, that is, the probability the miner completes the Proof-of-Work of the next block to be added to the blockchain before every other miner does. Our theoretical results can be applied to existing Proof-of-Work based blockchain protocols, such as Bitcoin or Ethereum. We also point out some security issues implied by our findings, which makes not trivial at all the design of multi-stage (i.e. $k \geq 2$) Proof-of-Work blockchain protocols.