Scalable Agreement Protocols with Optimal Optimistic Efficiency

Designing efficient distributed protocols for various agreement tasks such as Byzantine Agreement, Broadcast, and Committee Election is a fundamental goal with many applications, including most secure multiparty computation (MPC) protocols. Motivated by modern large-scale settings, we are interested in scalable protocols for these tasks, where each (honest) party communicates a number of bits which is sub-linear in n, the number of parties. The state of the art protocols require each party to send \(\tilde{O}(\sqrt{n})\) bits (We use the notation \(\tilde{O}(\cdot ),\tilde{\varOmega }(\cdot )\) to hide poly-logarithmic factors in n) throughout \(\tilde{O}(1)\) rounds. Despite significant efforts, getting protocols with \(o(\sqrt{n})\) communication per party has been a major challenge for several decades. We propose a new framework for designing efficient agreement protocols. Specifically, we design \(\tilde{O}(1)\) -round protocols for all of the above tasks (assuming constant \(<1/3\) fraction of static corruptions) with the following guarantees: Thus, all an adversary can gain from deviating from the honest execution is that honest parties will need to work harder (i.e., transmit more bits) to reach agreement and terminate. We use our new framework to get a scalable MPC protocol with optimistic and pessimistic complexities. Technically, we identify a relaxation of Byzantine Agreement (of independent interest) that allows us to fall-back to a pessimistic execution in a coordinated way by all parties. We implement this relaxation with \(\tilde{O}(1)\) communication bits per party and within \(\tilde{O}(1)\) rounds.