jzhao.xyz

Search

Search IconIcon to open search

Tendermint

Last updated Jul 3, 2022 Edit Source

Tendermint is most useful as an analog of Paxos/Raft but in a multi-stakeholder, or otherwise more adversarial, setting. However, the performance may not be as high due to the overhead of cryptographic operations

Source Paper, authored by Buchman, Kwon, Milosevic in 2018, stabilized in 2019.

A state machine replication protocol with a partially synchronous system model that, when $f < \frac n 3$, satisfies always consistency and eventually satisfies liveness (under the presence of an attack). However, the time to obtain a supermajority increases linearly with the number of nodes in the network.1

High-level ideas:

  1. Iterated single-shot consensus (something that looks like Byzantine Agreement) where the output of each single-shot consensus instance outputs a block (ordered list of transactions)
  2. For a fixed height, keep proposing + voting until agreement is reached
  3. Two stages of voting as different nodes may see different voting schemes

We assume PKI and a shared global clock. A round is $4 \Delta$ timesteps, leaders are rotated once per round.

# Properties

# Quorum Certificate (QC) Lemma

A collection of a supermajority ($\geq \frac 2 3$) of votes for a block $B$ in a particular round at some height $h$ and some stage $s$. Any two QCs overlap in at least one honest node as $overlap \geq n - \frac 1 3 n - \frac 1 3 n > f$ and thus any two QCs must support the same block $B$.

# State

# Pseudocode

Assume a specific height $h$ and round $r$ with leader $l$. We split each round into 4 phases ($t = 4 \Delta r$).

  1. $t = 4 \Delta r$:
    1. $l$ updates $(B_l,QC_l)$ to most recent QC known
    2. broadcast $(B_l, Q_l)$ signed by $l$ to all other nodes
  2. $t = 4\Delta r + \Delta$:
    1. honest node $i$ will ignore the proposal if it seems out of date ($QC_l$ seems behind $QC_i$)
    2. if node $i$ receives $(B_l, QC_l)$ from $l$ and it is up to date
      1. broadcast first-stage vote for $vote_1(B_l)$
      2. update $(B_i, Q_i) := (B_l, Q_l)$
      3. broadcast $(B_l, Q_l)$ signed by $i$
    3. else, do nothing
  3. $t = 4 \Delta r + 2\Delta$:
    1. if node $i$ receives $\geq \frac 2 3 n$ round-$r$ stage-1 votes (supermajority) for block $B$,
      1. if this occurs, all possible QCs must all support the same block (by QC overlap property)
      2. assemble QC from supermajority of votes
      3. set $QC_i := QC_\textrm{assembed}$, $B_i := B$
      4. after witnessing a conclusive winner to the first stage, we broadcast second stage vote for $vote_2(B_i)$
      5. broadcast $(B_i, QC_i)$ signed by $i$
    2. else, do nothing
  4. $t = 4\Delta r + 3 \Delta$:
    1. if node $i$ receives $\geq \frac 2 3 n$ round-$r$ stage-2 votes for block $B$,
      1. set $QC_i := QC_\textrm{assembed}$, $B_i := B$
      2. commit $B$ to local history
      3. broadcast $(B_i, QC_i)$ signed by $i$
      4. increment $h_i$, re-initialize $B_i$ and $QC_i$ to null
    2. else, do nothing
  5. $t = 4 \Delta r + 4 \Delta$ (just before round $r + 1$):
    1. If we have heard of a stage-2 QC for block $h_i$ supporting block B
      1. commit $B$ to local history
    2. else, do nothing

In the background,

# Proof of consistency

Definition of consistency: For a given block number, all honest nodes commit the same block $B^*$.

This seems pretty obvious from the QC lemma but we can formalize this through proof by induction:

Assumptions

  1. Fix a height $h$.
  2. Let $r$ be the first round in which $> \frac n 3$ honest nodes (set $S$) cast stage-2 votes for some block $B^*$. $r$ is the first round in which a stage-2 QC could have been created.

Induction: at the end of round $r$

These properties remain to be held in round $r + 1$ given they hold in round $r$ as no nodes of $S$ change their mind.

# Proof of liveness

Definition of liveness: if a transaction $T$ is known by all honest nodes, then it will get added to all of their local histories.

Note: this is a weaker definition of liveness than usual for SMR which states that if a single honest node knows about a transaction, then all honest nodes will eventually add that transaction to their local histories.

We define a clean round when

  1. we are post-GST
  2. there is an honest leader
  3. all honest nodes are working on the same block number

Proofs:


  1. “There is a practical limit to how decentralized a blockchain with PBFT-based consensus can be. For instance, most Tendermint based blockchains only have 100-150 validators; this is done to strike a balance between time to finality and decentralization” (from Scott’s Guide to Finality↩︎


Interactive Graph