.jpg)
Our current guide to business design, Blockchain-based proof of work, is the second iteration of our attempt to create a mining algorithm that we guarantee will remain CPU friendly and resistant to optimization by specialized hardware ASICs in the long term. Our first attempt, Dagger, attempted to take the idea of memory-hard algorithms like Scrypt one step further by creating an algorithm that is difficult to compute in terms of memory, but easy to verify from memory, using directed acyclic graphs (essentially, trees where each A node has multiple parents). Our current strategy takes a more stringent tack: making proof-of-work involve executing random blockchain contracts. Since Ethereum’s scripting language is Turing-complete, an ASIC that can execute Ethereum scripts is by definition a public computation ASIC, i.e. CPU – A much more elegant argument than “this is hard on memory so you can’t parallelize it as much”. Of course, there are issues like “well, can you make specific improvements and still get a lot of speed”, but it can be said that these are minor kinks that need to be worked out over time. The solution is also elegant because it is economical at the same time: if someone creates an ASIC, others will have an incentive to look for types of calculations that ASIC cannot do and “pollute” the blockchain with such contracts. Unfortunately, there is one much greater obstacle to such schemes in general, and it is unfortunately fairly basic: long-range attacks.
The ranged attack basically works as follows. In a traditional 51% attack, you put 100 BTC into a new account, then send that 100 BTC to a merchant in exchange for some digital goods for immediate delivery (for example, Litecoin). I wait for delivery (say, after 6 confirmations), but then I immediately start working on a new blockchain starting one block before the transaction that sends 100 bitcoins, and I make a transaction instead of sending those bitcoins back to myself. I then put more mining power into my fork than the rest of the network combined puts into the mainchain, and eventually my fork overtakes the mainchain and thus becomes the mainchain, so in the end I have Bitcoin and Litecoin. . In a long-range attack, instead of starting the fork 6 blocks away, I start the fork 60,000 blocks away, or even at the genesis block.
In Bitcoin, such a fork is useless, because you only increase the amount of time you will need to catch up. However, in blockchain-based proof of work, this presents a serious problem. The reason is that if you start a fork directly from the genesis block, while your mining will be slow at first, after a few hundred blocks, you will be able to populate the blockchain with contracts that are easy for you to mine, but difficult for everyone else. An example of such a contract is simply:
i = 0 while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f: i = i + 1
You know that the contract will take exactly a million runs before the hash matches, 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 instantly, but other people will have no choice but to actually run the code. An important property of such a scheme, a necessary consequence of Stopping problem, is that it is virtually impossible (as in it’s impossible to prove mathematically, not impossible in Hollywood) to build a mechanism to detect such smart contracts in the general case without actually running them. Thus, a long-range attacker could populate the blockchain with such contracts, “mine” them, convincing the network that it is doing an enormous amount of work when in fact it is taking a shortcut. Thus, after a few days, our attacker will “mine” billions of times faster than the main chain, thus quickly overtaking it.
Note that the above attack assumes little about how the algorithm actually works; All it assumes is that the requirement to produce a valid block depends on the blockchain itself, and there is a wide range of variation in the amount of impact on the blockchain that a single unit of computational power can have. One solution involves artificially capping the variance; This is done by requiring a tree-parted computation stack trace along with the nodes algorithm, something that cannot be created in short because even if you know that the computation will finish after a million steps and produce a certain output, you still need to run those million steps yourself to produce All intermediate hashes. However, although this solves the long-range attack problem, it also ensures that the underlying computation is not a public computation, but rather computation of 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 proof of stake algorithms that were implemented naively. In a naively implemented Proof of Stake, let’s say an attacker has 1% of all coins in the genesis block or shortly after. This attacker then starts his own chain, and begins mining it. Although an attacker would find themselves choosing to produce a block only 1% of the time, they could easily produce 100 times more blocks, and simply create a longer block this way. At first, I thought this problem was basic, but it is actually a problem that can be solved. One solution, for example, is to note that each block must have a timestamp, and users reject chains with timestamps far ahead of their own. Thus, a ranged attack should fit within the same amount of time, but since it involves a much smaller amount of currency units, its result will be much lower. Another alternative is Requires At least a percentage (e.g., 30%) of all coins to endorse each block or each block N, thus completely preventing all attacks with less than that percentage of coins. Our PoS algorithm, Slasherit can be easily updated and upgraded with any of these solutions.
Thus, in the long term, it seems that either pure Proof of Stake or hybrid Proof of Work/Proof of Stake is the way blockchain technology will go. In the case of a hybrid PoW/PoS, one can easily get a scheme where PoS is used to solve the problem described above using BBPoW. What we’re going to talk about for Ethereum 1.0 could be proof of stake, it could be a hybrid scheme, it could be boring old SHA3, knowing that no ASICs will be developed since manufacturers won’t see any benefit with the imminent arrival of Ethereum 1.0. Ethereum 2.0. However, there is one challenge that remains unresolved: the distribution model. For my own thoughts on that, stay tuned for the next part of this series.
