Further Reading: ByteBall , Credits: Vaibhav Saini
A complete list/comparison of all consensus algorithms.
Consensus algorithms are the basis of all the blockchains/DAGs. They are the most important part of the blockchain/DAG platforms.
Without them(consensus algorithms) we will be left with just a dumb, immutable database.
Here we list all the major consensus algorithms and will evaluate their pros and cons. If you find anything missing or wrong here then shoot that in the comments. Also, the article will be updated regularly as I study more about these algorithms and their economic impacts.
P.S. This article assumes that you have an understanding about what is a consensus algorithm and it’s significance in blockchains.
Here is a list of 30 consensus algorithms.
1. Proof of Work
- It has been tested in the wild since 2009 and stands steady today as well.
- It’s slow.
- Uses up a lot of energy, not good for the environment.
- Is susceptible to economies of scale.
Used by: Bitcoin, Ethereum, Litecoin, Dogecoin etc.
Type: Competitive consensus.
Explanation: It is the first consensus algorithm (proposed by Satoshi Nakamoto introduced in his article) to create distributed trustless consensus and solves the double-spend problem. POW is not a new idea, but the way Satoshi combined this and other existing concepts — cryptographic signatures, Merkle chains, and P2P networks — into a viable distributed consensus system, of which cryptocurrency is the first and basic application, was quite innovative.
The way it works that the participants of the blockchain(called miners) have to solve a complex but useless computational problem in order to add a block of transactions into the blockchain.
Basically, it is done to ensure that the miners are putting some money/resources (mining machines) to do the work, which shows that they won’t harm the blockchain system, cause harming the system will result in losing their investment; thus harming themselves.
The difficulty of the problem can be changed in runtime, to ensure the constant block time. Sometimes there is a situation in which more than one miners solve the problem simultaneously. In that case, miners choose one of the chains and the longest chain is considered the winner. So assuming most miners are working on the same chain, that one will grow fastest will be the longest and most trustworthy. Hence Bitcoin is safe as long as more than 50% of the work being put in by miners is honest.
Further Reading: Proof of work
2. Proof of Stake
- More expensive to attack for attackers.
- Not susceptible to economies of scale
- nothing-at-stake problem
Used by: Ethereum (soon), Peercoin, Nxt.
Type: Competitive consensus.
Explanation: The proof of stake was created as an alternative to the proof of work (PoW), to tackle inherent issues in the latter. Here instead of using mining, you have to have some stake(coins) in the system. So, if you own 10% of the stake(coins), then your probability of mining next block will be 10%.
Mining requires a great deal of computing power to run different cryptographic calculations to unlock the computational challenges. The computing power translates into a high amount of electricity and power needed for the proof of work. In 2015, it was estimated that one Bitcoin transaction required the amount of electricity needed to power up 1.57 American households per day. So, in order to save the power wastage PoS was introduced.
In PoS, a dollar is a dollar. For example, consider 10,000 miners, each spends $1/min ($87.6M/yr) may have less hashing power than one mining pool that spends $10,000/min (despite also spending $87.6M/yr). But in case of PoS, you can’t use it up all at once. Here a dollar is a dollar. Thus, it is not susceptible to economies of scale.
Also, attacking a PoS system is more expensive than attacking a PoW system. Quoting Vlad Zamfir
the cost profile of a repeated 51% attack in PoS is as if “your ASIC farm burned down” with each additional round.
This means that you lose your stake every time you do an attack on a PoS system, whereas in PoW you don’t lose your mining equipment or your coins if you attack the system; instead, you just make it(attacking a PoW system) hard to execute.
But one issue that can arise is the “nothing-at-stake” problem, wherein block generators have nothing to lose by voting for multiple blockchain histories(forks), thereby preventing consensus, from being achieved.
Because unlike in proof-of-work systems(where you have to do a lot of computation to extend a chain), there is little cost to working on several chains. Many projects have tried to solve this problem in different ways(mentioned in further reading). For eg. as stated above, one of the solutions is to punish the bad validators.
Further Reading: Proof of stake
3. Delayed Proof-of-Work
- Energy efficient
- Increased security
- can add value to other blockchains by indirectly providing Bitcoin(or any secure chain) security without paying the cost of Bitcoin(or any secure chain) transactions
- Only blockchains using PoW or PoS can be a part of this consensus.
- Under “Notaries Active” mode the hash rate for different nodes(notary and normal nodes) have to be calibrated, otherwise, the difference between the hash rates can explode(see below for more explanation)
Used by: Komodo
Type: Collaborative consensus
Explanation: Delayed Proof of Work (dPoW) is a hybrid consensus method that allows one blockchain to take advantage of the security provided through the hashing power of a secondary blockchain. This is achieved through a group of notary nodes that add data from the first blockchain onto the second, which would then require both blockchains to be compromised to undermine the security of the first. The first to make use of this consensus method is Komodo, which is attached to the Bitcoin blockchain.
The blockchain relying on dPoW can make use of either the Proof of Work (PoW) or Proof of Stake (PoS) consensus methods to function; and it can attach itself to any PoW blockchain desired. However, Bitcoin’s hash rate currently provides the greatest level of security to blockchains being secured by dPoW. The illustration below shows the relationship of individual records to the primary blockchain and its attached PoW blockchain:
There are two types of nodes within a dPoW system: notary nodes and normal nodes. The 64 notary nodes are elected by dPoW blockchain stakeholders to add (notarize) confirmed blocks from the dPoW blockchain onto the attached PoW blockchain. Once a block has been completed, its hash is added to a Bitcoin transaction signed by 33 of the notary nodes, creating a record of dPoW block hashes on the Bitcoin blockchain that have been notarized by a majority of the network’s notary nodes.
To prevent mining wars between notary nodes, which would reduce the network’s efficiency, Komodo has devised a round-robin method of mining that operates on two modes. The “No Notary” mode allows for all network nodes to mine blocks, similar to a traditional PoW consensus mechanism; however, under “Notaries Active” mode, the network notaries will mine at a significantly reduced network difficulty rate. Within this scheme, each notary is allowed to mine one block at its current difficulty rate, while the other notary nodes must mine at 10 times higher and all the normal nodes will always mine at 100 times the difficulty rate of the notary nodes.
But this causes some problems. As mentioned in one of my conversations with the founder of Komodo it can lead to high differences between the hash rate of notary miners and the normal miners :
The dPoW system is designed to allow the blockchain to continue functioning without the notary nodes. In such a situation, the dPoW blockchain can continue operating based upon its initial consensus method; however, it would no longer have the added security of the attached blockchain.
Delayed Proof of Work, then, allows for increased security and reduced energy usage for any blockchain making use of this consensus method. For example, as Komodo uses the Equihash hashing algorithm to prevent mining with ASICs and it relies upon a round-robin method of mining for notary nodes, incentives are structured to reduce the possibility that competition between nodes will lead to excessive use of energy or computing power.
In addition, a dPoW blockchain such as Komodo can add value to other blockchains by indirectly providing Bitcoin security without paying the cost of Bitcoin transactions: A third blockchain using dPoW can attach itself to Komodo, which is subsequently attached to Bitcoin. In this way, dPoW blockchains can benefit from Bitcoin’s high hash rate without having to be directly attached to the Bitcoin blockchain.
Finally, the separated functions of notary nodes and normal nodes within the system ensure that the initial consensus mechanism continues to operate in the event that the notary nodes fail. This interdependence creates an incentive for other networks to support the continued maintenance of the Bitcoin network without becoming entirely reliant upon its direct functionality.
Further Reading: Delegated-Proof of Work
4. Delegated Proof-of-Stake
- Fast. Steemit, a high traffic blogging site uses it. EOS has a block-time of 0.5 sec.
- A bit centralized.
- Participants with high stakes can vote themselves in to become a validator. Something which is seen recently in EOS.
Used by: BitShares, Steemit, EOS, Lisk, Ark
Type: Collaborative consensus
Explanation: In DPoS, the stakeholders in the system can elect leaders(witnesses) who will vote in their behalf. This makes it faster than normal PoS.
For eg. in case of EOS, 21 witnesses get elected at a time and a pool of nodes(potential witnesses) are kept at standby so that if someone of the witness nodes dies or does some malicious activity, then it could be replaced by a new node immediately. The witnesses are paid a fee for producing blocks. The fee is set by the stakeholders.
Usually, all the nodes produce blocks one at a time in a round-robin fashion. This prevents a node from publishing consecutive blocks, preventing him to execute double-spending attacks. If a witness does not produce a block in their time slot, then that time slot is skipped, and the next witness produces the next block. If a witness continually misses his blocks or publishes invalid transactions then the stakers vote him out and replace him with a better witness.
In DPoS, miners can collaborate to make blocks instead of competing like in PoW and PoS. By partially centralizing the creation of blocks, DPoS is able to run orders of magnitude faster than most other consensus algorithms. EOS(which uses dPoS) is the first blockchain to achieve a block time of 0.5 second!.
Further Reading: Delegated-Proof of Stake
- Energy efficient.
- A bit centralized. Can be used in public blockchains but usually used in private, permissioned blockchains.
Used by: POA.Network, Ethereum Kovan testnet, VeChain
Type: Collaborative consensus
Explanation: In PoA-based networks, transactions and blocks are validated by approved accounts, known as validators. Validators run software allowing them to put transactions in blocks. The process is automated and does not require validators to be constantly monitoring their computers. It, however, does require maintaining the computer (the authority node) uncompromised.
The three main conditions that must be fulfilled for a validator to be established are:
- Identity must be formally verified on-chain, with a possibility to cross-check the information in a publicly available domain
- Eligibility must be difficult to obtain, to make the right to validate the blocks earned and valued. (Example: potential validators are required to obtain public notary license)
- There must be complete uniformity in the checks and procedures for establishing an authority
With PoA individuals earn the right to become validators, so there is an incentive to retain the position that they have gained. By attaching a reputation to identity, validators are incentivized to uphold the transaction process, as they do not wish to have their identities attached to a negative reputation, thus losing the hard-earned validator role.
Further Reading: Proof of Authority
- Highly Customisable and scalable.
- Incentivization can be hard.
Used by: Algorand
Type: Competitive consensus
Explanation: Proof-of-Weight is a broad classification of consensus algorithms based around the Algorand consensus model. The general idea is that wherein PoS, your percentage of tokens owned in the network represents your probability of “discovering” the next block, in a PoWeight system, some other relatively weighted value is used. Some of its implementations are Proof of Reputation and Proof of Space.
Further Reading: Proof of Weight
7. Proof of Reputation
- Good for private, permissoned networks.
- Only used in private, permissioned blockchains.
Used by: GoChain
Type: Collaborative consensus
Explanation: Similar to Proof of Authority. As mentioned by GoChain:
Proof of Reputation (PoR) consensus model depends on the reputation of the participants to keep the network secure. A participant (a block signer) must have a reputation important enough that they would face significant financial and brand consequences if they were to attempt to cheat the system. This is a relative concept as almost all businesses would suffer significantly if they were caught attempting to be deceitful, but larger companies will typically have more to lose and thus are chosen over companies with less to use (smaller businesses).
Once a company proves reputation and passes verification, they may be voted into the network as an authoritative node and at this point, it operates like a Proof of Authority network (PoA), where only authoritative nodes can sign and validate blocks.
You can find more about Proof of Reputation in Further Reading.
Further Reading: Proof of Reputation
8. Proof of Elapsed Time
- Low cost of participation. Thus more people can participate easily, thus decentralized.
- It is simple for all participants to verify that the leader was legitimately selected.
- The cost of controlling the leader election process is proportional to the value gained from it.
- Even though it’s cheap, you have to use specialized hardware. Thus cannot be mass-adopted.
- Not suited for public blockchains.
Used by: HyperLedger Sawtooth
Type: Competitive consensus
Explanation: PoET is a consensus mechanism algorithm that is often used on the permissioned blockchain networks to decide the mining rights or the block winners on the network. Permissioned blockchain networks are those which require any prospective participant to identify themselves before they are allowed to join. 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.
The working of the PoET algorithm is as follows. Each participating node in the network is required to wait for a randomly chosen time period, and the first one to complete the designated waiting time wins the new block. 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. First, that 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, and two, the winner has indeed completed the waiting time.
The PoET concept was invented during early 2016 by Intel, the famous chip manufacturing giant. It offers a readymade high tech tool to solve the computing problem of “random leader election.”
The ingrained mechanism allows applications to execute trusted code in a protected environment, and this ensures that both requirements — for randomly selecting the waiting time for all participating nodes and genuine completion of waiting time by the winning participant — are fulfilled.
The mechanism of running trusted code within a secure environment also takes care of many other necessities of the network. It ensures that the trusted code indeed runs within the secure environment and is not alterable by any external participant. It also ensures that the results are verifiable by external participants and entities, thereby enhancing the transparency of the network consensus.
PoET controls the cost of the consensus process and keeps it nimble so that the cost remains proportional to the value derived from the process, a key requirement for the cryptocurrency economy to continue flourishing.
Further Reading: Proof of Elapsed Time
9. Proof of Capacity aka Proof of Space
- Similar to PoW but uses space instead of computation. Thus much environmental friendly.
- Can be used for malware detection, by determining whether the L1 cache of a processor is empty (e.g., has enough space to evaluate the PoSpace routine without cache misses) or contains a routine that resisted being evicted.
- Can be used for anti-spam measures and denial of service attack prevention.
- Incentivization can be an issue.
Used by: Burstcoin, Chia, SpaceMint
Type: Collaborative Consensus
Explanation: Proof-of-space (PoSpace), also called proof-of-capacity (PoC), is a means of showing that one has a legitimate interest in a service (such as sending an email) by allocating a non-trivial amount of memory or disk space to solve a challenge presented by the service provider. The concept was formulated by Dziembowski et al. in 2015. (Ateniese et al.’s paper, while also titled Proof-of-space, is, in fact, a memory-hard proof-of-work protocol.)
Proofs of space are very similar to proofs of work, except that instead of computation, storage is used. Proof-of-space is related to, but also considerably different from, memory-hard functions and proofs of retrievability.
A proof-of-space is a piece of data that a prover sends to a verifier to prove that the prover has reserved a certain amount of space. For practicality, the verification process needs to be efficient, namely, consumes a small amount of space and time. For soundness, it should be hard for the prover to pass the verification if it does not actually reserve the claimed amount of space. One way of implementing PoSpace is by using hard-to-pebble graphs. The verifier asks the prover to build labelling of a hard-to-pebble graph. The prover commits to the labelling. The verifier then asks the prover to open several random locations in the commitment.
Proofs of space are seen as a fairer and greener alternative due to the general-purpose nature of storage and the lower energy cost required by storage.
Further Reading: Proof of Space
10. Proof of History
Used by: Solana
Explanation: The basic idea here is that instead of trusting the timestamp on the transaction, you could prove that the transaction occurred sometime before and after an event.
When you take a photograph with the cover of New York Times, you are creating a proof that your photograph was taken after that newspaper was published, or you have some way to influence what New York Times publishes. With Proof of History, you can create a historical record that proves that an event has occurred at a specific moment in time.
The Proof of History is a high-frequency Verifiable Delay Function. A Verifiable Delay Function requires a specific number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified.
This specific implementation uses a sequential pre-image resistant hash that runs over itself continuously with the previous output used as the next input. Periodically the count and the current output are recorded.
For a SHA256 hash function, this process is impossible to parallelize without a brute force attack using 2¹²⁸ cores.
We can then be certain that real-time has passed between each counter as it was generated, and that the recorded order each counter is the same as it was in real-time.
You can find all the details in Further Reading.
Further Reading: Proof of History
11. Proof of Stake Velocity
Used by: Reddcoin
Explanation: Proof of Stake Velocity (PoSV) is proposed as an alternative to Proof of Work (PoW) and Proof of Stake (PoS) to secure the peer-to-peer network and confirm transactions of Reddcoin, a cryptocurrency created specifically to facilitate social interactions in the digital age. PoSV is designed to encourage both ownership (Stake) and activity (Velocity) which directly correspond to the two main functions of Reddcoin as a real currency: store of value and medium of exchange. Reddcoin can also function as the unit of account in a heterogeneous social context.
Detailed description can be found in Further Reading.
Further Reading: Proof of Stake Velocity
12. Proof of Importance
- Better than PoS in evaluating stake.
Used by: NEM
Explanation: NEM’s consensus network depends not only the number of coins but on the possibility that productive system action ought to be remunerated. The chances of staking a block are a component of various factors, including notoriety (controlled by a different purpose-designed framework), balance, and the number of transactions made to and from that position. This is termed as importance calculation. This gives a more all-encompassing image of a ‘helpful’ system member.
In order to be eligible for the importance calculation, users need to have at least 10,000 XEM in their balance. Considering there are just under 9 billion XEM in circulation, achieving that goal is not overly expensive by any means. It is possible this threshold of 10,000 XEM is changed in the future, but for now, it is still the same. But the importance calculation is done utilizing a specific algorithm, not just by probability and size of their shares.
It is also important to note NEM’s proof-of-importance is resistant to arbitrary manipulation. Sybil attacks and loop attacks are mitigated using the underlying mechanisms of the consensus. It is equally important to remember proof of importance is not proof of stake, although it is easy to draw parallels between the two.
Further Reading: Proof of Importance
13. Proof of Burn
Used by: Slimcoin, TGCoin (Third Generation Coin)
Explanation: With proof of burn, instead of pouring money into expensive computer equipment, you ‘burn’ coins by sending them to an address where they are irretrievable. By committing your coins to never-never land, you earn a lifetime privilege to mine on the system based on a random selection process.
Depending on how proof of burn is implemented, miners may burn the native currency or the currency of an alternative chain, like bitcoin. The more coins you burn, the better chance you have of being selected to mine the next block.
Over time, your stake in the system decays, so eventually, you will want to burn more coins to increase your odds of being selected in the lottery. (This mimics bitcoin’s mining process, where you have to continually invest in more modern computing equipment to maintain hashing power.)
While proof of burn is an interesting alternative to proof of work, the protocol still wastes resources needlessly. Another criticism is that mining power simply goes to those who are willing to burn more money.
14. Proof of Identity
Explanation: Proof of Identity (PoI) is a cryptographic evidence (piece of data) which tells that any user knows a private key that compares to an authorized identity and cryptographically attached to a specific transaction. Every individual from some group can create a PoF (only a block of data) and present it to anyone for instance to the processing node.
Further Reading: Proof of Identity
15. Proof Of Activity
Used by: Decred
Explanation: To avoid hyperinflation (what happens when too much of a currency floods the system) bitcoin will only ever produce 21m bitcoins. That means, at some point, the bitcoin block reward subsidy will end and bitcoin miners will only receive transaction fees.
Some have speculated this might cause security issues resulting from a ‘tragedy of the commons’, where people act in self-interest and spoil the system. So, proof of activity was created as an alternative incentive structure for bitcoin. Proof of activity is a hybrid approach that combines both proof of work and proof of stake.
In proof of activity, mining kicks off in a traditional proof-of-work fashion, with miners racing to solve a cryptographic puzzle. Depending on the implementation, blocks mined do not contain any transactions (they are more like templates), so the winning block will only contain a header and the miner’s reward address.
At this point, the system switches to proof of stake. Based on information in the header, a random group of validators is chosen to sign the new block. The more coins in the system a validator owns, the more likely he or she is to be chosen. The template becomes a full-fledged block as soon as all of the validators sign it.
If some of the selected validators are not available to complete the block, then the next winning block is selected, a new group of validators is chosen, and so on until a block receives the correct amount of signatures. Fees are split between the miner and the validators who signed off on the block.
Criticisms of proof of activity are the same as for both proof of work (too much energy is required to mine blocks) and proof of stake (there is nothing to deter a validator from double signing).
16. Proof of Time
Used by: Chronologic
Explanation: Proof of time is introduced by Chronologic. They are planning to build a separate blockchain. As stated by their Lead developer:
The problem here is that the largest number that can be stored in a variable in solidity is of the order of magnitude 1076. This is making it difficult for us to work with time and the generation of tokens.
Further Reading: Proof of Time
17. Proof of Existence
Used by: Poex.io, HeroNode, DragonChain
Explanation: Proof of Existence is an online service that verifies the existence of computer files as of a specific time via timestamped transactions in the bitcoin blockchain.
It was launched in 2013 as an open-source project. It was developed by Manuel Araoz and Esteban Ordano.
- Digital Sign Agreement without revealing actual content.
- Demonstrating data ownership without revealing actual data.
- Document time stamping.
- Proving ownership
- Checking for document integrity
Further Reading: Proof of Existence
Used by: Cardano
Explanation: A variation of Proof-of-stake(with rigorous security guarantees) used by Cardano.
Further Reading: Ouroboros
19. Proof of Retrievability
Used by: Microsoft
Explanation: A proof of Retrievability (POR) is a compact proof by a file system (prover) to a client (verifier) that a target file F is intact, in the sense that the client can fully recover it. As PORs incur lower communication complexity than the transmission of F itself, they are an attractive building block for high-assurance remote storage systems. It can be really useful as a consensus algorithm for Cloud computing systems.
Detailed description can be found in Further Reading.
Further Reading: Proof of Retrievability
20. Byzantine Fault Tolerance
- Fast. Scalable.
- Usually used for private, permissioned networks.
Used by: Hyperledger Fabric, Stellar, Ripple, Dispatch
Explanation: There’s this classic problem is distributed computing that’s usually explained with Byzantine generals. The problem is that several Byzantine generals and their respective portions of the Byzantine army and have surrounded a city. They must decide in unison whether or not to attack. If some generals attack without the others, their siege will end in tragedy. The generals are usually separated by distance and have to pass messages to communicate. Several cryptocurrency protocols use some version of BFT to come to a consensus, each with their own pros and cons:
Practical Byzantine Fault Tolerance (PBFT): One of the first solutions to this problem was coined Practical Byzantine Fault Tolerance. Currently in use by Hyperledger Fabric, with few (< 20, after that things get a little ) pre-selected generals PBFT runs incredibly efficiently. Pros: High transaction throughput Cons: Centralized/permissioned
Federated Byzantine Agreement (FBA): FBA is another class of solutions to the Byzantine generals problem used by currencies like Stellar and Ripple. The general idea is that every Byzantine general, responsible for their own chain, sorts messages as they come in to establish the truth. In Ripple, the generals (validators) are pre-selected by the Ripple foundation. In Stellar, anyone can be a validator so you choose which validators to trust.
For its incredible throughput, low transaction cost, and network scalability, I believe the FBA class of consensus algorithms are the best we’ve discovered for distributed consensus.
21. Delegated Byzantine Fault Tolerance (dBFT)
- Fast. Scalable.
- Evеrуоnе is fіghtіng to be root chain. There саn be ѕеvеrаl rооt chains.
Used by: Neo
Explanation: The dBFT is called the Delegated Byzantine Fault Tolerant, a Byzantine fault-tolerant consensus mechanism that enables large-scale participation in consensus through proxy voting. The holder of the NEO token can, by voting, pick the bookkeeper it supports. The selected group of bookkeepers, through BFT algorithm, reach a consensus and generate new blocks. Voting in the NEO network continues in real-time, rather than in accordance with a fixed term.
The dBFT provides fault tolerance of f = [(n-1) / 3] for a consensus system consisting of n consensus nodes. This fault tolerance also includes both security and availability, resistant to general and Byzantine failures, and is suitable for any network environment. dBFT has good finality, meaning that once confirmations are final, the block can not be bifurcated, and the transaction will not be revoked or rolled back.
In the NEO dBFT consensus mechanism, taking about 15 to 20 seconds to generate a block, the transaction throughput is measured up to about 1,000 TPS, which is excellent performance among the public chains. Through appropriate optimization, there is potential to reach 10,000 TPS, allowing it to support large-scale commercial applications.
The dBFT combines digital identity technology, meaning the bookkeepers can be a real name of the individual or institution. Thus, it is possible to freeze, revoke, inherit, retrieve, and ownership transfer due to judicial decisions on them. This facilitates the registration of compliant financial assets in the NEO network. The NEO network plans to support such operations when necessary.
Further Reading: dBFT
- Simpler model than Paxos, but offers same safety.
- Implementation available in many languages.
- Usually used in private, permissioned networks.
Used by: IPFS Private Cluster, Quorum
Explanation: Raft is a consensus algorithm designed as an alternative to Paxos. It was meant to be more understandable than Paxos by means of separation of logic, but it is also formally proven safe and offers some additional features. Raft offers a generic way to distribute a state machine across a cluster of computing systems, ensuring that each node in the cluster agrees upon the same series of state transitions. It has a number of open-source reference implementations, with full-specification implementations in Go, C++, Java, and Scala.
Raft achieves consensus via an elected leader. A server in a raft cluster is either a leader or a follower and can be a candidate in the precise case of an election (leader unavailable). The leader is responsible for log replication to the followers. It regularly informs the followers of its existence by sending a heartbeat message. Each follower has a timeout (typically between 150 and 300 ms) in which it expects the heartbeat from the leader. The timeout is reset on receiving the heartbeat. If no heartbeat is received the follower changes its status to candidate and starts a leader election.
This info-graphic is highly recommended for understanding RAFT.
Further Reading: Raft
23. Stellar Consensus
- Decentralized control
- Low latency
- Flexible trust
- Asymptotic security
Used by: Stellar
Explanation: It is based on federated Byzantine agreement (mentioned above).
The Stellar Consensus Protocol (SCP) provides a way to reach consensus without relying on a closed system to accurately record financial transactions. SCP has a set of provable safety properties that optimize for safety over liveness — in the event of partition or misbehaving nodes, it halts progress of the network until consensus can be reached. SCP simultaneously enjoys four key properties: decentralized control, low latency, flexible trust, and asymptotic security.
Further Reading: Stellar Consensus
24. Proof of Believability
- More decentralized than traditional PoS by using the concept of Servi(mentioned in Explanation).
- Fast Finality as compared to traditional PoS.
Used by: IOST
Explanation: A major challenge faced by traditional Proof-of-Stake consensus mechanism is the tendency towards centralization. In order to mitigate this risk, IOST introduced Servi as both a measurement of users’ contribution to the community and a way to encourage members to contribute to the continued development of the IOSChain. It has the following attributes:
- Non-tradable: Since Servi is not designed as a medium of exchange, Servi can not be traded or exchanged in any way.
- Self-destructive: After validating a block, the system will automatically clear the Servi balance owned by the validator. In this way, nodes with high believability scores can take turns in validating blocks, to ensure a fair block generation process.
- Self-issuance: Servi will be generated and deposited to user accounts automatically after certain contributions, such as providing community services, evaluating services provided by other entities, and/or making other special contributions.
Traditional blockchain systems have an inherent trade-off between safety and throughput, depending on shard size. A system with a large number of small shards delivers better performance but provides less resiliency against bad actors, and vice versa(One of the problems also faced by Casper). In order to break the trade-off in a way that keeps safety and increases throughput, IOST proposed an innovative Proof-of-Believability (PoB) consensus protocol for IOSChain. PoB guarantees that the nodes are with negligible probability to misbehave, while significantly increasing the transaction throughput by size-one-shard.
The Proof-of-Believability consensus protocol uses an intra-shard Believable-First approach. The protocol divides all validators into two groups, a believable league and a normal league. Believable validators process transactions quickly in the first phase. Afterwards, normal validators sample and verify the transactions in the second phase to provide finality and ensure verifiability. The chance of a node being elected into the believable league is determined by believability score which is calculated by multiple factors (e.g., token balance, contributions to the community, reviews, etc). One with higher believability score is more likely to be elected into the believable league. Believable validators follow the procedures to decide the set of committed transactions and their order, as well as process them in order. Believable validators also form smaller groups — one validator per group. Transactions will be randomly distributed among these believable validators. Consequently, they produce smaller blocks with extremely low latency.
However, it may introduce security problem as only one node is performing the verification. As a result, some corrupted transactions might be committed by misbehaved validators. In order to solve this security problem, they specify a sampling probability that normal validators will sample transactions and detect inconsistencies. If a validator is detected as misbehaviour, it will lose all the tokens and reputation in the system while the defrauded users will be compensated for any loss. The believable-first approach makes processing transactions extremely fast as only a single (believable) validator is doing the verification and it is unlikely to misbehave.
To know more about their sharding policy, refer to Further Reading.
Further Reading: Proof of Believability
25. Directed Acyclic Graphs
- Highly scalable due to their non-linear structure.
- Energy efficient.
- Finality is achieved instantly.
- Smart contracts implementation can only be done by use of oracles.
Used by: Iota, HashGraph, Byteball, RaiBlocks/Nano
Explanation: DAGs or Directed Acyclic Graphs are a more general form of blockchain. They are popular for inherently high scalability due to their unique structure.
Basically, in any blockchain system, we have a linear structure, one-by-one blocks are added to the chain. This makes blockchain inherently slow as the blocks can’t be added parallelly to the chain. But in case of DAGs blocks/transactions are added parallelly, each block/transaction confirming a number of previous blocks. This makes DAGs inherently scalable.
There are a number of variations depending on:
- algorithm for choosing which previous blocks to verify aka tip-selection algorithm.
- How the ordering of transactions is done?
- How finality is reached?
Here are a few popular projects which use DAGs.
25 a) Tangle (IOTA)
Explanation: Tangle is the DAG consensus algorithm used by Iota. In order to send an Iota transaction, you need to validate two previous transactions you’re received. The two-for-one, pay-it-forward consensus strengthens the validity of transactions the more transactions are added to the Tangle. Because the consensus is established by the transactions, theoretically, if someone can generate 1/3 of the transactions they could convince the rest of the network their invalid transactions are valid. Until there’s enough transaction volume that creating 1/3rd of the volume becomes unfeasible, Iota is sort-of “double-checking” all of the network’s transactions on a centralized node called “The Coordinator”. Iota says The Coordinator works like training wheels for the system, and will be removed once the Tangle is big enough.
Further Reading: Tangle
25 b) Hashgraph
Explanation: Hashgraph is a gossip-protocol consensus developed by Leemon Baird. Nodes share their known transactions with other nodes at random so eventually, all the transactions are gossiped around to all of the nodes. Hashgraph is a great option for private networks, but you’re not going to see it implemented in a public network like Ethereum or dispatch any time soon.
Further Reading: HashGraph
25 c) Holochain
Explanation: Quite similar to HashGraph, but not Hashgraph. It provides a data structure that can be used to build decentralized apps. You have your own chain, which you can add data to, including financial transactions. The chains can merge, split, and interact in complex ways. The data is stored in a decentralized way (like Bittorrent). The data has a hash, which is a mathematical fingerprint that corresponds to the data. If someone tampers with the data, the mismatch between the data and the hash will be noticed, and the data rejected as invalid. Digital signatures guarantee the authorship of the data. It’s Bittorrent plus git plus digital signatures.
Further Reading: HoloChain
25 d) Block-Lattice (Nano)
Explanation: Nano (formerly Raiblocks) runs with a twist on the blockchain called a Block-lattice. The Block-lattice is a structure where every user (address) gets their own chain that only they can write to, and every one holds a copy of all of the chains.
Every transaction is broken down into both a send block on the sender’s chain and a receive block on the receiving party’s chain. The Block-lattice seems almost too simple to work, but it’s already out there running in the wild. The unique structure does leave the Block-lattice open to some unique attack vectors like the Penny-spend attack, where attackers inflate the number of chains node must keep track of by sending negligible amounts to a wide array of empty wallets.
Further Reading: Nano
25 e) SPECTRE
Explanation: Serialization of Proof-of-work Events: Confirming Transactions via Recursive Elections, better known as SPECTRE, is a proposed Bitcoin scaling solution that utilizes a combination of PoW and DAGs to reach scalable consensus. In SPECTRE, the blocks are mined pointing to multiple parents, not just one, so the network could potentially handle multiple blocks per second. Mining a block pointing to some parent blocks supports those blocks validity. Compared to PoW’s “longest chain wins”, SPECTRE uses something like “blocks with the most childen win.” SPECTRE hasn’t been battle-tested in the wild yet, and new attack vectors are likely to emerge, but it feels like a very clever potential way to fix Bitcoin.
Further Reading: SPECTRE
25 f) ByteBall
Explanation: Byteball uses DAG, which establishes partial order between transactions, plus adds the main chain within the DAG.
The main chain (MC) allows to define total order between transactions: the transaction which gets included (directly or indirectly) earlier on the MC, is deemed earlier in the total order. When there is a double-spend, the version of the transaction that comes earlier in the total order is deemed valid, all others are deemed void.
The main chain is defined deterministically based on the positions of transactions in the graph. Refer to the white paper for details, but as a general rule, the MC gravitates towards transactions authored by well-known users, which we call witnesses. The list of witnesses is defined by users themselves as they include the list in every transaction they post. The MC then follows the path within the DAG such that:
1. the witness lists of the neighbouring transactions on the chain are either identical or differ by only one mutation,
2. the chain goes through the most number of witness-authored transactions, compared with alternative chains.
It is also the first platform to include oracles in the system, which are needed for adding smart contract functionality in DAGs.
The above is a very brief and sketchy description with many important details omitted, refer to the white paper for a full technical story.
Further Reading: ByteBall
Credits: Vaibhav Saini