Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain

Starters

• For definitions, read the Primer by Chjango Unchained.
• For an overview of the Cosmos/Tendermint software stack, read The Value Proposition of Cosmos by Gautier MARIN.
• Watch the Cosmos Network Topological Overview by Sunny Aggarwal.

Intro

Itcan feel like information overload for the newly initiated to get a crash course about Tendermint, the Cosmos Network, and where the two intersect. We’ve written about the Cosmos/Tendermint stack at a high level, but in this post, we’ll dive a bit deeper into Tendermint Core’s consensus and networking layers. The design of said software stack is composed of an application layer (Cosmos-SDK), a consensus layer, and a networking layer (Tendermint Core). Tendermint marries consensus with a p2p gossip protocol in a completely novel way. Using a monolithic architecture is typically bad practice in computer science, as doing so makes it difficult to reuse components of the code, and attempts to do so result in complex maintenance procedures for forks of the codebase.

Top Down: Application Layer (Cosmos-SDK), Application Blockchain Interface (ABCI), Tendermint Core stack (consensus algorithm + p2p networking protocol).

First things first: semantics. Tendermint Core, the piece of software, is used synonymously with Tendermint, the organization that’s implementing Tendermint Core and the Cosmos Network software stack. Technically, Tendermint Core is a low-level protocol which is actually composed of two protocols in one: a consensus algorithm and a peer-to-peer networking protocol. Jae Kwon and Ethan Buchman, inspired by the design goal behind Raft and PBFT, specified Tendermint as an easy to understand, developer-friendly algorithm while doing algorithmically complex systems engineering.

The new generation of BFT Proof-of-Stake (PoS) consensus algorithms draw elements from Tendermint’s BFT adaptation to the public blockchain domain. This adaption is what we refer to as Tendermint BFT, and is more generally classified as BFT-based Proof-of-Stake (as opposed to chain-based Proof-of-Stake). For a crash course of chain-based versus BFT-based PoS, see: Casper vs. Tendermint.

Now that that’s out of the way, let’s bite into the meat of the introduction: What is Tendermint and how does it work at a high level?

Tendermint BFT Stack

Bitcoin is the intellectual ancestor of all blockchain-based cryptographic systems that we know and love today. The Tendermint protocol shares commonality with Bitcoin inasmuch as the two protocols record everything on a blockchain, yet they each provide their unique solutions to the Byzantine General’s Problem, also referred to as the consensus, or “agreement”, problem. Tendermint’s lineage is closely traced back to the world of distributed computing and Byzantine Fault Tolerance (BFT) literature in academia (e.g., see Ethan Buchman’s thesis). Whereas in the Bitcoin genesis story, after the many failed attempts of previous electronic cash systems — with the exception of PayPal — Bitcoin rose above the ashes as a censorship-resistant decentralized currency system.

The Bitcoin protocol optimizes for censorship-resistance, critically, due to its primary function as a payment system. Tendermint, on the other hand, optimizes for general Byzantine fault-tolerant distributed applications and data processing amidst a wide area network (WAN), e.g. hundreds of nodes (high node count). This distinction is nuanced and merits deeper investigation.

For context, in the world of academia, there had been very little research done on BFT systems for WAN and only for a small number of nodes — 4 to 7 at maximum — and always for a single administrative domain. As for BFT systems for WAN with a large number of nodes and for multiple administrative domains, no significant body of work has been widely adopted in practice.

Before 2009, when Bitcoin introduced a paradigm-shifting technology — the concept of a blockchain — to the world, the consensus problem in a WAN setting for high node counts was left largely unanswered. Despite solving the Two Generals’ problem, however, Bitcoin was not really an algorithm to solve consensus, in the purely theoretical sense in the research area of distributed systems. Furthering the work in the BFT domain was far from done.

In 2014, Jae Kwon, coming from a computer science and systems engineering background, envisioned a purely BFT-based protocol which would scale to the tune of hundreds of nodes in the permissionless setting with Proof-of-Stake (PoS) as the underlying security mechanism. And so Tendermint was created. Consequently, this system model designed with PoS as the primary security mechanism over a large number of validating nodes in a WAN turned out to be a significantly complex engineering endeavor, taking almost 4 years to implement in the public blockchain setting. That setting is Cosmos, slated to launch this summer in 2018.

The Model

