Skip to content

Latest commit

 

History

History
148 lines (84 loc) · 21.6 KB

consensus.asciidoc

File metadata and controls

148 lines (84 loc) · 21.6 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 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 should and should not be considered as truth. 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 in the access to 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. We explore all this within this chapter.

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 context of 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 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 finding difficult numbers, 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 put together, might be said to have the combined 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 if a hash fits the parameters is to use the analogy of a jigsaw puzzle. This puzzle would be quite difficult and time consuming to do, but it would be 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 like 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 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". 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, 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 the relatively primative 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 tweeking 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 tweek 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 an increased 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 offchain data, but about internal onchain 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 that 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 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. 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 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.

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

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 (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 of 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.

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

Consensus Of Ethereum

Introduction To 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 for ever more, 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 low memory to regenerate specific pieces of the dataset required.

PoW Function

Why GPU Does Matter ?

Introduction To Casper

PoS

The PoS consensus algorithm is expected to be introduced to the project. The functionality of PoS functions can be found as described above.

Slash Protocol

TODO

Introduction The 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 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 closest 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 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 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.

References