2025/10/31 by Jinyuan Chen, Chen, Jinyuan
Computer Science · #Distributed systems and fault tolerance #Cryptography and Data Security #Blockchain Technology Applications and Security
paper · pdf · doi:10.48550/arxiv.2511.00263
COOL (Chen'21) is an error-free, information-theoretically secure Byzantine agreement (BA) protocol proven to achieve BA consensus in the synchronous setting for an ℓ-bit message, with a total communication complexity of O(max\nℓ, nt log q\) bits, four communication rounds in the worst case, and a single invocation of a binary BA, under the optimal resilience assumption n ≥ 3t + 1 in a network of n nodes, where up to t nodes may behave dishonestly. Here, q denotes the alphabet size of the error correction code used in the protocol. In this work, we present an adaptive variant of COOL, called OciorACOOL, which achieves error-free, information-theoretically secure BA consensus in the asynchronous setting with total O(max\nℓ, n t log q\) communication bits, O(1) rounds, and a single invocation of an asynchronous binary BA protocol, still under the optimal resilience assumption n ≥ 3t + 1. Moreover, OciorACOOL retains the same low-complexity, traditional (n, k) error-correction encoding and decoding as COOL, with k=t/3.