Pokémon is entering the blockchain space (Avalanche)

Pokémon is entering the blockchain space — Protocol Introduction: Avalanche

Pokémon: Team Rocket

Avalanche is a collection of consensus protocols, which has been introduced by Team Rocket in 2018.

“This paper introduces a brand new family of consensus protocols suitable for cryptocurrencies, based on randomized sampling and metastable decision. The protocols provide a strong probabilistic safety guarantee, and a guarantee of liveness for correct clients.”

URL: Whitepaper

Protocol family consists of the following four:

• Slush (non-Byzantine)
• Snowflake (+ Byzantine Fault Tolerant)
• Snowball (+ Confidence Counters)
• Avalanche (combination of all three previous protocols)

Slush, Snowflake and Snowball have been introduced in the whitepaper to have a better understanding of the concepts behind the final protocol: Avalanche. All the concepts and enhancements are incorporated into it.

Avalanche promises the following:

• Quick finality
• Low latency (2 seconds)
• Scalability (successful tests in 10k to 10m nodes network)
• Robust (there is no need for precise membership; anyone can join / leave the network at any time — similar to e.g. Bitcoin)
• Consumes no huge amounts of energy — contrary to Proof-of-Work chains

The protocol is built on a deliberately metastable mechanism. Metastability essentially refers to the concept that the system is designed to eventually bring an answer and will not stay in balance.

• All nodes come eventually to consensus
• Random samples support to tip it in one way or the other
• Facilitates the scaling through the random subset sampling (of the entire network)

Example: Every node must decide between two colours: blue or red. Even if the network starts off with a 50:50 distribution, it will tip in one way or the other, through the random arbitration.

Key differentiator to current Nakamoto consensus protocols:

• Deliberately Metastable
• TPS / Latency
• Inspired by gossip protocols (queries are triggering other queries, which are triggering other queries, ..)
• Significant trade-off: liveness for conflicting transaction (only guarantees liveness for virtuous transactions)
• Runs “sub-quorums” (random subset sampling), which enables smaller instances of consensus in parallel, thus higher throughputs can be achieved. A side effect is that not all nodes will be fully in sync with each other at any given time, but will all eventually converge on the same history over time.

Provides two guarantees:

• Safety: No two honest nodes will accept conflicting transactions
• Liveness: Any virtuous transaction issued by a honest client will eventually be accepted by every honest node

Traditional Consensus vs Nakamoto Consensus

The Traditional Consensus mechanisms have a quadratic communication complex O(n²) (n is the number of nodes in the network) and require accurate knowledge membership. This means for every additional node added it takes an exponentially greater time to share information to all other nodes.

Source: https://flatoutcrypto.com/home/avalancheprotocol

Whereas with Nakamoto Consensus (named after and introduced by Satoshi Nakamoto in 2009) there is no need for precise membership. The consensus is reached through Proof-of-Work in which a leader (here: miner) is “randomly” chosen to produce a block. It allows a certain percentage of Byzantine (adversarial) nodes in the network and still come to a consent. However it has some drawback like the limited scalability, the high latency and the huge consumption of energy as sybil resistance.

Avalanche estimates their communication complexity in the following range:

O(kn log n) to O(kn)(n = nodes; k = security threshold)

Synchronous vs Asynchronous Networks

The papers describes Avalanche as a synchronous network. Bitcoin, Ethereum and whole bunch of other blockchain projects are synchronous networks. There are quite a lot of good resources on the Internet, however a simplified introduction should be reasonable to grasp the main idea.

Synchronous means that there is a timing assumptions. A Bitcoin message, e.g. a block should be produced every 10 minutes (plus some buffer: Block timestamp — Bitcoin Wiki), an Ethereum message (block) every 15 seconds. It is basically a certain known time limit. Any block that take longer than this are timed out and are counted as invalid.

Where in asynchronous networks a message can take an indefinitely long time to reach peers and each node can take an indefinitely amount of time to respond.

Synchronous networks are vulnerable against DoS (Denial of Service) attacks, which can slow down the network and certain time limits cannot be achieved.

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

Slush is the simplest protocol of the family. Slush and the underlying metastability are easily explained with the following example:

1. Node receives transactions from a client and initiates a query
2. The node queries to a constant sized (k) sample of the network uniformly at random
3. 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
4. The querying node collects k responses and checks if a fraction are for the same colour
5. If the threshold is met and the sampled colour differs from the node’s own colour, the node flips to that colour
6. It starts again with the query step and initiates a subsequent round of query, for a total of m rounds
7. 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

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

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.

1. Upon every query, the node increases its confidence counter for the respective colour.
2. The node flips its colour, when the confidence counter for its current colour is lower than the confidence counter of the new colour.

Avalanche

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

Source: http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/graphs-intro.pdf

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:

1. 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.
2. 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):

1. A transaction T is queried, all transaction implicitly reachable from T (by following the edges) are also part of the query.
2. A node will only respond positively to the query if T and its entire ancestry is the preferred set for them
3. 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.
4. 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.

Source: Whitepaper <chits, confidence>

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.

Open questions

• Sybil resistance (e.g. having a big number of malicious nodes in the network) one possible solution would be token staking for reputation (to some degree like DPoS)
• With conflicting transactions (double-spends) can money be lost? e.g. like a penalty  — is Liveness affected? — What if a wallet is broken and accidentally sends two transactions?

If you are interested in Distributed Ledger Technoloy, Blockchain, Ethereum, Bitcoin and more:

ynkzlk (@ynkzlk) | Twitter

Sources

• https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV
• https://flatoutcrypto.com/home/avalancheprotocol
• https://flatoutcrypto.com/home/avalancheprotocolpart2
• https://en.bitcoin.it/wiki/Block_timestamp
• https://bitcointalk.org/index.php?topic=99631.0

Pokémon is entering the blockchain space (Avalanche) was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.