### Multi-Threshold Asynchronous Reliable Broadcast and Consensus

Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang

##### Abstract

Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties $f$ is bounded by a single given threshold $t$. If $f > t$, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as $f \le t_v$, $f \le t_c$ and $f \le t_t$ respectively. For consensus, we consider both variants of $(1-\epsilon)$-consensus and \emph{almost-surely terminating} consensus, where termination is guaranteed with probability $(1-\epsilon)$ and $1$, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: -Multi-threshold reliable broadcast is possible if and only if $\max\{t_c,t_v\} + 2t_t < n$. -Multi-threshold almost-surely consensus is possible if $\max\{t_c, t_v\} + 2t_t < n$, $2t_v + t_t < n$ and $t_t < n/3$. Assuming a global coin, it is possible if and only if $\max\{t_c, t_v\} + 2t_t < n$ and $2t_v + t_t < n$. -Multi-threshold $(1-\epsilon)$-consensus is possible if and only if $\max\{t_c, t_v\} + 2t_t < n$ and $2t_v + t_t < n$.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
lichen @ inf ethz ch
History
Short URL
https://ia.cr/2020/958

CC BY

BibTeX

@misc{cryptoeprint:2020/958,
author = {Martin Hirt and Ard Kastrati and Chen-Da Liu-Zhang},
title = {Multi-Threshold Asynchronous Reliable Broadcast and Consensus},
howpublished = {Cryptology ePrint Archive, Paper 2020/958},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/958}},
url = {https://eprint.iacr.org/2020/958}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.