Demystifying “Snowflake to Avalanche”

Introduction

Not every day that somebody in the field of distributed systems, comes out and says “I have a new breakthrough to tell you about”. However, recently, Prof. Emin Gün Sirer, from Cornell University, said that he does. In this article, we are going to describe to you a new family of consensus protocols that just emerged several months ago. “Team Rocket — A pseudonymous team — with the collaboration of Prof. Sirer dropped this paper titled “Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies” on IPFS. The paper builds on comprehensive low-level details and proofs that are not easily comprehended by non-academics. In this article, we will simplify and visualize the protocol for you, leaving you with an understanding of this new approach.

Two Classes of Consensus Protocols

Consensus is one of the most important goals to be achieved when many distributed computers share the same task and resources.

A typical example is maintaining account balances in a banking system over multiple servers. Banks don’t rely on one single database to carry their data, but many geographically distributed machines across the globe to handle these transactions. They require a method to maintain a stable view across all these machines, thereby, reflecting a consistent representation of account balances.

Another example is maintaining a consistent view of Amazon’s online shopping services. In order to scale these services globally, they have to be (geographically) distributed across large datacenters. Amazon requires having a regular view of its stocked products or else, unexpected and undesired behaviour might happen, e.g., the last item can be sold twice to two different people.

This has been an important problem in Computer Science for a long time. To this end, academics/engineers have been working hard over the course of the last 40 years to find efficient solutions. In the field of distributed systems there are only two existing families of consensus protocols which we describe next.

Classical Consensus Protocols

The first class called classical consensus protocols were developed by two great computer scientists, namely, Leslie Lamport and Barbara Liskov. Both of them are Turing award winners — which is the equivalent of a Nobel prize for Computer scientists. The advantages of this protocol are various including quick finality and quick guarantees about the committed transactions. However, this comes with a price:

• They do not scale well beyond 10 to 1000s of nodes. That is because they require quadratic communication costs, i.e., O(n²), among the nodes who are participating.
• They require everyone in the network to know all the other participants.

Basically, their security comes down to the judicious overlap between a quorum of nodes that confirm seeing the same thing and go ahead commit to it. This approach is reasonable when building a permissioned blockchain, however, it is not a good foundation when you are in a dynamic environment of untrusted nodes. Therefore, permissionless chains are based on a different protocol for consensus.

Nakamoto Consensus Protocol

In 2009, another new family appeared on the scene. Satoshi Nakamoto came up with his new protocol family and presented his solution that was uniquely robust:

• We do not need to know all the nodes participating in the network. Any node can leave or join at any point in time and any miner could come up with a block and participate in the system.
• It can scale to large numbers of global nodes and participants.

However these benefits came with a price, in particular:

• Bitcoin is very slow, on average, users have to wait about 10–60 minutes before they get confirmation that their transactions are stored on the chain.
• Throughput is also very limited. Bitcoin can process about 3–7 transactions per second which is ,of course, nothing close to handling the the task of being a world currency.
• Finally, Bitcoin consumes an enormous amount of energy; approximately an energy equivalent to 4 Chernobyl nuclear power plants go into powering Bitcoin. That is a lot of energy spent on bookkeeping.

Avalanche

Avalanche comes in and combines the best of both world’s, in particular,

• Quick finality and low latency: That is, it takes around 2 seconds to achieve finality across the globe. This basically means that after 2 seconds, you can get your payment processed and verified.
• Higher throughput: 1000–10,000 transactions per second.
• Robust: The network does not need to agree on who the participants are to achieve undeniable consensus.
• Quiescent protocol: Most importantly, the protocol is green. That means that it is sustainable, it does not waste any energy, and that there is no special ecosystem of miners with their own separate interests from the users.

The Core Idea: MetastabilityThe Avalanche protocol in action¹. The core idea relies of subsampled voting.

The core idea of Avalanche is metastability. The worst thing for a consensus protocol is to be unable to decide between two choices, i.e., you don’t want it to say either this happened or that happened you want it to fall to one of the two sides. Avalanche’s metastable protocol is designed to tip the choice towards one of the sides.

