The introduction
Ethereum is the next big decentralized blockchain application after Bitcoin. As a decentralized application, the Ethereum network can safely operate on nodes distributed around the world, relying on the consensus mechanism behind it. This article describes the consensus mechanism used by Ethereum.
What is consensus
Consensus refers to the unified status of all nodes in a distributed system.
In the case of Ethereum, the essence of ethereum is a state machine, where each node stores the current “world state” (account balances, smart contract data, etc.) that changes with every transaction in the Ethereum network, such as transferring money or creating contracts. As shown below:
In practice, in order to determine the order of each transaction and avoid double-spending problems, Ethereum packages a batch of transactions into a block every 10 to 20 seconds and changes the current “state of the world” based on the transactions within the block. As shown in the figure below.
At the same time, each block also contains the hash value of the previous block (parentHash field), which is linked back and forth to determine the order in which transactions took place, thus forming a “blockchain”.
Starting with the founding block, each new block added changes the current chain, which in turn changes the current “state of the world.” So what we mean by consensus, in the ethereum context, is agreement on the right chain and “state of the world.”
Ethereum’s consensus algorithm
As stated above, the consensus of Ethereum is to agree on the correct chain, so the consensus algorithm’s job is to let the nodes in the network get the correct chain, and if a malicious node tries to spread the wrong chain, the consensus algorithm can reject the wrong chain.
Next, let’s talk about the Proof of Work algorithm that Ethereum is currently using
Proof of Work
The idea of work proof algorithm is that nodes need to pay some work to produce new blocks, so as to increase the difficulty of malicious nodes to generate error chain, and reward nodes that produce new blocks correctly, so as to attract more honest nodes to join and increase the security of the network.
Ethash algorithm
When Ethereum nodes want to add new blocks to an existing chain, they need to do some calculations. To avoid wasting productivity by people developing machines specifically for mining, Ethereum uses an I/ O-constrained algorithm called Ethash. The following is the algorithm process:
1. Prepare data
Before the calculation, the node first needs to prepare two groups of data: cache and dataset for the later workload proof calculation. Ethereum counts from 0 with 30,000 nodes in a cycle (epoch) :
epoch = Math.floor(block_number / 30000);
Copy the codeThe cache and dataset change with each cycle.
First, the node computs a seed hash of 256 bits, starting with all zeros, after which the next cycle’s seed hash will be the kecCAk-256 hash of the previous cycle’s seed hash. That is:
const initSeed = Buffer.alloc(32.0) // 256位0
function getSeed(epoch) { // epoch is the number of cycles
let seed = initSeed;
for(let i = 0; i < epoch; i++) {
seed = keccak256(seed);
}
return seed;
}
Copy the codeAfter calculating the seed hash value, we need to calculate the size of the cache, which is in bytes and is an integer multiple of the constant HASH_BYTE(64). The upper limit of the cache size increases linearly with the period, but to avoid the periodic pattern of the cache data caused by the linear increase in the size, we use the prime multiple of the maximum HASH_BYTE that is smaller than the upper limit of the current period as the cache size for the period. The specific process is as follows:
const INIT_CACHE_SIZE = 2 ** 24; // The initial cahCE size
const CACHE_SIZE_GROWTH = 2 ** 17; // The amount of cache growth per cycle
const HASH_BYTE = 64;
function getCacheSize(epoch) {
size = INIT_CACHE_SIZE + CACHE_SIZE_GROWTH * epoch;
size -= HASH_BYTE;
while(! isPrime(size / HASH_BYTE)) { size -=2 * HASH_BYTE;
}
return size;
}
Copy the codeWe then populate the cache based on the calculated cache size. The seed hash is used first (see code for filling), and after filling, three rounds of RandMemoHash are performed to get the final cache. The specific process is as follows:
const xor = require('buffer-xor'); // Bitwise xor on Buffer
const HASH_BYTE = 64;
function makeCache(size, seedHash) {
let n = size / HASH_BYTE;
// Populate with seedHash
let cache = [seedHash];
for(let i = 1; i < n; i++) {
cache.push(keccak512(cache[i-1]));
}
// Do RandMemoHash three times
for(let _ = 0; _ < 3; _ + +) {for(let i = 0; i < n; i++) {
v = cache[i].readUInt32LE(0) % n;
cache[i] = keccak512(xor(cache[(i - 1+ n) % n], cache[v])); }}return cache;
}
Copy the codeAfter obtaining the cache, we need to calculate the second part of the data — the dataset. First, we calculate the size of the dataset. The calculation method is similar to calculating the cache size, except that the initial parameter is different and the unit is MIX_BYTE(128). As follows:
const INIT_DATASET_SIZE = 2 ** 30; // The initial dataset size
const DATASET_SIZE_GROWTH = 2 ** 23; // The increment of each period dataset
const MIX_BYTE = 64;
function getCacheSize(epoch) {
size = INIT_DATASET_SIZE + DATASET_SIZE_GROWTH * epoch;
size -= MIX_BYTE;
while(! isPrime(size / MIX_BYTE)) { size -=2 * MIX_BYTE;
}
return size;
}
Copy the codeAfter obtaining the size of the dataset, we need to calculate the contents of the dataset according to the cache contents.
(Code to be added)Copy the codeAfter obtaining the contents of cache and dataset, we can perform the calculation of proof of work.
2. Proof of work calculation
In the block header, two fields are used for proof-of-work calculations — mixHash and Nounce. The length of mixHash is 256 bits and that of nounce is 64 bits. We call the block header that excludes these two fields truncatedHeader.
Let’s start with the PoW function, which takes truncatedHeader, nounce, and dataset, hashes a few columns, and outputs two 256-bit values: mixHash and result. As follows:
function PoW(truncatedHeader, nounce, dataset) {
// Perform a series of hashes
// ...
return {
mixHash,
result
};
}
Copy the codeDifferent nounce values produce different mixhashes and results.
There is also a field in the block header, the difficulty field, which is calculated from the block number, production time, and the previous block’s difficulty field. The difficulty for each block is automatically adjusted to control block production speed.
A node packages a new block header without the mixHash and Nounce fields, also known as truncatedHeader. In order for the block to be headchained, the node needs to do something:
- To find anounceValue (0 ~ 2^ 64-1) and use itnounce,truncatedHeaderAnd the current perioddatasetPlug into the PoW function, and you getmixHashValues andresultValue.
- resultValue must meet the following requirements:result< (2 ^ 256 /difficulty).
- ifresultThe value meets the condition and willmixHashValues andnounceThe value is written to the block header and the block is broadcast out, making the block on-chain.
- ifresultIf the value is not satisfied, continue to try a different onenounce.
- If a block broadcast by other nodes in the network is received during the calculation, the block is verified, and if the block is valid, the block is accepted and its own block is repackaged, ready to be added to the block.
The above process, also known as “mining”, is a process of constantly trying nounce and hashing and requires a certain amount of work.
Also, because each block stores the hash of the previous block in the parentHash field, if you want to modify one of the blocks on the chain, you need to recalculate the Nounce values of all subsequent blocks. This greatly increases the difficulty of modifying blocks.
The choice of the chain
Since each node can add new blocks after the previous block, it is inevitable that multiple nodes will add different blocks to the same height, resulting in fork, which makes the blocks in the network form a tree structure, as shown in the figure:
So how do nodes in a network choose the right chain? Bitcoin adopts the longest chain strategy, and selects the chain with the largest number of blocks. In the figure, the corresponding chain is 0->1->2->3B->4B->5.
Ethereum is slightly different. Ethereum first calculates the sum of the Block difficulty along the path from the root node of the Block tree (genesis node, Block 0) to each leaf node (Block 4A, Block 5, Block 4C). Choose the path with the greatest total difficulty as the correct chain. Nodes in the network add new blocks to the chain.
incentives
In Ethereum, every time a new block is created, 2Ether(December 3, 2021) revenue is generated, which goes into the address designated by the miner along with the gas fee for transactions on the block. But in addition to that, there are some additional rewards called ommer block rewards, which we’ll start with a little background.
In Bitcoin, the average block output time is controlled at 10 minutes. When one node finds the correct block, it broadcasts the block to the network. When the other nodes receive the block, they stop the current calculation and repackage the new block. The broadcast block in the network has a certain delay (it may take tens of seconds for other nodes to receive it), but this delay is negligible compared to the computation time of 10 minutes. As a result, there are not too many duplicate blocks in the Bitcoin network when calculating blocks of the same height.
However, in the Ethereum network, the average block generation time is very short (10-20s), and many times, when calculating blocks of the same height, there will be a delay in broadcasting, resulting in a lot of extra blocks to be calculated. For example, when the height of block 50000 is calculated, node A finds the correct block 50000 and broadcasts to the network. Node B calculates block 50000 10 seconds later and starts to broadcast to the network. It takes 5 seconds for node B to receive block 50000 calculated by node A. However, other nodes in the network have already calculated block 50001 based on Block 50000 of A, and node 50000 calculated by B will not be adopted.
Due to the fast block production speed and the influence of network delay, there will be a large number of redundant blocks, which will reduce the profit of miners. Too little profit will cause the loss of miners and reduce the security of the network. So Ethereum came up with a way to distribute revenue to ommer nodes.
OmmerBlock rewards
Ommer is an English term for siblings of parents, without reference to gender. Ethereum uses the word ommer instead of uncle or aunt to avoid gender arguments. But in Ethereum, ommer blocks are not just blocks that share a parent block with the parent block of the current block, but also blocks that are siblings to the parent block of the current block.
As shown in the figure, take Block 107 as an example, its six ancestors are Block 101 ~ 106, so the sibling blocks of the six ancestors, namely 101A, 104A, 104B and 106A, all belong to the Ommer Block of Block 107, while 100A is not.
When the node packages block 107, it will form a list of up to two Ommer blocks from the received ommer blocks and pack them together into block 107. The ommerHash field in the block header represents the hash value of the OMmer list. If block 107 packages the Ommer block, then it will receive an additional 1/32, 1/16 ether, as a reward for packaging the Ommer block.
So total revenue from digging up a block = basic revenue + gas fee + bonus for packaging ommer block.
The Ommer block, which gets bundled into block 107, also gets Ether. The gain depends on the difference between the height of the block and the height of the current block, as follows:
reward = (8 + N_ommer – N_current) / 8 * 2
Where 2 is the base revenue of the current block (excluding ommer bonus and gas revenue package)
For example, block 106A will receive (8+ 106-107) /8 * 2 = 14/8 Ether.
Ethereum’s use of ommer block rewards increases miners’ motivation to mine, ensures the number of nodes in the network, and improves network security.
Preventing Malicious Nodes
As mentioned earlier, what protection does the Ethereum network have if a malicious node wants to replace the main chain in the network with its own chain? Let’s look at the picture below:
As shown in the figure, if the malicious node wants to start branching off in block 101 to form a chain of its own, it needs to produce new blocks on its chain continuously. The probability of A node producing A new block is proportional to node computing power. For example, if node A has 25% computing power of the whole network, then the next block in the network has 25% probability to be produced by A.
Assuming that the malicious node has 25% computing power, the probability of it producing one block is 25%, the probability of two blocks is 0.25^2 = 0.125, and the probability of producing six blocks in a row is 0.25^6 = 0.000244140625, less than 0.1%.
So, as long as most of the computing power in the network is held by honest nodes, we have a high probability that the current chain in the network is the right one.
For more discussion On the correctness of chains, please refer to the article On Settlement Finality
The relevant data
- Ethereum EVM illastrated
- On Settlement Finality
- Ethereum Yellow Book