Skip to content

Latest commit

 

History

History
170 lines (96 loc) · 24.7 KB

consensus.asciidoc

File metadata and controls

170 lines (96 loc) · 24.7 KB
Raw

Consensus

"Consensus" within the Ethereum network refers to the capacity for multiple nodes, users or agents to agree on the "world state" of Ethereum at a given point in time. This is closely related to but distinct from the conventional definition of consensus, which is defined as a general agreement between individuals or groups around a particular topic or decision. In the blockchain context, the community must solve the challenges of coming to consensus both technically (within the computer-run network) and socially (to ensure that the protocol does not fork or fracture). This chapter will outline some of the technicalities around establishing consensus.

When it comes to the core function of decentralized record keeping and verification, it can become problematic to rely on trust alone to ensure that information derived from state updates is correct. This rather general challenge is particularly pronounced in decentralized networks because there is no central entity to decide what is true. The lack of a central decision-making entity is one of the main attractions of blockchain platforms, because of the resulting capacity to resist censorship and the lack of dependence on authority for permission to access information. However, these benefits come at a cost: without a trusted arbitrator, any disagreements, deceptions or differences need to be reconciled using other means. Possible approaches here include mathematical, economic and social techniques. A decentralized system is therefore more resilient to attack but can be less decisive in responding to changes.

The capacity to come to consensus and trust information will have important implications for the future adoption and utility of blockchain platforms as hosts to new asset classes, and blockchain technology as infrastructure. To address this challenge and maintain the valued property of decentralization, the community continues to experiment with different models of consensus. This chapter explores all these issues.

Consensus Metrics

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 the context of blockchain technology, consensus metrics must be 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 definitely 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 defrauding the network by submitting blocks containing false information. As a result of the consensus metric of a blockchain, its integrity is not only established but 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.

Hash-Based Metrics

Commonly known as Proof-of-Work (PoW) metrics, these metrics establish consensus because protocols that use them set computers to work on solving hard problems, most commonly using a hash function to find suitable hashes. The difficulty in finding a hash that fits the parameters of the network requires nodes to commit processing power and use electricity to compete with other nodes to come up with a valid hash. For the sake of illustration, consider supercomputers whose only job in life is to search all integers for prime numbers. Now consider a whole network of average computers. These computers, when combined, might have the computational 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, despite the significant difficulty in producing a hash that fits the criteria set by the network. One way of imagining the difference between computing a hash and verifying that a hash fits the parameters is to use the analogy of a jigsaw puzzle: the puzzle can be quite difficult and time consuming to do, but it is easy to tell at a glance if it has been completed.

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 as SHA-256 hashes are found by computers. SHA-256 hashes are easier to find than new prime numbers; however, the difficulty inherent in finding hashes gives hash-based metrics their power.

Every SHA-256 hash has 64 hexadecimal characters in it. For example, here is the SHA-256 hash for the word "yank". SHA256("yank") = 45F1B9FC8FD5F760A2134289579DF920AA55830F2A23DCF50D34E16C1292D7E0

Compare this to the SHA-256 hash of the three letters "yan".

SHA256("yan") = 281ACA1A80B52620BD717E8B14A0386B8ADA92AE859AC2C8A2AC222EFA02EDBB

Compare this further to the SHA-256 hash of the two letters "ya".

SHA256("ya") = 6663103A3E47EFC879EA31FA38458BE23BE0CE0895F3D8B27B7EA19A1120B3D4

Lastly, compare this to the SHA-256 hash of the single letter "y".

SHA256("y") = A1FCE4363854FF888CFF4B8E7875D600C2682390412A8CF79B37D0B11148B0FA

Notice how, despite the small change in the letters being hashed, the resulting output hashes are vastly different.

If you hash enough random phrases, 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 the relatively primitive hash-based metric approach of Bitcoin, except Bitcoin requires that hashes be found by matching the pattern beginning with "000". Candidate hashes are created by tweaking block information and feeding it into the SHA-256 hashing algorithm. As long as the output hash has the right number of leading zeros, the network will accept it and the block reward can be yours. If the output hash doesn’t have enough leading zeros, unlucky. You have to tweak some of the information in your block and hash again. The more leading zeros required, the more difficult finding an acceptable hash will be.

Since the total number of processors wanting to mine Bitcoin seems to be continuously increasing, there is (currently) ever more compute effort per second going into finding SHA-256 hashes to confirm Bitcoin blocks. The Bitcoin protocol deals with this ongoing change by periodically adjusting the difficulty of the consensus metric upwards, requiring a greater number of leading zeros for acceptable blocks. This acts as insurance that new blocks are created in roughly the same increments of time as previous blocks. For the Bitcoin network, that increment is targeted to ten minutes, though it is often less because the Bitcoin network waits for roughly two weeks to adjust the difficultly. In contrast to this, Ethereum re-adjusts its difficultly every block, and thus does a very good job of maintaining the target block separation time average of about 14 seconds.

Risk-Based Metrics

Commonly known as Proof-of-Stake (PoS) metrics, these establish consensus based on the fact that everyone who chooses to create invalid blocks stands to lose a great deal more than they have to gain by creating valid ones. This metric is manufactured by consensus not about external off-chain data, but about internal on-chain data. Hash-based consensus metrics are primarily concerned with the quality and precise nature of SHA-256 hashes. Risk-based metrics are primarily concerned with the risk which any particular node takes when adding a new block.

