nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Thunderella: Blockchains with Optimistic Instant Confirmation

verfasst von : Rafael Pass, Elaine Shi

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

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, or “consensus”, is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous “fall-back” path (which only gets executed if something goes wrong); as a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet “optimistically” (if a super majority of the players are honest), the protocol “instantly” confirms transactions.

We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically—if 3/4 of the computing power is controlled by honest players, and a special player called the “accelerator”, is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority.

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

Nächstes Kapitel But Why Does It Work? A Rational Protocol Design Treatment of Bitcoin

Although the term “consensus” has been used in the distributed systems literature to mean other related abstractions such as single-shot consensus; in this paper, we use “consensus” to specifically refer to “state machine replication”.

The paper has multiple adaptively secure versions; here we rely on the one that achieves adaptive security with erasures in the random oracle model (as this protocol has better parameters than the one which satisfies adaptive security without a random oracle).

Later in the paper, for instantiations in the permissioned model under a PKI, authenticated channels are implied by the PKI.

Transactions of a lucky sequence are allowed to appear out of order in the blockchain.

Unless otherwise noted, all messages sent from the \(\varPi _\mathrm{blockchain} \) instance or destined for \(\varPi _\mathrm{blockchain} \) are automatically passed through, but these messages also count towards the view of the current \(\varPi _\mathrm{thunder}\) protocol instance.

We say that a public key \(\mathsf {pk}\in \mathsf{committee}\) is honest and online in round r if some node that is honest and online in round r output \(\mathsf {pk}\) to \({{\mathcal {Z}}} \) earlier.

Attiya, H., Dwork, C., Lynch, N., Stockmeyer, L.: Bounds on the time to reach agreement in the presence of timing uncertainty. J. ACM 41(1), 122–152 (1994)MathSciNetCrossRefMATH

Bentov, I., Gabizon, A., Mizrahi, A.: Cryptocurrencies without proof of work. In: Financial Cryptography Bitcoin Workshop (2016)

Bentov, I., Lee, C., Mizrahi, A., Rosenfeld, M.: Proof of activity: extending bitcoin’s proof of work via proof of stake. In: NetEcon (2014)

Birman, K.P., Joseph, T.A.: Exploiting virtual synchrony in distributed systems. In: SOSP (1987)

Burrows, M.: The chubby lock service for loosely-coupled distributed systems. In: OSDI (2006)

Buterin, V. (2017). https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c

Buterin, V., Zamfir, V.: Casper (2015). https://blog.ethereum.org/2015/08/01/introducing-casper-friendly-ghost/

Castañeda, A., Gonczarowski, Y.A., Moses, Y.: Unbeatable consensus. In: DISC (2014)

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

10.

User “cunicula”, Rosenfeld, M.: Proof of stake brainstorming, August 2011. https://bitcointalk.org/index.php?topic=37194.0

11.

Daian, P., Pass, R., Shi, E.: Snow white: provably secure proofs of stake. Cryptology ePrint Archive, Report 2016/919 (2016)

12.

Decker, C., Seidel, J., Wattenhofer, R.: Bitcoin meets strong consistency. In: ICDCN (2016)

13.

Dolev, D., Reischuk, R., Raymond Strong, H.: Early stopping in byzantine agreement. J. ACM 37(4), 720–741 (1990)MathSciNetCrossRefMATH

14.

Dolev, D., Raymond Strong, H.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. SIAMCOMP 12(4), 656–666 (1983)MathSciNetCrossRefMATH

15.

Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35, 288–323 (1988)MathSciNetCrossRef

16.

Dwork, C., Moses, Y.: Knowledge and common knowledge in a byzantine environment I: crash failures. In: TARK, pp. 149–169 (1986)

17.

Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. In: FC (2014)

18.

Garay, J.A., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol with chains of variable difficulty. Cryptology ePrint Archive, 2016/1048 (2016)

19.

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_10

20.

Guerraoui, R., Knežević, N., Quéma, V., Vukolić, M.: The next 700 BFT protocols. In: Proceedings of the 5th European Conference on Computer Systems, EuroSys 2010, pp. 363–376. ACM, New York (2010)

21.

Halpern, J.Y., Moses, Y., Waarts, O.: A characterization of eventual Byzantine agreement. SIAM J. Comput. 31(3), 838–865 (2001)MathSciNetCrossRefMATH

22.

Herlihy, M., Moses, Y., Tuttle, M.R.: Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. In: PODC (2011)

23.

Herzberg, A., Kutten, S.: Early detection of message forwarding faults. SIAM J. Comput. 30(4), 1169–1196 (2000)MathSciNetCrossRefMATH

24.

Junqueira, F.P., Reed, B.C., Serafini, M.: Zab: high-performance broadcast for primary-backup systems. In: DSN (2011)

25.

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

26.

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

27.

King, S., Nadal, S.: PPCoin: peer-to-peer crypto-currency with proof-of-stake (2012). https://peercoin.net/assets/paper/peercoin-paper.pdf

28.

Kokoris-Kogias, E., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., Ford, B.: Enhancing bitcoin security and performance with strong consistency via collective signing. CoRR, abs/1602.06997 (2016)

29.

Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.L.: Zyzzyva: speculative byzantine fault tolerance. In: SOSP (2007)

30.

Lamport, L.: Fast paxos. Distrib. Comput. 19(2), 79–103 (2006)MathSciNetCrossRefMATH

31.

Lamport, L., Malkhi, D., Zhou, L.: Vertical paxos and primary-backup replication. In: PODC, pp. 312–313 (2009)

32.

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

33.

Moses, Y., Raynal, M.: No double discount: condition-based simultaneity yields limited gain. Inf. Comput. 214, 47–58 (2012)MathSciNetCrossRefMATH

34.

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

35.

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_22CrossRef

36.

Pass, R., Shi, E.: Thunderella: blockchains with optimistic instant confirmation. https://eprint.iacr.org/2017/913

37.

Pass, R., Shi, E.: Fruitchains: a fair blockchain. In: PODC (2017)

38.

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

39.

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

40.

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

41.

User “QuantumMechanic”: Proof of stake instead of proof of work, July 2011. https://bitcointalk.org/index.php?topic=27787.0

42.

Song, Y.J., van Renesse, R.: Bosco: one-step byzantine asynchronous consensus. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 438–450. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87779-0_30CrossRef

Titel: Thunderella: Blockchains with Optimistic Instant Confirmation
verfasst von: Rafael Pass
Elaine Shi
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78374-1

Electronic ISBN: 978-3-319-78375-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78375-8_1

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"