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.
Proof of Work
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
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 spend $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.
your ASIC farm burned down
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.
In PoS you can stake your assets on both sides of the chain(“nothing-at-stake” problem) whereas in PoW you can’t mine on both the sides(as it is too hard).
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 solution is to punish the bad validators.
Further Reading: Proof of stake
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 time 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 founder of Komodo it can lead to high differences between the hashrate of notary miners and the normal miners :
screen shot from our conversation on discord
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
Just a meme on stakes.
Type: Collaborative consensus
Explanation: In DPoS, the stake holders in the system can elect leaders(witnesses) who will vote in their behalf. This makes it faster than the 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 stake holders.
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!.
EOS as Flash
Further Reading: Delegated-Proof of Stake
Proof of Authority
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:
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
Proof of Weight
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 where in 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 it’s implementations are Proof of Reputation and Proof of Space.
Further Reading: Proof of Weight
Proof of Reputation
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
Proof of Elapsed Time
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 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
Proof of Space
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 a labeling of a hard-to-pebble graph. The prover commits to the labeling. 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
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.
Proof of History Timestamps
The Proof of History is a high frequency . 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
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 heterogeneous social context.
Detailed description can be found in Further Reading.
Further Reading: Proof of Stake Velocity
Proof of Importance
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
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.
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
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).
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
Proof of Existence
It was launched in 2013 as an open source project. It was developed by Manuel Araoz and Esteban Ordano.
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
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 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
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 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 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.
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
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
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
Proof of Believability
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:
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
Explanation: DAGs or Directed Acyclic Graphs are more general form of blockchain. They are popular for inherently high scalablity 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 parallely to the chain. But in case of DAGs blocks/transactions are added parallely, each block/transaction confirming a number of previous blocks. This makes DAGs inherently scalable.
There are a number of variations depending on:
Here are a few popular projects which use DAGs.
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
HashGraph gossip protocol
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
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
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 everyone 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
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
Explanation: Byteball uses DAG, which establishes partial order between transactions, plus adds the main chain within the DAG.
Byteball consensus with mainchain
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 neighboring 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
Mokka is the consensus protocol, resistant to network splits and anonymous attacks. The main goal of the algorithm is in the strict quorum, verification of each action (which may lead to a change of state), and strong history (without an ability to rewrite logs). Mokka resolves these issues by using SSS and asymmetric cryptography — as a part of voting and log appending processes, and merke tree for verification of logs safety. According to mokka, there are only three actions, which may lead to state change: voting, log append, gossip temp logs.
In order to secure the voting and log append processes, mokka use the following approach: during each voting, mokka generate a special secret (based on timestamp + term), split it into shares (through SSS),and send each share to the certain peer. In case, follower vote for this candidate, then he signs the share, and return to the candidate. The candidate validates the signatures + try to restore the secret (in case some peer will send the wrong share, his vote won’t be accepted). After that, candidate build the proof, which is an encoded string, which contains original secret + signatures. Then, on each state mutation (i.e. log appending), the leader uses this proof. The interesting thing is in SSS secret generation. According to the rule, you can create the shares with an ability of restoration > 50%. For instance, in order to build the proof for the network with 5 nodes, you need to obtain, at least 3 shares during the voting process.
Gossip protocol is used in mokka for transmitting logs to leader node from the follower nodes (in case the client used the follower node for pushing new log). The gossip protocol delivers the pending log to the leader and other followers. This gives an additional backup, in case the leader node dies, another follower may become leader node, and accept this temp log. As for the security aspect, before pushing the log to gossip, the node, which got this log, have to sign it with its private key. The signature will be validated by the leader node. In case, the signature is valid — log will be obtained, if not — then it will be just pulled.
For the moment, there is one implementation, written in typescript, and already ported for the browser (you can play with it on the website).Also, the solution has an abstraction over the protocol, so you can write your own (it can be TCP, UDP or even zmq).
Further Reading: Mokka website
That’s all. If you find anything missing or wrong here then shoot that in the comments.
Thanks for reading;)
Hold down the clap button if you liked the content! It helps me gain exposure.
About the Author
He works as Senior blockchain developer and has worked on several blockchain platforms including Ethereum, Quorum, EOS, Nano, Hashgraph, IOTA.
He is currently a sophomore at IIT Delhi.
Want to learn more? Checkout my previous articles.
Clap 50 times and follow me on Twitter: