Cob: a Multidimensional Byzantine Agreement Protocol for Asynchronous Incomplete Networks

In this paper we extend the Multidimensional Byzantine Agreement (MBA) Protocol arXiv:2105.13487v2, a leaderless Byzantine agreement for vectors of arbitrary values, into the \emph{Cob} protocol, that works in Asynchronous Gossiping (AG) networks. This generalization allows the consensus process to be run by an incomplete network of nodes provided with (non-synchronized) same-speed clocks. Not all nodes are active in every step, so the network size does not hamper the efficiency, as long as the gossiping broadcast delivers the messages to every node in reasonable time. These network assumptions model more closely real-life communication channels, so the Cob protocol may be applicable to a variety of practical problems, such as blockchain platforms implementing sharding. The Cob protocol has the same Bernoulli-like distribution that upper bounds the number of steps required as the MBA protocol, and we prove its correctness and security assuming a supermajority of honest nodes in the network.