Paper 2020/677

Blockchain with Varying Number of Players

T-H. Hubert Chan, Naomi Ephraim, Antonio Marcedone, Andrew Morgan, Rafael Pass, and Elaine Shi


Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting--anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al. (EuroCrypt'17) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-difficulty is appropriately set as a function of the maximum network message delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. These works, however, leave open the question of how to set the puzzle difficulty in a setting where the computational power in the network is changing. Nakamoto's protocol indeed also includes a description of a difficutly update procedure. A recent work by Garay et al. (Crypto'17) indeed shows a variant of this difficulty adjustment procedure can be used to get a sound protocol as long as the computational power does not change too fast --- however, under two restrictions: 1) their analysis assumes that the attacker cannot delays network messages, and 2) the changes in computational power in the network changes are statically set (i.e., cannot be adaptively selected by the adversary). In this work, we show the same result but without these two restrictions, demonstrating the soundness of a (slightly different) difficulty update procedure, assuming only that the computational power in the network does not change too fast (as a function of the maximum network message delays); as an additional contribution, our analysis yields a tight bound on the ``chain quality'' of the protocol.

Available format(s)
Publication info
Preprint. MINOR revision.
blockchainpuzzle difficulty
Contact author(s)
hubert @ cs hku hk
runting @ gmail com
rafael pass @ gmail com
2020-06-08: received
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Naomi Ephraim and Antonio Marcedone and Andrew Morgan and Rafael Pass and Elaine Shi},
      title = {Blockchain with Varying Number of Players},
      howpublished = {Cryptology ePrint Archive, Paper 2020/677},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.