The sleepy model of consensus

Rafael Pass, Elaine Shi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


The literature on distributed computing (as well as the cryptography literature) typically considers two types of players—honest players and corrupted players. Resilience properties are then analyzed assuming a lower bound on the fraction of honest players. Honest players, however, are not only assumed to follow the prescribed the protocol, but also assumed to be online throughout the whole execution of the protocol. The advent of “large-scale” consensus protocols (e.g., the blockchain protocol) where we may have millions of players, makes this assumption unrealistic. In this work, we initiate a study of distributed protocols in a “sleepy” model of computation where players can be either online (awake) or offline (asleep), and their online status may change at any point during the protocol. The main question we address is: Can we design consensus protocols that remain resilient under “sporadic participation”, where at any given point, only a subset of the players are actually online? As far as we know, all standard consensus protocols break down under such sporadic participation, even if we assume that 99 % of the online players are honest. Our main result answers the above question in the affirmative. We present a construction of a consensus protocol in the sleepy model, which is resilient assuming only that a majority of the online players are honest. Our protocol relies on a Public-Key Infrastructure (PKI), a Common Random String (CRS) and is proven secure in the timing model of Dwork-Naor-Sahai (STOC’98) where all players are assumed to have weakly-synchronized clocks (all clocks are within Δ of the “real time”) and all messages sent on the network are delivered within Δ time, and assuming the existence of sub-exponentially secure collision-resistant hash functions and enhanced trapdoor permutations. Perhaps surprisingly, our protocol significantly departs from the standard approaches to distributed consensus, and we instead rely on key ideas behind Nakamoto’s blockchain protocol (while dispensing the need for “proofs-of-work”). We finally observe that sleepy consensus is impossible in the presence of a dishonest majority of online players.

שפה מקוריתאנגלית
כותר פרסום המארחAdvances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings
עורכיםTsuyoshi Takagi, Thomas Peyrin
מספר עמודים30
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2017
פורסם באופן חיצוניכן
אירוע23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 - Hong Kong, הונג קונג
משך הזמן: 3 דצמ׳ 20177 דצמ׳ 2017

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך10625 LNCS


כנס23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
מדינה/אזורהונג קונג
עירHong Kong

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The sleepy model of consensus'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי