Source-linked AI summary
The latest gossip on BFT consensus
Ethan Buchman, Jae Kwon, Zarko Milosevic
TL;DR
The paper addresses Byzantine consensus for wide-area networks with many mutually distrusted nodes communicating through gossip. It presents Tendermint’s consensus algorithm and a gossip-aware termination mechanism. The algorithm provides agreement and validity, while its design targets termination without additional communication and uses a single execution mode.
Problem
BFT consensus must support wide-area networks with high numbers of mutually distrusted nodes communicating through gossip-based peer-to-peer networks.
Method
Tendermint presents a Byzantine-fault-tolerant consensus algorithm with a termination mechanism that exploits gossip communication and a single execution mode.
Results
The algorithm satisfies Agreement and Validity, and its termination mechanism requires no additional information beyond messages already sent.
Takeaways & Limitations
Tendermint is designed as a BFT SMR platform for many mutually distrusted nodes communicating over gossip-based peer-to-peer networks.
Abstract
from arXiv · showhide
The paper presents Tendermint, a new protocol for ordering events in a distributed network under adversarial conditions. More commonly known as Byzantine Fault Tolerant (BFT) consensus or atomic broadcast, the problem has attracted significant attention in recent years due to the widespread success of blockchain-based digital currencies, such as Bitcoin and Ethereum, which successfully solved the problem in a public setting without a central authority. Tendermint modernizes classic academic work on the subject and simplifies the design of the BFT algorithm by relying on a peer-to-peer gossip protocol among nodes.
I. INTRODUCTION
Blockchain deployments create new BFT consensus requirements: many mutually distrusted nodes communicate over wide-area, gossip-based networks. Tendermint addresses these requirements with a novel algorithm and a termination mechanism that avoids extra communication and uses one execution mode.
- Blockchain systems must reach agreement among large numbers of nodes across wide-area networks, even when some nodes behave maliciously.
- Unlike traditional data-center deployments, blockchain nodes connect only to subsets of peers and communicate through gossip-based protocols.
- Tendermint introduces a Byzantine-fault-tolerant consensus algorithm as the core of a BFT state-machine-replication platform.
- Existing proposal mechanisms can have communication complexity that increases with the number of processes because they transmit signed message sets or values.
- Its termination mechanism requires no additional communication, uses a single execution mode, and is intended to simplify implementation.
II. DEFINITIONS
The paper models Byzantine processes communicating through gossip in a partially synchronous network and defines the replication and consensus properties Tendermint must satisfy. SMR requires replicas to execute valid client requests in the same order, while consensus requires agreement, termination, and validity.
- The system permits arbitrary Byzantine behavior, uses signed protocol messages, and assigns processes voting power that may be zero.
- Processes communicate with subsets of peers, with gossip providing an indirect communication channel among correct processes.
- The network is partially synchronous: after GST, correct-process communication is reliable and delivered within the bound ∆.
- State-machine replication keeps replicas synchronized by starting them in the same state and applying client requests in the same order.
- Only valid client transactions are processed, because the replicated service verifies requests before execution.
- Tendermint requires agreement, termination, and validity, with valid() determining whether a decided value satisfies the application-specific predicate.
III. TENDERMINT CONSENSUS ALGORITHM
Tendermint runs a round-based, three-message BFT consensus protocol with weighted proposers, timeouts, and gossip-based communication. Its novel termination mechanism reuses already-sent messages while ensuring that correct processes eventually decide.
- Fault model: The protocol assumes n > 3f, so faulty processes have less than one third of total voting power, and presents the simpler case n = 3f + 1.Voting-power thresholds determine when message conditions become true.
- Round structure: Tendermint proceeds in rounds with a dedicated proposer selected by weighted round-robin according to voting power.The proposer mapping is known to all processes, and internal transitions are triggered by message reception or timeout expiration.
- Timeouts: Three increasing timeouts prevent indefinite blocking, advance processes between rounds, and eventually accommodate timely communication between correct processes after GST.The timeout schedule is timeoutX(r) = initTimeoutX + r * timeoutDelta and resets for each consensus instance.
- Message exchange: Processes exchange PROPOSAL, PREVOTE, and PRECOMMIT messages, with only PROPOSAL carrying the potentially large value and votes carrying its constant-size identifier.This design suits blockchain values such as transaction blocks while keeping voting messages small.
IV. PROOF OF TENDERMINT CONSENSUS ALGORITHM
The paper proves that Tendermint satisfies termination, agreement, and validity under its voting-power and timing assumptions. It also shows that after a suitable correct proposer enters a round, all correct processes can decide within a bounded time.
- Agreement: Lemma 3 establishes agreement: if correct processes decide in the same or later rounds, they decide the same value.The proof relies on the intersection of any two voting-power sets of size 2f + 1 in at least one correct process.
- Validity: Lemma 4 establishes validity because the decision rule allows a process to decide only when the proposed value is valid.The proof directly invokes the validity check at line 50.
- Bounded decision: Under the stated assumptions, all correct processes decide in round r before t + 4∆ + timeoutPrecommit(r − 1).The assumptions include a correct proposer, compatible locked and valid rounds, and sufficiently long propose, prevote, and precommit timeouts.
- Timing argument: The proofs use gossip to disseminate quorum messages, allowing correct processes to receive the proposal and required votes within the timing bounds.After receiving the relevant messages, all correct processes can send PRECOMMIT and decide before the precommit timeout expires.
- Value propagation: If a correct process locks v after GST and timeoutPrecommit(r) > 2∆, all correct processes set validValue to v and validRound to r before round r + 1.This property propagates the locked value into later proposals.
V. CONCLUSION
Tendermint is a Byzantine-fault tolerant consensus algorithm for wide-area networks with many mutually distrusted nodes communicating through gossip-based peer-to-peer networking. Its single execution mode and gossip-based termination mechanism aim to simplify the algorithm and its proofs, making correct implementation easier.
- Tendermint is a new Byzantine-fault tolerant consensus algorithm forming the core of the Tendermint BFT SMR platform.
- The algorithm targets wide-area networks with many mutually distrusted nodes communicating over a gossip-based peer-to-peer network.
- Tendermint uses a single execution mode, with a communication pattern similar to the normal case of PBFT.
- Its novel termination mechanism exploits gossip-based communication between nodes.
- The algorithm and proofs are presented as simple and elegant, making Tendermint easier to understand and implement correctly.