(This is a semantic layer attack on Bitcoin, based on what’s given in the immediately available public docs. The standard implementations may already be resistant to it. More on this at the end. Update: They already were! Take this post as an explanation of why the thing which I say ‘may even be in the standard implementation already’ is, in fact, necessary.)
Bitcoin mostly manages to avoid any nondeterministic calculations in evaluating the validity of a blockchain, but there’s one place where it doesn’t quite manage to do that: timestamps. To keep timestamps from getting too far off, two sanity checks are put on them:
- Mining operations with timestamps more than two hours in the future are ignored. This is the one and only place in Bitcoin where something nondeterministic is used to calculate whether a part of the blockchain is valid. Obviously its results can change over time.
- A mining operation whose timestamp is less than the median of the previous eleven is deemed invalid. (Presumably there’s some sanity check at very beginning of the block chain as well, probably a hard coded beginning of mining.) This is a deterministic calculation, but as I’ll get to later, it’s based on potentially unreliable earlier timestamps.
The one and only place where timestamps are used is in resetting the difficulty of doing a mining operation. If one were to use timestamps far into the future, one could make mining very easy in the next round and collect lots of coin for oneself. That doesn’t work because first of all, whoever’s receiving coin in a transaction won’t accept things which claim to happen in the distant future, and second of all when alternative blockchains are compared the one which wins is the one which has had more work done not the one which has more mining operations completed. This is the reason for that.
With the current heuristics for deciding what timestamps to accept whoever sets the very last one, which directly determines what mining difficulty is set to, has discretion to set it to between about an hour ago (Mining operations take about ten minutes so the median of the last eleven was about an hour ago) and two hours in the future (directly enforced, although you probably need to set it to a few seconds shy to be on the safe side because there really is clock skew.) Setting it to later will make mining slightly easier in the next cycle, but that will be offset by mining being harder in the cycle after that. It doesn’t completely even out though. If the last timestamps are alternately set as far into the future and as far into the past as possible, the overall amount of mining will be slightly greater than it would be otherwise. This is a very slight effect though and benefits all miners equally not just the ‘attacker’, so I think it isn’t worth worrying about. Maintainers of Bitcoin implementations may wish to add this trick. Knock yourselves out.
Now on to the actual attack.
The two possible attacks are when someone who controls a significant fraction of mining either consistently sets their clocks as far into the past or as far into the future as possible. Setting into the past doesn’t cause any damage, but into the future is a lot more interesting. As it happens, the two hours which timestamps can be set in the future is greater than the expected amount of time since the median of the last eleven timestamps, and eleven isn’t all that large a number, so an attacker with much less than half the mining capacity can set all their timestamps for two hours in the future and eventually get everyone else’s mining operations to get rejected by sanity check on timestamps. At first this will only have the effect of denying everyone else’s mining without increasing the amount of mining of the attacker, which might have the effect of increasing Bitcoin price in the short run by reducing supply but not otherwise be particularly beneficial to the attacker, but if they managed to keep it up for an entire setting of proof of work cycle (and, uh, good luck with that) then the difficulty of work would be reduced to what the attacker could produce and they’d be free to collect all mining rewards for themselves while everyone else’s attempts at mining got rejected.
If an attacker has about 15% of all mining capacity this attack would take about a week on average to pull off. It’s randomized though, so if they’ve spent time and still haven’t succeeded then the expected about of time for a hijack to happen remains the same. If they have 10% it’s about two months. Below that it basically stops working. Another 2-4 weeks is necessary for a mining difficulty reset to happen, depending on where in the cycle the hijack happens. I calculated these values using randomized simulations. An attacker with 20% of capacity would take an average of two days, 30% about half a day.
One could mitigate this attack by reducing the amount into the future which timestamps are allowed to be, from 2 hours to something less than 1 hour. While this sounds reasonable, it would require universal acceptance to work properly, which would be very hard to do, and I’m loathe to advocate that people change a clear standard of normal expected behavior.
The much better and more immediate fix is that miners should check what the earliest acceptable time for their next mining operation is, and if that time is somewhere in the future they use that for their timestamp instead of the actual current time. This completely fixes the problem immediately and is a totally reasonable sanity check in its own right, in case the local time is skewed heavily into the past. It may even be in the standard implementation already. Anyone maintaining Bitcoin mining software should make sure that theirs behaves in this way.