International Association for Cryptologic Research

International Association
for Cryptologic Research


Dynamic Ad Hoc Clock Synchronization

Christian Badertscher , IOHK
Peter Gaži , IOHK
Aggelos Kiayias , University of Edinburgh and IOHK
Alexander Russell , University of Connecticut and IOHK
Vassilis Zikas , Purdue University
DOI: 10.1007/978-3-030-77883-5_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2021
Abstract: Clock synchronization allows parties to establish a common notion of global time by leveraging a weaker synchrony assumption, i.e., local clocks with approximately the same speed. Despite intensive investigation of the problem in the fault-tolerant distributed computing literature, existing solutions do not apply to settings where participation is unknown, e.g., the ad hoc model of Beimel et al. [EUROCRYPT 17], or is dynamically shifting over time, e.g., the fluctuating/sleepy/dynamic-availability models of Garay et al. [CRYPTO 17], Pass and Shi [ASIACRYPT 17] and Badertscher et al. CCS 18]. We show how to apply and extend ideas from the blockchain literature to devise synchronizers that work in such dynamic ad hoc settings and tolerate corrupted minorities under the standard assumption that local clocks advance at approximately the same speed. We discuss both the setting of honest-majority hashing power and that of a PKI with honest majority. Our main result is a synchronizer that is directly integrated with a new proof-of-stake (PoS) blockchain protocol, Ouroboros Chronos, which we construct and prove secure; to our knowledge, this is the first PoS blockchain protocol to rely only on local clocks, while tolerating worst-case corruption and dynamically fluctuating participation. We believe that this result might be of independent interest.
Video from EUROCRYPT 2021
  title={Dynamic Ad Hoc Clock Synchronization},
  author={Christian Badertscher and Peter Gaži and Aggelos Kiayias and Alexander Russell and Vassilis Zikas},