The current proof-of-work design, Blockchain-based proof of workThis is the second iteration in our effort to create a mining algorithm that is friendly to CPUs and resistant to optimization by specialized hardware (ASICs). Our first attempt, Dagger, attempted to use hard-memory algorithms like Scrypt and go one step further by creating an algorithm that is difficult to calculate with memory, but easy to verify using directed-acyclic graphs. This is basically a tree where each node has multiple parents. Our current strategy follows a stricter path of making proof-of-work involve running random contracts on the blockchain. Because the Ethereum scripting language is Turing-complete, an ASIC that can run Ethereum scripts is an ASIC for general computing. This is a more elegant argument than “this is memory intensive, so you can’t parallelize as much”. Of course, “well, can you do specific optimizations and still get great speedup” are issues, but you can argue that these are minor problems that will be solved over time. The solution is elegant and inexpensive, as it is both simple and cheap. If someone creates an ASIC, then other people will be motivated to find computing options that the ASIC can’t do. “pollute” these contracts onto the blockchain.
Unfortunately, there’s a greater hurdle to prevent such schemes from happening, and it is one that is unfortunately fundamental: the long-range attack. The long-range attack is basically the same as this. In a traditional 51% attack: I deposit 100 bitcoins in a new account and then send the 100 bitcoins to a seller in exchange for a digital good with instant delivery (like litecoins). I wait for delivery, which takes 6 confirmations. Then, I immediately begin working on a blockchain from the block that precedes the transaction that sends 100 bitcoins. My fork eventually outperforms the mainchain. In the end, I have both bitcoins and litecoins. On a long-range attack, instead of starting the fork 6 blocks back, I start the fork 60000 blocks back, or at the genesis blocks. In Bitcoin, this fork is ineffective, as it only increases the time required to catch up. However, it is a serious problem in blockchain-based proofs of work. The reason is that, although your initial mining speed will be slow, once you have accumulated a few hundred blocks, you will be able to fill the blockchain with contracts that you can mine very easily, while they are difficult for everyone else. An example of such an agreement is:
i = 0 while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f: i = i + 1
The contract will take exactly 1,000,000 rounds before the hash matches. This allows you to calculate how many steps it will take, how much gas it will use, and what state it will reach at the end. But other people will still have to run the code. An important property of such a plan, which is a necessary consequence of stopping the problem, is that it is not mathematically possible to develop a mechanism to detect smart contracts in the general situation without actually executing them. Thus, a long-range attacker might fill the blockchain in with such contracts, “mine” them, and convince the network that he is actually doing a lot of work, when in reality he is only taking the shortcut. So our attacker will be able to overtake us in a few days, “mining” billions of times faster than the main chain.
You must show proof of participation
An alternative version of this attack is available for proof-of-stake algorithms that are not yet implemented. Assume that an attacker has 1% of coins in the genesis block, or soon thereafter. This is a foolishly implemented proof of stake. The attacker starts to mine his own chain. Although the attacker will be targeted if he produces a block less than 1% of the time, he can produce 100 times more blocks and create a longer blockchain this way. Although I initially thought this was a critical problem, it is actually fixable. One solution is to make sure that each block has a timestamp. Users will reject chains with timestamps far beyond their own. So long-range attacks will need to be completed within the same timeframe. However, because they involve a lesser number of currency units, their score will be lower. Alternatives, such as “Insatiable customer”, require a minimum of 30% (or 30%) of all coins to be used to support each block and every nth block. This will prevent any attacks with less than that amount. Our own
