Skip to main content
Top

2019 | OriginalPaper | Chapter

Consensus Through Herding

Authors : T.-H. Hubert Chan, Rafael Pass, Elaine Shi

Published in: Advances in Cryptology – EUROCRYPT 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

State Machine Replication (SMR) is an important abstraction for a set of nodes to agree on an ever-growing, linearly-ordered log of transactions. In decentralized cryptocurrency applications, we would like to design SMR protocols that (1) resist adaptive corruptions; and (2) achieve small bandwidth and small confirmation time. All past approaches towards constructing SMR fail to achieve either small confirmation time or small bandwidth under adaptive corruptions (without resorting to strong assumptions such as the erasure model or proof-of-work).
We propose a novel paradigm for reaching consensus that departs significantly from classical approaches. Our protocol is inspired by a social phenomenon called herding, where people tend to make choices considered as the social norm. In our consensus protocol, leader election and voting are coalesced into a single (randomized) process: in every round, every node tries to cast a vote for what it views as the most popular item so far: such a voting attempt is not always successful, but rather, successful with a certain probability. Importantly, the probability that the node is elected to vote for v is independent from the probability it is elected to vote for \(v' \ne v\). We will show how to realize such a distributed, randomized election process using appropriate, adaptively secure cryptographic building blocks.
We show that amazingly, not only can this new paradigm achieve consensus (e.g., on a batch of unconfirmed transactions in a cryptocurrency system), but it also allows us to derive the first SMR protocol which, even under adaptive corruptions, requires only polylogarithmically many rounds and polylogarithmically many honest messages to be multicast to confirm each batch of transactions; and importantly, we attain these guarantees under standard cryptographic assumptions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
If assuming subexponential security of the underlying cryptographic building blocks, \(\chi \) can be set to \(\mathsf{poly} \log \kappa \).
 
2
If communication efficiency is not a concern, we could have n broadcast instances (composed either sequentially or in parallel) where everyone is given the chance to act as the leader and suggest the next batch of transactions to confirm; we can then concatenate the outputs of these n broadcasts and treat it as the next block.
 
3
As discussed in the Supplemental Materials this assumption can be removed in a synchronous network while preserving communication efficiency.
 
4
Note that “forever honest” is in fact defined w.r.t. the protocol we are concerned with.
 
5
See the “Syntax” and “Constraints on https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17653-2_24/480582_1_En_24_IEq263_HTML.gif ” paragraphs.
 
6
The state machine replication protocol above invokes many instances of batch agreement which may then invoke one or more instances of scoring agreement. Recall that each scoring agreement instance calls https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17653-2_24/480582_1_En_24_IEq419_HTML.gif . For composition, calls to https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17653-2_24/480582_1_En_24_IEq420_HTML.gif are tagged with an instance identifier. Here the instance identifier contains a pair: first the identifier of the batch agreement instance and then the identifier of the scoring agreement.
 
Literature
2.
go back to reference Abraham, I., et al.: Communication complexity of byzantine agreement, revisited. CoRR, abs/1805.03391 (2018) Abraham, I., et al.: Communication complexity of byzantine agreement, revisited. CoRR, abs/1805.03391 (2018)
3.
go back to reference Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Efficient synchronous byzantine consensus. In: Financial Cryptography (2019) Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Efficient synchronous byzantine consensus. In: Financial Cryptography (2019)
5.
go back to reference Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI (1999) Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI (1999)
7.
go back to reference Daian, P., Pass, R., Shi, E.: Snow white: robustly reconfigurable consensus and applications to provably secure proofs of stake. In: Financial Cryptography (2019). First appeared on Cryptology ePrint Archive, Report 2016/919 Daian, P., Pass, R., Shi, E.: Snow white: robustly reconfigurable consensus and applications to provably secure proofs of stake. In: Financial Cryptography (2019). First appeared on Cryptology ePrint Archive, Report 2016/919
10.
go back to reference Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26, 873–933 (1997)MathSciNetCrossRef Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26, 873–933 (1997)MathSciNetCrossRef
12.
go back to reference Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1–11:35 (2012)MathSciNetCrossRef Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1–11:35 (2012)MathSciNetCrossRef
14.
go back to reference Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91–112 (2009)MathSciNetCrossRef Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91–112 (2009)MathSciNetCrossRef
17.
go back to reference Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: FOCS (1999) Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: FOCS (1999)
18.
go back to reference Micali, S., Vaikuntanathan, V.: Optimal and player-replaceable consensus with an honest majority. MIT CSAIL Technical Report, 2017–004 (2017) Micali, S., Vaikuntanathan, V.: Optimal and player-replaceable consensus with an honest majority. MIT CSAIL Technical Report, 2017–004 (2017)
19.
go back to reference Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008) Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)
21.
go back to reference Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: DISC (2017) Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: DISC (2017)
22.
go back to reference Pass, R., Shi, E.: Rethinking large-scale consensus (invited paper). In: CSF (2017) Pass, R., Shi, E.: Rethinking large-scale consensus (invited paper). In: CSF (2017)
24.
go back to reference Pass, R., Shi, E.: Rethinking large-scale consensus. IACR Cryptology ePrint Archive 2018:302 (2018) Pass, R., Shi, E.: Rethinking large-scale consensus. IACR Cryptology ePrint Archive 2018:302 (2018)
25.
go back to reference Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)CrossRef Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)CrossRef
Metadata
Title
Consensus Through Herding
Authors
T.-H. Hubert Chan
Rafael Pass
Elaine Shi
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-17653-2_24

Premium Partner