Prefix Consensus For Censorship Resistant BFT
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910009844039680 |
|---|---|
| author | Xiang, Zhuolun Tonkikh, Andrei Spiegelman, Alexander |
| author_facet | Xiang, Zhuolun Tonkikh, Andrei Spiegelman, Alexander |
| contents | Despite broad use of BFT consensus in blockchains, censorship resistance is weak: leaders can exclude transactions, a growing concern for trading and DeFi.
We address this by introducing a new abstraction and protocol stack. First, we introduce \emph{Prefix Consensus}, where parties input vectors and output $(v^{\sf low},v^{\sf high})$ that (i) extend the maximum common prefix of honest inputs and (ii) satisfy $v_i^{\sf low}\preceq v_j^{\sf high}$ for all honest $i,j$. Unlike classical consensus, no single output is required. We show Prefix Consensus is solvable asynchronously and give tight round-complexity bounds.
We then define \emph{Strong Prefix Consensus}, requiring agreement on the \emph{high} output. Our protocol is leaderless and partially synchronous: one Prefix Consensus instance decides (possibly different) lows, and additional instances yield a unique safe-to-extend high, even if an adversary can suspend one party per round.
We lift this to a leaderless, multi-proposer, censorship-resistant BFT SMR protocol: per slot, all parties broadcast proposals, deterministically rank them, and run one Strong Prefix Consensus on proposal hashes, committing honest proposals in \emph{four rounds}. A deterministic demotion rule updates the ranking when a party's proposal is excluded, implying that after GST at most $f$ slots can miss an honest proposal while progress remains leaderless under suspension and up to $f{-}1$ Byzantine faults.
Finally, we connect Prefix Consensus to graded and binary/validated consensus: we obtain an optimal-latency graded consensus (3 message delays) and leaderless Binary/Validated Consensus with worst-case message complexity $O(n^3)$ and communication $O(n^4)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02892 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Prefix Consensus For Censorship Resistant BFT Xiang, Zhuolun Tonkikh, Andrei Spiegelman, Alexander Distributed, Parallel, and Cluster Computing Despite broad use of BFT consensus in blockchains, censorship resistance is weak: leaders can exclude transactions, a growing concern for trading and DeFi. We address this by introducing a new abstraction and protocol stack. First, we introduce \emph{Prefix Consensus}, where parties input vectors and output $(v^{\sf low},v^{\sf high})$ that (i) extend the maximum common prefix of honest inputs and (ii) satisfy $v_i^{\sf low}\preceq v_j^{\sf high}$ for all honest $i,j$. Unlike classical consensus, no single output is required. We show Prefix Consensus is solvable asynchronously and give tight round-complexity bounds. We then define \emph{Strong Prefix Consensus}, requiring agreement on the \emph{high} output. Our protocol is leaderless and partially synchronous: one Prefix Consensus instance decides (possibly different) lows, and additional instances yield a unique safe-to-extend high, even if an adversary can suspend one party per round. We lift this to a leaderless, multi-proposer, censorship-resistant BFT SMR protocol: per slot, all parties broadcast proposals, deterministically rank them, and run one Strong Prefix Consensus on proposal hashes, committing honest proposals in \emph{four rounds}. A deterministic demotion rule updates the ranking when a party's proposal is excluded, implying that after GST at most $f$ slots can miss an honest proposal while progress remains leaderless under suspension and up to $f{-}1$ Byzantine faults. Finally, we connect Prefix Consensus to graded and binary/validated consensus: we obtain an optimal-latency graded consensus (3 message delays) and leaderless Binary/Validated Consensus with worst-case message complexity $O(n^3)$ and communication $O(n^4)$. |
| title | Prefix Consensus For Censorship Resistant BFT |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2602.02892 |