Byzantine Fault Tolerance in the Age of Blockchain: Tendermint

Tendermint: Byzantine Fault Tolerance in the Age of Blockchains

Ethan Buchman

Translation: Rao Yunkun

Proofreading: Fu Xiaobo

This is an excerpt

This chapter describes the Tendermint consensus algorithm and related blockchains for Atomic Broadcast. The Byzantine fault-tolerant consensus problem will be discussed in detail, and a formal illustration of the Tendermint consensus will be given in pi-calculus form. The Tendermint blockchain has been unofficially proven to satisfy atomic broadcasting. In the future, we will describe the full blockchain protocol in terms of process evolution and demonstrate the related characteristics.

Tendermint is a secure state machine replication algorithm in the blockchain paradigm. Its algorithm form is BFT-ABC, and the additional responsibility system, easy to verify the dishonest behavior of Byzantine nodes.

The Tendermint algorithm assigns an incremental index or height to each block. At a certain height, only one valid block exists. The blockchain starts from the Genesis block with a height of 0, and a set of verifier votes to generate the next block, each of which is identified by its own public key. Each verifier needs to maintain a complete copy of the replication state. In the process of voting to produce a block of a certain height, at least one round of voting is required before a block of a certain height can be committed. Each round produces a proposer using a round robin method that broadcasts a proposal in each round to a group vote of the proposers to decide whether to submit the block or move on to the next round. Before the proposed block is actually committed, verifiers need two rounds of pre-vote & pre-commit to prevent less than 1/3 of the Byzantine nodes from attacking through a simple locking mechanism. Due to the Asynchrony nature of the Tendermint network, when Byzantine nodes exceed 1/3 of the total number, the network may crash.

Note that the core of tendermint’s multi-round voting mechanism is consensus algorithms. Each block contains some metadata, called headers. The block header contains the height of the block, the proposed time, and the Mekelgen hashes of all transactions in the block.

Consensus algorithm can be roughly divided into the following parts:

• Proposals: In each round, the proposers of new blocks must be valid and tell other verifiers gossiped. If no proposal is received within a certain period of time, the current proposer will be replaced by the subsequent proposer.

Votes: Two-stage voting is based on optimized Byzantine fault tolerance. These are called pre-vote and pre-commit, respectively. If there are more than 2/3 pre-commits for the same block in the same round, a commit will be generated. • Locks: In cases where the Number of Byzantine nodes is less than 1/3 of the total number of nodes, the locking mechanism in Tendermint ensures that no two verifiers commit two different blocks at the same height. The locking mechanism ensures that the next round of pre-vote or pre-commit of the verifier at the current height depends on the next round of pre-vote or pre-commit.

To deal with a single Byzantine failure node, the Tendermint network needs to include at least four verifiers. Each verifier has a pair of asymmetric keys, where the private key is used for digital signature and the public key is used to identify its identity ID. Verifiers start with a common initial state, which contains a list of verifiers. All proposals and votes require their own private key signatures to facilitate public key verification by other verifiers.

