Avrio: What, When, Why, How?

Through this article, I hope to answer the most frequently asked questions, and explain the core protocol is easy to understand, high-level terms. If you have any further questions, please check out the discord

Photo by NASA on Unsplash

What?

Probably the most asked question of them all. What is avrio? Avrio is a disconnected polytree DAG-based cryptocurrency with a focus on scalability and speed. Woah. Let's break that down.

Polytree DAG. This refers to one of the key differences in avrio. Rather than having a single blockchain (like in the diagram) as used in bitcoin, ethereum and other large cryptocurrencies, in avrio each wallet has its own blockchain

A normal, single blockchain setup

Avrios blockchain layout, in each circle, is their block height relative to their chain, with red lines showing linkage via previous block hash and block lines showing receive blocks (in blue) referencing the send blocks (in black)

You might wonder why we do this. In BTC one huge issue is sync times. To securely participate in the network (eg send transactions), you must download and verify an entire copy of the whole blockchain to validate future transactions. While there are methods o reduce this (eg block pruning, light mode, etc) they reduce security and still require you to download and process transactions irrelevant to you. In avrio, this is not needed. Let's say Alice wants to import her wallet to her phone. It already has some funds in it. She takes her private key and enters it into the app on her phone. In BTC her phone would then need to download the entire blockchain to find her balance, or used a node and trust it is not lying to you. However, in avrio, all her phone has to download is her own chain (as well as a very small amount of data about some other chains, which we will explain later). That means a phone can sync in a matter of seconds, as opposed to the days and weeks needed for BTC nodes.

The splitting of each wallet onto its own blockchain also has another desired effect. The key problem avrio is trying to solve is scalability. There are plenty of very well written articles explaining this problem which I recommend you read, but in summary, sharding is splitting tasks (eg validating transactions) across multiple nodes. In BTC every node has to validate every block and transaction. At the time of writing, BTC has about 100,000 nodes and a block has ~500 transactions in (on average). This means a single block results in 50000000 transaction validation operations. That is a huge number. In avrio, validators (more on them later!) are grouped into committees, collections of multiple validators who are tasked with validating a certain subset of the network. As each wallet has its own blockchain, creating these subsets is simple.

How?

Now we understand what avrio is and what its goals are let's start explaining how we do this. If you are more mathematically inclined or would prefer a more in-depth explanation you should check out our whitepaper instead.

First off, let's define some basic terms. A transaction is a data structure called by a user, the sender, that executes a certain task. In most cases, this will be transferring funds from the sender's balance to the linked receiver's account.

A node is any server running the avrio software. There are multiple ‘levels’ a node can be at. The top one is observer, these are nodes who keep a full, unpruned copy of every blockchain in the avrio network. These nodes are most often run by large services using avrio to allow them to quickly access and validate data within the avrio network. While there are MANY other levels a node can run on, the only one you need to know about is the default one. At this level, the node only keeps a copy of its own blockchain and the bare minimum about other chains (as well as the consensus chain).

A verifier is a node that has registered to take place in the consensus of new blocks, and in turn, receives rewards. These nodes are organised into committees and manage a certain subset of the network. You will also see these nodes referred to as ‘fullnodes

A shard is a subset of the networks blockchains. Each committee (other than the consensus committee) is assigned a single shard.

A committee is a collection of verifiers/ fullnodes. The number of fullnodes in the committees depends on the number of online fullnodes. The amount of committees is near-constant, with changes to it requiring a hard fork. Committees have two tasks, depending on their type. The consensus committee is the first committee to be created during committee sampling. It coordinates the epoch and is the committee with the task of creating epoch salt/randomness, managing new validator memberships and sampling the next epoch’s committees. Every other committee is tasked with validating blocks sent from its shard.

A block is a collection of transactions, all from the same sender. There are two types of blocks. Send blocks, and receive blocks. Send blocks are created by the sender’s wallet. They contain new transactions, all sent by the block creator. Receive blocks are created by committees. When a committee hears about a transaction in which one of the receivers is managed by it, it creates a receive block for that chain. More on these later.

An epoch is the period of time in between committee members being shuffled.

Now we have these definitions out of the way we can proceed to explain the core mechanisms underlying avrio.

First of all, how does an epoch start? At the end of each epoch, the consensus member elects a ‘round leader’. This is done by finding the member with the public key, hashed with some deterministically random value to protect against an adaptive adversary) closest to the current epoch salt. This is a non-interactive method of sortition, every node on the network does this. Once the round leader has been chosen, every member of the consensus committee produces a VRF: a verifiable random function. I won't go into the specifics of VRFs in this article, all you need to know is a VRF takes in a message and private key and produces proof and (from this proof) a random number. This proof can be used to check if the number is truly random or if it has been tampered with. Using this VRF, no node is capable of affecting the epoch randomness. Once every member of the consensus committee has produced a VRF, it sends this proof and the random number to the elected round leader (using the GUID p2p system described later in this article). Once the round leader has signatures from at least 2/3 of the committee + 1, they also produce a VRF. They bundle all of these VRF proofs into a transaction. This is not a normal transaction, instead, this type of transaction (announceEpochSaltSeeds) can only be sent by the round leader of the consensus committee once per epoch. This special transaction is put into a block on the ‘consensus chain’. The consensus chain is a special address that cannot be sent to and does not have a balance. Instead, it contains only transactions sent by the round leader. Once the round leader has created this block and got its BlockChunk (these are explained in later paragraphs) signed by enough members of the committee ((2/3)+1) it broadcasts it to the network. When a node sees this special transaction it can calculate the next epoch randomness. To do this, the node first validates each VRF. If they are valid, the node takes every VRF and combines it into a single number. As this is done by every node, it can be assumed after this transaction each node will have correct epoch randomness which can be used as a seed for various operations requiring deterministic randomness.

