{"ID":2847782,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00263","arxiv_id":"2511.00263","title":"COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement","abstract":"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 $\\ell$-bit message, with a total communication complexity of $O(\\max\\{n\\ell, 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 \\geq 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\\ell, 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 \\geq 3t + 1$. Moreover, OciorACOOL retains the same low-complexity, traditional $(n, k)$ error-correction encoding and decoding as COOL, with $k=t/3$.","short_abstract":"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 $\\ell$-bit message, with a total communication complexity of $O(\\max\\{n\\ell, nt \\log q\\})$ bits, four communication rounds in the worst case, and a single...","url_abs":"https://arxiv.org/abs/2511.00263","url_pdf":"https://arxiv.org/pdf/2511.00263v1","authors":"[\"Jinyuan Chen\"]","published":"2025-10-31T21:23:55Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.CR\",\"cs.IT\"]","methods":"[]","has_code":false}