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
الصفحات380-409
عدد الصفحات30
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2017
منشور خارجيًانعم
الحدث23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 - Hong Kong, هونغ كونغ
المدة: ٣ ديسمبر ٢٠١٧٧ ديسمبر ٢٠١٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت10625 LNCS

!!Conference

!!Conference23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
الدولة/الإقليمهونغ كونغ
المدينةHong Kong
المدة٣/١٢/١٧٧/١٢/١٧

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “The sleepy model of consensus'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا