owned this note
owned this note
Published
Linked with GitHub
# 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<span> </span>**m**<span> </span>will eventually get delivered
* agreement
* all processes will eventually deliver<span> </span>**m**
* integrity
* **m**<span> </span>is only delivered once and only broadcasted by its sender
* Raft was developed in 2013.
* Byzantine Fault Tolerance
* The number of failures<span> </span>**f**<span> </span>that a Byzantine system can handle is<span style="box-sizing: border-box;"><span class="katex-display" style="box-sizing: border-box; display: block; margin: 1em 0px; text-align: center;"><span class="katex" style="box-sizing: border-box; font: 1.21em / 1.2 KaTeX_Main, "Times New Roman", serif; text-indent: 0px; text-rendering: auto; display: block; text-align: center; white-space: nowrap;"><span class="katex-mathml" style="box-sizing: border-box; border: 0px; clip: rect(1px, 1px, 1px, 1px); height: 1px; overflow: hidden; padding: 0px; position: absolute; width: 1px;"><math><semantics><annotation encoding="application/x-tex">2f+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true" style="box-sizing: border-box; display: block; position: relative;"><span class="base" style="box-sizing: border-box; position: relative; white-space: nowrap; width: min-content; display: inline-block;"><span class="strut" style="box-sizing: border-box; display: inline-block; height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord" style="box-sizing: border-box;">2</span><span class="mord mathdefault" style="box-sizing: border-box; font-family: KaTeX_Math; font-style: italic; margin-right: 0.10764em;">f</span><span class="mspace" style="box-sizing: border-box; display: inline-block; margin-right: 0.222222em;"></span><span class="mbin" style="box-sizing: border-box;">+</span><span class="mspace" style="box-sizing: border-box; display: inline-block; margin-right: 0.222222em;"></span></span><span class="base" style="box-sizing: border-box; position: relative; white-space: nowrap; width: min-content; display: inline-block;"><span class="strut" style="box-sizing: border-box; display: inline-block; height: 0.64444em; vertical-align: 0em;"></span><span class="mord" style="box-sizing: border-box;">1</span></span></span></span></span></span>
* 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<span> </span>**commit**
* IF validator does not receive a proposal before<span> </span>**ProposalTimeout**, that validator votes for<span> </span>**nil**
* Voting on<span> </span>**nil**<span> </span>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<span> </span>**reset**<span> </span>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