Once this transaction has been broadcast, the epoch progresses to the next stage. This is the stage in which new fullnodes can join the network. To do this, every fullnode candidate (nodes who have previously submitted a special transaction showing they want to become a validator) produces a VRF. The candidates do not broadcast this VRF yet. Instead, they first check if it is below a certain value. This value acts as a threshold and regulates the number of fullnodes who join the network each epoch. This is based on the partially interactive VRF based sortition method introduced by algorand. The specifics of this sortition can be found in our whitepaper, or in articles about algorand. If a candidate’s produced VRF is below this threshold it sends this in a special type of transaction to its own chain. When the consensus committee sees this, it first checks the VRF is valid and is below the threshold. If it is, the round leader is notified. This stage lasts a set period of time, which is still being decided, but it will be short around a few minutes long. Once this stage is complete, the round leader checks they have a full view of the candidates who have submitted a VRF by asking the other members. They then do two things:

1. Form a new VRF, with the previously generated epoch salt as the message and put this in a special transaction (announceShuffleBits). This new VRF is called the shuffle bits and is the number used to shuffle fullnode member lists
2. Create a new special transaction (fullnodeDeltaListTx) ncontaining the hash of the transaction each VRF was broadcast in, as well as any fullnodes who are no longer validators/fullnodes and the reason (more on this later).

The same process as with the first special consensus committee only txn takes place on these two new transactions, resulting in a block chunk being broadcast. This last block chunk officially marks the end of the current epoch and the start of the next. However, before the fullnodes can start their usual tasks they must derive the members of each committee. To do this, they first apply the new fullnode entry and exits (as broadcast in the fullnodeDeltaListTxn) to their fullnode list. This list is sorted from the largest public key to the smallest (big-endian order). Then this list is shuffled using the fisher-yates algorithm, if you are not familiar, it allows you to shuffle a vector of objects. To supply the needed random numbers we seed a deterministic, platform-agnostic RNG like randchacha with the epoch randomness + the shuffle bits. This means any node (and every node does) who runs the shuffling operation on the fullnode member list will get the same result. After a node has shuffled its member list, it spits the member list into a certain number of equal parts, the committees. This means if there are an odd number of fullnodes, the node at the end of the shuffled list will be ‘excluded’ and wait until the next epoch to partake in consensus.

Once a fullnode has figured out the committee it is in (by calculating the member list of each committee as above and checking it is not excluded) it calculates which members of the committee it need to ‘contact’ (eg make a connection with over the internet). Rather than trying to talk to every member of the committee, it is in (which would result in poor scalability with committee size) the member uses a kademlia like ‘p2p routing system’. In this system, a node connects to 2 * log(commitee_size) members in the committee. I won't go into the specifics of figuring out which members the fullnode connects to, but know it is a function of the fullnode’s and members’ public keys. If you want to know more about this GUID p2p routing system look into kademlia.

Once the fullnode has contacted all the members of the committee it needs to it begins the ‘main loop’ of the epoch. If the node is in a ‘normal’ (not consensus) committee it has two functions:

• Validate, enact and include in block chunks blocks sent by wallets included in its shard
• Form receive blocks for the wallets it does manage when they are included in another chains block

The main stage starts by electing a round leader in the same way previously described for the consensus committee. However, in the main loop of an epoch, this differs slightly. The target value (the value the round leader’s public key hashed with the epoch salt + round leader must be closest to) is the hash of the round number (how many ‘rounds’ or elections have taken place during this epoch) + the epoch salt + epoch number + previous round leaders public key. For the first round in an epoch, the previous round leader field is omitted. Once a round leader has been chosen the round begins. This uses algorand’s binary Byzantine agreement system. Normally this system works as follows:

• Round leader proposes a block containing transactions
• Round leader signs block and send to the other committee members
• Committee members validate the block and sign it, returning the signature to the round leader
• The rounder leader collects signatures if it does not get 2/3+1 signatures within a certain period of time (hardcoded, a few 10s of seconds) a ‘empty block’ is used which contains no transactions and the round aborts. The round leader collects these signatures, and once it has enough broadcasts them along with the block to the network

However, to use this system in avrio effectively requires some changes:

