Paper 2019/838

Ouroboros Chronos: Permissionless Clock Synchronization via Proof-of-Stake

Christian Badertscher and Peter Gaži and Aggelos Kiayias and Alexander Russell and Vassilis Zikas

Abstract

Proof-of-stake (PoS) has been shown to be a suitable replacement—in many respects—for the expensive proof-of-work mechanism introduced by the Bitcoin protocol. Nevertheless, one common and seemingly intrinsic shortcoming of all existing PoS blockchains in the permissionless “dynamic availability” setting introduced by Badertscher et al. [CCS 2018], where parties come and go without warning, is that they require explicit use of a common notion of time among the participants, i.e., a “global” clock that provides the correct time on demand. We design and analyze a PoS blockchain protocol that we prove UC-secure without assuming access to a global time functionality. Central to our construction is a novel clock synchronization mechanism that enables joining parties to adjust their local clocks correctly, relying only on knowledge of the genesis block and the assumption that their local, initially desynchronized clocks advance at approximately the same speed. This is particularly challenging as we work in the dynamic availability setting which addresses optimal resilience under arbitrary and potential adversarial participation patterns. As a corollary of our construction, we obtain a permissionless PoS implementation of a global clock that may be used whenever access to global time is a requirement in a higher level protocol.