Round-optimal Byzantine agreement (Q2169994)

Byzantine agreement protocol allows \(n\) distributed parties to agree on a common value when \(t < n/2\) of the parties (dishonest minority) become corrupted. The main efficiency metric for known distributed protocols is their round complexity -- the number of synchronous communication rounds that are needed for achieving agreement; in the first proposed protocols communication complexity was exponential in \(n\). Here, a probabilistic protocol is proposed for use in a public-key infrastructure with a trusted setup with a strongly rushing adaptive adversary who can observe messages of honest parties before choosing its own messages and replacing their messages with its own message. The authors claim, that their protocol improves the optimal agreement probability (with simultaneous termination) in rounds and is secure against a strongly rushing adaptive adversary that can corrupt any \(t = (1 - \varepsilon )n/2\) parties, for any constant \(\varepsilon > 0\). But the protocol uses ``ideal 1-round coin-flip'', which is based on a random oracle, thus its security is unknown (see e.g. [\textit{R. Canetti} et al., J. ACM 51, No. 4, 557--594 (2004; Zbl 1204.94063)]). Some simulation data is provided comparing the speed of convergence (decreasing in the number of rounds) of their algorithm with some known (also probabilistic) ones using the failure probability in three regimes: \(t < n/10\), \(t < n/3\) and \(t = 0.49n\) (the value of \(n\) is not provided); there are also proposals for directions of future research. The paper contains several meaningless assertions: ``number of corruptions is linear in the number of parties'' -- this could imply \(t \geqslant n\), ``adversary that can corrupt any \(t = (1 - \varepsilon )n/2\) parties, for any constant \(\varepsilon > 0\) -- with \(\varepsilon = 2\)'' this could imply that the new protocol can create new negatively corrupt (i.e. honest) parties. For the entire collection see [Zbl 1493.94001].