Tendermint
Tendermint is most useful as an analog of Paxos/Raft but in a multistakeholder, 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}
Highlevel ideas:
 Iterated singleshot consensus (something that looks like Byzantine Agreement) where the output of each singleshot consensus instance outputs a block (ordered list of transactions)
 For a fixed height, keep proposing + voting until agreement is reached
 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
 Each node maintains a ($B_i$, $QC_i$) and periodically updates these variables blockQC pair it’s heard about
 Each node also keeps a local appendonly data structure for blocks considered ‘delivered’
 Each node maintains it’s own height (which block it is currently working on) and ignores all messages about other heights
# Pseudocode
Assume a specific height $h$ and round $r$ with leader $l$. We split each round into 4 phases ($t = 4 \Delta r$).
 $t = 4 \Delta r$:
 $l$ updates $(B_l,QC_l)$ to most recent QC known
 broadcast $(B_l, Q_l)$ signed by $l$ to all other nodes
 $t = 4\Delta r + \Delta$:
 honest node $i$ will ignore the proposal if it seems out of date ($QC_l$ seems behind $QC_i$)
 if node $i$ receives $(B_l, QC_l)$ from $l$ and it is up to date
 broadcast firststage vote for $vote_1(B_l)$
 update $(B_i, Q_i) := (B_l, Q_l)$
 broadcast $(B_l, Q_l)$ signed by $i$
 else, do nothing
 $t = 4 \Delta r + 2\Delta$:
 if node $i$ receives $\geq \frac 2 3 n$ round$r$ stage1 votes (supermajority) for block $B$,
 if this occurs, all possible QCs must all support the same block (by QC overlap property)
 assemble QC from supermajority of votes
 set $QC_i := QC_\textrm{assembed}$, $B_i := B$
 after witnessing a conclusive winner to the first stage, we broadcast second stage vote for $vote_2(B_i)$
 broadcast $(B_i, QC_i)$ signed by $i$
 else, do nothing
 if node $i$ receives $\geq \frac 2 3 n$ round$r$ stage1 votes (supermajority) for block $B$,
 $t = 4\Delta r + 3 \Delta$:
 if node $i$ receives $\geq \frac 2 3 n$ round$r$ stage2 votes for block $B$,
 set $QC_i := QC_\textrm{assembed}$, $B_i := B$
 commit $B$ to local history
 broadcast $(B_i, QC_i)$ signed by $i$
 increment $h_i$, reinitialize $B_i$ and $QC_i$ to null
 else, do nothing
 if node $i$ receives $\geq \frac 2 3 n$ round$r$ stage2 votes for block $B$,
 $t = 4 \Delta r + 4 \Delta$ (just before round $r + 1$):
 If we have heard of a stage2 QC for block $h_i$ supporting block B
 commit $B$ to local history
 else, do nothing
 If we have heard of a stage2 QC for block $h_i$ supporting block B
In the background,
 All honest nodes store all QCs received for future blocks $h_i + 1, h_i + 2, \dots$
# 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
 Fix a height $h$.
 Let $r$ be the first round in which $> \frac n 3$ honest nodes (set $S$) cast stage2 votes for some block $B^*$. $r$ is the first round in which a stage2 QC could have been created.
Induction: at the end of round $r$
 we know $B_i = B^*$, $\forall i \in S$
 current $QC_i$ is from round$r$ stage1 or later
 all QCs for other blocks are from round $r  1$ or earlier
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
 we are postGST
 there is an honest leader
 all honest nodes are working on the same block number
Proofs:
 Fast forward to pair of $r_1$, $r_2$ consecutive rounds after $GST + \Delta$ with honest leaders $l_1$, $l_2$ (this must be true for $f < \frac n 3$)
 Lemma: at the start of round $r_1$, every honest node is working on either block $h$ or $h+1$
 True because of the broadcast of a stage2 QC at the end of $t = 4\Delta (r  1) + 3 \Delta$, and all nodes should pick this up by $t = 4 \Delta r + 3 \Delta$ and be working on at least $h$
 Nodes could possibly be split between working on $h$ and $h + 1$ if a Byzantine node keeps secret a stage2 QC for $h$ and selectively forward it to honest nodes.
 Lemma: if there is a clean round, all honest nodes commit the block proposed by the leader
 By part 2 in assumption of clean round, after the update in the first phase, the leader’s QC is at least as recent as any other honest nodes.
 As we are postGST, vote request will arrive at each node for $4 \Delta r + \Delta$ where they all broadcast stage1 votes for $B_l$ and have their local variable updated.
 Nodes assemble super majority for $B_l$ and can create a QC… same argument for stage2 votes
 All nodes then commit $B_l$ to their local history

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