Top

Published in:

2020 | OriginalPaper | Chapter

Order-Fairness for Byzantine Consensus

Authors : Mahimna Kelkar, Fan Zhang, Steven Goldfeder, Ari Juels

Published in: Advances in Cryptology – CRYPTO 2020

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering.

To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them.

We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

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!

inform now

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!

inform now

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!

inform now

previous chapter Alzette: A 64-Bit ARX-box

next chapter Generically Speeding-Up Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions

The term “consensus” has been used in systems literature for a number of related primitives, including “single-shot” consensus. However, in this paper, we use “consensus” to refer to the problem of “state machine replication.”

Aequitas (IPA pronunciation: /

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-56877-1_16/MediaObjects/503460_1_En_16_Figa_HTML.gif

/) is the Roman personification of fairness.

Abraham, I., et al.: Solida: a blockchain protocol based on reconfigurable byzantine consensus. In: OPODIS, pp. 25:1–25:19 (2017)

Abraham, I., et al.: Sync HotStuff: simple and practical synchronous state machine replication. Cryptology ePrint Archive, Report 2019/270 (2019)

Amir, Y., et al.: Prime: byzantine replication under attack. IEEE TDSC 8(4), 564–577 (2011)

Asayag, A., et al.: A fair consensus protocol for transaction ordering. In: ICNP, pp. 55–65 (2018)

Aublin, P.-L., Mokhtar, S.B., Quéma, V.: RBFT: redundant byzantine fault tolerance. In: ICDCS, pp. 297–306 (2013)

Baird, L.: The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance (2016). https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf

Bano, S., et al.: Consensus in the age of blockchains. arXiv:1711.03936 (2017)

Bessani, A., Sousa, J., Alchieri, E.E.P.: State machine replication for the masses with BFT-SMART. In: DSN, pp. 355–362 (2014)

Bracha, G., Toueg, S.: Asynchronous consensus and broadcast protocols. J. ACM 32(4), 824–840 (1985)MathSciNetCrossRef

10.

Cachin, C., Vukolić, M.: Blockchain consensus protocols in the wild. arXiv:1707.01873 (2017)

11.

Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 524–541. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_31CrossRef

12.

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136–147 (2001)

13.

Canetti, R., Rabin, T.: Universal composition with joint state. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_16CrossRef

14.

Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_4CrossRef

15.

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

16.

Hubert Chan, T.-H., Pass, R., Shi, E.: Consensus through herding. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 720–749. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_24CrossRef

17.

Clement, A., et al.: Making byzantine fault tolerant systems tolerate byzantine faults. In: NDSI, pp. 153–168 (2009)

18.

Condorcet Paradox. https://wikipedia.org/wiki/Condorcet_paradox

19.

Cristian, F., et al.: Atomic broadcast: from simple message diffusion to byzantine agreement. Inf. Comput. 118(1), 158–179 (1995)MathSciNetCrossRef

20.

Daian, P., et al.: Flash boys 2.0: frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: IEEE S&P, pp. 585–602 (2020)

21.

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

22.

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

23.

Ethereum. https://ethereum.org/

24.

Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 436–454. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_28CrossRef

25.

Gilad, Y., et al.: Algorand: scaling byzantine agreements for cryptocurrencies. In: SOSP, pp. 51–68 (2017)

26.

Ho, C., Dolev, D., van Renesse, R.: Making distributed applications robust. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 232–246. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77096-1_17CrossRef

27.

Kelkar, M., et al.: Order-fairness for byzantine consensus. Cryptology ePrint Archive, Report 2020/269 (2020)

28.

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

29.

Kokoris-Kogias, E., et al.: OmniLedger: a secure, scale-out, decentralized ledger via sharding. In: IEEE S&P, pp. 583–598 (2018)

30.

Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. TOPLAS 4(3), 382–401 (1982)CrossRef

31.

Lev-Ari, K., et al.: FairLedger: a fair blockchain protocol for financial institutions. In: OPODIS, pp. 1:1–1:16 (2019)

32.

Lewis, M.: Flash Boys: A Wall Street Revolt. WW Norton & Company, New York (2014)

33.

Luu, L., et al.: SmartPool: practical decentralized pooled mining. In: USENIX Security, pp. 1409–1426 (2017)

34.

Martin, J.-P., Alvisi, L.: Fast byzantine consensus. IEEE TDSC 3(3), 202–215 (2006)

35.

Miller, A., et al.: Non-outsourceable scratch-off puzzles to discourage bitcoin mining coalitions. In: ACM CCS, pp. 680–691 (2015)

36.

Miller, A., et al.: The honey badger of BFT protocols. In: ACM CCS, pp. 31–42 (2016)

37.

Pass, R., Shi, E.: FruitChains: a fair blockchain. In: PODC, pp. 315–324 (2017)

38.

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

39.

Pass, R., Shi, E.: Rethinking large-scale consensus. In: CSF, pp. 15–129 (2017)

40.

Pass, R., Shi, E.: Thunderella: blockchains with optimistic instant confirmation. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 3–33. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_1CrossRef

41.

Rocket, T., et al.: Scalable and probabilistic leaderless BFT consensus through metastability. arXiv:1906.08936 (2019)

42.

Veronese, G.S., et al.: Efficient byzantine fault-tolerance. IEEE Trans. Comput. 62(1), 16–30 (2013)MathSciNetCrossRef

43.

Veronese, G.S., et al.: Spin one’s wheels? Byzantine fault tolerance with a spinning primary. In: SRDS, pp. 135–144 (2009)

44.

Yin, M., et al.: HotStuff: BFT consensus with linearity and responsiveness. In: PODC, pp. 347–356 (2019)

Title: Order-Fairness for Byzantine Consensus
Authors: Mahimna Kelkar
Fan Zhang
Steven Goldfeder
Ari Juels
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_16

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner