Comparison of PoS projects: Unbiased Leader Election

Introduction

Prior to the Bitcoin blockchain of “Satoshi Nakamoto”, distributed ledger systems were lacking two important properties which are essential for a decentralized digital cash system. The first property which existing distributed ledger systems were missing, was the ability to scale to a network of millions of users. And secondly, systems at the time were not permissionless, i.e. were not open to everybody to join the network at any time without the need to ask for permission.

The Proof-of-Work (PoW) blockchain by Nakamoto solves these two problems. But, one essential detail of PoW consensus, an innocent looking game-theoretic incentive to make users behave honestly, led to a very big “mining industry”. This in turn caused a strong concentration of “mining” power contradicting the philosophy of decentralization. Even if this could be resolved (see e.g. FruitChain), there is still the problem that to maintain a PoW blockchain consumes a tremendous amount of energy which increases with the network size.

Instead of providing a proof of having spent time and energy in mining (“work”), the basic idea of a Proof-of-Stake (PoS) based consensus protocol relies on distributing the rights to participate in the validation process on the basis of the amount of money the users have in the blockchain. Therefore, the consumption of energy in a PoS protocol reduces basically to the election of block proposers and transaction verification which is negligible in comparison to a PoW based system, and is per se not prone to mining power concentration.

Energy consumption and power concentration are not the only problems that PoW blockchains are faced with. To keep the blockchain secure, the block generation rate cannot be arbitrarily small (in fact, about 10 minutes in Bitcoin) which implies a limit in number of transactions per second. A PoS based blockchain can scale to hundreds of transactions per second, and committee-based PoS protocols can have (almost) instant transaction finality.

There are many PoS protocols, most notably Ethereum’s Casper PoS, and delgated PoS proposals, e.g. BitShares, EOS, or Steem. The documentation of Casper PoS provides an excellent introduction into PoS. In this short post we present an overview of a few other PoS consensus protocols. We restrict ourselves to a descriptive overview. See here for a starting point for fair PoS comparison metrics. We consider:

1. Algorand
2. Cardano (Ouroboros, see also Ouroboros Praos)
3. Dfinity
4. Snow White (based on Sleepy Model)

Preliminaries

A blockchain protocol allows building a ledger of all valid transactions passing through the network. The network nodes must order and verify the transactions, but since the network nodes cannot trust each other, the challenge is to have (1) a secure (2) agreement between the honest users. Let’s formalize this:

• Availability or Liveness: If an honest node outputs a new transaction, then it will eventually appear in everybody’s view of the ledger.
• Consistency or Safety: If one honest node adds a transaction X to its replica, then every other honest node will add transaction X to its replica.

As long as “enough” honest peers maintain the ledger, these two properties should be satisfied with an overwhelmingly high probability. Section 9 of the Ouroboros article provides a list of possible attack vectors on PoS consensus models. To name just a few:

• Grinding attack
• Desynchronization attack
• Eclipse attack
• Bribery attack
• Nothing at Stake
• Network splitting (–> CAP theorem)

How to elect Block Proposers and Committees

All of the four protocols proceed in rounds. The challenge of all protocols consists in having “unbiased” lotteries of block proposers in each round.  Some PoS protocols elect committees, i.e. changing subsets of the network, who validate the block proposal to speed up the finality of transactions. All this introduces new challenges. The election of the block proposer and the committee has to be unpredictable and safe against any adversarial intent to bias or prevent the outcome, and must be at the same time verifiable to everybody.

Election

Algorand: All users participate in the lottery and can win the ticket to become the block proposer or a ticket to be member of the validating committee in round r. Every user runs its own “lottery machine” fuelled with a public random seed and her/his private key. These lottery machines are verifiable random functions (VRF) (see this article). They produce uniformly distributed random values, and provide a non-interactive proof so that any other user knowing only the public key of the winning user can verify the outcome once the chosen lottery winner makes his ticket public. If the value of the ticket is close to some target value or threshold, this user can participate in proposing or validating blocks.

Cardano: Out of all the users who have a minimum of stake, a subset is elected which can propose blocks. Each round is subdivided into slots where each slot has one block proposer. The election algorithm takes as input a random seed generated in the previous round r-1. Their Follow-the-Satoshi algorithm chooses some (smallest units of) coins out of all coins on the blockchain, and the new block proposers are the owners of these coins. The protocol of Cardano does not elect a committee.

Dfinity: Out of all the registered users a subset is elected which is responsible to notarize blocks (see below).  Also, a block proposer is elected, and both elections depend on the random seed produced in the previous round r-1. Every round starts with an update of the set of all registerd users. The election algorithm for the committee uses a pseudo-random permutation on all registered users, and ranks all block proposals through the given random seed of round r-1.

