Optimal Good-Case Latency for Sleepy Consensus

In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2round good-case BB is possible if and only if at all times, at least 1 φ ≈ 0.618 fraction of the active parties are correct, where φ = 1+ √ 5 2 ≈ 1.618 is the golden ratio; 1-round good-case BA is possible if and only if at least 1 √ 2 ≈ 0.707 fraction of the active parties are correct.

of the membership set of parties operating the protocol (also called "stake shift" in the context of proof-of-stake blockchains). No reconfiguration of the set of operating parties takes place throughout this paper.

Part. Model Achiev. Resil. Imposs. Resil. BB 2 Static P. 1/2 [1] Open * Unknown P. 1/2 (Thm. 5) Open * Dynamic P. 1 -1/φ (Thm. 3) 1 -1/φ (Thm. 1) BB ≥ 3 Static P. 1/2 [1] † Open * Unknown P. 1/2 (Thm. 5) † Open * Dynamic P. 1/2 (Thm. 6) 1/2 [25] BA 1 Static P. 1/3 (Folk.: Lem. 1) 1/3 (Folk.: Lem. 2) Unknown P. 1 -1/ √ 2 (Thm. 4) ‡ 1 -1/ √ 2 (Thm. 2) Dynamic P. 1 -1/ √ 2 (Thm. 4) 1 -1/ √ 2 (Thm. 2) ‡ BA ≥ 2 Static P. 1/2 (Thm. 7) ‡ 1/2 [3] Unknown P. 1/2 (Thm. 7) ‡ 1/2 ‡ Dynamic P.

1/2 (Thm. 7) 1/2 ‡ "Folk." indicates a result is folklore. * The landscape of Byzantine broadcast in the "adversarial majority" regime remains incomplete, even under static participation. The protocol provided in [26] achieves Tgc = O( n n-f ). This matches the impossibility results [1] asymptotically, but concrete gaps remain. This lack of clarity seeps into the unknown participation model, since crashed honest parties can be treated as Byzantine for the purpose of protocols tolerating an adversarial majority of parties [25]. For dynamic participation, we fully characterize the good-case latency and resilience achievable for Byzantine broadcast and Byzantine agreement. † Implied by a protocol with better latency. ‡ Implied by a protocol or impossibility result for a more demanding model.