Research Summary: Dissecting Tendermint

Consensus
, , ,
1

TLDR

  • This paper assesses the correctness of Tendermint, one of the industry’s most popular consensus protocols for cryptonetworks.
  • By reverse engineering the protocol and setting the correctness criteria for evaluation, the authors find that Tendermint is correct under the most adversarial conditions.

Citation

  • Y, Amoussou-Guenou, A. del Pozzo, M. Potop-Butucaru, S. Tucci-Piergiovanni, “Dissecting Tendermint”, in Networked Systems, pp. 166-182, Springer International Publishing, 2019.

    https://arxiv.org/abs/1809.09858

Core Research Question

  • Is Tendermint consensus correct?

Background

  • Bitcoin and Ethereum, today’s most notable blockchain networks, achieve consensus using proof-of-work (PoW) algorithms; essentially, nodes run in a trustless network, competing among themselves to solve a crypto-puzzle. The node that gets to solve this puzzle first is granted the right to produce the next block of transactions, which is then appended to the blockchain. The winning node, in turn, receives rewards for proposing the next block.

  • PoW-based systems, however, suffer from two major issues: (1) Due to the complexity of solving the PoW puzzle, network throughput is inherently limited; in Ethereum, the theoretical throughput is 30 transactions per second; (2) when two or more nodes solve the PoW puzzle, different chain suffixes exist until the network agrees on what the canonical chain should be. Until then, the blockchain state is not deterministic, but rather defined in terms of a high probability.

  • Byzantine Fault Tolerance (BFT) consensus protocols comprise a family of protocols initially designed to solve state-machine replication (e.g., a database) so that systems can converge on a single, canonical sequence of events in light of inconsistent database replicas.

  • Over three decades of BFT research has led to practical protocols, such as the one in seminal work by Castro and Liskov: Practical Byzantine Fault Tolerance (PBFT). PBFT protocols stand as an alternative to PoW-based consensus.

  • PBFT protocols guarantee consensus even if some participating network nodes display Byzantine behavior, i.e., they have an arbitrary behavior (which may not necessarily be intentional or malicious), provided the following conditions hold:

    • The number of nodes is at least 3f + 1, where f denotes the number of nodes with Byzantine behavior (arbitrary behavior, and may or not be intentional/malicious). An explanation proving this requirement can be found here;
    • Nodes participating in the consensus must be known. In Tendermint, these are called validators;
    • Communication occurs through an eventually synchronous network, i.e., after a finite but unknown time, a sent message is received within a given amount of expected delay. The intuition is as follows: there is a period of time that the network is asynchronous (a message can be delayed indefinitely), after which it is synchronous (there is an upper bound limit for the delay).

  • As an alternative to previous iterations of consensus protocols, Tendermint provides a PBFT-based consensus implementation. As such, the same conditions imposed by PBFT apply to Tendermint. For a lightweight presentation of the internals of Tendermint’s consensus protocol, we refer readers to Tendermint’s official post: What is Tendermint?.

  • When studying Tendermint, the authors make use of a system model outlining their basic assumptions, which entails: the number of nodes currently running in the network (arrival model), which nodes can exhibit Byzantine behavior (failure model), the network communication model, and the execution steps in which the nodes operate (execution model):

    • Arrival model:
      • The number of nodes in the network is finite at any given time; the amount of nodes in any given point in is not known beforehand;
      • The pool of nodes that could potentially join the network is unlimited;
      • Validator nodes are a subset of the nodes in any given point in time. Nodes can become validators based on some merit parameter; for instance, based on a bond provided to the network (stake). The validator set can be changed over time, and its size is always known beforehand.
    • Failure model: Any number of nodes in the network can have a Bynzatine behavior. Such nodes are denoted as faulty. Non-faulty nodes are deemed as correct. At any given time, the number of nodes (n) in the network is at least three times the number of faulty nodes (3f) plus one: n >= 3f + 1;
    • Communication model: nodes communicate in a eventually synchronous network;
    • Execution model: Each correct node operates in rounds made of three phases, namely:
      1. Send: initially, a node broadcasts messages computed in the previous round, or sends a default one if it is the first round. This operation is atomic (either it fully succeeds or fails);
      2. Delivery: collect messages sent by other nodes. This operation is also atomic;
      3. Compute: performs based on the messages delivered, the node updates its state.

  • The send and delivery phases are taken to be instantaneous operations whereas the delivery phase is not;

  • No global clock exists; nodes rely solely on their local clock.

Summary

  • The authors analyze the correctness of the consensus implementation in Tendermint, with respect to:
    • Termination: eventually, every correct validator eventually decides on a state;
    • Integrity: no correct nodes decided twice;
    • Agreement: if a correct validator decides on a given state s, then eventually all correct nodes also decide that its state should also be s;
    • Validity: a state is said to be valid if it satisfies a corresponding predicate, abstracted as valid.
  • State essentially means which block should be appended to the local copy of the blockchain as kept by each node.

