Cryptology ePrint Archive: Report 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.

Category / Keywords: applications / Mining probability, Hypoexponential Distribution, Proof-of-Work, Blockchain

Date: received 11 Oct 2020, last revised 12 Oct 2020

Contact author: francescomogavero at outlook com

Available format(s): PDF | BibTeX Citation

Version: 20201014:180328 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]