Tendermint: Byzantine Fault Tolerance in the Age of Blockchains

# Tendermint: Byzantine Fault Tolerance in the Age of Blockchains * Link:: https://atrium.lib.uoguelph.ca/xmlui/bitstream/handle/10214/9769/Buchman_Ethan_201606_MAsc.pdf * # Background * Replicated State Machine * is a deterministic distributed calculation * It is the responsibility of the consensus protocol to order the transactions so that the resulting state is replicated by every process (node) * Asynchrony * Safety * Nothing bad happens * Liveliness * Something good will eventually happen * Even tough synchronous communications works they still costs a lot to keep "in synch". Such as using atomic clocks in data centers. * Broadcast Consensus * RBC * validity * message **m** will eventually get delivered * agreement * all processes will eventually deliver **m** * integrity * **m** is only delivered once and only broadcasted by its sender * Raft was developed in 2013. * Byzantine Fault Tolerance * The number of failures **f** that a Byzantine system can handle is<math><semantics><annotation encoding="application/x-tex">2f+1</annotation></semantics></math>2f+1 * The upper bound of faulty process tolerated by Byzantine system is lower than a none byzantine one. This means less process need to fail to break the system. Increasing the number of total processes reduces this fault chance. * ![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Fsebastians_mind_map%2Fxj_ULqClGJ.png?alt=media&token=b9f301d9-11af-40d1-82a0-551284730360) * Cryptography, Trust, and Economics * "It is well known that civilizations that have greater forms of institutional trust, such as the rule-of-law, have higher productivity and more vibrant economies. This is like [[Markets are Eating the World]]. * Cryptography can form the basis of a new form of trust * Blockchain * Tendermint was the first proposal to update Byzantine Fault Tolerance algorithm from the 80s * Process Calculus * ?? * # Tendermint Consensus * Consensus is divided in * Proposals * A proposed block must be broadcasted to all processes though gossip. * Proposers are ordered through a deterministic round robin. Because of this every validator knows the correct proposer. * Liveliness is maintained through cycling of proposers, since others can pick up the dropper proposal. * Votes * There are two votes 1. pre-vote 2. pre-commit 1. pre-commits more thatn 2/3rds of majority in the same block is equal to a **commit** * IF validator does not receive a proposal before **ProposalTimeout**, that validator votes for **nil** * Voting on **nil** indicates the network that it should move to the next proposer. * "polka" is a set of more than 2/3rds of prevotes for a single block at a given round * polka * nil-polka * Pre-commit "polka" is a sign to the nextwork that is ready with the current block of the round. * Locks * Ensures that now two validators commit a different block at the same height. There is a locking mechanism in the "pre-vote" and "pre-commit" phases. * Rules: * Prevote-the-Lock * the proposer locks on to the block it will proposer. This prevents voting on different blocks on the pre-vote and on a diffrent polka of pre-commit * Unlock-on-Polka * This means that a validator is free to vote on new blocks one it has seen its propose block have a polka at a round greater than the lock round. * The core of the consensus is two messages: * ProposalMsg * A proposal for a block * VoteMsg * Blockchain * Why Blocks? * Bandwidth optimizaitons * Validators only have to check the block for all of the votes and commits * Integrity optimizations * The block hash and the previous block hash helps with integrity * Increase the minimum latency. Set a time cadence for when the votes and commits should occur. * Safety * Atomic broadcast of Tendermint: * validity * broadcast of message m eventually delivers m * agreement * if m is delivered, eventually all correct processes will deliver m * integrity * m is only delivered once and only broadcast by its sender * total order * the order of the messages is respected across all correct processes. * Accountability * Validators are held accountable * One is when they propose two blocks within a round * One is that they vote for conflicting blocks at the same height and commit phases * By collecting all votes a violaton of the Prevote-the-Lock will be seen. * Faults and Availability * clocks of validators do not to be in sync since the clocks **reset** after a validator sees a votes of a polka. * If 1/3 + 1 vlaidators go down the networks halt since 2/3rds majority cannot be reached. * # Tendermint Subprotocols * P2P Networking * Connects to all peers from an initial list of peers * Consensus Gossip * Broadcasts the node's state to all of its peers * A cheap way to gossip data is using [[Merkle Trees]] * The proof is small compared to the data size * The signed proposal includes just the merkle root hash * Mempool * Transactions are gossiped using multicast algorithm once they are validated * Syncing the Blockchain * When a node connects to a new peer the peer shares its current height * # Building Applications * Communication is done with the "Tendermint Socket Protocol (TMSP)") * Tendermint Socket Protocol (TMSP) * Applications usually have two components * Engine * handles core security, networking, replication * State-machine * "Tendermint Socket Protocol (TMSP)" * This is the interface that connects the consensus engine to the application state machine * At it is core the two important messages are * AppendTx * Commit * ![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Fsebastians_mind_map%2FcHO2j-jHZ1.png?alt=media&token=34aaa2c6-15dc-4f15-aaca-cdbbac9f9737) * The AppendTx TMSP call allows the conensus engine to proceed into the commit phase * Separating Agreement and Execution * Using the TMSP affords us an explicit separation between consensus, or agreement on the order of transactions, and their actual execution in the state-machine. In particular, we achieve consensus on the * order first * then execute the ordered transactions. * CheckTx can be used as an optimistic execution returning a result to the transaction sender with the caveat that the result may be wrong if a block is committed with a conflicting transaction before the transaction of interest is committed * Microservice Architecture * Applications running ontop of "Tendermint Socket Protocol (TMSP)" will propably use microservices. * "In fact, one might even build an application which can launch sub-applications using data sent in transactions. For instance, including the hash of a docker image in a transaction, such that the image could be pulled from some file-storage backend and run as a sub-application where future transactions in the consensus could cause it to execute." * Determinism * All ABCI applications must be deterministic. * That is, every node must reach the same result * Using functional programming languages can help * Using proof methods also helps * Termination * The application must stop executing. * Examples of ABCIs * Merkleyes * Basecoin * Ethereum * # Governance * Governmint * Allows for upgrading of validators sets * Uses "Quadratic Voting" * Quadratic Voting * Validator Set Changes * Voting power of a validator gets forced to Zero * If the block at height H returns an updated validator set, then the block at height H + 1 will reflect the update. * Punishing Byzantine Validators * Basically slashing * Software Upgrades * Crisis Recovery * Tendermint assures that the misbehaving validators can be identified * Since 1/3 or more validators violated a lock rule, the network cannot commit for the next block. * # Client Considerations * Discovery * The genesis will always have to be out of band * Another tendermint protocol could bootstrap the genesis of a new network * Broadcasting Transactions * Clients just proxy to validator nodes until the transaction gets added to a block * ## Mempool * # Implementation * Crypography * RIPEMD160 is the hashing algorithm * Schorr signatures for signing instead of ED25519