| description |
|---|
An overview of the consensus mechanism used by Echo to achieve fast finality. |
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 (e.g. Bitcoin) : The actors with the highest computational power compete for the ability to add blocks, massive real world hardware and electricity cost 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 (e.g. Casper): 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 amount 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 (e.g. EOS): A fixed-size committee of actors has the ability to generate and verify blocks. Actors can only join this committee by vote of the entire network and votes are weighted by the amount 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.
In EchoRand consensus, every user 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 pool of all network users. 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 be come the subject of bribe or DDoS attacks.
EchoRand solves this issue of coordination through a cryptographic trick called a verifiable random function (VRF), which is a pseudo-random function introduced by Silvio Micali, Michael Rabin, and Salil Vadhan. Using this VRF, each user essentially participates in their own, individual lottery to determine if they were a "winner" for that given block, with the winning tickets eligible to participate in block production. The key innovation is that each user can do this by themselves, without any coordination necessary with the other users. However, all users can easily validate if a ticket is an unforgeable, cryptographically signed "winning ticket". In addition, each users likelihood of winning the lottery is proportional to their balance of tokens.
Once each EchoRand user participates in this lottery, called cryptographic sortition, the "winners" immediately generate a block of transactions and broadcast it to the network, along with their winning lottery ticket. In this way, the network only knows who is chosen as block producer when the block has already been shared with the network, eliminating the opportunity for bribe and DDoS attacks.
Once the signed blocks are broadcast to all users, a similar "lottery drawing" is held for an additional set of winners who participate in verifying the block and voting on it's validity. The set of winning users in this lottery "verifiers" come to consensus on the best block to add to the network through Byzantine agreement, and once agreement is reached, all users on the network add the block to their local copy of the ledger.
All users are eligible to participate in every lottery to determine if they have a "winning ticket" to serve as a block producer or verifier for each block. The only requirement is that after every block is finalized, each user must independently run the VRF computation to generate a "lottery ticket" for the next block. This requires that the user have an online node that's connected to the rest of the network and the ability to sign new blocks with their private key. Although EchoRand is designed to be minimally resource intensive for node operators, the protocol recognizes that every user may not be able to run their own node, and provides a way to "delegate" the block production role to another node by providing a type of secret key called a delegation key, which allows another user to participate in consensus on their behalf but not spend funds from their account. Because of these feature, every user should be able to participate in the consensus mechanism either by operating their own node or by delegating that right.
EchoRand consists of three main steps:
- Cryptographic Sortition
- Block Generation
- Best Block Voting and Application
For each block, a new list of possible producers is determined with the help of verifiable random function (VRF). The mechanism is as follows: for the nth block, we have a hash, which is the result of the previous block hash signing by the producer. Since the producer can’t affect the result of the hash function (as the data that is hashed and the private key are strictly defined), and the hashing is checked using public key, we receive a new pseudo-random number in each block. This number (hash) from the n block is used as a random index definition for selecting the first producer on the list to generate a block. The index of this producer is used to get the next producer on the list, etc. until a complete list of those who will offer the block is set up. Since all input data for the VRF is already included in the previous blocks, each node in the network determines the list of producers independently, and it is the same for everyone (deterministic). Each network node generates a list of producers for the current block and if the authorized account on the node is one from the list, it generates and sends the block to the network.
Voting for the choice of the best block takes place in two stages, which is divided into steps. 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.
This stage consists of three steps. At this stage, the goal of the verifiers is to vote and announce to the network which of the potential next blocks broadcast by producers they consider to be the best candidate for addition to the network.
Each of the selected producers generates new block and announce it to the network.
Each of the selected verifiers tells the network which of the blocks they consider preferable for the current round.
Based on the messages received from other verifiers in step 1, each verifier tallies the votes to determine which of the potential blocks got the most votes.
After receiving the voting results of the previous steps, all nodes know whether the verifiers were able to agree on the choice of the best block for the current round. Each verifier creates a message including information on the outcome (whether an agreement was reached or not) and the details of the block agreement and broadcasts this message to the network.
After this step, all nodes in the network have a preliminary idea of whether the best block has been determined or not. In an honest network, this would be enough to complete the round and append the block to the existing ledger. But since we allow the possibility of unscrupulous participants, the network needs an additional step to verify the data. This is the objective of the next stage.
At each step of the algorithm work, all nodes in the network can be divided into two groups:
1.) Nodes that have received a sufficient number of messages in the previous rounds with identical values, allowing them to settle on this message value as the correct one.
2.) Nodes that have received messages with two different solutions which are unable to determine which is correct ("unsure" nodes).
In the latter case, undecided nodes again use a VRF to generate a shared random number from the set of {0, 1} (e.g. a coin flip) to make a decision about which message to apply. Since the random number will be the same for all “unsure” nodes, all these nodes will reach the same decision on the outcome.
The stage consists of rounds, which include 3 steps each. At each step in the cycle, a new set of verifiers chosen by VRF sends their determination of the result vote in binary form. If, as a result of the round, 2/3rds + 1 (~67%) of verifiers agree on the outcome, the block is considered valid and appended to the chain. If consensus is not met, a new round begins.
If over 4 rounds (which involves 4 rounds x 3 verifiers = 12 unique, random sets of verifiers) the network is unable to come to consensus about which block to add, an empty block is applied by the network and the entire consensus mechanism begins again from the the very first step - cryptographic sortition for new block producers.
All network nodes receive all messages sent by producers and verifiers at each stage of the consensus mechanism. Based on these messages, each node independently determines which block to apply and append to the ledger. Nodes who are not selected as producers or verifiers for a given block simply listen for these messages to make their own determination about the outcome of the consensus process.
Because the selection of block producers and verifiers is weighted by the users balance of tokens, EchoRand transforms the typical byzantine fault tolerance requirement of 2/3rd of honest nodes to a more sybil-resistant requirement that 2/3rds of tokens are held by honest nodes. This assumption is also improved because the nodes with the highest token 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 tokens 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 tokens 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 hash rate in a proof of work-based currency.
EchoRand introduces a formal incentive scheme to reward users for participating in the consensus process either by running a full node or delegating to another node. This incentive scheme is designed to balance the optimal security and performance of EchoRand network by incentivizing more nodes 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 created tokens, similarly 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 amount of newly created tokens. 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 failure of consensus (whether because of an attacker or through low participation in consensus by honest users), the protocol increases the block reward (which inflates the entire token supply) 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.
For example, Bitcoin with PoW consensus can be forked when some block producers using different "parent" blocks on their generated block, in such case other nodes received two valid blocks and blockchain forks.
The number of steps of the algorithm and dependence on the state of the whole account database makes the possibility of forks unlikely. However, EchoRand still has a mechanism for choosing between diverging chains. The fork selection takes place according to one of the following scenarios:
- To switch to the longest chain (with the highest number of completed non zero rounds) in the presence of several chains.
- If there is more than one long chain at the end of a r-length chain, to follow the one in which the r block has the smallest hash value.
This process is based on algorand-v9 (9. Handling Forks, page 70). According to it the probability of forks is about 10^−12 or 10^−18.
Also we have constant (named ECHO_REVERSIBLE_BLOCKS_COUNT) that controls amount of reversible blocks and equals 15.
So if you block have number n, it will be irreversible after n + 15 blocks.
Irreversiblemeans that this block cannot be canceled as a result of a fork.