To explain the core intuition of the process, lets go through a simplified example, as visualized in the figure above. Consider a network of trustless nodes that want to vote for either blue or red.

• A single node of the network starts with picking a small number of random peer nodes, say five, and asks them to choose a color.
• Each peer node then responds with a vote which the requesting node uses to form a weighted result of all votes. In the figure above (in the first frame), from the node’s perspective the entire network is tilting towards red based on one round of polling.
• This process repeats itself for everybody else.

The protocol resembles a recurring subsampled voting process. What happens here is that even if we start out in the worst possible scenario of a 50–50 split between red and blue, after one round, with high probability, the scenario will no longer hold. Furthermore, chances of that are astronomically small after two rounds, even smaller after three, and so on, i.e., it decays exponentially. The protocol is designed to tip and not stay in the middle. As it tips more and more, the network’s perception shifts to one color or the other. The speed with which we move towards one direction (nodes vote one color more than the other) is going to increase and increase and at some point we reach to the point of no-return where the entire network has agreed on a color.

Notes on the protocol

• Efficient scalability: The protocol is lightweight and therefore admits scalability and low latency.
• Byzantine tolerance: It can tolerate a large percentage of Byzantine participants with no impact on safety. In particular, you can have up to 50% of the nodes being Byzantine, i.e., nodes that try to trick the network and keep the entire network imbalanced. However, they will be unable to do this in a way that causes two nodes to decide on two different colors.
• Egalitarian ecosystem: The avalanche protocol gives rise to an egalitarian ecosystem, i.e., all nodes in the network are born the same. There are no miners and no special privileges are given to them.
• No liveness guarantee for conflicting transactions: If an attacker tries to spend the same money twice in two different transactions (double-spending), then the Avalanche protocol will not be able to decide between these two, causing this money to be lost. Classical consensus and Nakamoto protocols would have decided on one transaction or the other, however, the Avalanche protocol might not. This is a very interesting property for the protocol, that it implicitly and naturally punishes bad actors without any additional complications to the protocol.

The Avalanche Token: AVA

AVA — short for Avalanche, resembles the new token represented by this protocol.

• Sybil deterrence via staking: The Avalanche protocol prevents sybil attacks through staking of AVA tokens. That means nodes stake AVA tokens to show that they have some ownership in the system. Unlike Ethereum and others, that stake is not a collateral and will never be lost. If you misbehave there is no risk of your money being taken from you. So the stake here is solely to make sure that you cannot impersonate other people. This is one of the great outcomes of the Avalanche protocol. Staking is not used for consensus, in fact, it is completely independent of it.
• Economic governance via voting: An interesting point this whole entire system gives, is governance. The core idea introduced till now using was subsampled voting to achieve consensus. We can use that same mechanism to agree on critical parameters of the protocol itself. So for example, the network can decide to increase the minting rate if they don’t have enough stakers. On the contrary, the network can decide to reduce the minting rate to boost the price and reduce the available supply of coins. In contrast, Nakamoto had to come up with his fixed 21 million minting curve. Instead, Avalanche is essentially a crowd oracle, that replaces central banks with people who have a vested interest in seeing the coin managed properly for their own interests.

Conclusion

People often talk about the consensus protocol used in Bitcoin as if it was a pure decentralized approach that determines the opinions of all network participants equally. Unfortunately it is not, in Bitcoin the decisions are mostly made by the miners.

In contrast, Avalanche separates the consensus problem from the governance problem. Each one is tackled modularly and independently. Consensus is achieved via a smart combination of gossip protocols with recurrent subsampling. While, fair governance is achieved via sampling and staking resulting in a direct tie between users and their decisions.

References:

1. Cryptoconf 2018, Emin Gün Sirer talk — Snowflake to Avalanche
2. Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies, Team Rocket, 2018

If you like this post or if you have any further questions or chart-requests, please reach out to me on Twitter or LinkedIn.

Disclaimer: Information in this article is for educational purposes only and cannot be taken as investment advice.

Demystifying “Snowflake to Avalanche” was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.