(Re)-envisioning Approximate Agreement for Distributed Cryptography and Oracles

Asynchronous agreement protocols are crucial in various emerging applications, spanning from blockchains to fault-tolerant cyber-physical systems. Present asynchronous agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high $\tilde{\mathcal{O}}(n^3)$ communication for an n-node system. We address this inefficiency of approximate agreement protocols in the context of two different applications: a) Convex Agreement for Distributed Oracles, and b) Asynchronous random beacons, by proposing two protocols titled Delphi and HashRand, respectively.