Consensus: Patterns and Implementations

“An ambiguous and problematic word which can mean several different things, both in Bitcoin and elsewhere. It is often used to hand-wave decision issues as, “well, everyone will basically agree.”

In Bitcoin, the word “consensus” is unfortunately used in several very different ways. Really, all of these usages should be replaced by distinct, different words, and the word consensus should never be used.”

- Bitcoin wiki

In the following lines we will review the most known consensus patterns and implementations, and demonstrate the technical features behind each.

Byzantine fault tolerance

One of the major issues of distributed computing is concurrency properties, i.e reach a global agreement between multiple nodes collaborating in order to achieve a common goal.

Byzantine faults are situations where the network contains a cluster of faulty nodes, presenting arbitrarily or conflicting informations to other nodes.

Byzantine fault tolerance refers to all the models presented in the context of distributed systems to address the challenge of Byzantine faults.

Commander lieutenant problem

Let’s consider this scenario: Commander and lieutenant are about to strike a common enemy, and in order for the attack to be successful, both need to cooperate, i.e strike simultaneously

The problem is they need to synchronize in order to agree about a common time to strike.

The commander start by sending a messenger to the lieutenant to inform him about the time, however, once the message is delivered, the commander is uncertain whether the lieutenant has been informed or not, i.e receives his message, or not.

Moreover, if the lieutenant sends the messenger to acknowledge, he would have no clue that the commander will receive the confirmation.

Both will hold back due to the risk of being the sole attacker.

General Byzantine problem

A generalized version of the commander and lieutenant paradigm, instead more than two actors are involved, in addition, one or more of the members can be a traitor, i.e broadcast a faulty informations to other members, in order to achieve consensus, all lieutenants take the majority vote.

PS: If traitors are greater than 1/3 of the network, consensus can not reached.

This algorithm is considered fault tolerant as long as the number of the faulty nodes is limited.

Byzantine fault tolerance

As Byzantine nodes can broadcast faulty informations, mislead (on purpose or not) other nodes concerned, the network must establish consensus in spite of any malicious interference.

Byzantine fault tolerance is the capability of a distributed system to operate as desired and securely reach a sufficient agreement in the presence of malicious nodes propagating faulty information.

Several Byzantine fault tolerance approaches has been developed to set up a safe and reliable communication between nodes, whilst negating the Byzantine general’s Problem.

As instance, within the context of peer to peer networks, which is a sort of distributed system, bitcoin founder and godfather of blockchain technology, Satoshi Nakamoto, has introduced the famous Proof of Work, a Byzantine fault tolerance model, so all nodes agree on one commun information across the blockchain, thus achieve the consensus.

Practical Byzantine fault tolerance

PBFT model is comprised of a set of nodes ordered sequentially with the first being the primary node or leader and the others are deemed to be the backup.

The purpose of this model is to achieve a global agreement of the “world state” between all the honest nodes through the majority of the whole.

In the end, the result is the replies received by the client from the nodes in question.

Every round, also named views in the PBFT model is comprised of six phases:

1- Client invokes a method or service from the leader.

2- Leader broadcasts the request to backup nodes.

3- Each backup node run the service and send the result to the client.

4- Client collects the first (number of faulty nodes + 1) same replies from backup nodes.

5- The result of the operation is the common agreement of the first (number of faulty nodes + 1) nodes.

6- For each view, a new leader node is selected in a round robin format.

Simplified Byzantine fault tolerance

A known entity, named validator, collects and validates proposed transactions, wrap them together into a block to be broadcasted regularly, consensus is reached when a determined set of nodes accept to sign the block, the number of signers depends on the proportion of faulty nodes within the network.

Within a system which tolerates f faulty nodes, a block needs a minimum of 2*f+1 signatures in order to be appended into the blockchain.

As instance if the blockchain is comprised of 20 nodes, 5 of them are deemed faulty, 2*5+1=11 signatures at least are accepted for a block to be confirmed.

Delegated Byzantine fault tolerance

The network is comprised of three types of nodes:

1- Citizens: Ordinary nodes.

2- Delegates: Elected by citizens to perform the consensus task, usually a set of features are required for the node to be a delegated.

3- Speaker: A randomly selected delegate.

Citizens give their vote to a delegate nevertheless the amount of tokens they have, the speaker, randomly chosen among the delegates broadcasts the block to all the delegates to be confirmed, a minimum of 2*f+1, given f the number of faulty nodes, is needed to confirm the block in question, in the case of less than 2*f+1 confirmations is provided, a new speaker is randomly selected and the process restarts again.

1- Proof of Work

An algorithm used to prohibit service abuses (denial of service attacks, spam) against networks.

The underlying network demands some “exhaustive” task in order to benefit the service it offers, often by resolving a computational problem.

The task has to be both relatively hard to compute but easy to verify.

In the context of Blockchain, nodes uses this process in order to validate and append blocks to the chain, the first who successfully resolves the mining problem gets the reward.

The mining problem often consists of a brute-force with the hope of eventually guessing correctly a threshold, called hash.

A sample of a POW algorithm within the Bitcoin protocol is shown above.

The complexity of the problem depends basically on the size and the power supported by the network.

If the mining problem is too hard to compute, the workflow would be stuck for a while, appending blocks would take a long time and as a result, transactions might never be confirmed, likewise, if the problem is too simple, the network would be vulnerable to denial of service attacks.

Once miner solves the problem, it confirms the pending transactions and broadcasts the new block, each block is comprised of the hashes of all previous blocks which emphasize the security and prohibit any network abuse.

2- Proof of Stake

An alternative of proof of work, invented to address the inherent challenges of the latter, which requires a great amount of computing power (thereby a high amount of electricity) to solve different cryptographic problems.

Still the purpose is the same as the proof of work, but the method to achieve the goal is a bit different: The miner of the next block (also known as forger) is selected in a pedestrian way, depending on its wealth (also known as stake).

Forgers have to vest a sum of their fortune in order to have a chance of being chosen to validate blocks, and gain the reward in return.

Selection is a pseudo-random process, basically two factors are considered.

First, the forger’s stake, the amount of his fortune involved, the higher a stake, the better the chance of being selected, acting maliciously would cost them losing a greater stake than others who vest less.

The second factor is used to avoid the abuse of the system by the wealthiest, (consistently hoard fortune in order to gain more), by including a tweak of hazard to the selection process, two methods are commonly used.

Randomised Block Selection, a combination of the lowest hash value computed by the forgers and the amount of each stake involved in the underlying block.

Coin Age Selection, a combination of the time elapsed since the coins have been staked and the amount of each stake involved in the underlying block.

Some platforms combines both methods.

PS: In contrast of POW, where fortune is minted, (possibly distributed) from the beginning of the game, which means rewards are restricted to transactions fees, and there will be no more freshly generated coins for the winner.

Delegated Proof of Stake

A sort of technological democracy which seeks to achieve consensus in a more secure, less decentralised way.

DPOS leverages the power of stakeholder approval to delegate the resolution of consensus issues to a restricted set of “elected” nodes.

The network is comprised of three types of nodes.

1- Voters: Users ‘vote’ to select ‘witnesses’ (other users they trust to validate transactions), and the top tier of witnesses (who have collected the most votes) earn the right to validate transactions, votes are weighted according to the size of each voter’s stake.

2- Witnesses: The number of witnesses in the top tier is capped at a certain number. These witnesses are responsible for validating transactions and creating blocks, and are in return awarded the associated fees, voting is a continuous process and each witness in the top tier is always at risk of being replaced by another.

3- Users in DPoS systems also vote for a group of ‘delegates’ (trusted parties responsible for maintaining the network), for example, the delegates can propose changing the size of a block, or the amount a witness should be paid in return for validating a block.

Below is Lisk version of DPOS.

Leased Proof of Stake

An enhanced alternative of POS, “In classic PoS, holders with small balances are unlikely to stake a block — just as small miners with low hashrate are unlikely to mine a block in bitcoin. It may be many years before a smallholder is lucky enough to generate a block. This means that many holders with low balances don’t run a node, and leave maintaining the network to a limited number of larger players. Since network security is better when there are more participants, it is important to incentivise these smaller holders to take part”.

A perfect assimilation to mutual funds in finance, where investors (light nodes) can lease their balances to different contractors (full nodes) which will be rewarded a percentage of the reward depending on their performance, the rest is shared between all “leasers“ depending on the weight invested by each.

Chances of being able to mine a block depends on the stake comprised of the leased coins pooled by different light nodes held within a common full node.

The purpose is to enable all nodes to benefit from the mining process which incentivize each to contribute to the sake of the network.

The following picture demonstrates Waves’ implementation of LPOS.

3- Proof of Weight

This concept combines a wide range of blockchain consensus algorithms, including the famous POS, based around the Algorand model: a protocol that confirms transactions very quickly, and prevent any potential fork.

Weighted nodes play a deterministic role in this model, hence the term Proof-of-Weight.

Whereas in POS, the amount locked by the forger determines his chance to be selected to validate the next block, in POWeight model, other relatively weighted value may be used.

4- Proof of Capacity

Miners “plot” their hard drives in order to take part in creating blocks: pre-compute and store the solutions to the mining problems before the mining process begins.

These solutions relies on Shabal256 algorithm (a rather heavy and slow crypto in relation to many other like i.e. SHA256) have to be calculated prior as they are too complicated to solve in real time.

A Plot is a file containing pre-computed hashes that can be used to forge blocks for blockchain. The plots are later used by mining software and can be thought of as the miner’s hash rate.

Before we dive deep into how plotting works we need to get familiar with all different terms used in the procedure.

1- Hash: A hash or digest in this context is a 32Byte (256bit) long result of the Shabal256 Crypto.

2- Nonce: When generating a plot file, you generate something that is called nonces. Each nonce contains 256Kilobyte of data that can be used by miners to calculate Deadlines. Each nonce will have its own individual number. This number can range between 0–18446744073709551615. the number is also used as a seed when creating the nonce. Because of this each nonce has its own unique set of data. One plot file can contain many nonces.

3- Scoop: Each nonce is sorted into 4096 different places of data. These places are called scoop numbers. Each scoop contains 64byte of data which holds 2 hashes. Each of these hashes are xored with a final hash.

4- Account ID: When you create your plot file it will be bound to a specific account. The numeric account ID is used when you create your nonces. Because of this all miners have different plot files even if they use the same nonce numbers.

Plotting

In order to generate a nonce, we need first to create the first seed, it consists of 16byte long value containing the account id and the nonce number, we feed Shabal256 with it to get our first hash.

The result is the last hash in the nonce (#8191), we append it to the starting seed to obtain the new seed for the Shabal256 function.

We now have produced hash #8190. A loop until we get the first hash #0.

Once all hashes are created, we make a Final hash. This is done by using all 8192 hashes and the first 16bytes as seed.

Final hash xor all other hashes individually.

The nonce is comprised of all hashes bundled into scoops, we store it in a plot file.

Loop.

Mining

A miner’s wallet generates mining informations:

1- New generation signature = 32byte Shabal256(previous generation signature, previous block generator): This value is used by miners to forge a new block, block generator is the account used when forging a block.

2- Base target: Calculated from the last 24 blocks. This value adjusts the difficulty for the miners. The lower the base target, the harder it is for a miner to find a low deadline.

3- Next block height: 8byte Current block height + 1: An individual number for a forged block.

A seed comprised of generation signature, and the block height, is used to feed Shabal256 to get a hash value called Generation hash.

Modulo 4096 to obtain a scoop number.

The miner now extract all scoops from all nonces within all plot files, process each through shabal256 together with the new generation signature to get a new hash called target, divided with base target, first 8bytes of the result is the deadline.

Forging

After receiving the Deadline from the miner, the wallet creates the nonce in order to verify the value itself.

The wallet then compare the time passed to the Deadline submitted.

If less seconds have passed, wait until it is equal.

If valid forged block (from another wallet) is broadcasted before the Deadline, discard.

If miner submits new Deadline, repeat, compare to the old Deadline and discard the highest one.

Else forge a block.

5- Proof of Activity

“We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity (PoA) protocol offers good security against possibly practical future attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. We explore various attack scenarios and suggest remedies to potential vulnerabilities of the PoA protocol, as well as evaluate the performance of its core subroutine.”

White paper

We begin with a proof of work process: Miners are competing to find a nonce and claim the reward, except blocks are “templates” with header containing informations.

1- Hash(prev. block)

2- Pub. address of the miner

3- Nonce

Once the template is mined, we switch to proof of stake process, we select a pseudo-random set of (connected) stakeholders based on these informations to sign the new block, the larger the stake, the greater the reward will be obtained.

Transaction fees are split between the miner and the stakeholders.

Follow-the-satoshi

Select a pseudorandom index between zero and the total number of satoshis (the smallest unit of the cryptocurrency) in existence up to the last block.

Find the block within this satoshi was minted.

Follow each transaction containing this satoshi until the address that currently controls it.

PS: If Alice has 2 coins and Bob has 6 coins then Alice is 3 times less likely to be picked compared to Bob.

Mining

Miners are competing to create a template: an empty block header containing the hash of the previous block, the miner’s public address, and a nonce.

The first miner (the hash of its block header data is smaller than the current difficulty target) broadcasts the block header to the other nodes.

Stakeholders are derived from the data within the block header submitted.

Stakeholder#n = follow-the-satoshi(concat(hash(block), hash(prev. block), fixed value#n))

Connected stakeholders verify whether the block header submitted contains hash(prev. block) and meets the current difficulty, then whether they have been selected among the derived stakeholders from the template, the N-1 luckiest sign the hash of the template with their private key (which controls the satoshi) and submit their signature to the Nth stakeholder. The later includes (as many transactions as possible, (N-1) signatures of template, its signature of curr. block).

Nth stakeholder broadcasts the wrapped block to the network.

6- Proof of Elapsed-Time

Often used by permessioned networks.

Based on the principle of a fair lottery system where every single node is equally likely to be a winner, the POET mechanism is based on spreading the chances of a winning fairly across the largest possible number of network participants.

Each node in the blockchain network generates a random wait time and goes to sleep for that specified duration. The one to wake up first — that is, the one with the shortest wait time — wakes up and commits a new block to the blockchain, broadcasting the necessary information to the whole peer network. The same process then repeats for the discovery of the next block.

The POET network consensus mechanism needs to ensure two important factors.

1- The participating nodes genuinely select a time that is indeed random and not a shorter duration chosen purposely by the participants in order to win.

2- The winner has indeed completed the waiting time.

PoET comes from Intel, and it relies on a special CPU instruction set called Intel Software Guard Extensions (SGX). SGX allows applications to run trusted code in a protected environment. For PoET, the trusted code is what ensures that these two requirements are satisfied — keeping the lottery fair.

SGX

A specialized hardware component which can create an attestation that some particular trusted code was set up correctly in a protected environment. e.g. An external party can use the attestation to verify that the right code is running the right way: allows a network participant to prove to other participants that it is running the right trusted code for the network.

Trusted code runs in an environment that is private to the rest of the application. e.g. The rest of the application can’t inspect or interfere with the memory space of the trusted code: ensures that a malicious participant can’t cheat by manipulating the PoET trusted code after it’s been set up.

Joining the network

1- A new participant downloads the trusted code for the blockchain.

2- On initialization, the trusted code creates a new key-pair.

3- Participant sends a SGX attestation (which includes the trusted code’s public key) to the rest of the network as part of a join request.

Participating in the lottery

1- Participant obtains a signed timer object from the trusted code.

2- Participant waits for the time specified by the timer object.

3- Participant obtains a certificate (signed by the trusted code’s private key) that the timer has completed. Participant sends this certificate to the rest of the network along with the new block for the blockchain.

PS: The protocol also involves other protections on top of SGX. For example, the network measures how often a given participant wins the lottery in order to detect participants with a compromised SGX system. Bad actors can then be blacklisted.

7- Proof of Burn

Miners must send an amount of coins to an unspendable address, named “eater address”, in order to remove them permanently out of the circulation.

Transactions to the eater address are stamped within the blockchain to prove that these coins have been genuinely burnt.

The miner who transfers these coins to the eater address is rewarded.

Long term commitment

The purpose of this mechanism is to promote long-term commitment, miners burning their fortune are proving their willingness to postpone their profits by taking a short-term loss in exchange for a long-term gain.

Reward

Miners who burns their coins are continuously receiving their rewards, increasing either their fortune, or their privileges for mining, chances of successfully mining the next block, respectively the amount of the reward, depends on the coins burnt.

Burn mechanism

There are two options for a POB platform to burn coins, either Bitcoins in exchange of new coins minted (adopted by most platforms), or burn native coins in exchange of increased mining privileges.

Costs

As Proof of Work costs is continuously increasing, in term of electricity, costs of POB burn also increases as stakes of successful miners rise which harden the odds of being picked.

the platform benefits from this rivalry, as the coins burnt will reduce the circulating supply which improve the value of their native coin.

Proof of burn

All POB transactions are unchangeably recorded within the blockchain. Once these transactions are successfully confirmed, users are then rewarded.

Eater address

Coins burnt are no longer spendable, they are simply sent to a randomly generated public address that is not linked to any private one, typically, without a private address users are unable to spend their coins which is the purpose in this case.

For example: 1BitcoinEaterAddressDontSendf59kuE It is highly unlikely that a private key exists or statistically be generated to that particular bitcoin address.

8- Proof of Importance

A blockchain consensus algorithm that was first introduced by NEM.

The mechanism consists of selecting among the members of the network which node is eligible to append a block to the blockchain, in order to collect transaction fees within that particular block.

the probability of being selected, depends on each node’s score, and to be considered for the potential reward requires nodes to vest a minimum of stake.

The POI was invented to address the challenge of existing consensus mechanisms such as proof of stake, which rewards miners depending on their funds, nodes are limited to ‘mining’ a percentage of transactions that is reflective of their stake in a cryptocurrency, which leads to hoard the networks fortune within a few miners, as the blockchain grows.

POI considers several facts rather than only the stake, the overall support of the network: vesting, transaction partners, and number and size of transactions in the last 30 days.

Vesting

• A minimum of vested coins is required for harvesting.
• The higher the number of vested coins, the higher the account’s proof of importance score.
• Proof of importance only counts coins that have been in an account for a set number of days.

Transaction Partners

• Proof of importance rewards users who make transactions with other accounts on the network.
• Users cannot game the network by trading back and forth between accounts, the algorithm only accounts for net transfers over time.

Number and size of transactions in the last 30 days

• Each transaction (above a minimum size) contributes to an account’s proof of importance score.
• Larger and more frequent transactions have a greater impact on the proof of importance score.