Tendermint is modeled as a deterministic protocol, live under partial synchrony, which achieves throughput within the bounds of the latency of the network and individual processes themselves. See where the purple is outlined in Vlad Zamfir’s triangle? Tendermint falls somewhere along the bottom-left corner.

Vlad Zamfir’s Tradeoff Triangle for fault tolerant consensus protocols

FLP Impossibility

Theorem: “…we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death.” As in, consensus cannot be solved in purely asynchronous networks with a deterministic protocol if at least a single process can fail.

Defined by Dwork, Lynch, and Stockmeyer in their paper, Consensus in the Presence of Partial Synchrony: “Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound…on the time required for a message to be sent from one processor to another and a known fixed upper bound…on the relative speeds of different processors. In an asynchronous system no fixed upper bounds…exist….The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds….” It was in attempting to solve this problem that Tendermint was born. Tendermint is thus a modified version of the aforementioned DLS protocol.

Consensus Algorithm

Partially Synchronous, Synchronous, and Asynchronous Communication

Let’s explore the synchronous case, using a well-known protocol for reference: the Bitcoin protocol. In Bitcoin, there is a “known fixed upper bound”. This is referring to the 10 minute block time. In order for the Bitcoin network to move forward with creating blocks, the protocol artificially imposes a timing assumption, giving the entire network of nodes 10 whole minutes to listen for, collect, validate, and gossip transactions propagating across its peer network.

Ethereum is another example of a protocol that makes synchrony assumptions with block times averaging 15 seconds. While 15 seconds is much faster than 10 minutes — giving the Ethereum network the benefit of higher throughput — this comes at the expense of its miners, as this results in more orphaned blocks; there is less time for transactions to propagate through its network.

Tendermint belongs to a class of protocols which solve consensus under partially synchronous communication, wherein, a partially synchronous system model alternates between periods of synchrony and asynchrony; we sometimes refer to this model as “weakly synchronous”. What this means is, Tendermint does rely on timing assumptions in order to make progress. However, in contrast to synchronous systems, the speed of progress does not depend on system parameters, but instead depends on real network speed.

Liveness & Termination

Defined: “The termination property is just that each correct processor should eventually make a decision.”

Those algorithms that of Nakamoto consensus, Peercoin, NXT, Snow White, Ouroboros, etc., in the synchronous system model, rely on synchrony assumptions not just for process termination but for safety. Those algorithms designed for synchronous systems always have fixed bounds which are known and always hold. And in the event that the synchrony bounds do not hold, consensus is broken, and the chain will fork. Therefore, Bitcoin’s 10 minute block time, for example, is duly conservative, as to preserve safety.

By way of contrast, Tendermint never forks in the presence of asynchrony if less than 1/3 of processes are faulty. This property is what makes Tendermint a BFT-based PoS protocol, in which it strictly prefers safety over liveness (see: CAP Theorem). As a result, a Tendermint blockchain will halt momentarily until a supermajority, i.e. more than 2/3, of the validator set comes to consensus.

Now, there are consensus protocols that work in purely asynchronous networks, but, adhering to the FLP Impossibility Theorem, they cannot simultaneously be deterministic.

Deterministic vs. Nondeterministic Protocol

