[July 2026 edition]
Consensus Algorithms, Underground (Part 3) — Lying Nodes, from PBFT to DAG-BFT
Published: Jul 22, 2026
Reading time: ~9 min
The algorithms covered so far assumed the crash failure model, in which nodes stop but do not lie. This part removes that assumption.
The Constant n = 3f + 1
In the Byzantine failure model, a node may take the following actions.
- Send different values to different recipients
- Claim votes that do not exist
- Replay stale messages
- Censor selected proposals
- Deliberately obstruct progress
- Use its private key to sign contradictory messages
The last item is the essential one. The presence of a signature says nothing about the correctness of the content. A signature attests only to the identity of the sender; it does not attest that the sender makes the same claim to everyone.
Typical BFT tolerates up to f Byzantine nodes with n = 3f + 1 nodes.
4 validators → 1 Byzantine fault
7 validators → 2 Byzantine faults
10 validators → 3 Byzantine faultsA decision certificate normally uses 2f+1 votes, and that number has a reason. With n = 3f+1, two sets of 2f+1 intersect in at least (2f+1) + (2f+1) − (3f+1) = f+1 nodes. Since at most f nodes are Byzantine, the intersection necessarily contains at least one honest node. That honest node is why two contradictory decisions cannot both stand.
Structurally this is the same as the majority quorum of the crash model, thickened by exactly the margin the liars require.
PBFT: Three-Phase Voting
PBFT targets deciding the same operation order across a replica set that contains malicious nodes.
client
↓
primary: PRE-PREPARE
↓
replicas: PREPARE
↓
replicas: COMMIT
↓
executeReduced to essentials, each replica is merely counting votes.
class PBFTReplica:
def __init__(self, node_id, f):
self.node_id = node_id
self.f = f
self.prepares = {}
self.commits = {}
def on_prepare(self, digest, sender):
self.prepares.setdefault(digest, set()).add(sender)
return len(self.prepares[digest]) >= 2 * self.f
def on_commit(self, digest, sender):
self.commits.setdefault(digest, set()).add(sender)
return len(self.commits[digest]) >= 2 * self.f + 1In practice, views, sequence numbers, checkpoints, signature verification, watermarks, and view changes are all required.
The reason for three phases rather than two is as follows. PREPARE establishes only that the replica agreed to this order in this view; it does not establish that other replicas reached the same conclusion. COMMIT is the phase that confirms that fact itself has been sufficiently shared. The property that a decision survives a leader change is what this second stage secures.
The problem is message volume. Because each replica sends to many others, the normal path tends toward O(n²). This is practical for small permissioned networks, but communication load grows sharply with the validator count.
Tendermint: Without Locking, Rounds Diverge
Tendermint-family consensus selects a proposer per round and runs two stages of voting.
proposal → prevote → precommit → commitAfter a validator precommits to a value, locking rules restrict it from voting for a conflicting value.
def on_proposal(block, proposal):
if locked_block is None:
return prevote(block)
if block.id == locked_block.id:
return prevote(block)
if proposal.valid_round > locked_round:
return prevote(block)
return prevote_nil()The core of Tendermint is not the simple rule that two-thirds of votes decide a value, but the condition under which a lock is released across rounds. Without locking rules, network delay can cause different values to be decided in different rounds.
BFT safety lives not in the vote counting, but in the part that defines when a node is permitted to change its preference.
HotStuff: Folding Votes into a Quorum Certificate
The weakness of PBFT-family protocols was the complexity of communication, particularly at leader change, and the resulting sensitivity to validator count.
HotStuff aggregates votes at the leader and packages them as a quorum certificate (QC).
validators
\ | /
leader
|
QCA QC is proof that 2f+1 votes were collected for a block.
struct Vote {
validator: ValidatorId,
block_hash: Hash,
view: u64,
signature: Signature,
}
struct QuorumCertificate {
block_hash: Hash,
view: u64,
signatures: AggregateSignature,
}Instead of distributing messages all-to-all, the leader distributes a single aggregated certificate. HotStuff is a leader-based BFT protocol in the partial synchrony model that combines responsiveness — progress at actual network speed under a correct leader — with linear communication complexity.
Chained HotStuff
Each block contains the QC of its parent.
B1 ← B2 ← B3 ← B4
QC1 QC2 QC3Once a multi-level certified chain forms, the ancestor block is committed. The conceptual three-chain rule is as follows.
def try_commit(block):
parent = block.parent
grandparent = parent.parent if parent else None
if block.qc.certifies(parent) and parent.qc.certifies(grandparent):
commit(grandparent)The essence is that PREPARE, PRE-COMMIT, and COMMIT — which PBFT held as independent message round trips — are pipelined into successive QCs on the chain. The number of stages is unchanged; the stages have been converted into an overlapping flow.
HotStuff’s design strongly influenced the Libra/Diem line and the subsequent BFT work around Aptos and Sui. Current Sui and Aptos, however, have moved to DAG-based consensus rather than plain HotStuff.
Narwhal: Separating Data Dissemination from Ordering
In traditional BFT, the leader distributes a large transaction batch and collects votes on its contents. Two distinct problems are mixed here: the availability question of whether everyone can obtain the proposed data, and the question of how the order is decided.
Narwhal separated them.
transaction dissemination
↓
DAG store
↓
consensus ordering protocolNarwhal is a DAG-based mempool responsible for high-throughput data dissemination and preservation of causal history. Ordering is handled by a separate consensus layer such as Tusk, Bullshark, or HotStuff.
A validator disseminates a batch and forms a certificate once it collects sufficient signatures.
struct Header {
author: AuthorityId,
round: u64,
payload: Vec<BatchDigest>,
parents: Vec<CertificateDigest>,
}
struct Certificate {
header: Header,
votes: Vec<SignedVote>,
}The certificate does not mean agreement with the header. It functions as proof of availability: a sufficient number of honest nodes have received the data and it can be retrieved later. The design fixes where the data is before deciding the order.
Bullshark: Extracting a Deterministic Order from the DAG
Bullshark derives a deterministic order over the round-based DAG that Narwhal builds.
round 1 round 2 round 3
A1 ────────▶ A2 ────────▶ A3
│ ╲ ▲ ╲ ▲
│ ╲ │ ╲ │
B1 ────────▶ B2 ────────▶ B3
│ ▲ ▲
C1 ────────▶ C2 ────────▶ C3Each node references multiple certificates from the previous round. A leader certificate that receives sufficient strong support is committed as an anchor, and its ancestor DAG is output in a deterministic order.
def strongly_supported(anchor, next_round, f):
supporters = {
cert.author
for cert in next_round
if anchor.digest in cert.parents
}
return len(supporters) >= 2 * f + 1In HotStuff the leader is the center of both ordering and proposal distribution. In Bullshark each validator adds data to the DAG in parallel, and the leader becomes closer to an ordering criterion within the DAG than a monopolist of distribution. Every validator uses bandwidth continuously, and the messages that serve as votes are carried as part of the DAG, so almost no additional voting round trips are required.
An implementation-level analysis (arXiv:2507.04956, 2025) reports 297,000 TPS with roughly 2 seconds of latency for Bullshark on Narwhal. This is a value under specific experimental conditions and does not guarantee production performance.
Mysticeti: Dropping Certification
In Narwhal/Bullshark, a certificate is formed for each DAG vertex before proceeding. This is safe, but it requires an extra round of signature collection per vertex.
The distinguishing feature of the Mysticeti family is the move to an uncertified DAG, in which DAG blocks are not certified in advance. Each validator references received DAG blocks directly from the next block it issues.
broadcast block
↓
receive blocks
↓
reference them directly
↓
implicit support accumulatesBecause a reference itself constitutes support, the round trip that formed certificates disappears. The paper (NDSS 2025) reports reaching the lower bound of three message rounds for DAG-based BFT, achieving 0.5 second consensus commit over a WAN together with throughput above 200k TPS. Integrating it into Sui is reported to have reduced latency to less than a quarter.
There is a cost. The explicit data availability boundary that a certified DAG provided is weakened, and defenses against equivocation and selective distribution by Byzantine validators move into the DAG interpretation rules. Adelie (arXiv:2408.02000, 2024) likewise notes that the uncertified DAG enables low latency while opening attack surfaces that did not exist in certified DAG protocols, and addresses their detection and prevention.
The cost removed by the speedup did not vanish; it moved to another layer as defensive complexity.
The Shoal Family: Not Waiting on a Slow Leader
Even in DAG-BFT, round progress stalls when the selected anchor leader is slow or malicious.
The approach of Shoal and Shoal++ is to update leader reputation from information already in the DAG, select leaders likely to succeed, and skip failed anchors quickly.
def choose_leader(authorities, reputation):
return max(
authorities,
key=lambda a: (
reputation[a].recent_success,
-reputation[a].latency,
reputation[a].availability,
),
)This is not merely a performance optimization. With a fixed round robin, a Byzantine leader takes its turn periodically, and each turn costs a timeout. Using past behavior observable from the DAG reduces the stall cost imposed by bad leaders. The advantage of this approach is that the evidence is already contained in the DAG at hand. Aptos Core publishes a consensus implementation that includes DAG-based order rules.
Fairness Is the Next Problem
Once performance improves, the next problems are stake concentration, reward concentration, and fairness in validator selection.
FairWave (arXiv:2606.10982, 2026) addresses the trilemma of Sybil resistance, reward fairness, and plutocracy, proposing to separate anchor selection from reward distribution into distinct channels in DAG-BFT. The selection channel is super-linear in stake so that splitting into Sybils yields no gain, while the reward channel is normalized by square root to mitigate concentration. As of now this is a recent research proposal and should not be treated as an established method with production history.
Summary
- The constants n = 3f+1 and 2f+1 derive from the requirement that any two quorums intersect in at least one honest node.
- PBFT has three phases because agreeing on an order and that agreement being shared are two different facts. The cost is O(n²) communication.
- The core of Tendermint is its locking rules. Safety lives in the conditions under which a node may change its preference.
- HotStuff folds votes into quorum certificates, converting PBFT’s three round trips into a pipeline on the chain and making communication linear.
- Narwhal separates dissemination from ordering and uses certificates as proof of data availability. Bullshark derives a deterministic order from that DAG (297,000 TPS with roughly 2 seconds reported).
- Mysticeti removes certificate formation from the normal path and reaches three message rounds (0.5 s over a WAN, above 200k TPS). In exchange, defenses against equivocation and availability attacks move into the DAG interpretation rules, prompting follow-up work such as Adelie.
Part 4 removes the final assumption, covering environments where neither the identity nor the number of participants is known: PoW and PoS, Solana’s ordering, Avalanche’s repeated sampling, and the option of avoiding agreement altogether.