Byzantine Fault Tolerance

In a BFT protocol, each proposal is accompanied by signatures from participating replicas. A verifier checks that a quorum of signatures supports the proposal before committing. If a faulty node tries to equivocate by sending conflicting messages to different peers, the honest nodes detect the inconsistency and refuse to commit. This mechanism relies on signed messages and a broadcast primitive that guarantees that honest nodes see the same set of messages. In practice, certificates or digital signatures are used to bind identities to messages, ensuring accountability and preventing impersonation. Symmetry and determinism in the validation process help ensure that forks do not arise when honest replicas follow the protocol.

Many BFT protocols use a rotating leader to prevent a fixed leader from becoming a bottleneck or a target for sabotage. In a round, the current leader proposes a value, replicas exchange messages, and if a supermajority confirms, the value is committed. When the round ends, the leadership rotates to the next replica in a predetermined order. This rotation helps maintain liveness even if some leaders misbehave or fail by ensuring progress over time through diverse participation. The design choice affects latency and fault tolerance, but the safety properties remain preserved as long as the quorum thresholds are respected.

Suppose there are 4 nodes (3f+1 with f=1). A value proposal is broadcast. Nodes exchange PRE-PREPARE and PREPARE messages with signatures. If at least 3 matching PREPARE messages (a supermajority) are received, nodes move to COMMIT. With a COMMIT quorum, the value is decided and becomes the single agreed state. If a faulty node sends conflicting PREPARE messages to different nodes, honest replicas detect the discrepancy and prevent progress until the misbehavior is resolved. The protocol thus achieves agreement even when one node behaves incorrectly. The key takeaway is that agreement depends not on trust but on verifiable, threshold-based messaging.

In a 7-node BFT setup tolerating f=2, a typical commit requires at least 2f+1 = 5 matching votes. This threshold ensures that any two honest replicas intersect in at least 3 honest nodes, preventing conflicting commits. Implementations may also use 3f+1 baseline for the total and 2f+1 for supermajorities. The precise numbers depend on the protocol variant and the desired balance between safety and liveness, but the core principle remains: a quorum of authentic, non-faulty messages is required to advance decisions.

If the leader (or primary) stops responding, a BFT protocol may initiate a view change to elect a new leader. This preserves safety because nodes continue to validate proposals from the new leader with the same quorum requirements. The view change protocol collects information about progress and ensures that the new leader cannot propose conflicting values that would be accepted by a large subset of replicas. While timeouts can degrade performance, they are essential for liveness in the presence of failures. The coordination among replicas during view change ensures that no committed state is lost and that progress resumes once a non-faulty leader resumes control.

A BFT protocol prioritizes safety: two honest replicas cannot decide on different states. To guarantee safety, messages about a proposal must be cryptographically signed and cross-checked. Liveness, on the other hand, requires the system to make progress. In adverse conditions, some protocol designs may temporarily slow or pause decisions to avoid inconsistent histories, choosing to wait for enough evidence before moving to the next stage. This trade-off is central to practical BFT: you want to guarantee correctness while still making progress despite faults and delays.

In PBFT, there is a primary (leader) and several backups. The primary proposes a value, witnesses sign and relay it, and replicas move through PRE-PREPARE, PREPARE, and COMMIT phases. If the primary misbehaves or crashes, a view change occurs to elect another primary. The design ensures that, as long as fewer than f faulty nodes exist (with n = 3f+1), honest replicas will eventually commit the same value. The combination of threshold signatures and quorum intersections guarantees safety, while the structured rounds ensure liveness under partial synchrony.

Suppose n=4 and f=1. A commit requires at least 3 matching messages. Any two honest nodes see at least 2 common honest nodes in their quorums, guaranteeing that they cannot commit different values. This intersection property is key to preventing forks and ensuring global agreement. The mathematical bound 3f+1 underpins this guarantee. In practice, systems may implement digital signatures, round IDs, and view-change mechanics to preserve consistency across failures.

In a PBFT-like system, a typical commit requires multiple rounds of messaging. The latency depends on the network delay and the number of replicas. As the network scales, leader rotation and batching can reduce per-transaction overhead. However, increasing n also increases the number of messages required for safety, so optimizations like pipelining and quorums are used. The trade-off is between higher resilience to faults and higher communication cost. Designers often choose cautious defaults (e.g., 3f+1 total replicas) to balance reliability with practical performance.

Threshold signatures allow a group of t keys to produce a single compact signature that can be verified by anyone. In BFT, this enables smaller proofs for quorum validation. For example, in a 4-node network with f=1, a threshold of 3 signatures may be required to certify a commit. In larger networks, distributed signature schemes like BLS signatures are used to aggregate many signatures efficiently, reducing the communication cost while preserving security properties.