The Question of Mining

The Quest for Decentralized Mining

As the Ethereum protocol continues to evolve, one of the most pressing challenges facing the community is the question of mining decentralization. While the basic idea behind the mining algorithm is in place, the devil is in the details. In this article, we'll delve into the intricacies of the proposed mining algorithm, its benefits, and the challenges that remain.

A Hashcash-Based Implementation

The proposed mining algorithm is a Hashcash-based implementation, similar to Bitcoin's SHA256 and Litecoin's scrypt. The idea is for the miner to repeatedly compute a pseudorandom function on a block and a nonce, trying a different nonce each time, until eventually some nonce produces a result that starts with a large number of zeroes. The only room to innovate in this kind of implementation is changing the function.

The Function Definition

In Ethereum's case, the rough outline of the function, taking the blockchain state (defined as the header, the current state tree, and all the data of the last 16 blocks), is as follows:

Let h[i] = sha3(sha3(block_header) ++ nonce ++ i) for 0 < i < 15

Let S be the blockchain state 16 blocks ago.

Let C[i] be the transaction count of the block i blocks ago. Let T[i] be the (h[i] mod C[i])th transaction from the block i blocks ago.

Apply T[0], T[1] … T[15] sequentially to S. However, every time the transaction leads to processing a contract, (pseudo-)randomly make minor modifications to the code of all contracts affected.

Let S' be the resulting state. Let r be the sha3 of the root of S'.

If r < 2^256 / diff, then nonce is a valid nonce.

The Benefits of This Approach

This approach has several benefits. Firstly, it requires the entire blockchain state to mine, essentially requiring every miner to be a full node. This helps with network decentralization, as a larger number of full nodes exist. Secondly, because every miner is now required to be a full node, mining pools become much less useful. In the Bitcoin world, mining pools serve two key purposes: they even out the mining reward and provide centralized block validation. With this algorithm, the second argument is moot, and the first concern can be adequately met by peer-to-peer pools that do not give control of a significant portion of network hashpower to a centralized service.

ASIC-Resistance

This algorithm is almost by definition ASIC-resistant. Because the EVM language is Turing-complete, any kind of computation that can be done in a normal programming language can be encoded into EVM code. Therefore, an ASIC that can run all of EVM is by necessity an ASIC for generalized computation – in other words, a CPU. This also has a Primecoin-like social benefit: effort spent toward building EVM ASICs also has the side benefit of building hardware to make the network faster.

Challenges Remain

However, there are still several major challenges that remain. Firstly, it is not entirely clear that the system of picking random transactions actually ends up requiring the miner to use the entire blockchain. Ideally, the blockchain accesses would be random; in such a setup, a miner with half the blockchain would succeed only on about 1 in 216 nonces. In reality, however, 95% of all transactions will likely use 5% of the blockchain; in such a system, a node with 5% of the memory will only take a slowdown penalty of about 2x.

Secondly, and more importantly, however, it is difficult to say how much an EVM miner could be optimized. The algorithm definition above asks the miner to “randomly make minor modifications” to the contract. This part is crucial. The reason is this: most transactions have results that are independent of each other; the transactions might be of the form “A sends to B”, “C sends to D”, “E sends to contract F that affects G and H”, etc, with no overlap. Hence, without random modification there would be little need for an EVM miner to actually do much computation; the computation would happen once, and then the miner would just precompute and store the deltas and apply them immediately. The random modifications mean that the miner has to actually make new EVM computations each time the algorithm is run.

Community-Led Solutions

Another interesting point in favor of this kind of mining is that even if optimized hardware miners emerge, the community has the ability to work together to essentially change the mining algorithm by “poisoning” the transaction pool. Engineers can analyze existing ASICs, determine what their optimizations are, and dump transactions into the blockchain that such optimizations simply do not work with. If 5% of all transactions are effectively poisoned, then ASICs cannot possibly have a speedup of more than 20x. The nice thing is that there is a reason why people would pay the transaction fees to do this: each individual ASIC company has the incentive to poison the well for its competitors.

Conclusion

The question of mining decentralization is a complex one, and the proposed mining algorithm is still in its infancy. However, the benefits of this approach are clear: it requires the entire blockchain state to mine, making it more decentralized, and it is almost by definition ASIC-resistant. While challenges remain, the community has the ability to work together to address them. As the Ethereum protocol continues to evolve, it will be exciting to see how this approach develops and what implications it will have for the network.

Source: https://blog.ethereum.org/en/2014/03/20/the-question-of-mining