Our current proof of work design, blockchain-based proof of work, is the second iteration of our attempt to create a mining algorithm that is guaranteed to remain CPU-friendly and resistant to optimization by specialized hardware (ASICs) in the long term. Our first attempt, Dagger, tried to take the idea of memory-hard algorithms like Scrypt one step further by creating an algorithm which is memory-hard to compute, but memory-easy to verify, using directed acyclic graphs (basically, trees where each node has multiple parents). Our current strategy takes a much more rigorous track: make the proof of work involve executing random contracts from the blockchain. Because the Ethereum scripting language is Turing-complete, an ASIC that can execute Ethereum scripts is by definition an ASIC for general computation, ie. a CPU – a much more elegant argument than “this is memory-hard so you can’t parallelize as much”. Of course, there are issues of “well, can you make specific optimizations and still get a large speedup”, but it can be argued that those are minor kinks to be worked out over time. The solution is also elegant because it is simultaneously an economic one: if someone does create an ASIC, then others will have the incentive to look for types of computation that the ASIC can’t do and “pollute” the blockchain with such contracts. Unfortunately, however, there is one much larger obstacle to such schemes in general, and one which is unfortunately to some degree fundamental: long-range attacks.
A long-range attack basically works as follows. In a traditional 51% attack, I put 100 bitcoins into a fresh new account, then send those 100 bitcoins to a merchant in exchange for some instant-delivery digital good (say, litecoins). I wait for delivery (eg. after 6 confirmations), but then I immediately start working on a new blockchain starting from one block before the transaction sending the 100 bitcoins, and put in a transaction instead sending those bitcoins back to myself. I then put more mining power into my fork than the rest of the network combined is putting into the main chain, and eventually my fork overtakes the main chain and thereby becomes the main chain, so at the end I have both the bitcoins and the litecoins. In a long-range attack, instead of starting a fork 6 blocks back, I start the fork 60000 blocks back, or even at the genesis block.
In Bitcoin, such a fork is useless, since you’re just increasing the amount of time you would need to catch up. In blockchain-based proof of work, however, it is a serious problem. The reason is that if you start a fork straight from the genesis block, then while your mining will be slow at first, after a few hundred blocks you will be able to fill the blockchain up with contracts that are very easy for you to mine, but difficult for everyone else. One example of such a contract is simply:
i = 0
while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:
i = i + 1
You know that the contract will take exactly one million rounds before the hash matches up, so you can calculate exactly how many steps and how much gas it will take to run and what the state will be at the end immediately, but other people will have no choice but to actually run through the code. An important property of such a scheme, a necessary consequence of the halting problem, is that it is actually impossible (as in, mathematically provably impossible, not Hollywood impossible) to construct a mechanism for detecting such clever contracts in the general case without actually running them. Hence, the long-range-attacker could fill the blockchain with such contracts, “mine” them, and convince the network that it is doing a massive amount of work when it is actually just taking the shortcut. Thus, after a few days, our attacker will be “mining” billions of times faster than the main chain, and thereby quickly overtake it.
Notice that the above attack assumes little about how the algorithm actually works; all it assumes is that the condition for producing a valid block is dependent on the blockchain itself, and there is a wide range of variability in how much influence on the blockchain a single unit of computational power can have. One solution involves artificially capping the variability; this is done by requiring a tree-hashed computational stack trace alongside the contract algorithm, which is something that cannot be shortcut-generated because even if you know that the computation will terminate after 1 million steps and produce a certain output you still need to run those million steps yourself to produce all of the intermediate hashes. However, although this solves the long-range-attack problem it also ensures that the primary computation is not general computation, but rather computing lots and lots of SHA3s – making the algorithm once again vulnerable to specialized hardware.
Proof of Stake
A version of this attack also exists for naively implemented proof of stake algorithms. In a naively implemented proof of stake, suppose that there is an attacker with 1% of all coins at or shortly after the genesis block. That attacker then starts their own chain, and starts mining it. Although the attacker will find themselves selected for producing a block only 1% of the time, they can easily produce 100 times as many blocks, and simply create a longer blockchain in that way. Originally, I thought that this problem was fundamental, but in reality it’s an issue that can be worked around. One solution, for example, is to note that every block must have a timestamp, and users reject chains with timestamps that are far ahead of their own. A long-range attack will thus have to fit into the same length of time, but because it involves a much smaller quantity of currency units its score will be much lower. Another alternative is to require at least some percentage (say, 30%) of all coins to endorse either every block or every Nth block, thereby absolutely preventing all attacks with less than that percent of coins. Our own PoS algorithm, Slasher, can easily be retrofitted with either of these solutions.
Thus, in the long term, it seems like either pure proof of stake or hybrid PoW/PoS are the way that blockchains are going to go. In the case of a hybrid PoW/PoS, one can easily have a scheme where PoS is used to resolve the issue described above with BBPoW. What we’ll go with for Ethereum 1.0 may be proof of stake, it might be a hybrid scheme, and it might be boring old SHA3, with the understanding that ASICs will not be developed since manufacturers would see no benefit with the impending arrival of Ethereum 2.0. However, there is still one challenge that arguably remains unresolved: the distribution model. For my own thoughts on that, stay tuned for the next part of this series.