Consensus Algorithms

patrickcty 9月 27, 2017

PoW(Proof of Work)

Explanation

PoW is a consensus strategy used in Bitcoin network.

In PoW, each node of the network is calculating a hash value of the constantly changing block header.

The consensus requires that the calculated value must be equal or small than a certain given value.

When one node obtains the relevant value, all other nodes must mutally validated in case of frauds. Then a new block is added to the blockchain.

Example

Bitcoin network regard the blockchain head as the input, including:

• version number(4 Bytes)
• previous block hash(32 Bytes)
• Merkle root(32 Bytes, formed by transactions in current block)
• timestamp(4 Bytes)
• bits(4 Bytes, representing the difficulty of the calculation)
• nonce(4 Bytes, a random number, by changing which miners guess the solution)

As has been mentioned above, miners changes the value of the nonce(and the timestamp) to guess the solution. And the function that is used to calculate the result is SHA256.

The solution or the target value is controlled by ‘bits’, and here is the computational formula：

targe value = max target value / bits

And max target value is a constant value:

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

That is to say, the larger the ‘bits’ value is, the harder the target value can be guessed.

Above all, the procedures botcoin miners do to prove their work can be concluded with three steps:

• generate the Merkle Root Hash using transactions
• combine all the fields as the input
• change the nonce value in the blockchain head and calculate SHA256(SHA256(Block_Header)), compare it with the target value, if it is smaller then the proof is done

Other PoW Protocols

PoW needs a lot of computer calculations which is a waste of resources. To take advantage of the loss, some PoW protocols are designed to have some side-applications.

• Primecoin searches for special prime number chains to be used in mathematical research.
• PoB(Proof of Burn) uses bitcoin instead of electricity to mine blocks.(It’s kind of similar to buying a lottery)

PoS(Proof of Stake)

Explanation

PoS requires people to prove the ownership of the amount of currency, which means that preople with more currencies is more likely to forge the next block.

To avoid the result that the single richest prople domain the network, solutions are often proposed with the combination of the stake size.

P.S. PoS still has to calculate the hash value.

Examples

Blackcoin uses a formula that looks for the lowest hash value in combination with the size of the stake.

In peercoin, older and larger sets of coins have a greater probability of mining the next block.

PBFT(Practical Byzantine Fault Tolerance)

Explanation

PBFT is a replication algorithm to tolerate byzantine faults.

A new block is determined in a round.

In each round, a primary would be selected according to some rules. And it is responsible for ording the transaction.

The whole process could be divided into three phrases: pre-prepared, prepared and commit. In each phrase, a node would enter next phrase if it has received votes from over 2/3 of all nodes.

P.S. PBFT requires that every node is known to the network.

DPoS(Delegated Proof of Stake)

Explanation

In DPoS, miners get their priority to generate the blocks according to their stake.

Stakeholders elect their delegates to generate and validate a block, which will significantly improve the speed of confirmation.

Besides, the parameters of the network such as block size and block intervals could be tuned by elected delegates.

P.S. DPoS still has to calculate the hash value.

Ripple

Explanation

Ripple is a consensus algorithm that utilizes collectively-trusted subnetworks within the large network.

In this network, nodes are divided into two types:

• server: participate consensus process
• client: only transfer funds

In PBFT, nodes have to ask every node, but in Ripple each node only has a Unique Node List(UNL) to query.

When determining whether to put a transaction into the ledger, the server would query the nodes in UNL. If the received agreements have reached 80%, the transaction would be packed into the ledger.

Tendermint

Explanation

In Tendermint, a new node is determined in a round.

A propser would be selected to broadcast an unconfirmed block in this round.

It would be devided into three steps:

1. Prevote
2. Precommit
3. Commit

Only if the node has received 2/3 or the agreement can it reach the next step. And when the node has received 2/3 of the commits, it accepts the block.

It’s similar to PBFT, but in this method nodes have to lock their coins to become validators.

P.S. Tendermint requires that every node is known to the network.