











Abstract:Despite broad adoption of BFT consensus in blockchains, censorship resistance remains weak: existing designs offer limited inclusion guarantees and allow leaders to exclude transactions.
We address this with a new abstraction and protocol stack. We define \emph{Prefix Consensus}, where parties input vectors and output two consistent vectors $(v^{\sf low},v^{\sf high})$ that extend the maximum common prefix of honest inputs and satisfy $v_i^{\sf low}\preceq v_j^{\sf high}$ for all honest parties $i,j$. We show that Prefix Consensus is solvable asynchronously and establish tight round-complexity bounds.
We then define \emph{Strong Prefix Consensus}, which additionally requires agreement on the high output, and give a leaderless partially synchronous protocol. Using its accountable variant, we build a leaderless, multi-proposer, censorship-resistant BFT SMR protocol with amortized four-round commit latency under synchronized starts, while guaranteeing that after GST at most $f$ slots can be censored.
Finally, we connect Prefix Consensus to graded consensus, obtaining a matching lower bound and a 3-round protocol, and derive leaderless Binary Consensus with improved worst-case complexity.
From: Zhuolun Xiang [view email]
[v1]
Mon, 2 Feb 2026 22:55:29 UTC (121 KB)
[v2]
Thu, 16 Jul 2026 22:26:03 UTC (117 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。