Nondeterministic protocols which solve consensus under the purely asynchronous case potentially rely on random oracles and generally incur high message complexity overhead, as they depend on reliable broadcasting for all communication. In the asynchronous environment, the overhead cost of a single reliable broadcast is about equivalent to one [round](http://tendermint.readthedocs.io/projects/tools/en/master/introduction.html#consensus-overview) of Tendermint. Protocols like HoneyBadger BFT fall into this class of nondeterministic protocols under asynchrony. Normally, they require three instances of reliable broadcast for a single round of communication.

Tendermint instead is a totally deterministic protocol; there is no randomness in the protocol whatsoever. Leaders are elected deterministically, through a defined mathematical function in the implementation. As such, we are able to mathematically prove that the system is live and that the protocol is guaranteed to make decisions.

Rotating Leader Election

Tendermint rotates through the validator set, i.e. block proposers, in a weighted round-robin fashion. The more stake, i.e. voting power, that a validator has delegated to them, the more weight that they have, and the proportionally more times they will be elected as leaders. To illustrate, if one validator has the same amount of voting power as another validator, they will both be elected by the protocol an equal amount of times.

The simplified explanation of how the algorithm works looks like this:

1. Validator weight is established
2. Validator is elected, their turn to propose a block
3. Weight is recalculated, decreases some amount after round is complete
4. As each round progresses, weight increases incrementally in proportion to voting power
5. Validator is selected again

Because the protocol selects block proposers deterministically, given that you know the validator set and each validator’s voting power, you could compute exactly who the next block proposers will be in rounds x, x + 1,...,x + n. Because of this, critics argue that Tendermint isn't decentralized enough. When you can know predictably who the leaders will be, an attacker could target those leaders and launch a DDoS attack against them and potentially halt the chain from progressing. We mitigate this attack vector by implementing something called Sentry Architecture in Tendermint.

P2P Networking Protocol

Sentry Node Architecture

A properly set up validator will never expose the IP address of or accept incoming connections to their validator node. A correctly set up, well-defended validator will actively spawn sentry nodes, which act as full node proxies to the network, to obfuscate the real location of their validator node. IP addresses on the p2p layer are never exposed.

That said, taking advantage of Sentry Node Architecture is opt-in; the onus is on the validator to maintain a fault-tolerant full node. This is where we make extra-protocol assumptions based on cryptoeconomic incentives. The assumption is, a validator will want to take all precautionary measures so as to maintain fault-tolerance, remain available, and ultimately play their part in keeping the network live. Because if they don’t, they get kicked out of the validator set for being offline for over a certain amount of time.

Peer Exchange (PEX) Reactor

Tendermint borrows from Bitcoin’s peer discovery protocol. More specifically, Tendermint adopts the p2p AddressBook from btcd, the Bitcoin alternative implementation in Go. The PEX enables dynamic peer discovery by default.

Tendermint in Practice

After all is said and done, beyond the fancy algorithmic design and academic jargon, what is Tendermint actually useful for?

Bad news is, everyday people won’t find Tendermint useful. Good news is, application developers can bridge the gap between protocol and end-user. Tendermint is designed to be customizable and flexible enough to fit any setting, be it public or enterprise, where a consensus protocol is desired.

Tendermint is ideal for a developer who wants to implement an application on top of its own blockchain. It comes pre-assembled, so if the developer chooses to go for a pure Proof-of-Stake, BFT-based consensus engine to power their dAppzone, they can easily do so.

The fun part comes when users get to implement their high-level business logic with the Cosmos-SDK. To interface with the consensus/networking layers of Tendermint is then done through a Tendermint socket protocol we call the Application Blockchain Interface, or the ABCI.

• Application Layer: Cosmos-SDK (Blockchain Application Framework)
• Cosmos-SDK Alpha Release
• Tendermint ABCI

Ongoing Research

Currently, we are delving into BLS signature research which could potentially lead to a reduction in the size of Tendermint block headers from 3.2 KB (with ~100 validators) to 64 bytes.

We also have a design for randomizing the round-robin proposer selection function in a secure way to make DDoS’ing the next proposer even more difficult, but the initial step is the Sentry Node Architecture.

Cosmos Academy Inaugural Meetup!

We’re hosting an upcoming meetup in Berkeley, CA, with Zarko Milosevic, Senior BFT Distributed Systems Researcher, who will give a Q&A session about everything Tendermint. We will livestream this meetup and publish the broadcast on the Cosmos Network’s YouTube channel.

• Register for the first Cosmos Academy Meetup on May 26th: here.

Who Am I

Chjango Unchained heads Communications and the Cosmos Academy at Tendermint. She is the chief editor of the Cosmos blog and brings the creative direction behind all the video and written content from Cosmos. Primarily, she writes articles breaking down technical subjects about protocols, distributed systems, and blockchain tech to broad audiences of all levels. Before Cosmos, she came from NASA’s Jet Propulsion Laboratory, having never left space.

Additional Resources

• Read the Interview with Tendermint Core Senior Research Scientist, Zarko Milosevic: here.
• Kyle Kingsbury of Jepsen showcases Tendermint BFT:

• For the technical specification of Tendermint, see Readthedocs by Zach Ramsay.
• Read the original Tendermint whitepaper by Jae Kwon.
• Read the History of Distributed State by Ethan Buchman.
• Listen to the History of Distributed State with Ethan Buchman on the Software Engineering Daily podcast.
• Listen to The Blockchain Ecosystem in the Early Days on the Bitcoin Podcast Network with Zaki Manian.