On the round complexity of randomized Byzantine agreement. (English) Zbl 1489.94092
Summary: We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: 1. BA protocols resilient against \(n/3\) [resp., \(n/4\)] corruptions terminate (under attack) at the end of the first round with probability at most \(o(1)\) [resp., \(1/2+ o(1)\)]. 2. BA protocols resilient against a fraction of corruptions greater than 1/4 terminate at the end of the second round with probability at most \(1-\Theta (1)\). 3. For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against a fraction of corruptions greater than 1/3 [resp., 1/4] terminate at the end of the second round with probability at most \(o(1)\) [resp., \(1/2 + o(1)\)]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of S. Micali [“Very simple and efficient Byzantine agreement”, LIPIcs – Leibniz Int. Proc. Inform. 67, Article 6, 1 p. (2017; doi:10.4230/LIPIcs.ITCS.2017.6)] that tolerates up to \(n/3\) corruptions and terminates at the end of the third round with constant probability.
References:
| [1] | I. Abraham, T.H. Chan, D. Dolev, K. Nayak, R. Pass, L. Ren, E. Shi, Communication complexity of Byzantine agreement, revisited, in Proceedings of the 38th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2019a), pp. 317-326) · Zbl 07298693 |
| [2] | I. Abraham, S. Devadas, D. Dolev, K. Nayak, L. Ren, Synchronous Byzantine agreement with expected O(1) rounds, expected o(n \({}^{\text{2)}}\) communication, and optimal resilience, in Financial Cryptography and Data Security (2019b) · Zbl 1460.94033 |
| [3] | H. Attiya, K. Censor, Tight bounds for asynchronous randomized consensus. J. ACM, 55(5):20:1-20:26 (2008) · Zbl 1325.68031 |
| [4] | Attiya, H.; Censor-Hillel, K., Lower bounds for randomized consensus under a weak adversary, SIAM J. Comput., 39, 8, 3885-3904 (2010) · Zbl 1214.68241 · doi:10.1137/090751906 |
| [5] | Z. Bar-Joseph, M. Ben-Or, A tight lower bound for randomized synchronous consensus, in Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 193-199 (1998) · Zbl 1333.68043 |
| [6] | M. Ben-Or, Another advantage of free choice: completely asynchronous agreement protocols (extended abstract), in Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 27-30 (1983) |
| [7] | M. Ben-Or, N. Linial, Collective coin flipping, robust voting schemes and minima of banzhaf values, in Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), pp. 408-416 (1985) |
| [8] | M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10 (1988) |
| [9] | M. Ben-Or, E. Pavlov, V. Vaikuntanathan, Byzantine agreement in the full-information model in o(log n) rounds, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 179-186 (2006) · Zbl 1301.68061 |
| [10] | E. Ben-Sasson, A. Chiesa, M. Green, E. Tromer, M. Virza, Secure sampling of public parameters for succinct zero knowledge proofs, in IEEE Symposium on Security and Privacy, pp. 287-304 (2015) |
| [11] | M. Blum, P. Feldman, S. Micali, Non-interactive zero-knowledge and its applications (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 103-112 (1988) |
| [12] | J. Bourgain, J. Kahn, G. Kalai, Influential coalitions for Boolean functions, in CoRR, 2014. arXiv:1409.3033 |
| [13] | S. Bowe, A. Gabizon, M.D. Green, A multi-party protocol for constructing the public parameters of the pinocchio zk-snark, in Financial Cryptography and Data Security FC, pp. 64-77 (2018) |
| [14] | E. Boyle, R. Cohen, A. Goel, Breaking the o \(( \surd\) n)-bit barrier: Byzantine agreement with polylog bits per party, in Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 319-330 (2021) · Zbl 07824210 |
| [15] | G. Bracha, An asynchronou [(n-1)/3]-resilient consensus protocol, in Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 154-162 (1984) |
| [16] | M. Castro, B. Liskov. Practical Byzantine fault tolerance, in Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 173-186 (1999) |
| [17] | D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 11-19 (1988) |
| [18] | J. Chen, S. Micali, Algorand, in CoRR, 2016. arXiv:1607.01341 |
| [19] | B. Chor, B.A. Coan, A simple and efficient randomized Byzantine agreement algorithm, in Fourth Symposium on Reliability in Distributed Software and Database Systems, SRDS, pp. 98-106 (1984) |
| [20] | Chor, B.; Merritt, M.; Shmoys, DB, Simple constant-time consensus protocols in realistic failure models, J. ACM, 36, 3, 591-614 (1989) · Zbl 0675.90038 · doi:10.1145/65950.65956 |
| [21] | R. Cohen, S. Coretti, J.A. Garay, V. Zikas, Probabilistic termination and composability of cryptographic protocols, in Advances in Cryptology - CRYPTO 2016, part III, pp. 240-269 (2016) · Zbl 1406.94040 |
| [22] | R. Cohen, S. Coretti, J. Garay, V. Zikas, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 37:1-37:15 (2017) · Zbl 1441.68013 |
| [23] | R. Cohen, I. Haitner, N. Makriyannis, M. Orland, A. Samorodnitsky, On the round complexity of randomized byzantine agreement, in Proceedings of the 33st International Symposium on Distributed Computing (DISC), pp. 12:1-12:17 (2019) · Zbl 1515.68062 |
| [24] | Dolev, D.; Strong, R., Authenticated algorithms for Byzantine agreement, SIAM J. Comput., 12, 4, 656-666 (1983) · Zbl 0524.68021 · doi:10.1137/0212045 |
| [25] | Dolev, D.; Reischuk, R.; Strong, HR, Early stopping in Byzantine agreement, J. ACM, 37, 4, 720-741 (1990) · Zbl 0711.68008 · doi:10.1145/96559.96565 |
| [26] | Feldman, P.; Micali, S., An optimal probabilistic protocol for synchronous Byzantine agreement, SIAM J. Comput., 26, 4, 873-933 (1997) · Zbl 0885.68077 · doi:10.1137/S0097539790187084 |
| [27] | Fischer, MJ; Lynch, NA, A lower bound for the time to assure interactive consistency, Inf. Process. Lett., 14, 4, 183-186 (1982) · Zbl 0493.68026 · doi:10.1016/0020-0190(82)90033-3 |
| [28] | M.J. Fischer, N.A. Lynch, M. Merritt, Easy impossibility proofs for distributed consensus problems, in Proceedings of the 23th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 59-70 (1985) · Zbl 0598.68024 |
| [29] | M. Fitzi, J.A. Garay. Efficient player-optimal protocols for strong and differential consensus, in Proceedings of the 22th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 211-220 (2003) · Zbl 1321.68043 |
| [30] | M. Fitzi, J.B. Nielsen, On the number of synchronous rounds sufficient for authenticated Byzantine agreement, in Proceedings of the 23th International Symposium on Distributed Computing (DISC), pp. 449-463 (2009) · Zbl 1261.68025 |
| [31] | Friedgut, E., Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 18, 1, 27-35 (1998) · Zbl 0909.06008 · doi:10.1007/PL00009809 |
| [32] | J.A. Garay, Y. Moses, Fully polynomial Byzantine agreement in t+1 rounds, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 31-41 (1993) · Zbl 1310.68040 |
| [33] | J.A. Garay, J. Katz, C. Koo, R. Ostrovsky, Round complexity of authenticated broadcast with a dishonest majority, in Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), pp. 658-668 (2007) |
| [34] | R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure distributed key generation for discrete-log based cryptosystems, in Advances in Cryptology - EUROCRYPT ’99, pp. 295-310 (1999) · Zbl 0931.94021 |
| [35] | Y. Gilad, R. Hemo, S. Micali, G. Vlachos, N. Zeldovich, Algorand: Scaling Byzantine agreements for cryptocurrencies, in Proceedings of the 26th Symposium on Operating Systems Principles (SOSP), pp. 51-68 (2017) |
| [36] | O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218-229 (1987) |
| [37] | Goldreich, O.; Goldwasser, S.; Linial, N., Fault-tolerant computation in the full information model, SIAM J. Comput., 27, 2, 506-544 (1998) · Zbl 0912.68037 · doi:10.1137/S0097539793246689 |
| [38] | Goldwasser, S.; Micali, S.; Rivest, RL, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput., 17, 2, 281-308 (1988) · Zbl 0644.94012 · doi:10.1137/0217017 |
| [39] | S. Goldwasser, E. Pavlov, V. Vaikuntanathan, Fault-tolerant distributed computing in full-information networks, in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), pp. 15-26 (2006) |
| [40] | S. Goldwasser, Y.T. Kalai, S. Park, Adaptively secure coin-flipping, revisited, in Proceedings of the 42th International Colloquium on Automata, Languages, and Programming (ICALP), part II, pp. 663-674 (2015) · Zbl 1447.94061 |
| [41] | J. Groth, R. Ostrovsky, A. Sahai, New techniques for noninteractive zero-knowledge. J. ACM 59(3):11:1-11:35 (2012) · Zbl 1281.68102 |
| [42] | Hadzilacos, V., Connectivity requirements for Byzantine agreement under restricted types of failures, Distrib. Comput., 2, 2, 95-103 (1987) · doi:10.1007/BF01667081 |
| [43] | D. Hofheinz, T. Jager, Verifiable random functions from standard assumptions, in Proceedings of the 13th Theory of Cryptography Conference, TCC 2016-A, part I, pp. 336-362 (2016) · Zbl 1348.94056 |
| [44] | J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions (extended abstract), in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), pp. 68-80 (1988) |
| [45] | B.M. Kapron, D. Kempe, V. King, J. Saia, V. Sanwalani, Fast asynchronous Byzantine agreement and leader election with full information, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1038-1047 (2008) · Zbl 1192.68083 |
| [46] | A.R. Karlin, A.C. Yao, Probabilistic lower bounds for Byzantine agreement and clock synchronization. Unpublished manuscript (1984) |
| [47] | Katz, J.; Koo, C., On expected constant-round protocols for Byzantine agreement, Advances in Cryptology - CRYPTO, 2006, 445-462 (2006) · Zbl 1161.68322 |
| [48] | V. King, J. Saia, Byzantine agreement in polynomial expected time: [extended abstract], in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 401-410 (2013) · Zbl 1293.68056 |
| [49] | J. Kubiatowicz, D. Bindel, Y. Chen, S.E. Czerwinski, P.R. Eaton, D. Geels, R. Gummadi, S.C. Rhea, H. Weatherspoon, W. Weimer, C. Wells, B.Y. Zhao, Oceanstore: An architecture for global-scale persistent storage, in ASPLOS-IX Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 190-201 (2000) |
| [50] | Lamport, L.; Shostak, RE; Pease, MC, The Byzantine generals problem, ACM Trans. Program. Lang. Syst., 4, 3, 382-401 (1982) · Zbl 0483.68021 · doi:10.1145/357172.357176 |
| [51] | A.B. Lewko, The contest between simplicity and efficiency in asynchronous Byzantine agreement, in Proceedings of the 25th International Symposium on Distributed Computing (DISC), pp. 348-362 (2011) · Zbl 1350.68036 |
| [52] | A.B. Lewko, M. Lewko, On the complexity of asynchronous agreement against powerful adversaries, in Proceedings of the 32th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 280-289 (2013) · Zbl 1323.68304 |
| [53] | Lindell, Y.; Lysyanskaya, A.; Rabin, T., On the composition of authenticated Byzantine agreement, J. ACM, 53, 6, 881-917 (2006) · Zbl 1326.68041 · doi:10.1145/1217856.1217857 |
| [54] | S. Micali, Very simple and efficient Byzantine agreement, in Proceedings of the 8th Annual Innovations in Theoretical Computer Science (ITCS) conference, pp. 6:1-6:1 (2017) |
| [55] | S. Micali, V. Vaikuntanathan, Optimal and player-replaceable consensus with an honest majority. Unpublished manuscript (2017) |
| [56] | S. Micali, M.O. Rabin, S.P. Vadhan, Verifiable random functions, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 120-130 (1999) |
| [57] | Mossel, E.; O’Donnell, R.; Regev, O.; Steif, JE; Sudakov, B., Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Israel Journal of Mathematics, 154, 1, 299-336 (2006) · Zbl 1140.60007 · doi:10.1007/BF02773611 |
| [58] | Mossel, E.; Oleszkiewicz, K.; Sen, A., On reverse hypercontractivity, Geom. Funct. Anal., 23, 3, 1062-1097 (2013) · Zbl 1271.60033 · doi:10.1007/s00039-013-0229-4 |
| [59] | Neiger, G.; Toueg, S., Automatically increasing the fault-tolerance of distributed algorithms, J. Algorithms, 11, 3, 374-419 (1990) · Zbl 0707.68013 · doi:10.1016/0196-6774(90)90019-B |
| [60] | O’Donnell, R., Analysis of Boolean Functions (2014), Cambridge: Cambridge University Press, Cambridge · Zbl 1336.94096 · doi:10.1017/CBO9781139814782 |
| [61] | R. Pass and E. Shi. Hybrid consensus: Efficient consensus in the permissionless model, in Proceedings of the 31st International Symposium on Distributed Computing (DISC), pp. 39:1-39:16 (2017) · Zbl 1515.68076 |
| [62] | R. Pass, E. Shi, Thunderella: Blockchains with optimistic instant confirmation, in Advances in Cryptology - EUROCRYPT 2018, part II, pp. 3-33 (2018) · Zbl 1423.94094 |
| [63] | Pease, MC; Shostak, RE; Lamport, L., Reaching agreement in the presence of faults, J. ACM, 27, 2, 228-234 (1980) · Zbl 0434.68031 · doi:10.1145/322186.322188 |
| [64] | T.P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in Advances in Cryptology - CRYPTO ’91, pp. 129-140 (1991) · Zbl 0763.94015 |
| [65] | B. Pfitzmann, M. Waidner, Unconditional Byzantine agreement for any number of faulty processors, in Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 339-350 (1992) · Zbl 1493.68036 |
| [66] | M.O. Rabin, Randomized Byzantine generals, in Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 403-409 (1983) |
| [67] | M. Santha, U.V. Vazirani, Generating quasi-random sequences from slightly-random sources (extended abstract), in Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS), pp. 434-440 (1984) |
| [68] | Turpin, R.; Coan, BA, Extending binary Byzantine agreement to multivalued Byzantine agreement, Inf. Process. Lett., 18, 2, 73-76 (1984) · doi:10.1016/0020-0190(84)90027-9 |
| [69] | A.C. Yao, Protocols for secure computations (extended abstract), in Proceedings of the 23th Annual Symposium on Foundations of Computer Science (FOCS), pp. 160-164 (1982) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
