# Echo PoWR: Fast and Final Consensus Based on Proof of Weighted Randomness¶

[email protected]

March 2019 WORKING DRAFT

## Abstract¶

EchoRand is the consensus mechanism used by the Echo protocol to provide fast and final consensus on which set of transactions to append to a distributed ledger. By randomly selecting validators for each block rather than forcing every node to validate every block, EchoRand minimizes the resource requirements of running a node without compromising speed or security.

## Introduction¶

### Prior Work¶

The ability to reach network-wide agreement about the next suitable set of transactions and adding them to the ledger (e.g. the blockchain) is a critical property of any distributed ledger. This property has important implications for the censorship-resistance and resiliency of the network, as an adversary who disrupts this consensus process can prevent any new economic activity from happening on the protocol. The task of determining which actor (or committee of actors) in a decentralized network have the right to propose new blocks for addition to the ledger has been addressed by different protocols:

• Proof of Work (PoW): The actors with the highest computational power compete for the ability to add blocks, resulting in massive real-world hardware and electricity requirements to participate in block generation ("mining"). Anyone can permissionlessly join or leave this competition by adding their computing power to the network. The network functions properly as long as 51% of computing power ("hash rate") is held by honest actors.
• Proof of Stake (PoS): Network actors can lock ("stake") some or all of their token balance as a security deposit in order to earn the right to participate in block production. Their participation is proportional to the number of tokens staked, and this token deposit can be destroyed ("slashed") if they are proven to harm the network. The network is secure as long as 51% of the locked currency is staked by honest actors.
• Delegated Proof of Stake (dPoS): A fixed-size committee of actors has the ability to generate and verify blocks. Actors can only join this committee by a vote of the entire network and votes are weighted by the number of tokens that each network actor holds. This model most clearly parallels a representative democracy, where elected leaders are known publicly and are competing to offer the best service to the network so they will continue to be elected. The security assumption is that at least 51% of the committee members elected by the network votes are honest actors.
• Proof of Weighted Randomness (PoWR): A small committee of block producers or block validators are chosen randomly from the entire set of network actors. There is no requirement to lock up or "stake" currency, add computing power, or earn the votes of other users - every network user is eligible. The likelihood of being randomly selected for the committee is proportional to a user's balance of tokens. This committee exists only for a single block, and a new committee is randomly chosen for each new block of transactions. The network remains secure as long as at least 33% of tokens are held by honest actors.

The concept for the Echo PoWR algorithm is the Algorand v9 1 theoretical work, a Byzantine agreement protocol proposed by Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos. Algorand v9 describes an algorithm for reaching consensus in a decentralized network by with Byzantine fault tolerance. EchoRand combines techniques from early proof of stake blockchains like Bitshares 2 as well as delegated proof of stake blockchains like EOS 3 with the cryptographic sortition of projects like DFINITY 4 and Algorand. EchoRand also introduces a novel incentive and delegation scheme to increase network security.

### Design Goals¶

In designing any distributed consensus system, one of the biggest challenges is balancing transaction throughput with centralization. On one end of the spectrum, Bitcoin is limited to ~7 transactions per second in order to minimize the resource requirements necessary to run a full validating node. On the other end, EOS requires 21 elected block producers to maintain extremely sophisticated hardware setups, getting high transaction throughput at the cost of increased centralization.

However, this tradeoff between centralization and throughput is not fundamental. Blockchains rely on the assumption that a majority of the network is always honest. If that is the case, it follows that a random sample of the network should also consist mostly of honest nodes (provided, of course, that the sample is large enough). That is the principle that Echo relies on.

Rather than forcing every node to verify every transaction, Echo selects a random set of validators for every block. As long as enough of the validators attest that the block is valid, every other node on the network can accept it without needing to conduct their own verification. This allows Echo to achieve high throughput without requiring each individual node to verify every transaction like Bitcoin or compute every virtual machine state change like Ethereum.

Echo operates with a different trust model than Delegated Proof of Stake systems, where only a limited set of selected actors can advance the network, thus bringing an undesired element of centralization and trust into the network. Instead, EchoRand allows for a greater degree of decentralization through the involvement of all users in the consensus process, produces trust through verifiable randomness and delivers performance by limiting the proportion of users required for consensus in each round.

