Paper 2020/381

Proof-of-Reputation Blockchain with Nakamoto Fallback

Leonard Kleinrock, Rafail Ostrovsky, and Vassilis Zikas


Reputation is a major component of trustworthy systems. However, the subjective nature of reputation, makes it tricky to base a system’s security on it. In this work, we describe how to leverage reputation to establish a highly scalable and efficient blockchain. Our treatment puts emphasis on reputation fairness as a key feature of reputation-based protocols. We devise a definition of reputation fairness that ensures fair participation while giving chances to newly joining parties to participate and potentially build reputation. We also describe a concrete lottery in the random oracle model which achieves this definition of fairness. Our treatment of reputation-fairness can be of independent interest. To avoid potential safety and/or liveness concerns stemming from the subjective and volatile nature of reputation, we propose a hybrid design that uses a Nakamoto-style ledger as a fallback. To our knowledge, our proposal is the first cryptographically secure design of a proof-of-reputation-based (in short PoR-based) blockchain that fortifies its PoR-based security by optimized Nakamoto-style consensus. This results in a ledger protocol which is provably secure if the reputation system is accurate, and preserves its basic safety properties even if it is not, as long as the fallback blockchain does not fail.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. INDOCRYPT 2020
Blockchainproof of reputationByzantine agreement
Contact author(s)
vassilis zikas @ gmail com
2020-10-29: revised
2020-04-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Leonard Kleinrock and Rafail Ostrovsky and Vassilis Zikas},
      title = {Proof-of-Reputation Blockchain with Nakamoto Fallback},
      howpublished = {Cryptology ePrint Archive, Paper 2020/381},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.