When it comes to decentralized record keeping, which is one important aspect of how blockchain technology functions, it becomes infeasible to rely on trust alone to ensure that factual information is added to the record books. This problem arises in decentralized networks as a result of the lack of a central entity that would typically decide what should and should not be considered as fact. It’s difficult to avoid this issue when working with blockchain technology because it is this lack of a central entity that is one of the main contributors to blockchain’s popularity. In order to circumvent this issue a network must have a system in place by which a consensus can be reached by the nodes in the network.
A consensus metric is a measurable datum on which a blockchain network’s nodes must agree in order to establish and maintain consensus for the data contained in each block. In blockchain technology, consensus metrics are measured and approved by each network node every time a new block is to be added to the chain. As a result of the consensus metric, blockchains act as chains of truth extended from one certainly verifiable fact to the next. Because of the consensus metric, a blockchain protocol’s nodes become mini-notaries, instantly able to tell a false copy of the blockchain from the true one and report that fact to the entire network. These measures are required in order to keep bad actors from frauding the network by submitting blocks containing false information. As a result of the consensus metric of a blockchain the integrity of the blockchain is not only established, but also maintained, over the long run. Consensus metrics take a variety of forms, but the two most important for this discussion are risk-based metrics and work-based metrics.
Commonly known as Proof-of-Work (PoW) metrics, these metrics establish consensus because protocols that use them set computers to work on finding difficult numbers. For the sake of illustration, consider supercomputers whose only job in life is to search integer-space for prime numbers. Now consider a whole network of average computers. These computers, when put together, might be said to have the combined power of a supercomputer. The only job for this network of computers is similarly to search possible numbers for another kind of number called a SHA-256 hash. These numbers have unique properties, just like prime numbers, that make them easily identifiable when discovered.
When SHA-256 hashes are computed accurately they serve as an attestation that a certain amount of computing power has been used to find the number. The most recent prime number to be found is \$2^(77,232,917) − 1\$. It was found by a computer just like SHA-256 hashes are found by computers. SHA-256 hashes are easier to find than new prime numbers, however, and this is where hash-based metrics derive their power.
Every SHA-256 hash has 64 hexadecimal characters in it. For example, here is the SHA-256 hash for the word "yank".
"yank"(SHA-256) = 45F1B9FC8FD5F760A2134289579DF920AA55830F2A23DCF50D34E16C1292D7E0
Compare this to the SHA-256 hash of the three letters "yan".
"yan"(SHA-256) = 281ACA1A80B52620BD717E8B14A0386B8ADA92AE859AC2C8A2AC222EFA02EDBB
Compare this alternately to the SHA-256 hash of the two letters "ya".
"ya"(SHA-256) = 6663103A3E47EFC879EA31FA38458BE23BE0CE0895F3D8B27B7EA19A1120B3D4
Lastly, compare this to the SHA-256 hash of the single letter "y".
"y"(SHA-256) = A1FCE4363854FF888CFF4B8E7875D600C2682390412A8CF79B37D0B11148B0FA
If you hash enough random phrases, kind of like monkeys on a typewriter, eventually you will find a hash that matches a certain pattern. In the case of the hash for "ya", note that it begins with the pattern "666". This is similar to Bitcoin, except Bitcoin requires that hashes be found matching the pattern beginning with "000". Any hash that can be created by plugging information from the previous block into the SHA-256 hashing algorithm can be used to create the next block, as long as it has the right amount of leading zeros in the number, the network will agree on it and the block reward will be yours.
Since more and more people wish to mine Bitcoin every day, there is more computer power going to finding SHA-256 hashes, so the Bitcoin software automatically adjusts the difficulty of the consensus metric by requiring an increased amount of leading zeros to form consensus. This guarantees that new blocks are created in roughly the same increments of time as previous blocks.
Commonly known as Proof-of-Stake (PoS) metrics, these metrics establish consensus because everyone runs the same amount of risk if they fail to create correct blocks. Rather than demanding each node finds an arbitrary number to add a block, as with hash-based metrics, risk-based metrics only demand that some amount of money is at risk if the validator fails to create good blocks. The metric that all nodes agree upon here is whether or not another particular node has created a block in good faith. Rather than relying on hashing arbitrary numbers to make sure a certain amount of work has gone into creating a new block, risk-based chain nodes only need to agree that a certain amount has been staked and under what conditions that stake should be slashed.
Risk-based chains depend upon quick, immediate, and irreversible repercussions to any block creators that fail to create what other nodes in the network consider to be quality blocks. By enforcing risk of resources lost, the process of hash-based metrics (which also relies on people not wanting to waste resources to work) can be shortcutted and implemented in a simpler way. Although fully risk-based blockchains are a topic for current research and have yet to be implemented in Ethereum, there is good reason to believe that the model will operate sufficiently when implemented properly in software.
Proof of work is a consensus protocol that considers the valid blockchain in the network to be the chain that was most computationally expensive to create. The computational work that is referred to here is the work that had to be done to add all of the blocks to the current blockchain. This work is done by network nodes and must be computationally difficult, so as to make the work non-trivial, but must also be feasible, so as to be attainable after a reasonable amount of effort is exerted. Ultimately, the network will rely on nodes providing this POW in order to maintain the blockchain and is, therefore, in the best interest of the network to require a sensible POW.
In the Ethereum network, as well as in many other blockchain networks, obtaining the POW requires finding a hash of the block that is to be added to the blockchain. This hash is obtained by hashing a string consisting of the block’s data and a nonce (the method of creating this string may vary but the overall process is the same). This hash must be less than a certain threshold (determined by the difficulty of the network) and as soon as a node presents a nonce that produces this hash, the corresponding block is accepted and added to the blockchain.
The way this valid hash is found is by modifying the nonce, usually initializing it to zero and incrementing at each iteration, until a hash that is below the network threshold is produced. This process is called mining. Due to the nature of the hash functions used in mining the only way to find a valid nonce is through brute force, i.e. checking every possible value of the nonce until a hash that meets the network requirements is found. It is for this reason that providing a valid nonce is considered a POW.
Proof of Stake (PoS) is a category of consensus algorithms for public blockchains that depend on a validator’s economic stake in the network. In proof of work (PoW) based public blockchains (e.g. Bitcoin and the current implementation of Ethereum), the algorithm rewards participants who solve cryptographic puzzles in order to validate transactions and create new blocks (i.e. mining). In PoS-based public blockchains (e.g. Ethereum’s upcoming Casper implementation), a set of validators take turns proposing and voting on the next block, and the weight of each validator’s vote depends on the size of its deposit (i.e. stake). Significant advantages of PoS include security, reduced risk of centralization, and energy efficiency.
In general, a proof of stake algorithm looks as follows. The blockchain keeps track of a set of validators, and anyone who holds the blockchain’s base cryptocurrency (in Ethereum’s case, ether) can become a validator by sending a special type of transaction that locks up their ether into a deposit. The process of creating and agreeing to new blocks is then done through a consensus algorithm that all current validators can participate in.
There are many kinds of consensus algorithms, and many ways to assign rewards to validators who participate in the consensus algorithm, so there are many "flavors" of proof of stake. From an algorithmic perspective, there are two major types: chain-based proof of stake and BFT-style proof of stake.
-
In chain-based proof of stake, the algorithm pseudo-randomly selects a validator during each time slot (eg. every period of 10 seconds might be a time slot), and assigns that validator the right to create a single block, and this block must point to some previous block (normally the block at the end of the previously longest chain), and so over time most blocks converge into a single constantly growing chain.
-
In BFT-style proof of stake, validators are randomly assigned the right to propose blocks, but agreeing on which block is canonical is done through a multi-round process where every validator sends a "vote" for some specific block during each round, and at the end of the process all (honest and online) validators permanently agree on whether or not any given block is part of the chain. Note that blocks may still be chained together; the key difference is that consensus on a block can come within one block, and does not depend on the length or size of the chain after it.
Proof of Authority (POA) is a subset of POS consensus algorithms utilized by primarily by testnets and private or consortium networks. In POA-based blockchains, transaction validity is ultimately determined by a set of approved on-chain accounts, referred to as 'authority nodes'. The criteria for determining authority nodes are decided deterministically through an approach codified in the network’s governance structure.
POA is widely considerded to be the fastest route to consensus, but relies on the assumption that the validating node has not been compromised. Non-validating actors can access and use the network just as they would a public ethereum network (by leveraging p2p transactions, contracts, accounts etc.)
POA consensus relies on the validators reputation and past performance. The idea is that the validator node is staking its identity/reputation to mine. An important aspect in private consortium networks is the link between on-chain addresses to known, real world identities. Thus, We can say that the validating nodes are staking their "identity" or "reputation" (rather than their economic holdings). This creates some level accountability for validators and is best suited for enterprise, private, or test networks.
POA is currently employed by the test network Kovan, the POA network, and can be configured easily in Parity for private consortiums networks.
Delegated Proof of Stake (DPOS) is a modified form of Proof of Stake where network participants vote to elect an array of delegates (also called witnesses) to validate and secure the blockchain. These delegates are somewhat similiar to authority nodes in POA, except their authority may be revoked by the voters.
In DPOS consensus, like in POS, the weight of the vote is proportional to the amount of stake injected by the user. This creates a scenario where larger token holders have proportionally more voting power than smaller ones. This makes sense from a game theoretical perspective, as those with the more economic 'skin-in-the-game' will naturally have a larger incentive to elect the most efficient delegate witnesses.
In addition, delegate witnesses recieve a reward for validating each block, and thus are incentivised to remain honest and efficient - so as to not be replaced. However, there are ways to make a “bribe” that are quite plausible; for example, an exchange can offer interest rates for deposits (or, even more ambiguously, use the exchange’s own money to build a great interface and features), with the exchange operator using the large quantity of deposits to vote as they wish in a DPOS consensus.
Ethash is an Ethereum Proof of Work (PoW) algorithm that is dependent on the generation of the initial epoch of a dataset that is approximately 1GB in size known as the Directed Acyclic Graph (DAG). The DAG uses a version of the Dagger-Hashimoto Algorithm, which is a combination of Vitalik Buterin’s Dagger algorithm and Thaddeus Dryja’s Hashimoto algorithm. The Dagger-Hashimoto Algorithm is the mining algorithm used by Ethereum 1.0. Over time the DAG grows linearly and is updated once every epoch (30,000 blocks, 125 hours).
The PoW algorithm involves:
- Seed is computed for each block by scanning through prior block headers of the DAG.
- Cache is a 16MB pseudorandom cache that is computed from the seed for storage in Light Clients.
- Data Generation of the DAG from the cache to use for storage on Full Clients and Miners (where each item in the dataset only depends on a small number of items from the cache).
- Miners undertake mining by taking random slices of the dataset and hashing them together. Verification may be performed using the stored cache and low memory to regenerate specific pieces of the dataset required.
-
Ethash-DAG: https://github.com/ethereum/wiki/wiki/Ethash-DAG
-
Ethash Specification: https://github.com/ethereum/wiki/wiki/Ethash
-
Mining Ethash DAG: https://github.com/ethereum/wiki/wiki/Mining#ethash-dag
-
Dagger-Hashimoto Algorithm: https://github.com/ethereum/wiki/blob/master/Dagger-Hashimoto.md
-
DAG Explanation and Images: https://ethereum.stackexchange.com/questions/1993/what-actually-is-a-dag
-
Ethash in Ethereum Yellowpaper: https://ethereum.github.io/yellowpaper/paper.pdf#appendix.J
-
Ethash C API Example Usage: https://github.com/ethereum/wiki/wiki/Ethash-C-API
The POS consensus algorithm is expected to be introduced with this project, POS functions as described above.
Polkadot is an inter-chain blockchain protocol that will include integration with the Proof of Stake (POS) chain, allowing the parachain to gain consensus without its own internal consensus.
-
Relay-Chains that are connected to all Parachains and coordinate Consensus and transaction delivery between constituent blockchains, and uses a Validation Function to facilitate finalisation of Parachain transactions by verifying the correctness of PoV block candidates.
-
Parachains (parallelised chains across the network) that are constituent blockchains which gather and parallelise the processing of transactions to achieve scalability.
-
Trust-free Transaction Relaying directly between constituent blockchains instead of through intermediaries or decentralised exchanges.
-
Pooled Security that checks Parachain transaction validity against Consensus Protocol Rules (Rules). Security is achieved by bonding a proportion of Staking Token capital from each Group Member that is determined through dynamic Governance System. Group Membership requires the bonding of input of staking tokens from Validators, and Nominators, which may be deducted in the event of bad behaviour with Proofs of Misbehaviour in Tries.
-
Bridges provide extensibility by decoupling the linkage between blockchain networks that have different consensus architecture mechanisms.
-
Collators that are responsible for policing and maintaining a specific Parachain by collating its Available transactions into Proof of Validity (PoV) candidate blocks, reporting to Validators to prove that the transactions are valid and correctly execute in a block. Collators are incentivised with payment of any transaction fees they collected from creating the PoV candidate block if it has the winning ticket (signed by a Collator with the closest Polkadot address to the Golden Ticket) and becomes canonical and finalised. Collators are given a Polkadot address. Collators are not bonded with staking tokens.
-
Golden Ticket that is a specific Polkadot address in every block for each Parachain that contains a reward. Collators are given a Polkadot address and feed Validators with PoV candidate blocks that are signed by the Collator. Winners of the reward have a Collator Polkadot address in the PoV candidate block that is closes to the Golden Ticket Polkadot address
-
Fisherman that monitor the Polkadot network transactions to discover bad behaviour in the Polkadot Community. Fisherman who take a Validator to a Tribunal and prove they behaved badly are incentivised with a proportion of the Validator’s bond, since bonds are used as punishment to pay for bad behaviour.
-
Validators that are maintainers in the Parachain Community who are deployed to different Parachains to police the system. Validators agree on the root of Merkle Trees. Validators must make transactions Avaiable. Validators may be taken to a Tribunal by a Fisherman for not making a transaction Available and associated Collators may challenge whether the transaction was made available a Proof of Collator.
-
Nominators (similar to PoW mining) passively oversee and vote for Validators they deem to be acceptable by funding them with staking tokens.
Polkadot’s Relay-Chains use a Proof of Stake (PoS) system where a structured State Machine (SM) performs multiple Byzantine-Fault Tolerant (BFT) Consensus' in parallel so as the SM progresses it converges on a solution that comprises valid candidate blocks across multiple Parachain dimensions. Valid candidate blocks in each Parachain is determined based on the Availability and Validity of transactions, since according to the Consensus Mechanism the Destination Validators (next block) may only enact incoming messages from Source Validators (previous block) when they have sufficient transaction information that is both Available and Valid. Validators vote for valid candidate blocks that are proposed by Collators using Rules to reach Consensus.
-
Polkadot link: https://polkadot.network
-
Polkadot presentation at Berlin Parity Ethereum link: https://www.youtube.com/watch?v=gbXEcNTgNco