Proof-of-Approval: A Better Blockchain Consensus Protocol

12 min readMar 14, 2018

This article was updated for protocol updates on May 27, 2018.

Blockchains are ledgers. They record information (transactions, assets, etc.) in a ledger just like a government agency or a financial institution. What makes them different is that no single entity or organization owns or controls this ledger. This ledger is openly available for anyone to view. In addition, anyone can request to record a transaction in it, and subject to certain limitations, that transaction would get recorded. Once a transaction is recorded in the ledger, it should stay on the ledger forever. This property is typically called “finality” and simply means that if the ledger shows that someone owns something today, and he or she doesn’t transact or consume it, he or she will still own it the next year, the next decade or the next century.

How can a blockchain achieve all this functionality without having anyone trusted to secure this ledger? It is only possible by:

Having multiple parties working in their own self-interest, and
A protocol, or a step by step procedure, for parties to determine what goes in the ledger and what is in the ledger.

As one can imagine, the above mentioned protocol, called the consensus protocol, is pretty critical to the blockchain. In fact, a blockchain is considered only as secure and robust as its consensus protocol (A Survey on Security and Privacy Issues of Bitcoin). A poor choice of the consensus protocol will make the blockchain vulnerable to attacks, compromising its data and rendering it useless.

This post introduces a new, and perhaps better, protocol to achieve the desired features of a blockchain. Full description of the protocol can be found in the paper Proof-of-Approval: A Distributed Consensus Protocol for Blockchains.

Proof-of-Approval

A network using this protocol publishes blocks periodically at a predefined interval called slot. Each slot may create at most one block while some slots may not create any blocks. The protocol defines another larger interval containing a predefined number of slots, called epoch.

This protocol is permissionless, i.e., parties (nodes) are free to join and leave the network at will. For every slot, several nodes in the network having a minimum stake, are allowed to compete for block creation. Creator of the winning block is rewarded with fresh coins and transaction fees contained in the block.

A block must be approved by stakeholders holding a quorum of stake for it to be valid and placed in the blockchain. Block creators broadcast their blocks on the network and the receiving nodes validate and optionally approve the blocks. Nodes indicate their approval through an explicit message to the block creator. Approvers are allowed to approve as many blocks as they choose as long as the approved blocks share the same parent. If not, the approvals are considered conflicting and cannot be used. Approvers (with valid approvals) are rewarded in proportions to their stake in the network.

When the approvals exceed the required quorum stake, the block creators broadcast the collected approvals to the network. Creators of the next block would place these approvals inside the blocks they create. The approval stake stored inside a block also determines the owners of which coin rolls are allowed to create the next block. For every slot, the block creators build on the block containing the highest stored approval stake.

The last block of an epoch is special in the sense that it contains epoch approvals. Epoch approvals are similar to block approvals but are designed to receive approvals from nodes on slow or intermittent connections. Epoch approvers are awarded about the same as the block approvers but, unlike block approvals, requires little computation or network connectivity. Epoch approvals encourage all nodes, even those with limited computational or network capacity, to sign and approve the chain. Epoch approvals deter History attacks.

If the network encounters communication difficulties, it will continue to function as normal as long as a quorum of the stakeholders can be reached. If not, many slots will not create any blocks until the connectivity improves. A blockchain using Proof-of-Approval may look like Figure 1.

Fork Preference Determination

When a party first joins the network, or rejoins the network after a hiatus, it may receive multiple forks from other participants and must choose the preferred fork to build blocks on. It uses the following procedure:

If forks are unequal, select the longest fork. Note that the fork length is the number of slots spanned by the fork, not the number of blocks contained in it.
If the forks have any unshared epochs, first choose the preferred fork with unshared epochs (below) and reject other forks.
If there are still multiple forks, choose the fork with the highest approver stake stored at its head block.

Determination of preferred fork with unshared epochs:

For each pair of forks, determine unshared epochs and blocks and then determine parties having created any block, or approved any block, or approved any epoch, or signed any transaction (transferred or spent their stake). We call these the “signing” parties.
Determine the total stake fraction (of the total network stake) of all “signing” parties at the first separate block of each fork.
Select the fork with the larger signing stake fraction in the first separating block.

How is Interdependency of the Blockchain and the Stakes Handled?

Any stake-based decision process must take into account the changing stakes with every block of the blockchain, which in turn, are likely to be different in every fork. Inability to account for such stake changes may result in multiple different forks being preferred forks simultaneously resulting in failure of the blockchain. Proof-of-Approval resolves this problem with the following two properties.

Each block limits the maximum amount of stake that can be transferred (as a percentage of the total network stake). This prevents stakes of parties in different forks growing apart too rapidly. A typical implementation may put this amount to be 0.5%-1% of the total network stake.
Approvals are stored in the blockchain to prevent long-range attacks and resolve preference among forks very quickly. In fact, it takes only one additional block to determine the preferred fork.

Desirable Properties of a Blockchain

In order to meet its goals, a blockchain must have the following properties.

Security Properties

Since blockchains are distributed systems, they must tolerate system failures and malicious intent of the participants. A blockchain having many wonderful properties but unable to standup to such adversarial conditions will end up being controlled by the adversaries resulting in its failure. The following properties are used to gauge the security of a blockchain.

Adversarial Tolerance
It is the maximum fraction, of the most critical resource of a blockchain, that an adversary can control without gaining control of the blockchain. A blockchain’s performance is expected to deteriorate increasingly with increasing adversarial power eventually leading to its catastrophic failure.

Persistence
Persistence is the measure of durability of the records (blocks) in a blockchain. Unlike centralized ledgers where a transactions is perpetual once recorded, a transaction recorded on a blockchain may not be as durable, at least not for some time immediately after recording. For blockchains, persistence may be a probabilistic function of the number of blocks stored after the target transaction. What can cause a record to disappear from a blockchain? Blockchain network decision process can sometimes choose an alternate fork removing blocks in all other forks from the blockchain. Chances of a block being removed go down as additional blocks are added on top of a block.

Weak-finality and finality are points on the persistence scale that may be useful for practical purposes. Weak-finality can be considered a “good enough” durability of a transaction for e-commerce, e.g. shipping the goods. Finality, also called “strong consistency,” is durability comparable to the mainstream financial systems.

Other Desirable Properties

Liveness
Liveness property implies how often, compared to the target schedule, blocks are being added to the blockchain. If blocks are not being added, the blockchain is not doing its job of recording transactions. An ideal blockchain would add blocks exactly as scheduled without any empty slots. Most blockchains, in typical operating conditions, are able to achieve liveness close to their targets.

Fairness
Fairness property implies how easily can the reward process of a blockchain be exploited. Blockchains intend to provide reward in proportion to the resource most critical to them, which can be the mining power, the network stake or any other specified criteria. Parties would try to gain an unfair share of the rewards but should be deterred. An ideal blockchain would completely deter anyone trying to win an unfair proportion of the rewards.

Scalability, Transaction Rate and Sharding
Scalability of a blockchain is a combination of its transaction rate and sharding properties. Transaction rate is simply the result of its two design properties — the block-size and the block time-period. While a new blockchain can easily select these values, a public blockchain may require code upgrade and network consensus to make changes to these properties.

Sharding is a way to further increase the number of transactions stored in a blockchain by dividing each node’s workload to many nodes running in parallel. To adopt sharding, a blockchain may require code upgrade and network consensus.

In general, both transaction rate and sharding have more to do with a blockchain design choices than some extraordinary technology. Security, not the high transaction rate, is the main design concern of the most public blockchains today.

Comparison with Popular Blockchains

The comparison here will focus on security, the most critical aspect of a blockchain. Each blockchain’s and protocol’s own documentation and analysis are used here for comparison. In order to make the comparison easy to understand, numbers in identical situations are used instead of complex expressions.

The comparison looks at blockchains’ adversary tolerance along with their performance under those adversarial conditions. Two adversarial powers are used for comparison — 25% and just under 50% (no blockchain today can tolerate 50% or higher adversarial power). Persistence is compared by arbitrarily defining weak-finality to the certainty of “five nines” (99.999%) and finality to the certainty of “twelve nines.”

The following paragraphs discuss individual blockchains while Figure 3 shows the overall comparison result.

Figure 3: Comparison with Popular Blockchains

Ideal

An ideal protocol, if it were to exist, is used here as a gauge for other blockchains. As expected, it fully deters adversary (tolerance 100%) and offers instant weak-finality and finality (0 blocks).

Bitcoin

Bitcoin’s PoW protocol can tolerate 25% adversarial mining power. At 25% adversary mining power, it achieves weak-finality after 11 blocks and finality after 26 blocks have been deposited on the target transaction (On Settlement Finality). Since the protocol fails > 25% adversarial mining power, weak-finality and finality for ≈50% adversarial power are never achieved.

Ethereum and Ethereum with Casper FFG

Just like Bitcoin, Ethereum and Ethereum with Casper FFG use PoW which can tolerate 25% adversarial power and results in identical weak-finality and finality results. Casper FFG does not improve Ethereum’s adversary tolerance nor does not seem to have an effect on weak-finality and finality as defined for this comparison.

Ripple (XRP)

Ripple’s adversary tolerance is only 20% (The Ripple Protocol Consensus Algorithm) and therefore it never achieves either of the finality measures in our comparison.

Ripple calls itself an enterprise blockchain. While Ripple does use blockchain like data structures, and it does let nodes store data on their own computer systems, and it may be an “enterprise” application, but it is not a real blockchain because of the following reasons:

It does not solve The Byzantine Generals Problem (BGP). BGP setup states, “However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.” Ripple solves a trivialized version of this problem where it is easy to find a group of honest generals to work towards consensus.
It does not eliminate need of a trusted third party. As Nakamoto states in Bitcoin: A Peer-to-Peer Electronic Cash System, “… the main benefits are lost if a trusted third party is still required to prevent double-spending.” Ripple, on the other hand, allows and perhaps even requires manual interventions.

Steem, Tezos Alpha and EOS (DPoS)

The DPoS used by Steem, Tezos Alpha and EOS all rely on consensus protocol described in DPOS Consensus Algorithm — The Missing White Paper which focuses on the consensus process after the “block-producers” are chosen. That paper assumes that no more than 1/3 of the block-producers can be adversarial implying that the adversary tolerance of the protocol to be 1/3 of the total stake. But that would be completely wrong.

From papers How Many Steemians Are NOT Voting for a Witness? I Found the Answer! and Steem Secret #6: Witnesses Votes Give The Most!, we know that only about 7.5% of the users actually vote (or have proxy) for choosing the block-producers. It is easy to see that an adversary with 15–20% of the stake can dominate the block-producer selection process resulting in >1/3 block-producers be adversarial. Therefore, at adversarial stake of 25% or higher, it is unlikely that a transaction can achieve weak-finality or finality.

The adversarial tolerance of DPoS may actually be even worse. Since each party is expected to vote to elect block-producers, an honest party would only want to vote for another honest party. The only honest party one can be sure of is themselves. This is likely to fragment honest votes where most parties vote for themselves. On the other hand, the adversarial parties collude. This would result in adversarial candidates getting unfragmented votes and winning the block-producer spots. As a result, under adversarial attack, most block-producers are likely to be adversarial compromising the blockchain.

NEO

Using a variant of Practical Byzantine Fault Tolerance, this protocol achieves instant finality with maximum adversary tolerance of 33% of nodes. While this may sound fairly strong tolerance, it should be noted that it is 33% of nodes and not the 33% of the network stake. Breaking this blockchain simply requires 33% or a higher number of nodes to be adversarial.

Creating adversarial nodes will incur compute cost. Using DigitalOcean’s tiny droplets, one can create 10,000 nodes at the cost of mere $70/hour. A NEO blockchain with 30,000 nodes can be overtaken simply by $70 of compute expense!

Cardano

Cardano uses Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol for its consensus. It is a well thought out protocol that does exceed capabilities of DPoS of Steem and EOS.IO. At 25% adversarial stake, it performs reasonably well but around 50% adversarial stake, achieving weak-finality and finality takes thousands of blocks.

TON

TON blockchain makes a lot of claims but doesn’t disclose any information regarding how those claims are actually achieved. Simply put, their claims are more likely to be fantasy than reality.

Dfinity

Dfinity protocol is described in DFINITY Technology Overview Series Consensus System. While the protocol’s analysis holds to its claims based on its assumptions, its most basic assumption (Assumption 1 from Section 4.2 Thread Model), is rather inexpensive to break that may result in the adversary controlling the blockchain. The analysis here will use Dfinity paper’s 10,000 nodes example and will try to estimate the cost of creating 10,000 adversarial nodes that will violate the Assumption 1.

Creating each adversarial node will incur two hurdles — compute resource cost and the registration. Using DigitalOcean’s tiny droplets, one can create 10,000 nodes at the cost of mere $70/hour. This amount is so insignificant that it won’t even enter the subsequent calculations. Dfinity paper’s section 8.2.2 specifies the registration of nodes using an unspecified Sybil resistant method which may include endorsement, locked-up deposit, PoW puzzle or a certification by an authority. Each of these Sybil resistant methods can be converted to a cost — cost to create a fake identity, cost of resources for PoW, cost of deposit or cost to bribe an otherwise honest node. If Dfinity network intends to attract new members, this cost cannot be set too high. Assuming a midlevel Sybil barrier with cost of $100 per node, an adversary would only need to spend $1M to break the network. This cost is significantly smaller than $10-$50M required to break a PoW or PoS system. In fact, at 10,000 nodes, the Sybil barriers would have to be raised to $1,000-$5,000 in order to make it equally difficult for an adversary. The situation is actually even worse. No network, including Dfinity, can start out with 10,000 nodes from the get-go. At its onset it will have much smaller node count most likely under 1,000. To competitively secure the network with only 1,000 nodes will require Sybil barrier to be raised to $10,000-$50,000 per node. It is unlikely that a network can attract many nodes with that kind of cost of entry.