Abstract
In this work, we propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement (ABA) protocol, called OciorABA. This protocol achieves ABA consensus on an ℓ-bit message with an expected communication complexity of O(nℓ + n³ log q ) bits and an expected round complexity of O(1) rounds, under the optimal resilience condition n ≥ 3t + 1 in an n-node network, where up to t nodes may be dishonest. Here, q denotes the alphabet size of the error correction code used in the protocol. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA). In APVA, the distributed nodes input their vectors and aim to output a common vector, where some of the elements of those vectors may be missing or unknown. We propose an APVA protocol with an expected communication complexity of O( n³ log q ) bits and an expected round complexity of O(1) rounds. This APVA protocol serves as a key building block for our OciorABA protocol.