Avalanche (Consensus)

From CryptoWiki

Basics

  • Protocol that was released last year (19-5-2018) by a pseudonymous group going by the name “Team Rocket,” referring to the villains of the Pokémon game series.
  • "Referred to as Snowflake, Snowball, and Avalanche, the protocols randomly sample network participants, and ultimately choose a single result, Sirer said. “They rely on randomness and they rely on random interactions and yet they ensure after the interactions everyone has decided the same thing.”"
  • A consensus of nodes that are synchronous which therefore allows for reliable 0 confirmations and faster block propagation, since transaction ordering will be predetermined and known before block creation. To make this work there has to be a sybil prevention mechanism, possibly PoS.
  • Whitepaper can be found here.

Consensus

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

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 protocols then good, because that is the inspiration for it." 

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

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.

Avalanche

Avalanche, the 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.

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: 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.
  • 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

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.

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

Bitcoin Cash

The Avalanche proof-of-concept is a consensus algorithm that adds Byzantine fault tolerant proofs to a blockchain network so nodes can differentiate between two conflicting transactions. The protocol communicates with nodes in real time in order to bring consensus in a more efficient manner. This is because Avalanche queries the network of nodes and asks them to come to pre-consensus on which of the two conflicting transactions are preferred.

People are often confused with Avalanche being applied to BCH because it’s also being used in a proof-of-stake (PoS) project, called Avalanche (AVA) designed by Cornell Professor Emin Gün Sirer. On the BCH chain, Avalanche is only being used for pre-consensus and runs parallel with the original proof-of-work consensus mechanism.

The speed at which BCH transactions are processed shows the transaction’s finality is typically 2-3 seconds or less. Essentially this means the transaction (tx) listed on the Avalanche explorer has reached a point at which it can no longer be reversed by a double spend, even though the tx is unconfirmed by miners.

“If used this way, it would give Bitcoin Cash the equivalent of nearly instantaneous confirmations while improving mempool synchronization and reducing the financial incentive to 51% attack,” the Avalanche blockchain explorer details. “As you can see, at present most transactions become irreversible after just a couple seconds — To take this from proof-of-concept to an actual consensus rule will require lots of testing, experimentation, data collection, code review, and soft fork activation rules.”

  • There are more (10-2-2019) advantages explained in a post written by the ABC developer Mengerian, who says not only is transaction finality fast, but the Avalanche protocol “provides a good mechanism for post-consensus defense against blockchain reorganization attacks.” 

Snowglobe

"An Avalanche-Based Pre-Consensus Protocol for BCH. On December 20, BCHD and Openbazaar developer Tyler Smith published first draft specifications for a protocol he calls “Snowglobe.” Smith’s Github repository says that Snowglobe is a propagation protocol for nodes using Nakamoto Consensus and it uses an Avalanche-based consensus algorithm for the process.

“This document specifies a propagation protocol for nodes of a Nakamoto Consensus network in which participants actively work to reconcile their local states against each other,” the Snowglobe specs state. “It enables nodes to sample each others’ state in order to determine which item in a conflict set is currently chosen by the most nodes, and to work toward a super majority of nodes choosing the same set of items.”"

Avalanche (AVA)

Athereum

"AVA Labs Announces Aethereum

Athereum is a “spoon”, or friendly fork, of Ethereum, which benefits from the Avalanche consensus protocol and applications in the Ethereum ecosystem."

Comparison and contrast between Snowball with GRANDPA

  • From this AMA on Athereum where one of the team members of AVA Labs answered (11-2019):

I'm not an expert in what the Polkadot group does, so I am speaking purely from my understanding and previous reading. Please read this response with that in mind. I am skimming this article to refresh.

From the claims I have seen, both GRANDPA and Avalanche emphasize safety over liveness with a focus on being asynchronously safe. They both emphasize voting schemes, but with Avalanche it is sub-sample voting, which is the difference-maker.

Voting protocols fall under the classical consensus family, so the GRANDPA algorithm appears to be achieving finality with classical methods. The message overhead of the fastest consensus algorithm, Hotstuff is O(n) (which our own /u/Tederminant is author on). Most classical implementations are O(n2 ) where "n" is the number of validators. The claim of fast finality implies they are in the classical protocol as well. I haven't looked into what GRANDPA is doing enough to say, but there is a possible choke point as the number of validators increase. That might be mitigated by an architectural decision as well. They also appear to require proof of finality, which to me implies some coupling of the transaction history and the consensus, but I may be wrong there.

The Snow family of consensus protocols is completely new and are amortized O(1). For any decision, you make approximately constant number of messages. The subsampling improves confidence. If you want to improve your confidence, subsample a bit more. Our consensus is completely decoupled from the transaction history. This is why we can lend our consensus algorithm so easily to other protocols such as Ethereum, creating Athereum."

Retrieved from "https://cryptowiki.me/index.php?title=Avalanche_(Consensus)&oldid=5052"