Avalanche (Consensus Protocol)

Avalanche is a protocol for solving consensus in a network of unreliable machines, where failures may be crash-fault or Byzantine. The protocol was anonymously introduced on IPFS on May 2018 and was formalized in more detail by Cornell University researchers in 2019. The protocol has four basic interrelated mechanisms that compose structural support of the consensus tool. These four mechanisms are Slush, Snowflake, Snowball, and Avalanche. By using uses randomized sampling and metastability to ascertain and persist transactions, It represents a new protocol family. Although the original paper focused on a single protocol, namely Avalanche, it implicitly introduced a broad spectrum of voting-based, or quorum-based consensus protocols, called the Snow family. While Avalanche is a single instantiation, the Snow family seems to be able to generalize all quorum-based voting protocols for replica control. Unlike prior quorum-based work, the Snow family enables arbitrarily parametrizable failure probability at the quorum intersection level. Standard quorum-based protocols define this failure probability to be precisely zero, but by introducing errors in the quorum intersection, a larger set of consensus protocol design is available.

Background

Consensus protocols are the basis for the state machine replication problem, which aims to enable a set of machines to achieve agreement over a network even when a subset of the machines are corrupted. While consensus protocols have been researched since the 1980s, when they first became formalized with the work of Leslie Lamport and Barbara Liskov they have seen increased mainstream interest with the introduction of Bitcoin, which solves consensus over a network of participants that do have identities. There are two major families of consensus protocols to date - classical consensus and Nakomoto consensus protocols. The first achieves consensus through quorums, thus requires voting. Famous instantiations of this are Paxos (in the crash-fault-tolerant environment) and PBFT in the Byzantine-fault tolerant case. These protocols achieve agreement in a similar operation to a parliament: a proposal (transaction) is proposed and voted on to be accepted or rejected. If sufficient votes cast by the various replicas are accumulated (typically collected through elected leader replica), then a quorum is achieved, and thus agreement. The second family, pioneered by Satoshi Nakamoto and Bitcoin is that of Nakamoto consensus. Unlike quorum-based protocols, machines operating an instance of Nakamoto consensus achieve agreement on transactions by downloading the longest chain (typically called a fork). In Bitcoin, the longest chain is verified by ensuring that it is the one with the highest degree of work (or proof of work). Snow, while quorum-based, seems to be a universal generalization of all quorum-based protocols. Unlike prior work which requires that quorums be deterministic, i.e. the failure probability is precisely zero, Avalanche loosens this requirement, thus enabling quorum-based protocols to estimate global network state *with errors*.

History

The protocol's fundamentals were first shared on InterPlanetary File System (aka IPFS) on May 2018 by a pseudonymous group of enthusiasts going by the name “Team Rocket It was later developed by a dedicated team of researchers from the Cornell University. The research was led by Emin Gün Sirer, a professor of computer science and software engineer Kevin Sekniqi, both co-founders of AVA Labs, a startup technology company launched with the purpose to develop a faster blockchain network that would meet finance industry requirements. As a number of sources indicate, "the project was in the realm of academic circles interested in exploring consensus protocols that serve the same purpose of proof-of-work — securing transactions — but are more energy-efficient and have the potential to provide a basis for democratic development and the inclusion of more users in the consensus process". In March, 2020, the AVA codebase (Developer Accelerator Program or AVA DAP) for the Avalanche consensus protocol became open-source and available to public.

Assumptions

While the Snow family can be theoretically generalized to all classes of assumptions that quorum-based protocols have previously made, the formalization paper analyzes Avalanche under an asynchronous network in the Byzantine setting. The assumptions are as follows:

Processors

• Processors operate at arbitrary speed.

• Processors may experience arbitrary failures, even Byzantine ones.

• Processors with stable storage may re-join the protocol after failures.

• Processors can collude, lie, or otherwise attempt to subvert the protocol. (That is, Byzantine failures are permissible.)

Network

• Processors can send messages to any other processor.

• Messages are sent asynchronously and may take arbitrarily long to deliver.

• Messages may be lost, reordered, or duplicated.

• Messages are delivered without corruption, i.e. an adversary cannot forge digital signatures.

Safety and liveness properties

The Snow family generalizes the typical definitions of safety and liveness encountered in quorum-based protocols. For Avalanche specifically, these properties are:

Agreement (or consistency, or safety)

If any node (or machine) finalizes a value *v*, no other node will finalize another value *u* that conflicts with *v* with probability higher than $\epsilon$.

Termination (or liveness)