Snow White: Similar to Algorand, all users pick a private and a public random seed to fuel their lottery machines. The users with a winning ticket in round r can propose blocks for this round. Users evaluate a pseudo random function (PRF) using their secret string and a public random string infered from a common reference string (CRS). This allows users to prove later on the correct evaluation of the random function. If the random string produced by user u is under some threshold, then this user is elected.  There is no committee elected.

Random Seed

Note that in PoW the first miner who solves the crypto puzzle is randomly picked from all the miners, and this is provable to the entire network. PoS protocols need other solutions to introduce randomness, and it does not suffice to just use peseudo-random functions, but also requires random seeds.

Algorand: The random seed is publicly known, but it can’t be controlled by any adversary. This seed is generated using the VRF in round r-1 for round r which the block proposer includes in the block. You can find more details in section 5 of Algorand.

Cardano: The generation of the random seed is based on a coin-tossing protocol. Each block proposer of round r-1 commits to a secret string (commitment phase) which they have to reveal at the end of the round (opening phase) and from which the random seed is derived. To protect the protocol against adversaries who will not open their secret, Verifiable Secret Sharing (VSS) is used so that honest parties can recover the secret even if an adversary withholds it.

Dfinity: The generation of the random seed is based on the threshold signature scheme BLS of Boneh, Lynn, and Shacham. It produces a random string, namely the public signature. This public key is independent of the members who actually participated in the signing process, and serves as a VRF.  Members of the committee of round r-1 produce the random seed of the next round r. As long as more than a  certain number of members participate, the random seed is generated without having all members fulfilling their responsibility.

Snow White: Snow White uses a Coin-Tossing protocol to produce a random string for round r which is used to avoid a “bad seed”, i.e., using a well-chosen seed allows being the leader for a long period of time. All users publish their commitment to their secret string.

Weighted by Stake

Algorand: Algorand’s VRF elects users by providing a probability proportional to their amount of money. If W is the total amount of stake and w the stake of user u, the probability of user u to be chosen is p = w/W. This implies that possessing two accounts or one account doesn’t affect the probability to be elected as long as the total balance of the user is the same. This is a good protection against Sybil attacks.

Cardano: The output of the Coin-Tossing protocol is used to randomly select one “coin” out of the total stake on the blockchain (Following the Satoshi algorithm). So, if this coin belongs to a user u, this user will be the slot leader in the next round. Hence the probability to be elected is proportional to the money the user has at stake. See here for a short explanation or Cardano, pp. 35.

Dfinity: The role of the stake in Dfinity’s protocol is to deposit money during the registration process which will be confiscated, in case the stakeholder misbehaves. The probability to be elected is not weighted by the stake, only by the random seed.

Snow White: When a user u has many coins, she/he is recommended to output the quantity along with the corresponding public key used in the hash query for determining the next block proposer. Snow White’s core consensus protocol does not specify the implementation and leaves it open in their modular composition approach. See Snow White, section 4, p. 13.

Consensus

At this state of the protocol, we have a block proposer. How can we quickly reach an agreement about the correctness of the proposed block? We will explain this only from a high-level perspective.

Algorand: It is based on a very fast Byzantine Agreement (BA) protocol, called BA*, to agree on proposed blocks. The committees are constantly changing how they proceed, so that attacks on committee members are not possible. Forks appear in a negligible probability.

Cardano: The consensus of Cardano  is achieved by the longest chain rule (“Nakamoto style”). Slot leaders are known during the round. The consensus allows faster block generation, but forks may occur which will imply higher confirmation time.

Dfinity:  A “weight” of the chain, indicates honest users on which the chain they should build on. The notarization committee uses aggregated signatures to ensure that only blocks propagated in the given round can be considered as valid. Block proposals with a timestamp or proof of publication too old are not considered to be valid anymore. This allows near-instant finality.

Snow White: The consensus is achieved by the longest chain rule. Slot leaders are known during the round. The consensus allows faster block generation, but forks may occur which implies higher confirmation time (in blocks). Snow White is build upon the Sleepy Model  which might be safer against vulnerabilities arising from sleeping nodes, i.e. nodes which are honest but off-line when chosen as the leader.

Closing Remarks

We note that PoS improve scalability, but are not solving the problem entirely. There are many interesting proposals to scale blockchain. The proposals range from sharding techniques to new blockchain architectures. Please see here for an overview, or DAGs for a good introduction to new blockchain architectures.  Some of the most recent scaling proposals are:

• PARSEC  from MaidSafe.
• Phantom from DAGs Lab (SPECTRE).
• Snowflake to Avalanche from „Team Rocket“.