The metric that all nodes agree upon here is which nodes have created correct blocks and which have not. In a way, this is already built into the Bitcoin protocol. The Bitcoin protocol assumes that the correct block is the one which the most nodes are mining. It assumes that the miners will not choose an incorrect block, as it is not in their best interests to mine bad blocks.

Risk-based chains on the other hand, depend upon quick, immediate, and irreversible repercussions to any block creators that fail to create what other nodes in the network consider to be correct blocks. By risking the loss of resources, the hash-based metrics (which also rely on people not wanting to waste resources to work) can be implemented with less work. Research is currently underway to implement this model of consensus metric in Ethereum.

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 it 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 PoW.

Proof-of-Stake (PoS)

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 PoS algorithm works 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 Byzantine Fault Tolerance (BFT) style proof of stake.

  • In chain-based proof of stake, the algorithm pseudo-randomly selects a validator during each time slot (e.g. every period of 10 seconds might be a time slot), and assigns that validator the right to create a single block; 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.

PoA

Proof of Authority (PoA) is a subset of PoS consensus algorithms mainly used 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 considered 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.

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 of private consortium networks is the link between on-chain addresses and 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 of accountability for validators, and is best suited to enterprise, private, or test networks.

PoA is currently employed by the Kovan test network, and can be configured easily in Parity for private consortia’s networks.

DPoS

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 similar 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 more economic 'skin in the game' will naturally have a larger incentive to elect the best delegate witnesses.

In addition, delegate witnesses receive a reward for validating each block and thus are incentivized 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 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

Ethash is an Ethereum Proof-of-Work (PoW) algorithm that is dependent on the generation and analysis of a large dataset, known as the DAG (simply because it is a directed acyclic graph). The DAG started with a size of about 1GB and will continue to slowly and linearly grow in size evermore, being updated once every epoch (30,000 blocks, or roughly 125 hours). The Ethash PoW algorithm uses a version of the Dagger–Hashimoto Algorithm, which is a combination of Vitalik Buterin’s Dagger algorithm and Thaddeus Dryja’s Hashimoto algorithm.

Seed, Cache, Data Generation

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 a little memory to regenerate specific pieces of the dataset required.

PoW Function

Why does using GPUs matter?

Although Ethereum can be mined using CPUs, using them to mine Ethereum would not be a profitable exercise. Today most mining relies on the use of Graphical Processing Units (GPU). Modern GPUs—while great for 3D graphics and gaming—are also excellent at processing the computation-intensive Dagger–Hashimoto Algorithm which is necessary for PoW consensus on the Ethereum network.

Use of "normal" GPUs for carrying out the PoW on the Ethereum network means that more people around the world can participate in the mining process. The more independent miners there are, the more decentralized the mining power and we can avoid a situation like with Bitcoin where much of the mining power is concentrated in the hands of a few large industrial mining operations. The downside of the use of GPUs for mining is it led to the worldwide shortage GPUs in 2017, causing their price to rocket and an outcry from gamers. This led to purchase restrictions at retailers limiting buyers to a single GPU per customer or two if you are in luck.

Until recently, the threat of Application-Specific Integrated Circuit (ASIC) miners on the Ethereum network was largely non-existent. To use ASICs for Ethereum requires the design, manufacture, and distribution of highly customized hardware. Producing them requires considerable investment of time and money. The Ethereum developers' long-expressed plans to move to a PoS consensus algorithm likely kept ASIC suppliers away from targeting the Ethereum network for a long time. As soon as Ethereum moves to PoS, ASICs designed for the PoW algorithm will be rendered useless—that is, unless miners can use them to mine other cryptocurrencies instead. The latter option is now a reality with a range of other Ethash-based consensus coins available, such as PIRL, Ubiq, and of course Ethereum Classic, which has pledged to remain a PoW coin for the foreseeable future. This means that we will likely see ASIC mining begin to become a force on the Ethereum network while is it still operating on PoW consensus.

Casper

PoS

The PoS consensus algorithm is expected to be introduced to the project. The operation of PoS is described above.

Slash Protocol

Polkadot

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.

Polkadot comprises:

  • Relay-Chains connected to all Parachains, which coordinate Consensus and transaction delivery between constituent blockchains, and uses a Validation Function to facilitate finalization of Parachain transactions by verifying the correctness of PoV block candidates.

  • Parachains (parallelised chains across the network): constituent blockchains which gather and parallelize the processing of transactions to achieve scalability.

  • Trust-free Transaction Relaying directly between constituent blockchains instead of through intermediaries or decentralised exchanges.

  • Pooled Security checks Parachain transaction validity against Consensus Protocol Rules. Security is achieved by bonding a proportion of Staking Token capital from each Group Member that is determined through a dynamic Governance System. Group Membership requires the bonding of staking tokens from Validators and Nominators, which may be deducted in the event of bad behavior with Proofs of Misbehavior in Tries.

  • Bridges provide extensibility by decoupling the linkage between blockchain networks that have different consensus architecture mechanisms.

  • Collators 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 incentivized 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 finalized. Collators are given a Polkadot address. Collators are not bonded with staking tokens.

  • Golden Ticket: 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 signed by the Collator. Winners of the reward have a Collator Polkadot address in the PoV candidate block that is closest to the Golden Ticket Polkadot address.

  • Fishermen monitor the Polkadot network transactions to discover bad behavior in the Polkadot Community. Fishermen who take a Validator to a Tribunal and prove they behaved badly are incentivized with a proportion of the Validator’s bond, since bonds are used as punishment to pay for bad behavior.

  • Validators 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 available. 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 with 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 Consensuses 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 are 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.

References