The major goal for creating the EchoRand consensus mechanism is to reduce the amount of explicit synchronization needed for reaching consensus in a distributed ledger. Other design goals include:

• Maximizing network throughput in terms of number of transactions per second for fixed bandwidth
• Minimization of bandwidth and compute resources needed for the optimization of network operations
• Decentralization - all decisions within the network are made by a consensus of the network participants
• High resistance to any malicious actions by any network actors, including failure to propagate messages and sending contradictory messages
• Fast finality, meaning that once a transaction has been successfully added to a block, it cannot be reverted
• Resistance to blockchain forks and reorganizations

Practical requirements, conditions, and goals:

• Source code that is as simple and easy to audit as possible
• Isolation of the consensus algorithm implementation from other aspects of the network
• Programmatic separation of the Graded Consensus (GC) and Binary Byzantine Agreement (BBA) steps, to allow each to be changed or replaced independently

## Overview¶

In EchoRand, as in other distributed consensus systems, sets of network transactions are organized into a block, which is logical database unit for storing a transaction set and the related data (e.g. signatures), that can be verified by external means.

EchoRand is based on the concept of splitting the process of adding a new block of transactions to the distributed ledger into separate parts and randomly assigning each role to a set of nodes. A network node is a server running the echo_node process (with a local configuration and database), connected to other Echo network nodes and running an instance of EchoRand consensus.

There are three distinct roles in EchoRand consensus:

• Producers are a set of nodes responsible for the construction of a new block from unconfirmed transactions. Producers propose the next block to be added to the distributed ledger.
• Verifiers are a set of nodes responsible for validating a block proposed by the producers and reaching Byzantine agreement among the set of verifiers about which proposed block to add to the distributed ledger. There is a different set of verifiers for each consensus step.
• Acceptors are all other network nodes. They play a passive role, simply accepting an approved block signed by verifiers and appending the block to their own local instance of the distributed ledger.

EchoRand consensus is performed in rounds, with either a new block of transactions or an empty block being appended to the distributed ledger after each round. Each EchoRand round consists of three main steps:

1. Cryptographic Sortition
2. Block Generation
3. Best Block Voting and Application

### Cryptographic Sortition¶

At each round, a new set of producers and verifiers is selected from all nodes in the network in such a way that:

• The distribution of roles for the round is not known to any node in the network before the round begins.
• The assignment of roles for the round can be computed independently by every network node, without the need for any explicit communication or network-wide coordination to occur.
• The distribution of roles for any future round cannot be predicted in advance by any network node.

To accomplish this deterministic yet random assignment of roles, EchoRand uses a verifiable random function (VRF) 5, which is a pseudo-random function that provides publicly verifiable proofs of its outputs' correctness, originally introduced by Micali, Rabin, and Wadhan. Using a VRF, each network node can independently check if it is assigned the role of a producer or verifier for a given round and send cryptographically proof of that assignment to other network nodes along with the proposed next block (for producers) or signed next block (for verifiers).

The size of sets of producers and verifiers is globally-known and configurable. It can be dynamically adjusted to accomplish the best trade-off between security and performance. As a safeguard against Sybil attacks, each node's probability of becoming a verifier or a producer for the round is directly proportional to that node's account balance.

Each EchoRand block contains a set of proposed transactions and a randomness seed, which is a pseudo-random value that changes for each block and round. This seed serves as the basis for generating the sets of block producers and verifiers using the VRF. Every node in the network can verify that seed was generated by a block producer in accordance with network rules and thus it was not manipulated by the producer. However, there is no way to predict what seed should be generated by each producer in advance of receiving that seed from the producer.

A new EchoRand consensus round begins after a node receives the latest signed block and its randomness seed from its peers. That seed is then used to generate secondary random numbers. Using the same publicly known deterministic algorithm on every node of the network and the same seed as an input for that algorithm, the same set of secondary random numbers is independently generated for each round by each node in the network without any explicit communication between nodes. Each node in the EchoRand network maintains special uniformly organized ordered map of accounts and their balances. Using secondary random numbers and publicly known algorithm, each node in the network can independently identify the set of producers and verifiers for the round.

