The Avalanche Family
Slush, Snowflake and Snowball are the first protocols described in this paper. They are solely used for the sake of understanding the final member: Avalanche. They all provide technological aspects, which come together in the end.
Slush is the simplest protocol of the family. Slush and the underlying metastability are easily explained with the following example:
- Node receives transactions from a client and initiates a query
- The node queries to a constant sized (k) sample of the network uniformly at random
- Upon receiving a query,
3a. an uncoloured node adopts the colour, responds with that colour and initiates its own query;
3b. a coloured node simply responds with its own colour;
3c. if k responses are not received within a time bound, the node picks an additional sample from the remaining nodes
- The querying node collects k responses and checks if a fraction are for the same colour
- If the threshold is met and the sampled colour differs from the node’s own colour, the node flips to that colour
- It starts again with the query step and initiates a subsequent round of query, for a total of m rounds
- If m is high enough the protocol ensures that all nodes will be coloured identically
I developed a simple example with MS Excel (as far as the formulas allow me to do so. I intentionally avoided to use VBA here). This demonstrates, in a simplified way, how the metastability works by showing the effects of random sub-sampling: One colour will gain a slight edge and will amplify that imbalance (even if you start with a 50:50 state)
Slush is memoryless. It retains no state between different query rounds, except for it owns colour. It neither keeps the history of interactions with other nodes.
Furthermore, Slush is not Byzantine Fault Tolerant. (BFT) An adversarial actor could keep the network in a state of balance (continually flipping the colour of nodesI, so they reach the consensus.
Snowflake is based on Slush, but adds the Byzantine Fault Tolerance (BFT).
Every node has a counter cnt which stores the number of consecutive samples of the network that have given the result (all red or all blue).
A node accepts the current colours, if its cnt exceeds β (like a threshold).
- Upon every query that yields a certain amount of responses for the same colour as the node, the cnt is incremented.
- Upon every colour change, the node resets cnt to 0.
Snowball builds up on Snowflake and includes a state of confidence, since the counter cnt is ephemeral, because it resets with every colour change. A new confidence counter is added.
The confidence counter captures the number of queries that have yielded a threshold result for its corresponding colour, but the colour is only changed when its current colour becomes lower than the confidence value of the new colour.
- Upon every query, the node increases its confidence counter for the respective colour.
- The node flips its colour, when the confidence counter for its current colour is lower than the confidence counter of the new colour.
Avalanche is based on all three previous introduced protocols and adds further advancements.
It is based on a dynamic append-only direct acyclic graph (DAG). The DAG has a single sink which is the genesis vertex (Directed acyclic graph — Wikipedia).
In any digraph, we define a vertex v to be
a source, if there are no edges leading into v, and
a sink if there are no edges leading out of v.
There are two benefits of using a DAG:
- It increases efficiency, since a new transaction votes explicitly for its parents (1-n) transactions and implicitly to all transactions as a vote for one transaction is a vote for all transactions on its path back to the genesis vertex.
- It improves security, since it is harder (not impossible; basically the same finality like it is with blockchains) to undo past decisions.
Avalanche uses chits next to the confidence counters, which were explained with the Snowball protocol.
That’s the way it works (and especially important with conflicting transactions like e.g. double spend attempts):
- A transaction T is queried, all transaction implicitly reachable from T (by following the edges) are also part of the query.
- A node will only respond positively to the query if T and its entire ancestry is the preferred set for them
- If more than a certain threshold vote positively to the query, the transaction I said to collect a chit. The chits are the result of one-time samples and are immutable and the values range from 0 to 1.
- Node calculate their confidence as the sum of chit values not only to the transaction T itself but for also the parents and descendants (new transactions). The confidence can increase as the DAG grows.
For example, because T2 has larger confidence than T3 , its descendants are more likely collect chits in the future compared to T3.
The nodes consent on whether the transaction is correct or if it conflicts with another transaction. Avalanche, therefore, can be seen as using instances of Snowball to solve conflicts. Avalanche embodies a Snowball instance for each conflict.
Similar to Bitcoin, Avalanche leaves the decision of whether to accept a transaction or not to the application.