Communication-Optimal Convex Agreement

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 ℓ-bit inputs, BA can be achieved with the optimal communication complexity O(ℓn) for sufficiently large ℓ, 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.