Paper 2018/378

Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability

Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas

Abstract

Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Major revision. ACM CCS 2018
Keywords
BlockchainConsensus
Contact author(s)
christian badertscher @ ed ac uk
acr @ cse uconn edu
akiayias @ inf ed ac uk
peter gazi @ iohk io
vassilis zikas @ ed ac uk
History
2019-02-22: last of 3 revisions
2018-04-30: received
See all versions
Short URL
https://ia.cr/2018/378
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/378,
      author = {Christian Badertscher and Peter Gazi and Aggelos Kiayias and Alexander Russell and Vassilis Zikas},
      title = {Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability},
      howpublished = {Cryptology ePrint Archive, Paper 2018/378},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/378}},
      url = {https://eprint.iacr.org/2018/378}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.