Our present proof of work framework, blockchain-based proof of work, represents the second version of our effort to establish a mining algorithm that is assured to stay CPU-friendly and resistant to enhancement by specialized hardware (ASICs) in the long run. Our initial attempt, Dagger, sought to advance the concept of memory-hard algorithms like Scrypt by devising an algorithm that is memory-intensive to compute but memory-friendly to validate, employing directed acyclic graphs (essentially, trees with multiple parent nodes). Our current approach adopts a significantly more stringent path: making the proof of work reliant on executing random contracts from the blockchain. Given that the Ethereum scripting language is Turing-complete, an ASIC capable of executing Ethereum scripts inherently serves as an ASIC for general computation, i.e., a CPU – a far more sophisticated rationale than “this is memory-hard so you can’t parallelize as much”. Naturally, there are concerns about “well, can you implement specific optimizations and still achieve a significant speedup”, but it can be posited that those are minor issues to address over time. The resolution is also elegant as it is concurrently an economic one: if someone builds an ASIC, then others will be prompted to seek types of computation that the ASIC cannot handle and “contaminate” the blockchain with such contracts. Regrettably, though, there exists one far greater hurdle to such strategies in general, which is fundamentally significant: long-range attacks.
A long-range attack fundamentally operates as follows. In a classic 51% attack, I place 100 bitcoins into a completely new account, then transfer those 100 bitcoins to a merchant in return for some instant-delivery digital good (let’s say, litecoins). I await delivery (e.g., after 6 confirmations), but then I promptly begin working on a new blockchain starting from a single block prior to the transaction sending the 100 bitcoins, and include a transaction instead sending those bitcoins back to myself. Next, I allocate more mining power to my fork than the whole network combined is directing to the main chain, and eventually, my fork surpasses the main chain and thus becomes the principal chain, meaning at the conclusion, I possess both the bitcoins and the litecoins. In a long-range attack, rather than initiating a fork 6 blocks back, I initiate the fork 60000 blocks back, or even at the genesis block.
In Bitcoin, such a fork is ineffective because you simply extend the time required to catch up. However, in blockchain-based proof of work, it poses a significant challenge. The rationale is that if you commence a fork directly from the genesis block, while your mining will start slowly, after a few hundred blocks you will be able to saturate the blockchain with contracts that are very simple for you to mine, yet arduous for others. One example of such a contract is simply:
i = 0
while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:
i = i + 1
You know that the contract will require precisely one million iterations before the hash aligns, so you can precisely calculate the number of steps and the amount of gas it will consume to execute and what the endpoint state will be, whereas others must actually run through the code. A crucial attribute of such a scheme, an inevitable consequence of the halting problem, is that it is mathematically provably impossible to devise a method for detecting such ingenious contracts in the general case without executing them. Consequently, the long-range attacker could fill the blockchain with such contracts, “mine” them, and persuade the network that it is performing an enormous amount of work while it is merely taking a shortcut. Hence, after several days, our attacker will be “mining” billions of times faster than the main chain, rapidly overtaking it.
Observe that the aforementioned attack makes few assumptions about how the algorithm operates; all it presumes is that the condition for producing a valid block hinges on the blockchain itself, with considerable variability regarding how much effect a single unit of computational power can exert on the blockchain. One solution entails artificially limiting the variability; this is achieved by necessitating a tree-hashed computational stack trace alongside the contract algorithm, a requirement that cannot be generated through shortcuts since even if you know that the computation will conclude after 1 million steps and yield a specific output, you still need to execute those million steps to produce all the intermediate hashes. However, while this resolves the long-range attack issue, it further ensures that the primary computation is not general computation, but rather involves computing numerous SHA3s – once again making the algorithm susceptible to specialized hardware.
Proof of Stake
A variation of this attack also applies to naively executed proof of stake algorithms. In a simplistic proof of stake implementation, consider an attacker who possesses 1% of all coins at or shortly following the genesis block. That attacker then initiates their own chain and starts mining it. Despite the attacker being selected to produce a block only 1% of the time, they can effortlessly generate 100 times as many blocks, thereby simply creating a longer blockchain through that method. Initially, I believed this problem to be fundamental; however, it turns out to be an issue that can be circumvented. One solution, for instance, is to recognize that every block must include a timestamp, causing users to reject chains with timestamps that significantly precede their own. A long-range attack will thus need to conform to the same timeframe, but due to its involvement of a substantially smaller quantity of currency units, its score will be considerably lesser. Another option is to mandate at least some proportion (let’s say, 30%) of all coins to endorse either every block or every Nth block, effectively preventing all attacks with less than that percentage of coins. Our own PoS algorithm, Slasher, can be easily retrofitted with either of these approaches.
Thus, in the long haul, it appears that either pure proof of stake or hybrid PoW/PoS will be the paths that blockchains will follow. Regarding a hybrid PoW/PoS, one can readily implement a system where PoS addresses the concerns highlighted earlier in BBPoW. What we ultimately choose for Ethereum 1.0 may be proof of stake, it could be a hybrid model, or it might even revert to the traditional SHA3, with the understanding that ASICs will not be produced as manufacturers would perceive no advantage with the forthcoming arrival of Ethereum 2.0. However, one challenge continues to remain relatively unsolved: the distribution model. For my views on that, stay tuned for the next segment of this series.