(After initiating the proposal step, the verifier will proceed with the process if and only if it receives more than two-thirds (+2/3) votes from other verifiers. Dashed arrows indicate atomic broadcasts into the next block highly consensus process.

Consensus begins in round 0, when the first proposer is the first in the list of validators at the head of the blockchain. Each round eventually either completes a commit or goes straight to the next round at the current height, and each round produces a new proposer.

Unlike other leader election algorithms, Tendermint produces a new proposer each round, with the verifier voting on whether to advance to the next round, similar to the process of accepting proposals.

The start of each round is weakly dependent on synchronization. At the start of each round, there is a local synchronization clock for timing, and if the verifier does not receive a proposal within the timeoutVeto time, the verifier will participate in a vote to decide whether to skip the current committer. Timeoutwithdraw increases as the number of rounds increases.

After receiving the proposal each round, it enters full asynchronous mode. Each subsequent network decision of the verifier requires the approval of at least two-thirds of the verifier. This reduces the reliance on synchronous clocks or network latency. But this also means that if more than a third of the verifiers do not respond, the entire network will crash.

In short, each round starts with a weakly synchronized proposal and then the vote is completely asynchronous.

In order to enhance the security of Tendermint consensus network, a small number of locking rules were introduced to force verifier to prove the legitimacy of their vote. While we don’t need to broadcast their credentials in real time, we do expect verifiers to save their data. This allows the network to remain as evidence in the event of a Byzantine failure. This accountability mechanism ensures that the Tendermint has a more robust guarantee in the event of network failures, such as PBFT.

The verifier uses a different set of messages to manage blockchain, application state, P2P networks, and consensus. Among them, the core consensus algorithm contains two types of messages:

ProposalMsg: A proposal for blocks of a certain height and number of rounds signed by the proposer

VoteMsg: A signature vote on a proposal

Each round begins with a proposal, in which the proposer selects a number of transactions from the Mempool to form a block, which is then nested in a ProposalMsg, and finally the proposer broadcasts a ProposalMsg. If the proposer is a Byzantine node, it may broadcast a different ProposalMsg to a different verifier.

Proposers take turns through a simple and relatively fixed Roubd Robin, so there is only one valid proposer for each round that is accepted by all verifiers. If the verifier received a previous offer of a lower round or if the offer came from an illegal proposer, the offer will be rejected.

The rotation of the proposer was necessary for Byzantine fault tolerance. For example, for RAFT algorithm, if the leader elected is Byzantine and the network connection is good with other nodes, the leader can completely control the entire network, and the safety and normal operation of network nodes cannot be guaranteed. The Tendermint ensures system security through voting and locking mechanisms. If a proposer does not process any transactions within the time limit, the next proposer will take over. Even more interesting is the fact that the verifier can be removed or replaced by the vote of the governance module.

Once the verifier receives a complete proposal from the network, he signs the proposal pre-vote and broadcasts it to the network. If the verifier does not receive a valid proposal within a ProposalTimeout, its pre-vote on that proposal is nil.

In an asynchronous environment with Byzantine nodes, single-stage voting, where each verifier votes once for each proposal, is not sufficient to ensure the security of the entire system. In essence, because the verifier may do something dishonest and the arrival time of the message is not guaranteed, a dishonest verifier can collaborate with other verifiers to commit a block, while other verifiers who do not see the submitted block move on to a new round. And commit a different block.

A single-stage vote allows verifiers to communicate with each other what they know about the proposal. But in order to tolerate Byzantine glitches, they also need to tell each other what they know about the submission that other verifiers claim to know. In other words, a two-phase commit ensures that enough verifiers have witnessed the results of the first phase.

A non-empty pre-vote for a block is a vote that is ready for a network Commit block. Empty pre-voting is for the network to proceed directly to the next round of voting. In an ideal round, more than two-thirds of verifiers pre-voted for the proposal. In any round, a block with more than two-thirds of the pre-votes is called a polka. More than two-thirds of empty pre-votes became nil-polkas.

When a verifier receives a polka, he receives a signal that the network is ready to commit the block, sign as a verifier and broadcast a pre-commit endorsement. Sometimes, due to network heterogeneity, the verifier may not receive the corresponding polka or the polka may not exist at all. In this case, the verifier has no corresponding polk to endorse for this pre-submission, and the pre-submission is empty. That is, signing a pre-submission without receiving a polk endorsement is considered a bad faith act.

Pre-commit is a vote to commit a block. Empty pre-submission votes to proceed to the next round. If the verifier receives more than 2/3 of the pre-commits from the verifier, it commits the block locally, calculates the resulting status, and moves to round 0 of the next height. If the verifier receives more than 2/3 empty pre-submissions, the vote goes to the next round.

The security of multi-round voting is tricky, and it is necessary to avoid the situation of submitting two different blocks with different rounds at the same height. In the Tendermint, this problem can be solved by the locking mechanism. The lock mechanism is roughly located near polk. In essence, a pre-commit must have a polka to endorse it, and the verifier is locked to its most recent pre-commit block.

Locking rules:

· Prevote-the-lock: Verifiers can only pre-vote the block they are locked in. This prevents the verifier from pre-committing one block in the previous round and then pre-voting another block in the next round.

· Unlock on-polka: The verifier can release the lock only after seeing a higher round of Polka relative to the number of rounds it is currently locked. This allows verifiers to unlock if they pre-commit a block but the rest of the block network does not want to commit, thus protecting the entire network without compromising network security.

In simple terms, verifiers can be seen as locked on nil-blocks of any height -1 round, so polka unlock means that verifiers cannot pre-commit a block of a new height until they see a polka.

These rules can be understood more intuitively in the form of examples. Consider four verifiers, A,B,C, and D, and assume A round R proposal for blockX. Now assume that blockX already has A polka, but A can’t see it, and the pre-commit is empty, whereas someone else pre-commits to blockX. Suppose further that only D sees all the pre-commits, whereas the others do not see D’s pre-commits (they only see their pre-commits and A’s empty pre-commits). D will now commit the block, while the others enter the R+1 round. Since any verifier can be a new proposer, if they propose and vote for a new block blockY, they may submit the block. However, D has submitted bockX, so the security of the system is damaged. Notice, there’s no Byzantine behavior here, just nonsimultaneity.

Locking solves this problem by forcing verifiers to stick to their pre-commit block, since other verifiers may have committed on that block (D in the example above). In essence, once there are more than 2/3 pre-commits at any one node, the entire network is locked to that block, meaning that the next round cannot produce a different block of polka. This is the immediate motivation for pre-voting locks.

Of course, there must be a corresponding unlock method. Suppose that in one round, A and B pre-commit blockX, while C and D pre-commit is empty. So all verifiers move on to the next pre-vote blockY. Assuming A is Byzantium, there is also A pre-vote for blockY (regardless of its being locked to blockX), resulting in A polka. Suppose B doesn’t see the polka, the pre-commit is empty, and A goes offline, C and D pre-commit bolckY. They move on to the next round, but B is still locked in blockX and C and D are locked in blockY. Because A is offline, they will never get A polka. So even with less than a third of the Nodes in Byzantium, the normal functioning of the network here is affected.

The condition for unlocking is 1 polka. Once B sees blockY’s polk (used to endorse C and D’s pre-submission of blockY), he should be able to unlock and pre-commit blockY. This is the motivation for polka unlocking, which allows verifiers to unlock and commit new blocks when they see higher rounds of polka.

Tendermint processes transactions in batches or blocks. The blocks are linked together into a complete blockchain by encrypting the ha-ha algorithm. Blockchain consists of sequenced transaction logs and relevant evidence submitted by verifiers.

The consensus algorithm submits several transactions at a time. As mentioned in chapter 2. Looking at this from a batched atomic broadcast perspective, there are two major optimizations that give us more throughput and fault tolerance:

· Bandwidth optimization: Because each commit requires two rounds of communication between verifiers, batch processing of block by block transactions, amortises the cost of the commit over all transactions in the block.

· Integrity optimization: The block hash chain forms an immutable data structure, much like a Git repository, with the ability to check sub-state authentication at any point in history.

Blocks also cause another effect, seemingly more subtle but perhaps more important. They increase the minimum latency for individual transactions to the minimum latency for blocks, on the order of hundreds of milliseconds to seconds for Tendermint. Traditional serialization database systems provide commit delays on the order of milliseconds to hundreds of milliseconds. Their low latency is due to the fact that these databases are not Byzantine fault tolerant, requiring only one round of communication instead of two and a response from half of the nodes instead of two-thirds. However, unlike other election algorithms with fast commit times, Tendermint offers a more conventional pulse that is more responsive to the state of the entire network in terms of node failures and network differences.

The role of pulses in the consistency of communication autonomous systems is unclear, but the resulting delays are promising in financial markets.

The purpose of a block is to package a batch of transactions and link to a previous block. Links take two forms: a hash of the previous block and a pre-committed collection of previous blocks, also known as LastCommit. So a block consists of three parts: the block header, the transaction list, and Lastcommit.

Here we briefly prove that the Tendermint meets the requirements of atomic radio. Atomic broadcasting is defined as satisfying the following conditions:

· Validity – If a correct process broadcasts M, it eventually succeeds in communicating M

· Agreement — If one correct process successfully delivers M, all processes eventually deliver M successfully

· Integrity -M is transmitted only once and is broadcast by the sender

· Total order – if the correct processes P and Q pass m and m’ respectively, p pass M before M ‘, then Q pass M before M ‘

Note that Tendermint does not satisfy validity if m is considered a block, as there is no guarantee that the proposed block will most likely be submitted, as the verifier may enter a new round and submit a different block.

If we think of M as a batch of transactions in a block, then we can satisfy the validity by having the verifier repropose the same batch of transactions until the transaction is finally submitted.

To satisfy the first part of completeness, we must introduce additional rules to prohibit a legitimate verifier from proposing or pre-submitting a block containing transactions that have already been submitted. Fortunately, transactions can be indexed by Meckelgen, and relevant lookups can be performed to filter out submitted transactions before they are proposed and pre-submitted.

Alternatively, we can think of m as a transaction that satisfies validity by introducing a persistent property of the memory pool, that is, the transaction can remain in the memory pool until it is committed. To satisfy the first part of completeness, however, we must rely on application State to set some rules for transactions, such that a given transaction can only take place once. For example, it could be through an account-based serial number, as in Ethereum. Or keep a list of unused resources, each of which can only be used once, as in Bitcoin. Since there are multiple approaches, the Tendermint itself doesn’t guarantee that messages are delivered only once, but allows app developers to specify features. The second part of completeness is obvious, because only transactions in the block proposed by the correct proposer can be submitted.

To prove that Tendermint satisfies “total order”, we introduce a new feature, State Machine Safety, and can prove that a protocol that satisfies state machine security must satisfy “consistency” and “total order”. State machine security means that if one correct verifier submits a block at height H, no other verifier submits a different block at the same height. Considering that all messages are eventually received, this immediately implies consistency, because if one correct verifier submits a block B at height H, containing the transaction M, all other correct verifiers cannot submit other blocks, thus ultimately submitting block B, conveying the message M.

Now, we need to prove that the state machine is safe enough to meet the “total order” and Tendermint is safe enough to meet the state machine. To prove the former, consider two messages M and m’ sent by the verifier P and Q, respectively. State machine security ensures that P sends a message m at height Hm if and only if Q sends a message M at height Hm, and P sends a message m’ at height Hm’ if and only if Q sends a message m’ at height Hm’. Without loss of generality, because height is strictly increasing, let’s say Hm<Hm’. So we have p sending a message m before M prime if and only if Q sending a message m before m prime, that’s exactly the definition of total order.

Finally, to prove that Tendermint satisfies state machine security when the Byzantine nodes are less than 1/3, we use contradiction. Suppose the Tendermint does not satisfy state machine security, allowing multiple blocks to be submitted at a certain height. So we can show that we need at least 1/3 of the Byzantine nodes, contrary to our hypothesis.

Consider a valid verifier submitting a block B at height H and number of rounds R. Submitting a block means that the verifier received more than two-thirds of the pre-submissions for block B in round R. Suppose another block C is committed at height H. We have two options: either submit in round R or submit in round S (S>R).

If block C is submitted in Round R, then more than 2/3 of the verifiers must pre-submit for the block, which means that at least 1/3 of the verifiers pre-submitted for both block B and C in round R, then clearly these simultaneous nodes are Byzantine nodes. Assume that block C is submitted in round S. Since more than 2/3 have pre-submitted for Block B, they will also be locked into block B in round S, so they must pre-vote on block B. In order to pre-submit to block C, they must receive a polk on block C and therefore require more than 2/3 pre-votes on block C. However, more than two-thirds of the verifiers have been locked in block B. In order for a node to receive a polka of block C, at least 1/3 of the verifiers in the network must violate the lock mechanism, and these nodes are clearly Byzantine nodes. Therefore, in order to breach state machine security, at least 1/3 Byzantine verifier is required. If fewer than a third of the Byzantine nodes are in the network, Tendermint meets state machine security.

To sum up, Tendermint meets atomic radio.

In future work, we will provide more formal certification of the Tendermint’s security.

A Byzantine fault-tolerant algorithm with accountability identifies all Byzantine verifiers in the event of a security breach. The traditional Byzantine fault-tolerant algorithm does not correspond to this feature, nor does it have any corresponding guarantee. Of course, accountability can only apply in the case of 1/3 to 2/3 of the Byzantine nodes. If more than two-thirds of the nodes are Byzantine, they can fully occupy the protocol, at which point there is no guarantee that a legitimate verifier can receive any evidence of Byzantine node illegality.

Further, accountability is the ultimate best effort in an asynchronous network environment where security issues and delays in critical messages make it possible to discover Byzantine verifiers after security issues have been detected. In fact, if correct processes could accept evidence of Byzantine behavior, but irreversibly failed before they could communicate (irreversibly), May cause permanent failure of accountability, although in practice this can be overcome by an advanced backup strategy.

Byzantine verifiers can be identified by enumerating the various vulnerabilities of security issues, so that protocols are accountable. The Tendermint’s brevity gives it a simpler approach to analysis than other campaign-related deals.

There are two types of security breaches at Tendermint, each of which is accountable. In the first, the Byzantine proposer produces two conflicting proposals in a single round, and the Byzantine verifier votes on both proposals simultaneously. Second, after some verifiers commit in a single round, Byzantine verifiers violate locking rules, causing other verifiers to commit a different block in subsequent rounds. Note that if less than two-thirds of the Byzantine verifiers are present, security issues cannot be raised by violating the unlock mechanism alone, and that more than one-third of the nodes must violate the polka lock mechanism, since each submission (comMOT) requires a polka endorsement.

These Byzantine nodes can be identified by the signatures of conflicting proposals or votes that are accepted simultaneously in the presence of conflicting proposals or votes.

In the case of a violation of locking rules, with corresponding security issues, a valid verifier must broadcast all votes seen at the current height so that evidence can be collected. Less than two-thirds of the correct verifiers were collectively hidden in all votes that resulted in both blocks being submitted at the same time. In these votes, if there are no 1/3 or more votes with conflicting verifiers signatures, then 1/3 or more verifiers violate the locking mechanism.

If a pre-vote or pre-commit affects a commit, it must be seen by a legitimate verifier. Thus, by collecting all votes, and by matching every pre-vote with the most recent pre-submission, it is possible to detect violations of prevotethe-lock.

Similarly, violations of Unlock on-polka can be detected by matching pre-commits with polkas that endorsed them. Note that this means that if the Byzantine verifier can pre-commit before seeing polka, and if the corresponding polka eventually occurs, the Byzantine verifier will escape liability. However, these safety concerns would not exist if every pre-submission had a polka endorsement.

The current design provides accountability, along with the Post-crisis Broadcast Protocol, but it can be used to improve accountability in real time. That is, once the submission is changed, the corresponding pre-submission, the pre-cast endorsing the pre-submission, will change, all the way back to the Genesis block. In this way, votes without endorsements can be detected immediately if a security problem occurs.

As a Byzantine consensus fault tolerant algorithm, Tendermint can tolerate Byzantine failure nodes up to (but not up to) 1/3 of the total number of nodes. This means that nodes may crash, send different and conflicting messages to different nodes, reject relay messages, or behave abnormally, or have security or operational problems.

There are two places in the protocol where we can optimize for non-simultaneity by using the time-out feature of the local clock: after receiving 2/3 or more pre-votes (not for single blocks or nil) and after receiving 2/3 or more pre-commits (not for single blocks or nil). In each case, we can sleep for a period of time to give the delayed vote a chance to be accepted, thus reducing the likelihood that the block will not be submitted in a new round. Clocks do not need to be synchronized between verifiers because verifiers reset their time when two-thirds or more votes are observed.

If one-third or more of the verifiers crash, the network crashes, since any consensus progress requires more than two-thirds of the verifiers’ votes. The network can still read the data, but no new blocks are committed. As soon as the verifier comes back online, they can pick up where they left off. The consensus state machine should be configured with a write-ahead log so that the verifier coming back online can quickly fall back to where the machine crashed to make sure no rules were violated.

If one-third or more of the verifiers are Byzantine, they can compromise the security of the system in a number of ways. For example, commit two blocks in the same round and vote to commit both blocks or commit two different blocks in different rounds at the same height by violating the locking mechanism. In each case, there is clear evidence of which validators are Byzantine nodes. In the first example, they signed two different proposals in the same round, breaking the rules. In the second example, they locked in round R-1 and committed a different block in round R, violating the locking mechanism.

These additional accountability guarantees are decisive when economic and governance components are used to incentivize and manage consensus.

Tendermint itself is a weakly synchronous, Byzantine fault tolerant, state machine replication protocol that boasts optimized Byzantine fault tolerance and additional accountability to guarantee situations when the Byzantine fault tolerance assumptions are exceeded. The protocol uses the round Robin proposer generation method and skips a proposer using the same mechanism. Security between multiple rounds of voting is guaranteed by a locking mechanism.

This chapter is a description of the protocol, with many important details that need further discussion, such as efficient gossip ping of blocks, cached transactions, changes to the verifier set, and interfaces to apply logic. These important topics will be further explained in subsequent chapters.