Byzantine Consensus in the Partially Authenticated Setting

Abstract

Byzantine Agreement and Broadcast are traditionally studied in one of two extremes: the authenticated setting, where a public key infrastructure (PKI) enables universally verifiable signatures and yields higher fault tolerance, and the unauthenticated setting, where no PKI is available and resilience necessarily drops. Motivated by Proof-of-Stake blockchains, where only a stable subset of participants (e.g., validators) have registered long-term keys while others do not, we initiate a systematic study of consensus in the \emph{partially authenticated} setting, where a subset of parties are \emph{registered} in a PKI and the remaining parties are \emph{unregistered}. We provide a nearly complete feasibility characterization of the resilience as a function of the number $s$ of registered parties among $n$ total parties. First, we show that Byzantine Agreement or Byzantine Broadcast with an \emph{unregistered} sender is possible if and only if $t \le \max\{\lceil s/2\rceil,\lceil n/3\rceil\}-1$, matching a simple protocol and an impossibility bound. Second, for Byzantine Broadcast with a \emph{registered} sender, we give a deterministic synchronous broadcast protocol tolerating up to $t \le s + \lceil (n-s)/3\rceil - 1$ Byzantine faults (equivalently, $3t