“Snowflake to Avalanche” Consensus Protocol Family: Overview and Technicality
Team Rocket’s latest family of consensus protocol, explained.
We provide a technical explanation of the “Snowflake to Avalanche” consensus protocol family. We based our analysis on the May 16th, 2018 version of whitepaper published by Team Rocket. Although consensus protocols are related to cryptocurrency mining, we focus on “Snowflake to Avalanche” as a consensus mechanism.
Motivation of Creation
The most popular consensus mechanism currently in use is Proof-of-Work (PoW). Bitcoin and other cryptocurrencies that utilize PoW have multiple problems such as high energy consumption and low transaction per second, which prevent them from succeeding as functioning, day-to-day cryptocurrencies. “Snowflake to Avalanche” aims to solve these problems by presenting a new family of consensus protocol specialized for cryptocurrencies.
Note: “Snowflake to Avalanche” will be abbreviated as SoA on further explanation.
Introduction
At its core, traditional consensus protocols require absolute communication between all nodes to ensure that correct nodes agree on the same decision. This concept requires quadratic communication overhead O(n²) and accurate knowledge of membership (knowing all the network’s participants) which makes it difficult for scalability. Whereas Nakamoto consensus protocols instilled a probabilistic safety guarantee; meaning that, with very small probability, decisions have a possibility to revert. The underlying notions of these protocols are not efficient, requiring miners to constantly participate even when decisions are not necessary to be made.
Inspired by gossip algorithms, SoA ensures its safety by utilizing a metastable mechanism. The core idea is to tip all the nodes into 1 outcome. This can be achieved by utilizing a method that resembles a recurring subsampled voting process. SoA’s mechanism ensures with high probability that all nodes will fall into the same outcome after more than 1 round. Due to its exponentially decaying feature, the chances of it still being divided after more than 1 round is astronomically small.
In the words of the whitepaper: The system operates by repeatedly sampling the network at random and steering the correct nodes towards the same outcome.
SoA claims that its efficiency derives from 2 factors:
· Requiring communication overheads from O(kn log n) to O(kn) for some small security parameter k
· Establishing only a partial order among dependent transactions
The paper claims that one significant trade-off of this protocol is the liveness for conflicting transactions, meaning that SoA only guarantees liveness for honest transactions. Although this might stall the network, it does not tamper the safety of honest transactions. Lastly, the consensus protocol family SoA can be divided into 4 parts: Slush, Snowflake, Snowball, and Avalanche.
Slush
To begin, Slush is the foundation of this protocol family, it is a single-decree consensus protocol inspired by gossip algorithms. The main idea of Slush is, with high probability, to categorize all nodes in an identical manner. However, it is crucial to remember that Slush does not have a strong safety guarantee against Byzantine nodes, as these nodes lack state. This means that if Slush is deployed within a network that contains Byzantine nodes, malicious actors can interfere with the decisions. This problem will be addressed on the Snowflake part of SoA.
Slush Procedure
The procedure of Slush will be explained using the color red and blue for better understanding. Initially, a node starts out with no color, updating its own color based on the clients’ color upon receiving a transaction. This node will then initiates a query; the process to start a query is by picking a small, constant sized (k) sample uniformly from the network at random and sends a query message.
Other uncolored nodes within the network will then update its color based on the query’s. These nodes will then respond with that color and initiates their own query, creating a cycle. During this cycle, colored nodes that received a query simply response with their own color.
The system relies on ensuring that k responses are received within a time-bound, otherwise, the node will pick an additional sample uniformly at random from the rest of the nodes. It will then keep on sending queries until the necessary responses are collected.
In the case that k responses are collected, a protocol parameter α > 0.5 is utilized to ensure that a fraction ≥ αk falls on the same color. If this threshold is met and the node’s color differs from the sampled nodes’ color, the node will then flips to the sampled nodes’ color. Lastly, it will repeat the query step, initiating a subsequent round of query for m rounds to finalize the color.
Snowflake
The purpose of snowflake is to strengthen Slush with a single counter that emphasizes a node’s loyalty in its current color. In other words, a node will only accept its current color when the counter, which stores the number of consecutive samples that resulted in the same color, exceeds β, a security parameter.
Snowball
In a nutshell, snowball adds a layer of protection for SoA by implementing confidence counters. The purpose of these counters is to record the number of queries that yielded a threshold result for their specific color. Essentially, a node finalizes on a color if the confidence for that color exceeds the other color after a certain number of consecutive queries.
The code ensures that a node increments its confidence counter for that color after every successful query, and switches color when the counter in its current color is lower compared to the counterparts.
Avalanche
The final step of SoA, Avalanche, generalizes Snowball and maintains a dynamic append-only Directed Acyclic Graph (DAG) of all known transactions. The purpose of these steps is to improve efficiency and security. The DAG achieves efficiency due to a single sink called the genesis vertex, which enables a single vote on a DAG vertex to represent all transactions votes on the path to the genesis vertex. On the security side, DAG intertwines the fate of transactions, which simply means it ensures past decisions are difficult to undo without the approval of correct nodes.
In a nutshell, every transaction created contains one or more parents, that are inseparable and included within the transaction, forming the edges of the DAG. The term ancestor set is used to refer to all the reachable transactions via parents’ edges and progeny for all children transactions.
The difference between SoA and BTC is that SoA utilizes DAG which one of the use cases will be explained below.
The problem of maintaining DAG lies in the case of choosing conflicting transactions. In the use case of blockchain for the cryptocurrency, a conflicting transaction is typically a double-spend problem. Avalanche solves this problem by taking advantage of its DAG structure. Essentially a node will only respond positively to a query if a transaction and its entire ancestry are the preferred option in the conflict sets. When the threshold is met, a counter called chit is appended to the transaction, giving a value of 1, otherwise, the chit counter is equal to 0. Lastly, the node will count the sum of chit values in the progeny of that transaction as confidence.
Sources:
https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV
https://medium.com/zkcapital/demystifying-snowflake-to-avalanche-966f56c33fd7
