Paper 2024/251

Communication-Optimal Convex Agreement

Diana Ghinea, ETH Zurich
Chen-Da Liu-Zhang, Lucerne University of Applied Sciences and Arts, Web3 Foundation
Roger Wattenhofer, ETH Zurich

Byzantine Agreement (BA) allows a set of $n$ parties to agree on a value even when up to $t$ of the parties involved are corrupted. While previous works have shown that, for $\ell$-bit inputs, BA can be achieved with the optimal communication complexity $\mathcal{O}(\ell n)$ for sufficiently large $\ell$, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications. This gave rise to the notion of Convex Agreement (CA), introduced by Vaidya and Garg [PODC'13], which requires the honest parties' outputs to be in the convex hull of the honest inputs. Unfortunately, all existing CA protocols incur a communication complexity of at least $\Omega(\ell n^2)$. In this work, we introduce the first CA protocol with the optimal communication of $\mathcal{O}(\ell n)$ bits for inputs in $\mathbb{Z}$ of size $\ell = \Omega(\kappa \cdot n^2 \log n)$, where $\kappa$ is the security parameter.

Available format(s)
Cryptographic protocols
Publication info
Convex AgreementCommunication ComplexityLong Messages
Contact author(s)
ghinead @ ethz ch
chendaliu @ gmail com
wattenhofer @ ethz ch
2024-02-16: revised
2024-02-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Diana Ghinea and Chen-Da Liu-Zhang and Roger Wattenhofer},
      title = {Communication-Optimal Convex Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2024/251},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.