Paper 2023/1364

Meeting in a Convex World: Convex Consensus with Asynchronous Fallback

Andrei Constantinescu, ETH Zurich
Diana Ghinea, ETH Zurich
Roger Wattenhofer, ETH Zurich
Floris Westermann, ETH Zurich

Convex Consensus (CC) allows a set of parties to agree on a value $v$ inside the convex hull of their inputs with respect to a predefined convexity notion, even in the presence of byzantine parties. In this work, we focus on achieving CC in the best-of-both-worlds paradigm, i.e., simultaneously tolerating at most $t_s$ corruptions if communication is synchronous, and at most $t_a \leq t_s$ corruptions if it is asynchronous. Our protocol is randomized, which is a requirement under asynchrony, and we prove that it achieves optimal resilience. In the process, we introduce communication primitives tailored to the best-of-both-worlds model, which we believe to be of independent interest. These are a deterministic primitive, which allows honest parties to obtain intersecting views, and a randomized primitive, leading to identical views (which is impossible to achieve deterministically). Afterwards, we consider achieving consensus using deterministic protocols, for which the agreement condition must be appropriately relaxed depending on the convexity space. For the relevant case of graph convexity spaces, we find that a previous asynchronous approximate agreement protocol for chordal graphs is incorrect, and hereby give a new protocol for the problem designed for the best-of-both-worlds model and achieving tight point-wise resilience bounds. Finally, we show that asynchronous graph approximate agreement remains unsolvable by deterministic protocols even when corruptions are restricted to at most two crashing nodes and the distance agreement threshold is linear in the size of the graph.

Available format(s)
Cryptographic protocols
Publication info
hybrid protocolsnetwork-agnostic protocolsconvex consensusbyzantine agreementapproximate agreement
Contact author(s)
aconstantine @ ethz ch
ghinead @ ethz ch
wattenhofer @ ethz ch
wfloris @ ethz ch
2023-09-13: approved
2023-09-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrei Constantinescu and Diana Ghinea and Roger Wattenhofer and Floris Westermann},
      title = {Meeting in a Convex World: Convex Consensus with Asynchronous Fallback},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1364},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.