Method

  • The authors reverse engineer the properties of the Tendermint consensus protocol
  • They then provide mathematical proofs to reason about the protocol’s properties

Results

  • In an eventual synchronous system under Byzantine faults, the Tendermint consensus implementation is correct w.r.t. validity, integrity, agreement, and termination.

Implications & Follow-ups

  • While Tendermint scales better than its traditional blockchain consensus counterparts, prior to this work it was unknown whether its consensus implementation was correct. This paper sets this milestone.

Applicability

  • The paper presentation provides readers with the grounds to better understand the properties of Tendermint’s consensus protocol. This could be particularly useful to researchers willing to study Tendermint (and PBFT in the context of blockchain), as well as developers willing to contribute to the project’s open-source codebase.
  • The results of the paper also provide actors (DApp developer, node operators, validators, etc) interfacing with Tendermint with the specific (and verified) guarantees that the network provides.
7 Likes
2

The above linked version of this paper did not contain the technical proofs, but I was able to rustle up a version that does include them.

I have a handful of questions:

  • Are subsequent versions of Tendermint consensus correct under the conditions described in this assessment?
  • Have there been additional formal/academic assessments?
  • Has Ethereum’s PoS consensus model undergone similar academic assessments?

Personally I’m very interested in the lattermost topic, and in an effort to better educate myself I’m going to take a look through The Beacon Chain Ethereum 2.0 explainer you need to read first and Combining GHOST and Casper which suggests that it proves the desired qualities for Ethereum’s proof-of-stake consensus mechanism.

4 Likes
3

Thanks for finding and sharing a version that included the technical proofs. Great questions also, so I did a little digging and couldn’t really find much of an answer here.

I did stumble through some academic literature that is at least addressing and analyzing Tendermint. I’m not sure if they’re all behind paywalls, but based on your interest in the second paper, you might like Chained Tendermint: A Parallel BFT Consensus Mechanism by Lei, Lan, & Lin (2020). Although the paper is proposing its own consensus algorithm, it includes some analysis of Tendermint, Casper, HotStuff, and Grandpa that might start to provide some answers to your last question there.

4 Likes
4

Hi @Eric, thanks for your interest in this post. Here is my follow-up to your question:

Question: Are subsequent versions of Tendermint consensus correct under the conditions described in this assessment?

Answer: Depends. If the changes in subsequent versions changes the premises on which the current proofs rely on, then yes. Unfortunately, one would have to identify what these dependencies are, map them to the code, and only then monitor whether these specific parts of the code change, and to what degree.

Question: Has there been additional formal/academic assessments?

Answer: Yes, here is a list of some related work:

Question: Has Ethereum’s PoS consensus model undergone similar academic assessments?

Answer: I believe so, specifically by Runtimetime Verification and Consensys R&D.

Hope that helps :)

4 Likes
5

Thank you for a great summary @lnrdpss.

Tendermint runs on Practical Byzantine Fault Tolerance(PBFT) protocol which is an improvement on Byzantine Fault Tolerance. From this summary, it seems that PBFT solves one of the two issues of the PoW consensus mechanism.

Does this innovation of Proof of Work (PoW) enhancement implemented on Tendermint have any security implications? Does it undermine the security of PoW, thus making Tendermint a less secure consensus mechanism?

4 Likes
6

@lnrdpss This is my opinion on tendermint consensus; I hope it is well written.

Tendermint consensus is software that allows for the secure and consistent replication of an application across multiple machines. Tendermint works securely even if up to one-third of the machines fail in arbitrary ways. By consistently, we mean that every non-faulty machine sees and computes the same transaction log. Secure and consistent replication is a fundamental problem in distributed systems; it is critical to the fault tolerance of a wide range of applications, including currencies, elections, infrastructure orchestration, and more.

Byzantine fault tolerance refers to the ability to tolerate machines failing in unpredictable ways, including becoming malicious (BFT). BFT theory has been around for decades, but software implementations have only recently gained popularity, owing largely to the success of “blockchain technology” such as Bitcoin and Ethereum. Blockchain technology is simply a more formalized version of BFT in a more modern setting, with an emphasis on peer-to-peer networking and cryptographic authentication. The name derives from the way transactions are batched in blocks, with each block containing a cryptographic hash of the previous one, forming a chain. In practice, the blockchain data structure optimizes BFT design.

2 Likes
7

@Ulysses Thanks for your question.

To clarify, PBFT is not an innovation of PoW; it is a completely different mechanism (for instance, differently from PoW, there is no mining).

If you are coming which a perspective of which one is safer (PoW vs PBFT), that would certainly be a deeper conversation. It suffices to say, at least from this study, that the Tendermint PBFT design is correct (it works as intended), provided the assumptions outlined in the summary hold.

1 Like