Protocol Spotlight: Avalanche (Part 1)

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

Following the positive reaction (and most gratifyingly the high % of people who read all three parts!) to the PARSEC whitepaper breakdown last week I have decided to continue exploring some of the newer protocols including Thunderella and Avalanche. It is with the latter that I will begin.

The same disclaimers as per the PARSEC post apply, namely:

• I will explain the key concepts of Avalanche but not go through every single piece of how Avalanche works at a granular level — the whitepaper serves that purpose. As such, some of the intricacies, exceptions and smaller aspects that take many words but have a minimal impact will be omitted
• I will avoid validating — or refuting — Team Rocket’s claims. There are others better placed to do so. I am just explaining what the Avalanche whitepaper is outlining for those who might not have the inclination or technical background to read the whitepaper
• It might not be quite as long as the PARSEC article, but it’s still going to be pretty long!

What is Avalanche?

The Snowflake to Avalanche whitepaper was released anonymously in mid-May by a team identifying themselves only as Team Rocket. The whitepaper contains four protocols which build upon each other and together make a protocol family. These different protocols outlined are named:

• Slush
• Snowflake
• Snowball
• Avalanche (for simplicity I will refer to the family of protocols as Avalanche unless I am specifically referring to one of the other three)

Team Rocket (I’ll have ‘prepare for trouble and make it double’ ingrained in my mind by the end of this post) describe their work as a “novel metastable consensus protocol family for cryptocurrencies”.

As with PARSEC, let’s break down the abstract to clarify what exactly the team have developed.

This paper introduces a new family of leaderless Byzantine fault tolerance protocols, built on a metastable mechanism.

The paper claims that this is a new breed of protocols which stand separate to the previous duo of traditional consensus protocols and Nakamoto consensus protocols. The paper describes these as:

1. Traditional: Needs all nodes to communicate with all other nodes to reach consensus.
2. Nakamoto: Most commonly associated with Bitcoin, the Nakamoto consensus protocols reach consensus through Proof of Work in which a leader (miner) is chosen to produce each block.

Avalanche claims to be different from these two families by not needing to elect a leader in any form (hence leaderless), but rather the protocol simply ‘steers’ all nodes to consensus. Given most (and in the views of Team Rocket all) forms of consensus algorithms I can think of involve a leader in some shape (aside from the obvious ones like DPoS, the likes of PoW and PoS still elect one validator for a specific block etc), this is a distinguishing factor and one that is quite easy to overlook the importance of. Debates over how centralised many of these supposedly decentralised networks only adds to the significance, particularly given the problems a project like EOS has encountered since launch.

This approach is partially achieved by Avalanche’s metastable mechanism. Metastability essentially refers to the concept that the system is designed to bring an answer (i.e. all nodes vote one way or the other) and so will not stay in balance (because if the system remains in balance then consensus cannot be reached).

The reason Team Rocket describe Avalanche as a new family of protocols is because of this idea of metastability, a means to engender consensus by guiding all nodes towards an emerging consensus without the need for any leaders whilst achieving the same level of security and at a faster pace than current protocols. It does this by establishing ‘sub-quorums’, small randomised samples from nodes on the network, which allows for higher throughputs and parallel consensuses to run before they all eventually converge and come to an overarching consensus in time. If that sounds like how I described gossip protocolsthen good, because that is the inspiration for it.

These protocols provide a strong probabilistic safety guarantee in the presence of Byzantine adversaries, while their concurrent nature enables them to achieve high throughput and scalability.

High throughput = higher number of transactions per seconds than the likes of Bitcoin and Ethereum (you can read more on my thoughts about the difficulty of blockchains and DAGs scaling here)

Scalability = can support more people using the network. Part of the problem is that a system can be very fast when a small number of nodes are active, as there are less decisions to make, less nodes to be included in consensus making but when we try and add a lot of users and transactions to it (higher throughput) it will come crashing to a halt.

Unlike blockchains that rely on proof-of-work, they are quiescent and green.

Quiescent = to be inactive or dormant. In this context it means that, unlike a PoW implementation such as Bitcoin which requires constant active participation by miners, Avalanche can operate even when nodes are inactive (I guess, I haven’t come on to the rest of the paper here). And, like all other non-PoW implementations, it is more energy efficient owing to the lack of mining required.

Surprisingly, unlike traditional consensus protocols which require O(n² ) communication, their communication complexity ranges from O(kn log n) to O(kn) for some security parameter k << n.

Essentially Team Rocket are writing that the communication complexity of this family of protocols is far less intensive than the O(n²) used by traditional ones — which is good, because it makes the system faster and more scalable.

The Metcalfe Network effect (which this illustration depicts) is a good thing, but it can also be used to demonstration that all nodes being required to contact all other nodes becomes a limiting factor to scalability