If network resumes synchronous operation, then all nodes will achieve agreement.

Avalanche, like other asynchronous networks, is not guaranteed to terminate and thus does not have the liveness property, during asynchrony. Like Paxos, Avalanche's goal is to ensure fault tolerance and it guarantees safety under asynchrony, but not liveness. This is in contrast to Nakamoto consensus, which guarantees liveness, and not safety under asynchrony.

Basic Operation

While Yin et al. formalize the Snow family up to Avalanche, the various optimizations introduced to make Avalanche viable for a real-world deployment make its operation complex. However, the basic Snowflake is simple to describe.

Snowflake

The basic primitive used by Avalanche, called Snowflake, is similar in operation to the SIR model, in that nodes in the system adopt the state of some subset of other nodes in the system. In other words, instead of the nodes in the system being in a state of susceptible, infectious, or recovered as in the SIR model, they are in a binary state of 0 or 1, and must decide between the two in order to reach agreement. The ability to achieve agreement over a binary decision implies the ability to achieve agreement over any arbitrary number of choices. This enables, therefore, consensus on transactions. Snowflake is most similar to Ben-Or's protocol for asynchronous consensus, but where the quorum is not deterministic, but rather probabilistic.

Initialization

Nodes in the system are initialized to either of the elements of a binary set. In the original paper, the nomenclature of red and blue to label the two binary choices is adopted. There is no preference between red and blue colors, and therefore nodes can be initialized arbitrarily between the two.

Algorithm

The operation is simple: every node u in the system samples a random set of size k of other nodes from its neighbor view and adopts the color that some threshold majority of the k nodes prefer. This procedure is repeated until the same color majority is observed for some number of consecutive rounds. An example to illustrate this procedure is as follows. Suppose the network consists of five nodes, {u1, u2, u3, u4, u5}, where the first three are red and the last two are blue. Suppose k is 3, and therefore every node samples two nodes are random (including itself, this makes a sample set of three). Suppose that u4 samples u1 and u3. Then, the new sample set for u4 is {u1 = red, u3 = red, u4 = blue}. Since red is a majority color in this sample, then u4 switches to red itself.

Snowflake and Ben-Or's Algorithm

Snowflake is a generalization of Ben-Or's algorithm. Ben-Or requires that every node in the system samples every other node. In other words, k is equal to the network size. Allowing for k to be smaller enables a wide array of new design spaces, although such change immediately introduces a non-zero probability of errors in every sample.

Industry impact and practical aspects

Although the decentralized finance (DeFi) is still in its nascent stages, the potential applications are numerous, such as online banking, trade, and investments among others. However, to realize the anticipated benefits of the consensus protocol, the technology must prove its technical realization in practice. A number of financial institutions showed cautious general interest for central bank digital currencies or CBDC. In March 2020, Bank of England started a public discussion on distributed ledger technology.

The founders of the protocol claim to have developed a faster consensus protocol in computer networks that has the potential to close the gap between centralized payment systems currently in use and blockchain limitations. Bloomberg cites the company to be able of processing 6500 transactions per second, which is still slower than Visa (that claims to process 24 000 transactions per second) but much faster than current crypto-technologies can provide. For example, Bitcoin has 6 transactions per second and Ethereum has 15. The source also states that the technology has the capability to "wall off" parts of the blockchain, thus making financial services available to separate legal entities (for example, countries or financial systems) following specific regulations and laws in different countries.

Criticism

The new protocol has been met with skepticism by industry experts and competitors. According to Coindesk: "Ethereum developer Vlad Zamfir said on Twitter that due to the nature of the protocols, they fail to combine “the best of Nakamoto consensus with the best of classical consensus” and "combine “the worst of both worlds,” due to aspects of the code that could lead to weakened security. “It’s not asynchronously safe and it’s probabilistic,” he said, later adding “We don’t get to take a probabilistic model of the network for granted [in my opinion]”. As Wired states: "...none of the upstart networks have been fully built out, meaning their promised improvements are still mostly theoretical." Georgios Konstantopoulos, an independent consultant on blockchain scalability argued that "...scaling a decentralized network, at its core, means not only maximizing throughput and minimizing latency but also allowing any node to sync the chain. For this reason, a network should not require every node to process every transaction. ...This is not an “apples to apples comparison.” AVA is starting from a clean slate, whereas to sync Ethereum’s blockchain a new node must download more than 200 gigabytes"

See also

• Fault-tolerant computer system
• Replication (computing)
• Paxos
• Virtual synchrony
• Raft
• Chandra–Toueg consensus algorithm