Paper 2026/2702

The Authentication Complexity of Byzantine Consensus

Abstract

Byzantine broadcast and Byzantine agreement are fundamental problems in distributed computing and building blocks for secure multiparty computation. In complete synchronous networks of $n$ parties with channels identifying the immediate sender, classical results establish how authentication changes resilience to $t$ Byzantine faults. Without initially authenticated public keys, both tasks are possible if and only if $n>3t$~\cite{PSL80}. With a complete public-key infrastructure (PKI), broadcast tolerates every $t<n$~\cite{DS83}, and agreement is possible if and only if $n>2t$. These thresholds leave a substantial gap: \emph{how much initial authentication is necessary for a given fault bound, and how does its distribution affect feasibility?} We study this question by allowing each party's designated public verification key to be initially authenticated to any subset of the other parties. We represent this setup by a directed authentication graph $G$ whose vertices are parties, with an edge $x\to y$ exactly when $y$ is a \emph{verifier} of $x$: that is, $x$'s designated public verification key is initially authenticated to $y$. We count each edge as one unit and define \emph{authentication complexity} as the \emph{minimum} total bindings over all setups and protocols achieving the required task and fault tolerance. Protocols may establish further authentication during execution without adding initial cost. We give a tight graph characterization of the initial authentication setups that support agreement, including when each party knows only its own initial key table and is not given the authentication graph. For $2t<n\le3t$ and $r=n-2t$, we show that agreement has authentication complexity $\Theta(\min\{n^2,(n^2/r)\ln(en/r)\})$ and give a protocol with polynomial local computation. At $n=2t+1$, broadcast requires $\Omega(n\ln^2 n/\ln\ln n)$ initial authentications, and has a construction using $O(n^{3/2}\sqrt{\ln n})$ initial authentications. At this threshold, we also show a complete PKI setup is necessary for agreement. Surprisingly, broadcast has subquadratic authentication complexity even when $t=n/2+o(n)$. For every fixed fault fraction $\alpha\in(1/2,1)$, we show its authentication complexity is $\Theta_\alpha(n^2)$. We also determine the exact authentication complexity of broadcast at maximum resilience: $\binom n2-1$ initial authentications suffice and are necessary to tolerate $t=n-1$ faults.