Long Range Attacks: A Serious Problem with Adaptive Proof-of-Work

Our current proof-of-work design, Blockchain-based proof-of-workis the second iteration of an attempt to create a mining algorithm that ensures that it remains CPU-friendly in the long run and is resistant to optimization by specialized hardware (ASICs). Our first attempt, Dagger, seeks to take the idea of ​​memory-hard algorithms like Scrypt one step further by creating an algorithm that is memory-hard to compute but memory-easy to verify using a directed acyclic graph (essentially a tree with each tree). I did. A node has multiple parents). Our current strategy takes a much more rigorous path. Proof-of-work involves executing random contracts on a blockchain. Because the Ethereum scripting language is Turing-complete, any ASIC that can run Ethereum scripts is by definition an ASIC for general computation. CPU – A much more elegant argument than “this is memory hard so it can’t be parallelized”. Of course, there is the question of “can I make certain optimizations and still get a big speedup?”, but you could argue that this is a minor issue that should be resolved over time. This solution is economical and elegant at the same time. Once someone creates an ASIC, others have an incentive to look for types of computations that ASICs cannot perform and “pollute” the blockchain with such contracts. But, unfortunately, there are usually much bigger obstacles to these plans, and unfortunately, to some extent, the fundamental one is long-range attacks.

Ranged attacks basically work like this: In a traditional 51% attack, you deposit 100 Bitcoins into a new new account and then send those 100 Bitcoins to a merchant in exchange for a digital good (e.g. Litecoin) that is delivered immediately. Instead of waiting for delivery (e.g. after 6 confirmations) and starting one block before the transaction sending me 100 bitcoins, I immediately start working on a new blockchain and start the transaction instead of sending those bitcoins back to me. It then joins the rest of the network, putting more mining power into the fork than it puts into the main chain. Eventually my fork overtakes the main chain and becomes the main chain, so I end up having both Bitcoin and Litecoin. . In long-range attacks, instead of starting the fork back 6 blocks, it starts the fork back 60000 blocks, or even the genesis block.

In Bitcoin, such forks are useless. Because it only increases the time needed to catch up. However, this is a serious problem in blockchain-based proof-of-work. The reason is that if you start forking directly from the genesis block, mining will be slow at first, but after a few hundred blocks you will be able to populate the blockchain with contracts that are very easy to mine. But for others, it’s difficult. An example of such a contract is:

i = 0 sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f: i = i + 1

We know that a contract will take exactly 1 million rounds before the hashes match, so we can calculate exactly what steps and how much gas it will take to run it, and what the state will be like when it ends, but others have no choice other than actually running the code. There is no room. An important attribute of such a plan is stopping problem, it is practically impossible to build a mechanism to detect such clever contracts in the general case without actually executing them (it is impossible to prove mathematically, but not impossible in Hollywood). So a long-range attacker can populate a blockchain with such contracts, “mine” them, and convince the network that it is doing a huge amount of work when in fact it is taking shortcuts. So after a few days, attackers will quickly overtake it by “mining” it at a rate billions of times faster than the main chain.

The above attack makes few assumptions about how the algorithm actually works. The conditions for producing a valid block depend on the blockchain itself, and it is assumed that there is wide variability in how much impact a single unit of computational power can have on the blockchain. One solution is to artificially limit variability. This is done by requiring a tree hash calculation stack trace along with the contract algorithm. This is something you can’t generate right away, because even if you know that the computation will end after 1 million steps and produce a certain output, it still needs to be run. Generating all the intermediate hashes requires millions of manual steps. However, even if this solves the long-range attack problem, the underlying calculation computes numerous SHA3s rather than regular calculations, making the algorithm once again vulnerable to specialized hardware.

proof of stake

A version of this attack also exists in simple implementations of proof-of-stake algorithms. In a naive proof-of-stake implementation, it is assumed that there is an attacker with 1% of all coins at or shortly after the genesis block. The attacker then starts his own chain and starts mining. An attacker will be chosen to generate a block only 1% of the time, but they can easily generate 100 times as many blocks and that way simply create a longer blockchain. At first I thought this was a fundamental problem, but it is actually a solvable problem. For example, one solution is to note that every block must have a timestamp and that users will reject chains with timestamps much earlier than their own. So a ranged attack has to be hit at the same time, but has a much lower score because the amount of currency units is much smaller. Another alternative is need By having at least a certain percentage (e.g. 30%) of all coins approve every block or every Nth block, we absolutely prevent all attacks with coins below that percentage. Own PoS algorithm, slasherYou can easily retrofit with one of these solutions.

Therefore, in the long term, pure proof-of-stake or hybrid PoW/PoS will likely be the direction of blockchain. For hybrid PoW/PoS, one could easily have a way of using PoS to solve the BBBPoW problems described above. What we’ll use for Ethereum 1.0 could be proof-of-stake, a hybrid approach, or even boring old SHA3. Manufacturers must understand that ASICs will not be developed because they will not gain any benefit from the imminent launch. Ethereum 2.0. However, one challenge still remains unresolved. This is the distribution model. Stay tuned for the next part of this series to find out my thoughts on this.