H) is composed of one or many rounds.
Commitrepresent state machine states of a round. (aka
RoundStepor just “step”).
(H,R,S), or at
(H,R)in short to omit the step.
(H,R)is a vote signed with the bytes for
Rincluded in its sign-bytes.
(H,R)is called a proof-of-lock-change or PoLC for short.
At each height of the blockchain a round-based protocol is run to
determine the next block. Each round is composed of three steps
Precommit), along with two special steps
In the optimal scenario, the order of steps is:
NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...
(Propose -> Prevote -> Precommit) is called a round.
There may be more than one round required to commit a block at a given
height. Examples for why more rounds may be required include:
Precommitstep. Even though +2/3 of prevotes are necessary to progress to the next step, at least one validator may have voted
<nil>or maliciously voted for something else.
Some of these problems are resolved by moving onto the next round & proposer. Others are resolved by increasing certain round timeout parameters over each successive round.
+-------------------------------------+ v |(Wait til `CommmitTime+timeoutCommit`) +-----------+ +-----+-----+ +----------> | Propose +--------------+ | NewHeight | | +-----------+ | +-----------+ | | ^ |(Else, after timeoutPrecommit) v | +-----+-----+ +-----------+ | | Precommit | <------------------------+ Prevote | | +-----+-----+ +-----------+ | |(When +2/3 Precommits for block found) | v | +--------------------------------------------------------------------+ | Commit | | | | * Set CommitTime = now; | | * Wait for block, then stage/save/commit block; | +--------------------------------------------------------------------+
A node may not have a corresponding validator private key, but it nevertheless plays an active role in the consensus process by relaying relevant meta-data, proposals, blocks, and votes to its peers. A node that has the private keys of an active validator and is engaged in signing votes is called a validator-node. All nodes (not just validator-nodes) have an associated state (the current height, round, and step) and work to make progress.
Between two nodes there exists a
Connection, and multiplexed on top of
this connection are fairly throttled
Channels of information. An
epidemic gossip protocol is implemented among some of these channels to
bring peers up to speed on the most recent state of consensus. For
PartSetparts of the current round’s proposer’s proposed block. A LibSwift inspired algorithm is used to quickly broadcast blocks across the gossip network.
NODE_Athat is ahead of
NODE_Bprevotes or precommits for
NODE_B’s current (or future) round to enable it to progress forward.
ReceivedVotemessages to hint peers what votes it already has.
There’s more, but let’s not get ahead of ourselves here.
A proposal is signed and published by the designated proposer at each round. The proposer is chosen by a deterministic and non-choking round robin selection algorithm that selects proposers in proportion to their voting power (see implementation).
A proposal at
(H,R) is composed of a block and an optional latest
PoLC-Round < R which is included iff the proposer knows of one. This
hints the network to allow nodes to unlock (when safe) to ensure the
Propose step ends:
Propose. –> goto
PoLC-Round. –> goto
Prevote, each validator broadcasts its prevote vote.
LastLockRoundbut now has a PoLC for something else at round
LastLockRound < PoLC-Round < R, then it unlocks.
Propose(H,R)is good, it prevotes that.
Prevote step ends:
<nil>. –>; goto
timeoutPrevoteafter receiving any +2/3 prevotes. –> goto
Precommit, each validator broadcasts its precommit vote.
(H,R)for a particular block
B, it (re)locks (or changes lock to) and precommits
LastLockRound = R.
<nil>, it unlocks and precommits
A precommit for
<nil> means “I didn’t see a PoLC for this round, but I
did get +2/3 prevotes and waited a bit”.
The Precommit step ends:
<nil>. –> goto
timeoutPrecommitafter receiving any +2/3 precommits. –> goto
(H,R+x). –> goto
(H,R+x). –> goto
CommitTime = now()
LastCommitand increment height.
StartTime = CommitTime+timeoutCommit
StartTimeto receive straggler commits. –> goto
Assume that at most -1/3 of the voting power of validators is byzantine.
If a validator commits block
B at round
R, it’s because it saw +2/3
of precommits at round
R. This implies that 1/3+ of honest nodes are
still locked at round
R' > R. These locked validators will remain
locked until they see a PoLC at
R' > R, but this won’t happen because
1/3+ are locked and honest, so at most -2/3 are available to vote for
anything other than
If 1/3+ honest validators are locked on two different blocks from
different rounds, a proposers’
PoLC-Round will eventually cause nodes
locked from the earlier round to unlock. Eventually, the designated
proposer will be one that is aware of a PoLC at the later round. Also,
timeoutProposalR increments with round
R, while the size of a
proposal are capped, so eventually the network is able to “fully gossip”
the whole proposal (e.g. the block & PoLC).
Define the JSet (justification-vote-set) at height
H of a validator
V1 to be all the votes signed by the validator at
H along with
justification PoLC prevotes for each lock change. For example, if
signed the following precommits:
Precommit(B1 @ round 0),
Precommit(<nil> @ round 1),
Precommit(B2 @ round 4) (note that no
precommits were signed for rounds 2 and 3, and that’s ok),
Precommit(B1 @ round 0) must be justified by a PoLC at round 0, and
Precommit(B2 @ round 4) must be justified by a PoLC at round 4; but
the precommit for
<nil> at round 1 is not a lock-change by definition
so the JSet for
V1 need not include any prevotes at round 1, 2, or 3
V1 happened to have prevoted for those rounds).
Further, define the JSet at height
H of a set of validators
be the union of the JSets for each validator in
VSet. For a given
commit by honest validators at round
R for block
B we can construct
a JSet to justify the commit for
R. We say that a JSet
justifies a commit at
(H,R) if all the committers (validators in the
commit-set) are each justified in the JSet with no duplicitous vote
signatures (by the committers).
As a corollary, when there is a fork, an external process can determine the blame by requiring each validator to justify all of its round votes. Either we will find 1/3+ who cannot justify at least one of their votes, and/or, we will find 1/3+ who had double-signed.
Alternatively, we can take the JSet of a commit to be the “full commit”. That is, if light clients and validators do not consider a block to be committed unless the JSet of the commit is also known, then we get the desirable property that if there ever is a fork (e.g. there are two conflicting “full commits”), then 1/3+ of the validators are immediately punishable for double-signing.
There are many ways to ensure that the gossip network efficiently share the JSet of a commit. One solution is to add a new message type that tells peers that this node has (or does not have) a +2/3 majority for B (or) at (H,R), and a bitarray of which votes contributed towards that majority. Peers can react by responding with appropriate votes.
We will implement such an algorithm for the next iteration of the consensus protocol.
Other potential improvements include adding more data in votes such as the last known PoLC round that caused a lock change, and the last voted round/step (or, we may require that validators not skip any votes). This may make JSet verification/gossip logic easier to implement.
Due to the definition of a block commit, any 1/3+ coalition of validators can halt the blockchain by not broadcasting their votes. Such a coalition can also censor particular transactions by rejecting blocks that include these transactions, though this would result in a significant proportion of block proposals to be rejected, which would slow down the rate of block commits of the blockchain, reducing its utility and value. The malicious coalition might also broadcast votes in a trickle so as to grind blockchain block commits to a near halt, or engage in any combination of these attacks.
If a global active adversary were also involved, it can partition the network in such a way that it may appear that the wrong subset of validators were responsible for the slowdown. This is not just a limitation of Tendermint, but rather a limitation of all consensus protocols whose network is potentially controlled by an active adversary.
For these types of attacks, a subset of the validators through external means should coordinate to sign a reorg-proposal that chooses a fork (and any evidence thereof) and the initial subset of validators with their signatures. Validators who sign such a reorg-proposal forego its collateral on all other forks. Clients should verify the signatures on the reorg-proposal, verify any evidence, and make a judgement or prompt the end-user for a decision. For example, a phone wallet app may prompt the user with a security warning, while a refrigerator may accept any reorg-proposal signed by +1/2 of the original validators.
No non-synchronous Byzantine fault-tolerant algorithm can come to consensus when 1/3+ of validators are dishonest, yet a fork assumes that 1/3+ of validators have already been dishonest by double-signing or lock-changing without justification. So, signing the reorg-proposal is a coordination problem that cannot be solved by any non-synchronous protocol (i.e. automatically, and without making assumptions about the reliability of the underlying network). It must be provided by means external to the weakly-synchronous Tendermint consensus algorithm. For now, we leave the problem of reorg-proposal coordination to human coordination via internet media. Validators must take care to ensure that there are no significant network partitions, to avoid situations where two conflicting reorg-proposals are signed.
Assuming that the external coordination medium and protocol is robust, it follows that forks are less of a concern than censorship attacks.
We distinguish between “canonical” and “subjective” commits. A subjective commit is what
each validator sees locally when they decide to commit a block. The canonical commit is
what is included by the proposer of the next block in the
LastCommit field of
the block. This is what makes it canonical and ensures every validator agrees on the canonical commit,
even if it is different from the +2/3 votes a validator has seen, which caused the validator to
commit the respective block. Each block contains a canonical +2/3 commit for the previous