CryptoDB
Early Stopping Byzantine Agreement in $(1+\epsilon)\cdot f$ Rounds
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2024 |
| Abstract: | In this paper, we present two \textit{early stopping} Byzantine agreement protocols in the authenticated setting against a corrupt minority $t < n/2$, where $t$ represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes $f$ present during execution, irrespective of $t$. Our first protocol is deterministic and ensures early stopping termination in $ (d+5) \cdot (\lfloor f/d \rfloor +3)$ rounds, where $d$ is a fixed constant. For example, for all $d\ge 6$, our protocol runs in at most $(1+\epsilon )\cdot f$ rounds (where $0<\epsilon<1$), improving (for large $f$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg~\cite{Perry}, which terminates in $2f+4$ rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in $(d+9) \cdot (\lfloor f/d \rfloor +2)$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank.~\cite{GOLDREICH199045}, which \emph{always} requires an expected constant number of rounds and $O(t)$ rounds in the worst case, i.e., does not have the early stopping property. |
BibTeX
@inproceedings{asiacrypt-2024-34593,
title={Early Stopping Byzantine Agreement in $(1+\epsilon)\cdot f$ Rounds},
publisher={Springer-Verlag},
author={Fatima Elsheimy and Julian Loss and Charalampos Pamanthou},
year=2024
}