### Block Generation¶

The distribution of roles for the round is performed before the set transactions received with the last signed block are applied to the ledger of account balances. Therefore, the block producer, who generates both the seed and the set of transactions, is unable to manipulate transactions in the proposed set to affect the distribution of roles for the next round. Similarly, the producer is unable to manipulate the randomness seed for the next round, because its generation is verifiable by every node.

Once each node computes its role at the beginning of a round, the set of producers compile a set of unconfirmed transactions into a newly proposed block and broadcast it to their peers on the network, along with a new randomness seed.

### Best Block Voting and Application¶

The set of verifiers begin listening for proposed next blocks and begin the process of voting for the best block using a 2 stage Byzantine fault tolerant (BFT) consensus process. At the first stage, Graded Consensus (GC), each verifier announces their preliminary determination regarding the best block to append to the distributed ledger in a three-step process. The second stage, Binary Byzantine Agreement (BBA), Byzantine consensus is reached through the transfer of binary data between the verifiers and a reconciliation of the overall state of the network. At each step of each stage, the protocol selects a new set of verifiers - accounts that must perform an action according to the step of the consensus. The selection of verifiers is similar to the selection process for block producers, using a VRF on input data from a previous block. After BBA is complete, verifiers sign the best block and propagate it to the Echo network, where acceptors verify the signatures by verifiers and append the block to their own local instance of the distributed ledger.

## The EchoRand Mechanism¶

### Other Terms¶

• Executor - the network account selected in the step of the round for performing a specific consensus action
• Local configuration - a certain set of parameters accessible only to the running network node.
• Base (database) - a blockchain with a certain set of blocks, possibly "lagging behind" the state of most other network nodes. It stores public EDS keys of all the participants of the algorithm operation.
• Participant - a set of EdDSA private/public keys and an account balance within the Echo network. Basically, an Echo network user registered on a specific network node. A user can be registered as a participant only on a single network node at a given time. One network node permits registration of multiple participants.

### Legend¶

Symbol Description
$msg$ a message transmitted by a participating node to its peers during a specific step
$sig(x)$ the EdDSA signature of $x$
$H(x)$ the SHA-256 hash of $x$
$r$ the current round of the algorithm, which is equivalent to the number of blocks in the database plus one. $r >= 1$
$s$ the current step number of the algorithm in the round. $s >= 1$
$B_{r}$ a block created in round $r$, which equals to { $r$, $ID_{producer}$, $Q_{r}$, $H(B_{r})$, $H(B_{r-1})$, $sig(B)$, $PAY_{r}$, $CERT_{Br}$ }
$H(B_{r})$ the SHA-256 hash of $B_{r}$
$PAY_{r}$ the set of transactions contained in block $B_{r}$
$Q_{r}$ the shared randomness seed of round $r$
$sig(Q_{r})$ the signature of a random vector of the $r$ round
$sig(B_{r})$ the signature of a block of the $r$ round
$l(r)$ the round $r$ leader - determines $PAY_{r}$, creates $B_{r}$ and determines $Q_{r}$
$CERT_{r}$ a $B_{r}$ block certificate formed out of a set of bba_signature messages
$VRF(r, s)$ the ordered set of participants who act in step $s$ of round $r$
$VRFN(r, s)$ the ordered set of indexes of $VRF(r, s)$ participants who are registered on the current node and participate in step $s$ of round $r$
$id$ an account identifier in the blockchain
$A_s$ an array of account identifiers selected as participants in the step $s$
$N_s$ an array of $A_s$ indexes which correspond to the identifiers of users authorized on the current node in the step $s$
$l$ the id of the producer who is the leader in this round
$ctx$ the context of the current round as an object which contains all received messages for the round

### Parameters¶

The following algorithm parameters are set by constants, or configured at the echo_node startup and can potentially be adjusted within certain limits during the process of the algorithm operation.

