Top

Published in:

2020 | OriginalPaper | Chapter

Sublinear-Round Byzantine Agreement Under Corrupt Majority

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

Published in: Public-Key Cryptography – PKC 2020

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following: can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS’07) and Fitzi and Nielsen (DISC’09), we have partial and affirmative answers to this question albeit for the narrow regime \(f = n/2 + o(n)\) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting \(f > 0.51n\) even for static corruption!

In this paper, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in \(O(\frac{1}{\epsilon } \log \frac{1}{\delta })\) rounds in the worst case, satisfies consistency with probability at least \(1 - \delta \), and tolerates \((1-\epsilon )\) fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform “after-the-fact” removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant \(\varOmega (1/\epsilon )\) lower bound by Garay et al. (FOCS’07).

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 Topology-Hiding Computation for Networks with Unknown Delays

next chapter Bandwidth-Efficient Threshold EC-DSA

Here we use a different parameter \(\lambda \) to distinguish from the security parameter \(\kappa \) that is related to the strength of the cryptographic primitives employed.

Since in many consensus works the word broadcast is used to mean “Byzantine Agreement”, we use “multicast” rather than “broadcast” to avoid ambiguity.

The name \(\mathcal {F}_\mathrm{mine}\) is making an analogy to Bitcoin mining. Each call to \(\mathcal {F}_\mathrm{mine}\) is like an attempt to mine a ticket to vote in the protocol.

We need either the subgroup decision assumption or the decisional linear assumption according to Groth et al. [17].

Specifically, see the “Cryptographic building blocks” paragraph above for the required security notions of the cryptographic primitives employed.

Abraham, I., et al.: Communication complexity of Byzantine agreement, revisited. In: PODC (2019)

Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Synchronous Byzantine agreement with optimal resilience, expected \(o(n^2)\) communication, and expected \(o(1)\) rounds. In: Financial Cryptography and Data Security (FC) (2019)

Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742–762. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_36CrossRef

Braud-Santoni, N., Guerraoui, R., Huc, F.: Fast Byzantine agreement. In: ACM Symposium on Principles of Distributed Computing, PODC 2013, Montreal, QC, Canada, 22–24 July 2013, pp. 57–64 (2013)

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

Hubert Chan, T.-H., Pass, R., Shi, E.: Sublinear-round Byzantine agreement under corrupt majority (2019). Online full version of this paper. https://eprint.iacr.org/2019/886

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

Chor, B., Merritt, M., Shmoys, D.B.: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3), 591–614 (1989)MathSciNetCrossRef

Cohen, R., Coretti, S., Garay, J., Zikas, V.: Probabilistic termination and composability of cryptographic protocols. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 240–269. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_9CrossRef

10.

Cohen, R., Haitner, I., Makriyannis, N., Orland, M., Samorodnitsky, A.: On the round complexity of randomized Byzantine agreement. In: 33rd International Symposium on Distributed Computing, DISC 2019, Budapest, Hungary, 14–18 October 2019, pp. 12:1–12:17 (2019)

11.

Dolev, D., Strong, H.R.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. SIAM COMP 12(4), 656–666 (1983)MathSciNetCrossRef

12.

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

13.

Fitzi, M., Nielsen, J.B.: On the number of synchronous rounds sufficient for authenticated Byzantine agreement. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 449–463. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04355-0_46CrossRef

14.

Garay, J., Katz, J., Koo, C.-Y., Ostrovsky, R.: Round complexity of authenticated broadcast with a dishonest majority. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 2007

15.

Garay, J.A., Katz, J., Kumaresan, R., Zhou, H.-S.: Adaptively secure broadcast, revisited. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 179–186. ACM, New York (2011)

16.

Goldwasser, S., Pavlov, E., Vaikuntanathan, V.: Fault-tolerant distributed computing in full-information networks. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, California, USA, 21–24 October 2006, pp. 15–26 (2006)

17.

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

18.

Hirt, M., Zikas, V.: Adaptively secure broadcast. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 466–485. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_24CrossRef

19.

Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous Byzantine agreement and leader election with full information. ACM Trans. Algorithms 6(4), 68:1–68:28 (2010)MathSciNetCrossRef

20.

Karlin, A., Yao, A.C.-C.: Probabilistic lower bounds for byzantine agreement. Manuscript (1986)

21.

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

22.

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

23.

King, V., Saia, J.: Breaking the \(O(N^2)\) bit barrier: scalable Byzantine agreement with an adaptive adversary. J. ACM 58(4), 18:1–18:24 (2011)MathSciNetCrossRef

24.

King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA (2006)

25.

Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef

Title: Sublinear-Round Byzantine Agreement Under Corrupt Majority
Authors: T.-H. Hubert Chan
Rafael Pass
Elaine Shi
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_9

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