Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies
This paper ,by Team-Rocket introduces a brand new family of consensus protocols suitable for cryptocurrencies, based on randomized sampling and metastable decision. The protocols provide a strong probabilistic safety guarantee, and a guarantee of liveness for correct clients.This new leaderless Byzantine fault tolerance protocol called Avalanche
Introduction
Classical consensus requires nodes to know every other node in the network (required knowledge of membership) and to communicate with every other node (i.e., quadratic communication overhead). Nakamoto Consensus provides a probabilistic safety guarantee. Instead of every node agreeing on a value, nodes will all agree on the probability of the value is correct. Nakamoto also has a long waiting time for finality and consumes a large amount of energy due to minor operations.What is proposed here is a metastable consensus protocol inspired by epidemic protocols and gossip networks which comes with lessons learned from Classical Consensus and Nakamoto Consensus. This serves to combine the best of both to fundamentally improve the known issues in layer 1.
This paper introduces a new family of consensus protocols,inspired by gossip algorithms.This new family gains its safety through a deliberately metastable mechanism. Specifically, the system operates by repeatedly sampling the network at random, and steering the correct nodes towards the same outcome. This new protocol family provides a probabilistic safety guarantee, using a tunable security parameter that can render the possibility of a consensus failure arbitrarily small. Unlike Nakamoto consensus, the protocols are green, quiescent and efficient; they do not rely on proof-of-work and do not consume energy when there are no decisions to be made. The way this protocol works is incredibly simple yet incredibly powerful.
The paper starts with a non-Byzantine protocol, Slush, and then progressively build up Snowflake, Snowball and Avalanche, though with better Byzantine fault-tolerance (BFT) and irreversibility properties
Model:
Avalance adopts Bitcoin’s unspent transaction output (UTXO) model. In this model, clients issue cryptographically signed transactions that fully consume an existing UTXO and issue new UTXOs. Unlike nodes, clients do not participate in the decision process, but only supply transactions to the nodes running the consensus protocol. Two transactions conflict if they consume the same UTXO and yield different outputs. Correct clients never issue conflicting transactions, nor is it possible for Byzantine clients to forge conflicts with transactions issued by correct clients. However, Byzantine clients can issue multiple transactions that conflict with one another, and correct clients can only consume one of those transactions. The goal of our family of consensus protocols, then, is to accept a set of non-conflicting transactions in the presence of Byzantine behavior.
The Avalanche family of protocols provide the following guarantees with high probability
Safety: No two correct nodes will accept conflicting transactions.
Liveness: Any transaction issued by a correct client (aka virtuous transaction) will eventually be accepted by every correct node.
Slush: Introducing Metastability
Slush protocol is the most basic part of the Avalanche protocols. Slush protocol starts out initially in an uncolored state. Upon receiving a transaction, an uncolored node updates its own color to the one carried in the transaction and initiates a query.
To perform a query, a node picks a small, constant sized (k) sample of the network uniformly at random, and sends a query message. Upon receiving a query, an uncolored node adopts the color in the query, responds with that color, and initiates its own query; whereas a colored node simply responds with its current color. If k responses are not received within a time bound, the node picks an extra sample from the remaining nodes uniformly at random and queries them until it collects all responses.
Once the querying node collects k responses, it checks if a fraction ≥ αk is for the same color, where α > 0.5 is a protocol’s parameter. If the α k threshold is met and the sampled color differs from the node’s own color, the node flips to that color. It then goes back to the query step, and initiates a subsequent round of query, for a total of m rounds. Finally, the node decides the color it ended up with at time m. The paper shows in the analysis that m grows logarithmically with n
Snowflake:BFT
To enable BFT ,the second protocol in Avalanche is Snowflake.Snowflake augments Slush with a single counter that captures the strength of a node’s conviction in its current color. In the Snowflake protocol in Figure 2:
A node accepts the current color when its counter exceeds β, another security parameter.
Figure 2 shows the amended protocol, which includes the following modifications:
1. Each node maintains a counter cnt;
2. Upon every color change, the node resets cnt to 0;
3. Upon every successful query that yields ≥ αk responses for the same color as the node, the node increments cnt
Here the nodes can accept colors in an asynchronous manner, not all at the end of m rounds. Each can accept when its own counter exceeds β. When the protocol is correctly parameterized for a given threshold of Byzantine nodes and a desired ϵ guarantee, it can ensure both safety and liveness. The Byzantine nodes lose control past the phase shift,and the correct nodes begin to commit past the point of no-return, to adopt the same color, whp.
Snowball: Adding confidence
Snowflake’s notion of state is ephemeral: the counter gets reset with every color flip. That is too much history to forget based on one sampling result. Snowball augments Snowflake with momentum by adding confidence counters that capture the number of queries that have yielded a threshold result for their corresponding color (Figure 3):
- Upon every successful query, the node increments its confidence counter for that color.
- A node switches colors when the confidence in its current color becomes lower than the confidence value of the new color.
Snowball is not only harder to attack than Snowflake, but is more easily generalized to multi-decree protocols
Avalanche: Adding a DAG
Avalanche is the last protocol in the family of metastable protocols ,it generalizes Snowball and maintains a dynamic append-only Directed Acyclic Graph (DAG) of all known transactions.Adding a DAG provides two significant benefits. First, it improves efficiency, as a single vote on a DAG vertex implicitly votes for all transactions on the path to the genesis vertex. Secondly, it improves security, because the DAG intertwines the fate of transactions, similar to the Bitcoin blockchain. This makes past decisions difficult to undo without the approval of correct nodes.
When a client creates a transaction, it names one or more parents,in the DAG. The parent-child relationships encoded in the DAG may, but do not need to, correspond to application-specific dependencies; for instance, a child transaction need not spend or have any relationship with the funds received in the parent transaction.Avalanche embodies a Snowball instance for each conflict set. Whereas Snowball uses repeated queries and multiple counters to capture the amount of confidence built in conflicting transactions (colors), Avalanche takes advantage of the DAG structure and uses a transaction’s progeny.Specifically, when a transaction T is queried, all transactions reachable from T by following the DAG edges are implicitly part of the query. A node will only respond positively to the query if T and its entire ancestry are currently the preferred option in their respective conflict sets. If more than a threshold of responders vote positively, the transaction is said to collect a chit, cuT = 1, otherwise, cuT = 0. Nodes then compute their confidence as the sum of chit values in the progeny of that transaction
As Figure 5 shows, when node u discovers a transaction T through a query, it starts a one-time query process by sampling k random peers. A query starts by adding T to Transaction set, initializing cT=0, and then sending a message to the selected peers. Each correct node u keeps track of all transactions it has learned about in set Tu, partitioned into mutually exclusive conflict sets PT, T∈ Tu. Since conflicts are transitive, if Ti and Tj are conflicting, then PTi=PTj
In the above Figure 6 it explains what happens when a node receives a query for transaction T from peer j. The node determines if T is currently strongly preferred and returns a positive response to peer j. The transaction T is strongly preferred, if every single ancestor of T is preferred among its competing transactions .
The Figure 7 ,above explains a sample DAG built by Avalanche, where the shaded regions represents conflict sets. Sampling in Avalanche will create a positive feedback for the preference of a single transaction in its conflict set. For example, because T2 has larger confidence than T3, its descendants are more likely collect chits in the future compared to T3. So T9 would have an advantage over T6 and T7 in its conflict set
Implementation:
Team Rocket has fully ported Bitcoin transactions to Avalanche, to yield a bare-bones payment system.According to them,Deploying a full cryptocurrency involves bootstrapping, minting, staking, unstaking, and inflation control. While there are solutions for these issues, the discussion is beyond the scope of this paper.
Some Useful Links:
▪️Website: https://avax.network
▪️Whitepaper: https://avalabs.org/whitepapers
▪️Avalanche Hub: https://community.avax.network
▪️Twitter: https://twitter.com/avalancheavax
▪️Discord: https://chat.avax.network
▪️GitHub: https://github.com/ava-labs
▪️Documentation: https://docs.avalabs.org
▪️Explorer: https://explorer.avax.network
▪️Avalanche-X: https://avalabs.org/avalanche-x
▪️Telegram: https://t.me/avalancheavax
▪️Telegram announcement: https://t.me/avalanche_announcements
▪️Linkedin: https://linkedin.com/company/avalancheavax
▪️Reddit: https://reddit.com/r/avax
▪️Medium: https://medium.com/avalabs
▪️Facebook: https://www.facebook.com/avalancheavax
▪️Youtube: http://www.youtube.com/c/AVALabsOfficial
