OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector 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_ | 1866915122362974208 |
|---|---|
| author | Chen, Jinyuan |
| author_facet | Chen, Jinyuan |
| contents | 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 $\ell$-bit message with an expected communication complexity of $O(n\ell + n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds, under the optimal resilience condition $n \geq 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^3 \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11788 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement Chen, Jinyuan Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory 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 $\ell$-bit message with an expected communication complexity of $O(n\ell + n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds, under the optimal resilience condition $n \geq 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^3 \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. |
| title | OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement |
| topic | Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2501.11788 |