This is because O(n²) means that the rate of growth of the function is determined by n² , where n is the number of people on network. Therefore, for every additional person added it takes an exponentially greater time to share information to all people on the network e.g. 102 = 100, 1002 = 10,000, 1,0002 = 1,000,000. This makes sense, because traditional consensus protocols require everyone to communicate with everyone else — which quickly becomes an arduous process. This page goes into further detail if required.

As a small aside, I wish authors would refrain from using mathematical notation in their introductions, or at the very least explain what it means for those unfamiliar. It’s enough to put some people off which is a shame when we should be trying to aid greater understanding of the technology.

The paper describes the protocol family, instantiates it in three separate protocols, analyzes their guarantees, and describes how they can be used to construct the core of an internet-scale electronic payment system.

All self-explanatory — without wishing to sound patronising, it’s nice in a way to be back to a whitepaper that is describing how to build an actual payment system, given every project these days seems to be building for increasingly specific and non-currency focuses that will likely never be used. 10 years on, we do still need a proper cryptocurrency to come to fruition.

Snowflake to Avalanche: A novel metastable consensus protocol family for cryptocurrencies

Finally, returning to the title of the paper we can now understand that Team Rocket are positioning Avalanche as a new protocol designed squarely for payments (ergo cryptocurrencies) which should be considered as an entirely new method of protocols.

Points of Relevance

Assumptions

Team Rocket note that their paper assumes a synchronous network. I wrote about the differences between synchronous, partially synchronous and asynchronous networks here, but to recap briefly:

• Synchronous: There is a known timing for nodes to wait and receive information. Ethereum and Bitcoin are both examples of this; Bitcoin blocks are 10 minutes apart, Ethereum c. 15 seconds. If a node has not received an input within these boundaries they know that there is a problem.
• Partially Synchronous: A partially synchronous blockchain would know there was some timing limit but not know exactly what it was, with messages always being sent and received within the unknown deadline.
• Asynchronous: No timing assumption and allows for the potential that the sending and receiving of messages is delayed for an arbitrarily long time (which could include infinity). The speed is driven by the speed that the network can communicate. Rather than a fixed limit of X seconds (be it known or not), it just happens as and when consensus is reached.

A synchronous network is at risk of DoS attacks because if an attacker can slow down the network sufficiently then a synchronous protocol becomes unsafe and unable to operate. Dr. Emin Gün Sirer (Associate Professor at Cornell University and co-Director of the IC3 Initiative for Cryptocurrencies and Smart Contracts), who reviewed the paper prior to distribution, noted in an interview with ETHNews that “Despite Team Rocket’s methodologies only satisfying the more rudimentary synchronous byzantine fault tolerance, the new family reaches a level of security that is simply good enough, while surging forward with other advancements.” Google ‘Scalability Trilemma’ if you wish to know a bit more about the potential trade-offs teams make between decentralisation, security and scalability.

One point to highlight is that the paper assumes that no malicious actor can interfere in communication between correct nodes. This would seem to be ignoring potential attack vectors. However, as Gün Sirer clarified for me:

“The adversary model in this paper is incredibly strong. The adversary gets to see everyone that I communicated with, what they told me, and then gets to adjust his response accordingly. Real adversaries will not be this strong.

The statement that an adversary cannot interfere with communications allows the protocol to avoid having to make standard cryptographic assumptions for the consensus protocol. There’s no PKI. No reliance on crypto. This protocol is quantum-safe from the start.”

That said, it is important to note that this paper is not presenting a definitive protocol for instant use, but rather is putting forward the framework for a protocol that can be taken and used by projects in a similar way that PoW was used in Bitcoin but can also be used in a whole host of different projects.

As such, the paper is putting forward a series of test conditions that the team has tested it against. However, the absence of more stringent test conditions does not necessarily mean that the protocol is not capable of meeting them. It just means the paper is not covering the testing of them. In such a vein the team “conjecture that our results hold in partially synchronous networks, but the proof is left to future work”.

Guarantees

Finally, the paper describes that Avalanche provides the ‘following guarantees with high probability’:

• Safety: No two correct nodes will accept conflicting transactions.
• Liveness: Virtuous transactions will eventually be accepted by every correct node.

A virtuous transaction is defined as one that is issued by a correct client and does not conflict with another transaction. The paper subsequently notes that rogue transactions are not guaranteed liveness in the same manner and therefore may stall the network (presumably as they are ignored/not processed/left to rot) — we will come to how the network differentiates between virtuous and rogue later on.

Hopefully I have explained what Avalanche is trying to do and what it is aspiring to be. I will now move on to look at what Slush, Snowflake and Snowball are and how they build up to become Avalanche (I’m not sure if it’s just because I’m writing it out so much, but the name is really growing on me). You can find Part 2 here.

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 there.

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).