COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909880921620480 |
|---|---|
| author | Chen, Jinyuan |
| author_facet | Chen, Jinyuan |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00263 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement Chen, Jinyuan Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory 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$. |
| title | COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement |
| topic | Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2511.00263 |