Scalable Agreement Protocols with Optimal Optimistic Efficiency

Scalable Agreement Protocols with Optimal Optimistic Efficiency

연구 분야: Networking

학회: International Conference on Security and Cryptography for Networks

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 bits (We use the notation to hide poly-logarithmic factors in n) throughout rounds. Despite significant efforts, getting protocols with communication per party has been a major challenge for several decades. We propose a new framework for designing efficient agreement protocols. Specifically, we design -round protocols for all of the above tasks (assuming constant fraction of static corruptions) with the following guarantees: Optimistic complexity: In an honest execution, (honest) parties send only bits. Pessimistic complexity: In any other case, (honest) parties send bits. 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 communication bits per party and within rounds.