Designation Description
$Λ$ "large" interval, the average time required to distribute a 1 MB message across the network
$λ$ "small" interval, the average time required to distribute a 256-bit message across the network
$N_g$ the number of block producers in a round, used in the function $VRF(r, 1)$
$N_c$ the number of block verifiers in a round, used in the function $VRF(r, s), s > 1$

## Security and Performance¶

Because the selection of block producers and verifiers is weighted by the accounts balance, EchoRand transforms the typical Byzantine fault tolerance requirement of 2/3rd of honest nodes to a more Sybil-resistant requirement that 2/3rds of balances are held by honest nodes. This assumption is also improved because the nodes with the highest balances have the most "skin in the game", and thus the most economic value to lose of the network is attacked. As long as 2/3rds of balances are held by honest nodes participating in consensus, the network will run at maximum performance, with no loss of capacity.

In the case that less than 2/3rds of balances are held by honest users participating in consensus, the network will begin to suffer from degraded performance in the form of empty blocks being added to the ledger. As this honest participation rate declines from 67% to 33%, the statistical probability of empty blocks being added to the ledger increases linearly from 0 to 100%.

With more than 67% of tokens held by an attacker, the attacker could continually disrupt the consensus mechanism and prevent new blocks from being added to the ledger or censor transactions, just as an attacking miner with 51% of the total hash rate in a proof of work-based currency.

## Incentives¶

EchoRand introduced a formal incentive scheme to reward accounts for participating in the consensus process either by running an active node or delegating to another active node. This incentive scheme is designed to balance the optimal security and performance of EchoRand network by incentivizing more accounts to participate in consensus whenever performance drops below optimal levels while maintaining adequate security and decentralization.

Under this incentive mechanism, the block producers which generate a block which is successfully added to the ledger are reward with some newly generated balance, similar to a block reward in Bitcoin. Additionally, all verifiers who participated in the voting and validation process of a successful block are also rewarded with a smaller balance. In the case that an empty block is added to the network, no nodes receive a block reward.

When the network begins to generate empty blocks due to a failure of consensus (whether because of an attacker or through low participation in consensus by honest users), the protocol increases the block reward through inflation in order to incentivize more rational users to participate in consensus. When the performance returns to the acceptable threshold, the block reward is decreased over time until it returns to the minimum inflation rate. Research is ongoing into the idea rate of change and limits for the inflation rate.

## Conclusion¶

EchoRand is the consensus mechanism used by the Echo protocol to provide fast and final consensus. In EchoRand consensus, every account is automatically able to participate in the block production and validation process, either by running a node or delegating to an existing node. Each new block of transactions is generated by a committee randomly chosen from the set of all network accounts. There is no requirement to lock up or "stake" currency, add computing power, or earn the votes of other users - every network user is eligible. However, the task of securely choosing this committee out of the pool of all users would typically require a large coordination, communication, or computation overhead for the network. In addition, when this committee of block producers is announced by the network, the chosen actors could become the subject of bribe or DDoS attacks.

By randomly selecting validators for each block rather than forcing every node to validate every block, EchoRand minimizes the resource requirements of running a node without compromising speed or security.

1. Silvio Micali and Jing Chen. Algorand. Jul. 2016. URL: https://arxiv.org/abs/1607.01341v9

2. Daniel Larimer and Fabian Schuh. Bitshares 2.0: Financial Smart Contract Platform. URL: https://whitepaperdatabase.com/bitshares-bts-whitepaper/

3. Block.One. EOS.IO Technical White Paper v2. URL: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md

4. Timo Hanke, Mahnush Movahedi and Dominic Williams. DFINITY Technology Overview Series Consensus System. URL: https://dfinity.org/pdf-viewer/pdfs/viewer?file=../library/dfinity-consensus.pdf

5. Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable random functions. 1999. Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.

6. Descriptions of SHA-256, SHA-384, and SHA-512 from NIST. URL: https://web.archive.org/web/20130526224224/http://csrc.nist.gov/groups/STM/cavp/documents/shs/sha256-384-512.pdf

7. Daniel Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures". 2012. Journal of Cryptographic Engineering