Extending Asynchronous Byzantine Agreement with Crusader Agreement
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909621709438976 |
|---|---|
| author | Erbes, Mose Mizrahi Wattenhofer, Roger |
| author_facet | Erbes, Mose Mizrahi Wattenhofer, Roger |
| contents | In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on $\ell$-bit inputs and $Θ(\ell n + n^2)$ bits of additional communication.
As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-λ}$ against $t < \frac{n}{3}$ faults with $Θ(\ell n + n^2(λ+ \log n))$ bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any $\varepsilon > 0$ be set to tolerate $t \leq \frac{n}{3 + \varepsilon}$ faults with $\mathcal{O}\bigl(\frac{\ell n}{\min(1, \varepsilon^2)} + n^2\max\bigl(1, \log \frac{1}{\varepsilon}\bigr) \bigr)$ bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and information-theoretic security. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02320 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extending Asynchronous Byzantine Agreement with Crusader Agreement Erbes, Mose Mizrahi Wattenhofer, Roger Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on $\ell$-bit inputs and $Θ(\ell n + n^2)$ bits of additional communication. As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-λ}$ against $t < \frac{n}{3}$ faults with $Θ(\ell n + n^2(λ+ \log n))$ bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any $\varepsilon > 0$ be set to tolerate $t \leq \frac{n}{3 + \varepsilon}$ faults with $\mathcal{O}\bigl(\frac{\ell n}{\min(1, \varepsilon^2)} + n^2\max\bigl(1, \log \frac{1}{\varepsilon}\bigr) \bigr)$ bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and information-theoretic security. |
| title | Extending Asynchronous Byzantine Agreement with Crusader Agreement |
| topic | Distributed, Parallel, and Cluster Computing Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2502.02320 |