Skip to main content

2020 | OriginalPaper | Buchkapitel

Sublinear-Round Byzantine Agreement Under Corrupt Majority

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

Erschienen in: Public-Key Cryptography – PKC 2020

Verlag: Springer International Publishing

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

search-config
loading …

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).

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!

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!

Fußnoten
1
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.
 
2
Since in many consensus works the word broadcast is used to mean “Byzantine Agreement”, we use “multicast” rather than “broadcast” to avoid ambiguity.
 
3
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.
 
4
We need either the subgroup decision assumption or the decisional linear assumption according to Groth et al. [17].
 
5
Specifically, see the “Cryptographic building blocks” paragraph above for the required security notions of the cryptographic primitives employed.
 
Literatur
1.
Zurück zum Zitat Abraham, I., et al.: Communication complexity of Byzantine agreement, revisited. In: PODC (2019) Abraham, I., et al.: Communication complexity of Byzantine agreement, revisited. In: PODC (2019)
2.
Zurück zum Zitat 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) 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)
4.
Zurück zum Zitat 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) 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)
8.
Zurück zum Zitat Chor, B., Merritt, M., Shmoys, D.B.: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3), 591–614 (1989)MathSciNetCrossRef Chor, B., Merritt, M., Shmoys, D.B.: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3), 591–614 (1989)MathSciNetCrossRef
10.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Dolev, D., Strong, H.R.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. SIAM COMP 12(4), 656–666 (1983)MathSciNetCrossRef Dolev, D., Strong, H.R.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. SIAM COMP 12(4), 656–666 (1983)MathSciNetCrossRef
12.
Zurück zum Zitat Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)MathSciNetCrossRef Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)MathSciNetCrossRef
14.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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
19.
Zurück zum Zitat 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 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.
Zurück zum Zitat Karlin, A., Yao, A.C.-C.: Probabilistic lower bounds for byzantine agreement. Manuscript (1986) Karlin, A., Yao, A.C.-C.: Probabilistic lower bounds for byzantine agreement. Manuscript (1986)
21.
Zurück zum Zitat 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
23.
Zurück zum Zitat 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 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.
Zurück zum Zitat King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA (2006) King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA (2006)
25.
Zurück zum Zitat Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef
Metadaten
Titel
Sublinear-Round Byzantine Agreement Under Corrupt Majority
verfasst von
T.-H. Hubert Chan
Rafael Pass
Elaine Shi
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-45388-6_9