• Blocks are created by wallets (other than receive blocks) and hence the round leader will not create a block but rather just propose it
• Most blocks will have only 1 or two transactions, processing each block in a committee one by one is inefficient. Instead, we will group multiple blocks together into a block chunk, much like normal coins groups multiple transactions into a block. For small networks with infrequent transactions, this block chunk will contain only one or two blocks, however, larger networks could fit 100s of blocks into a single block chunk.

Therefore avrio’s modified the form of the binary Byzantine agreement system, the avrio byzantine agreement protocol (ABAP) works as follows:

• The round leader groups any blocks waiting to be processed by its committee into a block chunk
• This block chunk is sent to the members of the committee using the GUID p2p routing system described before.
• The peers return a BLS signature on the block chunk’s hash (the Merkle root of the included blocks hashes + some data regarding the round, proposer etc) if they believe both the chunk and all included blocks are valid
• The round leader collects signatures if it gains quorum before the round aborts it aggregates each signature into a single BLS signature, and sends this signature along with the hashes of the blocks included in the block chunk to the consensus committee.
• If a block chunk fails to gain quorum within the time limits an empty block chunk is instead used
• The next round leader is elected and the process starts again

As you can see, ABAP is very similar to BA* as proposed by algorand, with key differences to make it more performant in avrio. The true magic that makes the system faster than normal full validation is BLS aggregation. BLS signature aggregation allows you to take n signatures on the same message (in this case the block chunks hash) and combine them into a single, 32-byte signature. That's right, using BLS aggregation we go from O(n+1) signature validation operations to O(1). This is vital, using this method even a low power CPU can validate around 50,000 block chunks per second. That means if only 1 block is included per block chunk and each block has only 1 transaction in (‘worst-case scenario’) the network has a TPS validation speed of ~20,000 * committee count (the reduction to 20,000 accounts for intra-committee communication delays as well as a small delay to ensure enough non-fullnode nodes accept the block chunk). Not only this but unlike other signature-based Byzantine agreement protocols, the size of block chunks does not change with committee size, rather it is fixed at 32 bytes.
After a block chunk has been sent to the consensus committee the next round leader can be elected, and the process restarts. If a block chunk is not produced within or does not gain quorum before, 30 seconds, the round ‘aborts’. When this happens nothing has to be sent to the consensus committee, and the next round starts. In a small network, 99% of rounds will abort, however in an active network with frequent transactions the number of aborted rounds will be very low. This process repeats until the ‘end’ of an epoch (when a valid consensus block containing a shuffleBitsTxn & a fullnodeDeltaListTxn is received). While forming a block chunk a round leader also forms receive blocks for any send blocks affecting its committee’s managed chains. These formed receive blocks are then processed and included in the block chunk in the same way as blocks sent by the committees managed nodes.

In the consensus committee, however, the main epoch process is quite different. During this time, the consensus committee acts as a coordinator of the different committees. They receive the block chunks from each committee, validate the signatures and then announce them to everyone else. When a committee needs to see if a block (sent by a wallet it is not managing) is valid and has been accepted it simply asks the consensus committee for any block chunk containing this and validates it. When a member of the consensus committee receives a block chunk from a committee, it validates it (the signatures, not the contained block) before sending it to every peer in its GUID routing table. It also announces it to any non-fullnode nodes that it is connected to.

This is an oversimplified and reduced explanation for avrio’s core protocol. It does not include many features like usernames, the avrio voting system (AVS), or other unique features of avrio. These will be talked about in future articles. If you want to learn more about the protocol I would recommend reading the whitepaper (when released, currently no up to date whitepaper is available) and joining the discord to ask any questions.

When?

Now you have a basic understanding of the avrio project I hope you are interested. Avrio is currently under development, with the implementation being coded from scratch in rust by myself (Leo Cornelius). I am making good progress, and while I don't like to give dates or ETAs it is safe to assume it is still at least a couple of months away from production use. Before then we will have numerous public testnets and trials, so make sure to join the discord if you are interested in taking part. I am also currently the sole developer on the project, so if you are interested in contributing please do reach out. I am also looking for people with other skills, such as marketing, advertising, community moderation, etc to help out with avrio. If you believe one of your skills could be of use to us please do not hesitate to contact me.

Previously avrio had a PoW cryptonight based coin to aid the distribution before the above protocol is implemented. However, this was obviously a flawed decision, and hence the PoW based network is scheduled for decommissioning. All coins from that network will be swapped to the new network at launch with an undecided ratio (eg 10 coins on the Pow network will get you 1 coin on the new network).

Why?

All this is great, but do we really need a shardable coin?

Yes.

Some may disagree and argue we can still optimise blockchains further to improve performance, before using sharding. This is true, and avrio will do this. It will start off with a small number of committees (eg 10) which will grow as demand increases. Avrio is meant to be a stepping stone towards a fully scalable, sharding based cryptocurrency. It would be naive to assume avrio ‘solves’ the sharding problem; there will undoubtedly be improvements to avrios protocol as events unfold which improve it. I hope by providing a reference implementation of avrio will inspire future revisions as well as protocols. Avrio isn't the first coin to tackle sharding in a byzantine environment, and it won't be the last!