Avalanche Consensus, The Biggest Breakthrough since Nakamoto
Consensus is the means by which a series of independent voters (often called “validators”) come to an agreement on a decision, ensuring that the network has a synchronized view on the data, referred to as “state”. Without consensus there is no way to ensure that the state one validator believes is true will be shared by the other nodes.
Proof-of-Work and Proof-of-Stake are commonly mistaken as consensus protocols. They are not consensus protocols but instead sybil control mechanisms. PoS doesn’t achieve consensus by itself. It has to be coupled with a protocol, such as PBFT, Tendermint/Cosmos, or Avalanche, to make decisions. PoW, by itself, isn’t a consensus mechanism. In BTC/BCH, it works with the heaviest/”longest” chain selection rule to achieve consensus.
Over the 45-year history of distributed systems, there have been only three approaches to the consensus problem: Classical, Nakamoto, and Avalanche.
Classical consensus protocols
Classical consensus protocols, such as Practical Byzantine Fault Tolerance (PBFT), HotStuff and Tendermint/Cosmos, are based on all-to-all voting and this mechanism has been used since the 1980s. They typically have a designated leader who initiates the decision process and a series of rounds of all-to-all communication to ensure that all correct nodes reach the same decisions with absolute certainty. Transactions finalize immediately after a node has received responses from the requisite fraction of the nodes that comprise the system.
They typically require quadratic communication overhead with all-to-all communication of O(n²) (with 10 nodes each round requires 100 messages, with 100 nodes each round requires 10,000 messages and with 2000 validators each round requires 4,000,000 messages). In the event that the leader fails the communication overhead increases further to O(n³ ) as a view change is needed. In addition, they need accurate knowledge of membership of all participating nodes in consensus, any errors in maintaining membership in the system, or any difference in the views of the network can lead to safety violations. If an attacker gains control of 1/3 +1 of the network, they can launch a double-spend attack which is guaranteed to succeed.
The most scalable Classical protocol, HotStuff used by Facebooks Libra (which was designed by Ted Yin, who is now working on the Avalanche protocol) only supports approximately 100 validators before the performance begins to suffer. Whilst other projects using classical consensus protocols claim to scale to thousands of nodes, they are selecting only a small random selection of nodes to perform consensus for each block, whilst the other nodes are not participating in consensus. The cost of violating safety in such a system is only as low as the cost of corrupting any subcommittee, which may be very low.
Due to limitations in the scalability of number of participants and being more fragile where accurate membership needs to be maintained they are not suitable for large, open and permissionless networks where nodes may join and leave at-will.
Nakamoto consensus protocols
The first breakthrough in consensus protocols was with the Nakamoto consensus protocols and have become popular with the rise of Bitcoin. This does away with the requirement for all-to-all communication and as such is a natural fit for open, permissionless settings where any node can join the system at any time. Unlike classical consensus protocols they provide a probabilistic rather than deterministic safety guarantee. A protocol parameter allows this probability of a double spend to be rendered arbitrarily small, enabling high value financial systems to be constructed on this foundation.
Yet, these protocols are costly, wasteful, and limited in performance. It requires useless calculations that use vast amounts of energy; an analysis by the International Energy Agency estimates that cryptocurrency mining uses at least as much energy as the entire nation of Ireland. As a result, Nakamoto-based systems constantly leak value out of their ecosystems to power companies. To maintain the security of proof-of-work systems, the miners can never be switched off, thus ensuring that this eye-watering energy consumption never ends. Mining a block is difficult by design, so Nakamoto protocols finalize transactions very slowly — it takes an hour for a Bitcoin transaction to become final, and this low latency will not improve even as technology does.
Avalanche Consensus protocols
“Only three times in the 45-year-old history of distributed systems have we had a new family emerge. Avalanche is a brand-new family, as big of a breakthrough as Satoshi’s protocol was; it combines the best of Satoshi with the best of classical in scales like no other that allow anyone to integrate themselves into the consensus layer.” — Emin Gün Sirer
Avalanche Consensus protocols was the next big breakthrough in consensus protocols, combining the benefits of Nakamoto consensus (robustness, scale, decentralization) and all the benefits of Classical consensus (speed, quick finality, and energy efficiency). In 2018, a paper was distributed by a pseudonymous group named Team Rocket that proved that Classical protocols can be generalized to behave probabilistically and gain massive performance improvements as a result.
Just as Nakamoto traded off a small chance in probability for performance, Avalanche is also probabilistic and can make the error so small that it is even less likely that a safety violation will occur on an Avalanche node than the odds of finding a SHA-256 hash collision. To put this in greater perspective, it’s dozens of orders of magnitude more likely that a life-ending asteroid will collide with the Earth in the next hundred years than a SHA-256 collision is detected in the next thousand years by a network computing 1 quintillion hashes a second.
Avalanche protocols are also lightweight and sustainable. Unlike Nakamoto protocols, they use very little energy, and when there is no work to do, the system quiesces (waits in a low-energy-consumption state.) It truly is a game changer, enabling fast tps whilst importantly having low latency. The number of messages each node has to handle per decision is O(k) and does not grow as the network scales up so can scale to millions of validators all participating in consensus to achieve truly global scale decentralisation for permissionless blockchain to take blockchain mass adoption.
Protocols in the Avalanche family are very fast. They can achieve irreversible finality in sub 2 seconds (with most happening sub 1 second), quicker than a typical credit card transaction. They support many thousands of transactions per second, in excess of Visa’s typical throughput of 4500 TPS. These also aren’t the usual made up marketing figures that you see from many projects where they are tested on a handful of nodes in a single datacenter. These are taken directly from a real, fully implemented Avalanche network running on 2000 nodes, geo-distributed across the globe on low-end machines. Higher performance results (10,000+) can be achieved through assuming higher bandwidth provisioning for each node and dedicated hardware for signature verification. These are also metrics are at the base-layer. Layer-2 scaling solutions immediately augment these results considerably.
How does it work?
In a given round each validator randomly selects K nodes from the entire validator list (probability of selection is weighted by stake amount) to query for their preferred decision. Each queried validator responds with their preferred decisions, and if the majority of responses returned in a round differ to the node performing the query then it will update its own preferred decision to reflect that and respond to other nodes with that answer.
For ease of demonstration purposes the diagram below shows a validator set of 64 nodes, where nodes have to decide between the colour Blue or Yellow. The number of nodes randomly selected to query, represented as K is 5. We will initially just focus on the node in the very top left which is currently showing yellow as its preferred decision. It will then select 5 random nodes from the entire validator set (probability of selection is weighted by stake amount) to query for their preferred decision (the nodes selected have been highlighted in Red).
Here you can see 3 nodes have returned the answer Blue, whereas 2 nodes have returned the answer yellow, thus Blue is the majority and the top left node which perform the query updates its preferred decision to Blue.
Still only focusing on the top left node, the next round it will query another 5 randomly selected nodes for their preferred decision, in this case there are 4 Blue and 1 Yellow, thus it keeps its own preferred decision as Blue.
The important thing to realise is whilst we have just been focusing on the top left node, every single node is performing this same process, randomly selecting their own 5 nodes to query each round. There is no waiting in turns between nodes to query, they all perform the task independently. As can be seen below with just looking at 4 nodes each with their own selected nodes highlighted in Red, Black, Green, Purple you can quickly see when this scales to thousands that all participants are able to participate in consensus, yet the same load is placed on any single node regardless of the total number of participants.
By having every validator randomly select other validators in order to ask them what their preferences are, participants in Avalanche build confidence in the correct decision shared by all nodes in the network. So whilst one node doesn’t query every other node like you get in classical consensus, each node performs their own sample of randomly selected nodes, thus able to scale to hundreds of thousands or millions of nodes without adding lots of additional overhead on each node, as they are querying the same number of nodes. With enough confidence, a decision is finalized immediately. This process happens so quickly that Avalanche rivals major payment systems in its ability process and clear transactions in a network. The below shows consensus being reached when all nodes are performing the query using the same amount of Blue to Yellow initial votes, you can see how quickly they reach a decision.
Avalanche supports an arbitrarily large and parametrizable set of adversaries. If the network is parameterized for a 33% attacker, and an attacker has 34% stake unlike with Classical consensus protocols they can launch a double spend attack which is guaranteed to succeed, with Avalanche it just means they have a slightly higher chance to succeed rather than guaranteed. Because they also operate without a leader, they are immune to a large class of attacks that other consensus protocol families face. The large number of validators ensures immutability and censorship resistance that proof-of-work protocols, backed by small numbers of mining pools, cannot achieve.
There are currently 2 different consensus protocols available called Snowman and Avalanche, whilst work on a third called Frosty is on the roadmap. Snowman establishes a totally ordered timeline which is typically required for smart contracts. Whilst Avalanche establishes a partially ordered timeline where you don’t have to relate everything to everything else, enabling much higher throughput and get much better latencies and used for payments etc.
For more info on how Avalanche consensus works see this great article https://medium.com/avalabs/avalanche-consensus-101-99c68a3e3159 as well as the consensus whitepaper https://files.avalabs.org/papers/consensus.pdf
For an Overview of Avalanche see this article
Comparison between Avalanche, Cosmos and Polkadot
Why Avalanche (AVAX) has the potential to be an incredible store of value
Setting Up an Avalanche Node with Microsoft Azure (Cheaper than AWS)
