Skip to content

Latest commit

 

History

History
153 lines (84 loc) · 19 KB

consensus.asciidoc

File metadata and controls

153 lines (84 loc) · 19 KB
Raw

Consensus

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.

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

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

Validation for Hash-Based Metrics

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 the amount of total people wanting to mine Bitcoin is increasing, there is constantly more power per-second going into finding SHA-256 hashes. The Bitcoin software deals with this contingency by automatically adjusting the difficulty of the consensus metric, requiring an increased amount of leading zeros to form consensus. 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 ten minutes, though it can easily be changed. In Ethereum, the average block time is about 10 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 netrics 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.

POW

POW

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

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

Consensus Of Ethereum

Introduction To Ethash

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

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 with this project, POS functions 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 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.

References