nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Consensus Through Herding

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

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Proof-of-Stake Protocols for Privacy-Aware Blockchains

Nur mit Berechtigung zugänglich

If assuming subexponential security of the underlying cryptographic building blocks, \(\chi \) can be set to \(\mathsf{poly} \log \kappa \).

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.

As discussed in the Supplemental Materials this assumption can be removed in a synchronous network while preserving communication efficiency.

Note that “forever honest” is in fact defined w.r.t. the protocol we are concerned with.

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.

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.

Aura - authority round. https://wiki.parity.io/Aura

Abraham, I., et al.: Communication complexity of byzantine agreement, revisited. CoRR, abs/1805.03391 (2018)

Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Efficient synchronous byzantine consensus. In: Financial Cryptography (2019)

Canetti, R., Eiger, D., Goldwasser, S., Lim, D.-Y.: How to protect yourself without perfect shredding. Cryptology ePrint Archive, Report 2008/291 (2008). https://eprint.iacr.org/2008/291

Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI (1999)

Chen, J., Micali, S.: Algorand: the efficient and democratic ledger (2016). https://arxiv.org/abs/1607.01341

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

David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3CrossRef

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10CrossRef

10.

Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26, 873–933 (1997)MathSciNetCrossRef

11.

Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10CrossRef

12.

Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1–11:35 (2012)MathSciNetCrossRef

13.

Hanke, T., Movahedi, M., Williams, D.: Dfinity technology overview series consensus system. https://dfinity.org/tech

14.

Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91–112 (2009)MathSciNetCrossRef

15.

Kiayias, A., Russell, A.: Ouroboros-BFT: a simple byzantine fault tolerant consensus protocol. Cryptology ePrint Archive, Report 2018/1049 (2018). https://eprint.iacr.org/2018/1049

16.

Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12CrossRef

17.

Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: FOCS (1999)

18.

Micali, S., Vaikuntanathan, V.: Optimal and player-replaceable consensus with an honest majority. MIT CSAIL Technical Report, 2017–004 (2017)

19.

Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)

20.

Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22CrossRefMATH

21.

Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: DISC (2017)

22.

Pass, R., Shi, E.: Rethinking large-scale consensus (invited paper). In: CSF (2017)

23.

Pass, R., Shi, E.: The sleepy model of consensus. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 380–409. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_14CrossRef

24.

Pass, R., Shi, E.: Rethinking large-scale consensus. IACR Cryptology ePrint Archive 2018:302 (2018)

25.

Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)CrossRef

26.

Shi, E.: Analysis of deterministic longest-chain protocols. https://eprint.iacr.org/2018/1079.pdf

Titel: Consensus Through Herding
verfasst von: T.-H. Hubert Chan
Rafael Pass
Elaine Shi
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17652-5

Electronic ISBN: 978-3-030-17653-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17653-2_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner