Protocol Spotlight: Avalanche (Part 2)

Note: This article was first published on FlatOutCrypto on the 29th June.

This is Part 2 of an introduction to the Avalanche Protocol. Part 1 looked at what Avalanche is, what it is trying to achieve and the assumptions and guarantees Team Rocket outline. It can be found here. I will now look at the protocols that make up the Avalanche family and how they come together to form the leaderless protocol Avalanche.

The Avalanche Family

Slush

Slush is the most basic part of the Avalanche protocol series. It is explained in the whitepaper as a demonstration of how a group of nodes (let’s say 100) can come to a consensus between two colours e.g. red and blue:

1. A small sample of nodes (say nine) are uncoloured in their default state. These nine uncoloured nodes update their colour to either red or blue based on the transaction they receive. In this example, let us say one of these nodes we are following flips to blue
2. This blue node now queries a small sample of other nodes (for ease, let’s say nine again). These nine would update to blue if they were uncoloured or, if already coloured, respond to our blue node noting they are either blue or red
3. Once our node has received enough responses, it checks to see if the pre-defined threshold of nodes are for the same colour. If yes, it either remains blue or if enough of the other nodes responding to its query are red it flips to red
4. The node then goes back and performs another query with a different sample of nodes
5. This vote happens again and again across the network until enough nodes have chosen the same colour
6. Given enough time, all will eventually flip to the same colour and consensus is achieved

The obvious question is how do we know they’ve chosen the right colour and aren’t just voting randomly/for the ‘bad’ choice which then propagates across the network. This will be explored later, but remember that all blockchains and DLT implementations are at their heart about coming to a consensus.

Other points to note:

• There is no store of history — no node in Slush remembers anything other than the colour it currently is
• It is not Byzantine Fault Tolerant (I would recommend reading my introduction to the Byzantine Generals Problem if you are unfamiliar with what BFT or BGP means) which essentially means a malicious actor would be able to keep the network in a state of balance
• They could do this by continually flipping the colour of nodes to maintain enough red and blue nodes such that no consensus could ever be reached

Snowflake

Snowflake is a beautifully short part of the whitepaper and adds one basic feature to Slush, enabling it to become BFT. In Slush we noted that there was no store of history but Snowflake provides each node with a counter to store the number of consecutive samples of the network that have given the result of all red or all blue.

Why? Because then after a certain number of consecutive samples (a parameter that has to be set for a given threshold of Byzantine nodes/desired security guarantee) it accepts the colour for good. This allows correct nodes to commit and means that the nodes will come to consensus (the paper terms this ‘a point of no return after which a decision is inevitable). If the streak is broken then the counter returns to zero and the counter starts again.

Snowball

The short quarter page on Snowflake is followed by another lovely small section on Snowball (when you read enough whitepapers short is most definitely good!). Snowball builds upon Snowflake by adding in a state of confidence. It does this in order to make the protocol harder to attack, because it is now able to store information and make decisions based off that information that it was not able to before.

Snowball progresses Snowflake’s counters to ‘confidence counters’. These confidence counters mean that after each query that yields a result of either red or blue, the node increases its confidence counter by one. It switches colours if its confidence in the current colour goes below the confidence value of the other colour.

Instead of coming to a decision on a colour based on the number of consecutive results for a colour as per Snowflake, a node comes to a decision after a number of consecutive queries (again, this number has to be set as a given threshold of nodes/desired security guarantee) yield a result that means that nodes confidence for a colour exceeds that of other colours.

Now we come on to the final member of the family, Avalanche. I’m pretty sure even my Mum will understand Slush, Snowflake and Snowball so far, a personal golden standard I try to aspire to with every article (sidenote: she’s probably been holding her Ethereum longer than you’ve been in crypto) so hopefully Avalanche will be as easy to understand.

Avalanche

Avalanche, our final protocol, generalizes Snowball and maintains a dynamic append-only Directed Acyclic Graph (DAG) of all known transactions. The DAG has a single sink that is the genesis vertex.

As always, let’s break it down:

• Append-only: Transactions add on to previous ones. Essentially, when a node creates a transaction it is added on to one or more other transactions (parent transactions) which are then included in the transaction
• DAG: Going into the specifics of what a DAG is beyond the scope of this article but there is an introduction here which outlines what DAGs are if you are unsure. Basically, while a blockchain is linear (one block adds to the next), DAGs are unbounded — transactions proliferate out as they add to one another. The advantage of this is it allows transactions to be confirmed quicker (no wait to be pooled into a block of all transactions for that period as per Bitcoin or Ethereum) — they are confirmed as they are processed by newer transactions
• Side note: the DAG is the data structure. Avalanche is the consensus protocol. This is analogous to blockchain (data structure) and Proof of Work (consensus protocol). Avalanche could work on a different data structure, but Team Rocket presumably feels that the DAG is optimal for it
• Single sink: A sink, in the context of a DAG, is a node in which all points face inwards. The below image, sourced from here illustrates a DAG and what sources and sinks are in relation to one. And obviously there’s just one of them
• Genesis vertex: Point where two lines/edges meet (in this context, where two lines/edges meet between nodes in a DAG structure). Genesis = first one, into which all other points face into either directly or indirectly (see Figure 1 below, in which T1 is the genesis vertex and single sink)

