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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a novel Proof-of-Stake (PoS) protocol, Ouroboros Genesis,, that enables parties to safely join (or rejoin) the protocol execution using only the genesis block information. Prior to our work, PoS protocols either required parties to obtain a trusted "checkpoint" block upon joining and, furthermore, to be frequently online or required an accurate estimate of the number of online parties to be hardcoded into the protocol logic. This ability of new parties to "bootstrap from genesis" was a hallmark property of the Bitcoin blockchain and was considered an important advantage of PoW-based blockchains over PoS-based blockchains since it facilitates robust operation in a setting with dynamic availability, i.e., the natural setting---without external trusted objects such as checkpoint blocks---where parties come and go arbitrarily, may join at any moment, or remain offline for prolonged periods of time. We prove the security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake in a partially synchronous network with unknown message delay and unknown, varying levels of party availability. Our security proof is in the Universally Composable setting assuming the most natural abstraction of a hash function, known as the strict Global Random Oracle (ACM-CCS 2014); this highlights an important advantage of PoS blockchains over their PoW counterparts in terms of composability with respect to the hash function formalisation: rather than a strict GRO, PoW-based protocol security requires a "local" random oracle. Finally, 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.
Original languageEnglish
Title of host publicationProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
Place of PublicationNew York, NY, USA
PublisherACM
Pages913-930
Number of pages18
ISBN (Print)978-1-4503-5693-0
DOIs
Publication statusPublished - 15 Oct 2018
Event25th ACM Conference on Computer and Communications Security - Toronto, Canada
Duration: 15 Oct 201819 Oct 2018
https://www.sigsac.org/ccs/CCS2018/

Publication series

NameCCS '18
PublisherACM

Conference

Conference25th ACM Conference on Computer and Communications Security
Abbreviated titleACM CCS 2018
CountryCanada
CityToronto
Period15/10/1819/10/18
Internet address

Keywords

  • blockchain
  • distributed ledgers
  • proof-of-stake

Fingerprint Dive into the research topics of 'Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability'. Together they form a unique fingerprint.

Cite this