Near-Optimal Communication Byzantine Reliable Broadcast under a Message Adversary
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914970936016896 |
|---|---|
| author | Albouy, Timothé Frey, Davide Gelles, Ran Hazay, Carmit Raynal, Michel Schiller, Elad Michael Taïani, François Zikas, Vassilis |
| author_facet | Albouy, Timothé Frey, Davide Gelles, Ran Hazay, Carmit Raynal, Michel Schiller, Elad Michael Taïani, François Zikas, Vassilis |
| contents | We address the problem of Reliable Broadcast in asynchronous message-passing systems with $n$ nodes, of which up to $t$ are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates ${\cal O}(|m|+nκ)$ bits per node, where $|m|$ represents the length of the application message and $κ=Ω(\log n)$ is a security parameter. This communication complexity is optimal up to the parameter $κ$. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of ${\cal O}(n|m|+n^2κ)$ bits per node. Our solution sends at most $4n^2$ messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message $m$. Instead, nodes forward authenticated fragments of the encoding of $m$ using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming $n > 3t+2d$, where the adversary drops at most $d$ messages per broadcast, our algorithm allows at least $\ell = n - t - (1 + ε)d$ (for any arbitrarily low $ε> 0$) correct nodes to reconstruct $m$, despite missing fragments caused by the malicious nodes and the message adversary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16253 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Communication Byzantine Reliable Broadcast under a Message Adversary Albouy, Timothé Frey, Davide Gelles, Ran Hazay, Carmit Raynal, Michel Schiller, Elad Michael Taïani, François Zikas, Vassilis Distributed, Parallel, and Cluster Computing We address the problem of Reliable Broadcast in asynchronous message-passing systems with $n$ nodes, of which up to $t$ are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates ${\cal O}(|m|+nκ)$ bits per node, where $|m|$ represents the length of the application message and $κ=Ω(\log n)$ is a security parameter. This communication complexity is optimal up to the parameter $κ$. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of ${\cal O}(n|m|+n^2κ)$ bits per node. Our solution sends at most $4n^2$ messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message $m$. Instead, nodes forward authenticated fragments of the encoding of $m$ using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming $n > 3t+2d$, where the adversary drops at most $d$ messages per broadcast, our algorithm allows at least $\ell = n - t - (1 + ε)d$ (for any arbitrarily low $ε> 0$) correct nodes to reconstruct $m$, despite missing fragments caused by the malicious nodes and the message adversary. |
| title | Near-Optimal Communication Byzantine Reliable Broadcast under a Message Adversary |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2312.16253 |