Philipp Schneider with contributions by Ignacio Amores-Sesar and Christian Cachin

In this three part series, we look at the “Snow” protocols that address the fundamental consensus problem and were introduced in a whitepaper by a group associated with AvaLabs that pioneered the Avalanche blockchain infrastructure. This first part gives an overview of these Snow protocols and a summary of our findings.

This is cross-posted from the IC3 blog on Medium.

Part 1: Overview

Avalanche might be best known for its blockchain infrastructure and the associated crypto currency (AVAX) that runs on top of it, which, by now, is one of the biggest players measured by market capitalization. However, this is not necessarily the most interesting part of the Avalanche protocol at least from a scientific point of view. That is because the whitepaper from 2019 that outlined the first version of the Avalanche blockchain protocol also contains interesting ideas for solving the consensus problem, which is a core component for maintaining a blockchain. In recent work that is to be published in the proceedings of SIROCCO 2024 we set out to analyze the performance of these consensus protocols introduced by the Avalanche whitepaper. This three-part blog-post aims to give an overview of our findings.¹

The Consensus Problem

First, let us start with some explanations on what the consensus problem is and why it is important in the context of blockchains. Say there are n nodes and each node has an initial opinion. A solution to the consensus problem must satisfy certain requirements. Loosely speaking, all nodes must irrevocably decide on one and the same opinion, eventually. Here, we denote the time until such a consensus is reached as latency. In a blockchain, this corresponds to the time until a block is committed.

Attaining consensus becomes particularly challenging when some nodes do not follow the protocol, e.g., by crashing or failing in other ways or even deviating from the protocol in unintended ways, which includes attempts to sabotage the protocol (the latter is known as a malicious or Byzantine node). In a blockchain, an opinion corresponds to a suggestion for the next block to append to the chain, and there must be consensus so that each node appends the same block at the end.

The Family of Snow Consensus Protocols

The Avalanche whitepaper suggests interesting ideas to tackle the consensus problem. They introduce the Snow family of consensus protocols: Slush, Snowflake and Snowball. These protocols build on top of each other to iteratively enforce network-wide properties that in the end facilitate achieving consensus by using a randomized, self-stabilizing process. This process works by having each node repeatedly sample small random subsets of others and switch to a sufficiently strong majority opinion observed in the current sample. The underlying intuition is that a slight majority in one opinion will quickly reinforce thus a consensus opinion emerges fast, even if a number of nodes is malicious. This is roughly what the most basic protocol Slush does.

The advanced Snow protocols Snowflake and Snowball additionally provide mechanisms where nodes quickly recognize an emerging majority opinion based on past samples, which allows them to irrevocably settle on that opinion relatively fast and with high confidence, despite the fact that each node has only heard the opinion of a very small fraction of the whole network. This makes it an extremely light-weight and scalable approach for solving consensus - in particular when compared to common alternatives in the world of cryptocurrencies, such as protocols based on votes, which require that nodes exchange many messages, or protocols based on proof-of-work which establish consensus by setting the right economic incentives but consume a huge amount of resources.

Our Findings

Before we go into details in the second part of this blog, here is the compressed overview of our findings. We provide an analysis of how the randomized process of the Snow family of protocols plays out. In particular we give a probabilistic quantification how the Snow consensus protocols behave over time, depending on the sample size of the nodes. Using these insights, we confirm that the Snow protocols converge to a state where almost all nodes are in agreement very quickly, while tolerating a limited number of malicious nodes. Conversely, we show that increasing the size of the samples has a rather limited impact on this performance.

The more advanced protocols of the Snow family (Snowflake and Snowball) introduce additional mechanisms for the nodes to make a final decision once a network-wide majority emerges. Due to the randomized nature of the Snow protocols and the presence of malicious nodes it becomes imperative to enforce a certain level of safety that such mechanisms do in fact provide consensus, which means that the probability that the algorithm fails to enforce such a consensus should be very low.

For this purpose, Snowflake and Snowball introduce parameters that are intended to govern the level of safety, i.e., the confidence in a consensus, while at the same time not affecting latency too much. Here, we expose a design issue in the Snow consensus protocols, where this trade-off between safety and latency is unfavorable since a relatively weak adversary could potentially stall nodes for a certain period of time. Here, it is fair to point out that an adversary can only delay the final decision of a node, but the specified level of safety is maintained. Finally, we propose a modification of the original protocol and show that it has a much better trade-off between safety and latency.

Read more about Avalanche Consensus in part two and three of this blogpost.