So Avalanche uses Snowball and the idea of confidence counters but applies it to nodes on a DAG. Each transaction links onto a parent transaction which all eventually link back to the single sink, the genesis vertex. Why do we need this? Because just like other DAGs, there needs to be one transaction which acts as the basis for the rest (for example, IOTA has a genesis transaction); this is the nature of append-only transactions — they need something to add on to.

The DAG structure also means that new virtuous transactions become tied to undecided parent ones and in doing so “helps propel transactions towards a decision”.

Team Rocket explain the rationale behind using a DAG structure as twofold:

1. It makes voting more efficient, as a vote for one transaction is a vote for all transactions it is appended to (right back to the genesis vertex)
2. This also means that it is harder to undo past decisions (although note the wording here implies there is no finality, just as there isn’t with a blockchain)

This still leaves us with the problem of how to actually choose between conflicting transactions or double spends. Avalanche builds upon Snowball here, including not just confidence counters but also ‘chits’. A chit is collected by a transaction when a predefined threshold of nodes vote to affirm that a transaction and all of its parent transactions are the preferred option. The number of chits is then used by nodes to come to a confidence in not just the specific transaction but the parents and the descendants (i.e. newer transactions emerging). If there is a tie then nodes vote for the first seen. Figure 1 highlights the chit and confidence values of nodes.

A sample set of transactions highlighting their different {chit, confidence} values

Team Rocket are highlighting here that T2 has a larger confidence (5) than T3 (0) and so the children transactions formed off T2 (T4,5,8 and 9) are more likely to collect chits going forward than those of T3 (6 and 7).

This process uses the attributes we’ve already discussed in Slush, Snowflake and Snowball. Nodes send out queries to random samples of other nodes to garner votes on transactions as well as notify other nodes about new transactions. If a node sees that a transaction and all ancestor transactions are preferred among competing transactions then the transaction becomes ‘strongly preferred’ and receives a yes-vote. If the transaction or its ancestors are not preferred then it receives a no-vote.

Instead of red and blue, as per our previous example, the nodes come to a decision on if the transaction is correct or if it conflicts with another transaction. Avalanche, therefore, can be seen as using instances of Snowball to solve conflicts.

One final point, a virtuous transaction could find itself appended to a rogue parent, in which case it might struggle to gain the confidence and chits necessary to be confirmed. In this case a virtuous transaction would try again and can select a decided or fully confirmed parent.

Avalanche also uses another means to make sure that virtuous transactions with decided ancestry can receive enough chits, by allowing correct nodes to “examine the DAG for virtuous non-nop transactions that lack sufficient progeny and emit nop transactions to help increase their confidence”. A nop transaction is defined as being a transaction that has one parent and which can be issued by any node. However, they can’t be abused to game the system because they do not automatically grant chits.

Conclusion

Hopefully you now have an understanding of what Avalanche is and the principles of how it works. There is a lot of further information that I cannot cover in a single article and I may do a followup at some point because the above really only covers the first 1/3 of the whitepaper. The rest of Team Rocket’s paper covers:

• Section 3: Analysis of the system and proving what is described works
• Section 4: Implementation (worth reading as it refers to how they have fully ported Bitcoin transactions to Avalanche)
• Section 5: Evaluation (which provides additional metrics around performance)
• Section 6: A breakdown of other consensus protocols and their application to different networks

Team Rocket made clear that this paper was not designed to cover every eventuality and refers to a specific set of circumstances. However, there are a few aspects it will be interesting to see how Avalanche implementations handle such as how it is Sybil attack resistant.

It is a particularly opportune time for a leaderless protocol to launch given current circumstances, as the mainnet launch of projects such as EOS expose the extent to which centralisation has crept back into supposedly decentralised networks and as Bitmain’s hashpower on the Bitcoin network once again approaches 51% over decentralisation. As such, a protocol bringing forth an idea for leaderless protocol should always be welcomed and carefully scrutinised. I am looking forward to seeing further reviews by those better placed than myself in the coming months and the implementations that are soon to launch.

If you enjoyed this article please follow me @FlatOutCrypto. You can also find my work on Medium, although I am admittedly sometimes forgetful when it comes to posting on here.

Disclaimer: I do not own any Avalanche based networks (there are none) and have not invested in any of the ones soon to launch (such as Perlin).