Long-Range Attacks: The Serious Problem With Adaptive Proof of Work

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.


14 comments

  1. Can we not combine the stack trace hash trees with general computations and a weighting factor that weights the difficulty of the computations? Say the block nonce is something that gets fed into the first tx in a block. Using the previous block header, we select a pseudo random point in the execution of the first tx, concatenate the nonce and stack trace up to that point, hash that, take that hash, hash it with the output/return values of the first tx, and feed that result into the second tx, doing the same kind of procedure, all the way to the end. That way, the nonce propagates through every tx, requires general computation, includes stack traces, and furthermore we can weight the block difficulty by the computational complexity of the tx (long range attacks not being an issue because of the stack trace requirement). What do you think?

    • The problem with this is with “a weighting factor that weights the difficult of the computations” or “and furthermore we can weight the block difficult by the computational complexity of the tx” – these things are impossible to do in general. It’s pretty much along the same lines as the halting problem: you want a program that will tell you whether another program is complex – too ambitious for the reality of computability, I’m afraid 😉

      One approach might be to redefine the programming language of ethereum so that this kind of “computation of complexity” is possible, losing turing-completeness but hopefully still allowing arbitrary state transitions. Thats pretty hardcore, if you ask me, though 😉

      • No no. You do something simple like add up the total gas cost. You’re simply trying to avoid some one flooding the network with transactions that only add 1+1 or something and being able to mine quickly on that. Ethereum is already only quasi-Turing complete because of the Gas – the halting problem does not apply as strictly, since every contract is guaranteed to stop when it runs out of gas (though one can still ask “will it halt before it runs out of gas”)

      • Well consider the long-range-attack code that Vitalik cited in this article. The attacker knows how much gas it will cost in advance, while other nodes do not. It is like the halting problem in the sense that it requires that you run a program on another in order to calculate something about its execution.

  2. So the intention is to replace the current ‘set of broken systems’ whose main issues are to do with lack of transparency (pockets of poor information flows) – though arguably they have been getting more transparent as time goes by with secrets are increasingly harder to keep (ask the NSA or anyone else with power and influence) – with a system that is less transparent due to of necessity of being overly engineered and by definition brittle to change….

    Dare I suggest, if you can’t explain the new concepts in a sentence or two in non-technical language the ordinary man can understand, it will remain forever the province of geeks and trusting fools… never breaking into the mainstream. Can you see the irony of saying “we are building a system that does need trusted third parties – only trust us geniuses to build it (even though you and the majority of the people on this planet have no chance at understanding why we believe it to be secure”

    Whatever solution that is engineered, it is destined to be broken or made irrelevant in due course – surely that is the obvious lesson of evolutionary nature and you do not need even be highly educated to understand that, perhaps just blessed with a little common sense wisdom.

    The blockchain is a great idea, only because at first glance it serves to increase transparency of information flows without the possibility of corruption… clearly that is turning out not to be the case in it’s current implementation (or in anything else I have seen proposed and am pretty sure Vitalik here is amongst the forefront of thinkers in this field).

    IMO we ought to be looking not at an ”unbreakable’ system but one that has inbuilt self regulation so that it becomes easier to DETECT if there are attempts to game the system which in time there will invariably be…. a system that self corrects because the watchers are watched and in unison the majority can take action by removing their support of offending parties – a democratic system.

    Perhaps we ought to just accept that the new Internet ought to become a pure public space with no guarantee of anonymity, each transaction to be valid, traceable back to unique signatured identities of people, processes or things….

    If you want privacy, use meatspace and go to the park where no one can hear you (alas there may still be lip reading drones with cameras there). Truly private communications should NEVER be broadband.

    The Internet is increasingly too powerful to allow it be gamed in secret, the only solution I can see is to design out anonymity – any attempt to game the blockchain will be on the blockchain. Now that is radical.

    See this article by Kevin Kelly, Techno-philosopher extraordinaire of his vision of the future internet – I have come to similar conclusions by being a generalist and through a heck of varied reading and experience – he is far more articulate than I could ever be in these matters and has a great record as a technologist, hence suggest reading what he has to say can only help the development of ethereum and other bitcoin tech offshoots:

    I’d be interested in responses to the points in this article – I’d love to see them challenged convincingly:

    Why You Should Embrace Surveillance, Not Fight It
    http://www.wired.com/2014/03/going-tracked-heres-way-embrace-surveillance

    • > Dare I suggest, if you can’t explain the new concepts in a sentence or two in non-technical language the ordinary man can understand, it will remain forever the province of geeks and trusting fools… never breaking into the mainstream.

      Try explaining public key cryptography, SSL, chemotherapy, antiretrovirals, the internal combustion engine or maglev trains “in a sentence or two in non-technical language the ordinary man can understand”. You can’t. The way I view setting up trustable systems is by analogy with another concept that I developed (and as it turns out that other Bitcoin developers and many other cryptographers developed before me) in the context of Merkle state tree updates: efficient proofs of incorrectness. Almost no one in society is technically skilled enough to fully understand many life-critical systems that we use today. However, if someone comes up with such a system and it turns out to be defective, then if even one technically skilled person spots the error then he can make a statement to point out what the error is, and many other people, with their eyes now laser-focused on that, can much more easily confirm that an error indeed exists. At that point it’s the job of the scientific community and the media, and people skilled in the particular art in question embedded into their respective communities, to inform the general public.

      > IMO we ought to be looking not at an ”unbreakable’ system but one that has inbuilt self regulation so that it becomes easier to DETECT if there are attempts to game the system which in time there will invariably be

      I fully agree. Economic incentive-based solutions > thinking of every possible eventuality at the beginning. That’s actually the line of thinking that I try to follow as much as possible.

      > If you want privacy, use meatspace and go to the park where no one can hear you (alas there may still be lip reading drones with cameras there). Truly private communications should NEVER be broadband.

      Actually, David Friedman expresses the exact opposite opinion in Future Imperfect, and I fully agree with him: it is much easier to secure privacy online than it is in person. Online, I know for a fact that the NSA can’t figure out what value I just typed into my command line that hashes to c58dc4e82da3e362b117d4be6bb8491cc130af878741f5c63b7df66fa2b84661. The only way they could is if it’s done offline – and there powerful agencies are (or soon will be) quite capable of putting up one surveillance drone every hundred square meters in the world. So we will likely see a world where the online is going dark and the offline is brighter than ever.

      • Vitalik, if you number is accurate for the 100 meters, that means there need only be 14,000 of these drones to cover 90% of the world’s population as we only actually populate a small part of the planet. Shocking stuff to consider…

      • Ignore my other reply, I made a squaring error and confused KM for M. It will take 140 billion drones to do that over only the populated places on earth.

        Where did you get the 100square meters figure from Vitalik?

  3. Vitalik;

    So in conclusion, you are going to abandon contract validation as part of the mining algorithm?

    Are you also going to abandon proof of blockchain storage (IE proving that the miner has a full copy) ?

    -Schalk

    • My current instinct is to actually switch to random-code-execution as the pow, but keep proof of blockchain storage; I think that proof of blockchain storage is still a good idea. People won’t ASIC it no matter how broken it is due to the looming threat of Ethereum 2.0, but rapid-prototyed FPGA solutions will likely provide valuable insights, and the whole thing will likely take several rounds to be successful.

  4. >Try explaining public key cryptography, SSL, chemotherapy, antiretrovirals, the internal combustion engine or maglev trains “in a sentence or two in non-technical language the ordinary man can understand”. You can’t. The way I view setting up trustable systems is by analogy with another concept that I developed (and as it turns out that other Bitcoin developers and many other cryptographers developed before me) in the context of Merkle state tree updates: efficient proofs of incorrectness. Almost no one in society is technically skilled enough to fully understand many life-critical systems that we use today. However, if someone comes up with such a system and it turns out to be defective, then if even one technically skilled person spots the error then he can make a statement to point out what the error is, and many other people, with their eyes now laser-focused on that, can much more easily confirm that an error indeed exists. At that point it’s the job of the scientific community and the media, and people skilled in the particular art in question embedded into their respective communities, to inform the general public.

    Fully agree. I do not necessarily need or even want to understand these technologies in depth beyond the benefits (or not) they may bring me – I may have other interests such as fly-fishing. I just want to know enough to be able trust the ecosystem that has given rise to them. Being open to scrutiny of peers (i.e. transparent publishing) and a process for raising public objections speedily is part of ‘trust building’ of the ecosystem. In the light of new information, I would want the ability to ‘withdraw my trust’ just as easily as I gave it in the first place.

    So what is my point? My point is that engineering “Trustable Systems” need MORE TRUST if I have correctly understood you above and If that is the goal of the Ethereum project, then why not explicitly say so rather than the nonsense of “a decentralised system means you need not trust in third parties any more” which is blatantly false. Which of the two statements below is more likely to engender the trust of a non-technical audience?

    1) Trust us (A Third Party) to build a secure accountable system that does not need you to trust in Third Parties. We will be accountable in the way we do this, outside the accountable system we are building.

    (this is nonsensical in too many ways to list including the fact if probed deep enough – in the complex society we live in there are numerous third parties with implicated trust in the trivialest of transactions (on-line or offline) where any value is passed – anyone that objects to that statement I’d like an example of otherwise).

    2) Trust us to build a secure accountable system that makes it EASIER for you to Trust Others (and to withdraw your Trust quickly as needs be). We too will be accountable on the maintenance of the system going forwards.

    (Take Project Ethereum for instance, thanks to your open publishing here and elsewhere and and the willingness of your team to engage in conversations like these at the outset (which uncover the deep thought that is taking place) I have increasing confidence that you are on the right track to making a real difference… time will tell. Of course it is the process of openness here that is important and needs maintenance as the complexity of the project rises – it will be a challenge – I hope you recognise it is an important one to live up to)

    >Actually, David Friedman expresses the exact opposite opinion in Future Imperfect, and I fully agree with him: it is much easier to secure privacy online than it is in person. Online, I know for a fact that the NSA can’t figure out what value I just typed into my command line that hashes to c58dc4e82da3e362b117d4be6bb8491cc130af878741f5c63b7df66fa2b84661. The only way they could is if it’s done offline – and there powerful agencies are (or soon will be) quite capable of putting up one surveillance drone every hundred square meters in the world. So we will likely see a world where the online is going dark and the offline is brighter than ever.

    Thanks, I will look up ‘Future Imperfect’. But the point about your above example is the NSA can do just the same as you as you above and you and others MAY CARE if it is a transaction sent to someone to ‘take you out’. At least the NSA is somewhat accountable today (we know of them and are talking about them) – In addition to agencies like the NSA, governments, large corporations, moguls etc what about warped individuals/criminal organisations etc that ARE doing that just now on the internet with impunity affecting the lives of potentially millions without us having any chance to be aware of it. Anyone sending a million transactions is not committing a private act that deserves secrecy in my books – it is a public act – what I mean is I may not necessarily be able know detail of the message, but the fact that it emanated from the one identifiable, or a set of linked identifiable sources is important public domain information that SHOULD BE open to scrutiny in my opinion thanks to good engineering – I believe that could be possible. Also that there was an appropriate traceable cost to sending out a million or billion transactions which currently there is not.

    We started the conversation talking about ‘trustable systems’. My question to you is are able to list in ‘laymans terms’ what you believe the main principles of such a system are/could be and how Ethereum will seek to address them… assuming that is one of the goals of the project.

  5. Vitalik, can you expand more on the timestamping solution? Or point to somewher with more information on it. Thanks!

    > 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.

  6. You might be able to solve Long-Ranged Attacks by weighting the choice of which contracts to execute with how much ether has been spent on them.

    If you’re afraid that this might cause specialized hardware to be generated to solve the most used contracts, you can also add some decay to the weighting based on how old the contract is.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s