Let’s Do the Time Warp Again: The Verge Hack, Part Deux
The pitfalls of Frankenstein codebases, whether “size matters” wrt blockchains, why inadequately fixing broken things is a bad idea, and a plea against blind, tribalistic crypto-shilling — plus colorful charts and graphs!
Note: This is a follow-up post; you may want to first read part 1 here.
If you want to scare somebody in the cryptocurrency world, just utter the phrase “51% attack.” This method of network assault — in which a single party manages to acquire enough mining power to outperform the joint forces of the rest of the network — can no longer be written off as an unfeasible hypothetical, at least not for smaller-scale altcoins [1]. Bitcoin Gold and Monacoin were both recently hit with such an an attack, and it seems inevitable that more will soon follow.
As far as these attacks go, however, there are important distinctions to note: when Verge was attacked at the beginning of April, it was widely reported as being in the 51% category. However, as I explained in part 1, a combination of questionable design decisions and outright mistakes in Verge’s software enabled the attacker to pull off their feat with far less than the majority of the hash-power, making the “51%” label wrong, or at best misleading [2].
Well, as it so happens, on 5/22, Verge was attacked again. From the outside, the attack looked suspiciously similar to the first, which was odd. Surely, in the six-week interval between attacks, some sort of fix must have been implemented that would at least make the attacker’s life more complicated. Right? Perhaps this time, it was a legitimate 51% attack? Or maybe the attacker found some new, clever, fascinating, heretofore unfathomed security hole to exploit? I was curious to know the details, and many others seemed to be as well, so I decided to dig back in.
Here’s a drastically condensed version of what I discovered:
- Much to my disappointment, the second hack was virtually identical to the first one, with one minor, un-clever, uninteresting difference.
- An issue that I hadn’t covered in part one (that actually is pretty interesting!) renders the whole situation, for both hacks, far worse than I’d realized.
- In the current state of the Verge repo, of the three sources of vulnerabilities that lead to the attacks, two are slightly mitigated (at best) and the third remains completely unfixed.
- This is all bad.
Why The Second Hack Looks Just Like The First (With One Insignificant, and Disappointingly Uninteresting Difference)
The first time around, I explained how the mining exploit was made possible by two aspects of Verge’s design: a high permitted time-drift window that allows throttling of difficulty, and the use of five independent mining algorithms, which makes difficulty throttling a far more serious problem.
After a few fits and starts (more on that later), the Verge devs ultimately implemented a patch that involves making the five mining algorithms a tad less independent (while leaving timestamp issues and difficulty adjustment untouched [3]):
In English: “when you give me a block mined with algorithm x, I look at the previous 10 blocks, and if at least 5 of them were also mined with algorithm x, I reject your block.” This very directly prevents all blocks from being mined with a single algorithm for any significant amount of time. The idea, presumably, was that since one algorithm dominated the whole network last time, explicitly preventing that particular case should be enough to thwart future attacks.
A minor objection one could raise: keeping the algorithms completely independent actually makes economic sense, and thus, imposing this limitation is bound to have some unintended consequences. If difficulty is low enough for more than five of ten consecutive blocks to be mined with one algorithm, preventing this from happening also prevents retargeting from smoothly hitting equilibrium. Abrupt peaks and valleys in difficulty will likely occur.
…A major objection one could raise: as some keen observers were quick to point out, this patch does little to actually fix the vulnerability; the attack vectors basically remain wide open.
As a purely speculative and hypothetical example: imagine that the attacker can amass enough hash-power to overwhelm the network for two of Verge’s allotted mining algorithms, instead of just one. At absolute best, this would make the attack roughly twice as expensive; given how shockingly cheap it has become to rent computational mining power, this may amount to no more than a trifling inconvenience. In either case, “this will be a bit more costly to pull off a second time” isn’t exactly a comforting phrase in the world of cybersecurity.
Once the dominant hash rate on two algorithms is achieved, our totally imaginary, speculative attacker could simply repeat the early April attack, but instead of mining all of the blocks with one algorithm, just alternate between the two in intervals of five blocks at a time.
Well, wouldn’tcha know:
So that’s pretty much that.
The Bigger, More Interesting Issue
So going back to the aftermath of the first attack: some curious observers at the time wondered how and why it actually came to be that Verge would have a 30 minute difficulty adjustment window while allowing a time drift of two hours. It’s clearly a mistake, but an error this egregious begs for some sort of explanation. One can’t ever claim absolute certainty of the sources of others’ blunders, but in this case, there does appear to be a highly probable culprit: Verge copied portions of their code from another project, Peercoin, and in doing so, accidentally inherited the other coin’s two-hour time drift (two hours is an appropriate time drift for Peercoin, given its much larger block times and difficulty adjustment window relative to Verge’s [4].)
Before going any further, it’s worth making something explicitly clear here: I am not claiming there is anything wrong with copying code from an open source project. Indeed, making a project open-source is an inherent invitation for others to freely draw from it. Reusing others’ code is a part of being a developer. If I were forbidden from copying and pasting others’ solutions from stackoverflow.com, I wouldn’t be able to pay my rent.
However, there is something very wrong with reusing code for a high-stakes project without understanding the implications it will have in your software. Different projects, even those with many superficial similarities, involve different design decisions and require different security considerations. If you’re patching together software from different sources (in the case of Verge, they appear to draw from Peercoin, Shield, Dogecoin, and Fantom, among others), failure to understand the implications of even a single numerical constant can (and indeed did) result in catastrophe.
So anyway, yes, odds are that that’s how the two-hour drift value snuck in. But that, in and of itself, isn’t particularly noteworthy. Bad code does as bad code does, regardless of where it came from. The reason I’ve bothered bringing all of this up is because, when one goes down the rabbit-hole of investigating what else Verge inherited from Peercoin, a new, alarming issue comes to light.
First, to the whiteboard:
Longest Vs. Strongest Chain
You’re a blockchain protocol: how do you determine if a chain is valid? This, in a sense, is actually pretty straightforward: in short, you look at it. The data is all saved on a public ledger, so you can just explicitly check that all state-transition rules are being properly abided by (if Alice pays Bob, Alice cryptographically verified that she actually has that money; nobody created new money out of thin air; things like that.)
Okay, but this is an open protocol, so what if there are two different chains given to you, and both of them are valid? Which one do you pick as the canonical record? Ultimately, one has to be chosen. We can only have one version of history; that money has to belong to somebody.
This is a stranger problem that requires a more novel solution, a solution which Satoshi provided: for a block of transactions to be considered valid, the block has to be mined, a computational process that involves consuming a non-trivial amount of energy. Then, if two competing valid chains are presented, the protocol selects whichever one has had the most mining work invested in its creation. Thus, as time goes on, it becomes increasingly costly for multiple chains to coexist, thereby increasingly incentivizing the network to come to consensus.
Now you’ll often hear “longest chain” as the shorthand for “chain with the most work” (aka “strongest chain”). But if we take “longest chain” to mean “the chain with most blocks,” there’s a subtle but important difference between these two notions. For the simple reason that mining difficulty can change over time (as Verge has so nicely illustrated for us), the longest and strongest chain need not necessarily be one and the same; three low-difficulty blocks may take less hash-power to mine than one higher-difficulty block, for example. Thus, there will be edge-cases when simply accepting the longest chain would compromise the security of the system.
Interestedly, this distinction appears to have initially been missed by Satoshi himself; the early implementations of Bitcoin went with the longest-chain rule before this was surreptitiously updated. Since then, using the strongest-chain rule has become the standard for proof of work coins, and rightfully so.
Now Peercoin, however, still does use the longest-chain policy, but for them this makes perfect sense; Peercoin’s consensus protocol uses proof of stake instead of proof of work. Blocks aren’t mined, but rather, are voted on by nodes with currency locked into the system. The important point here being that unlike blocks in proof of work systems, Peercoin’s blocks don’t have “weight” in any sense. Things are binary — a given block is either accepted or rejected. Thus, when selecting between two competing chains, it’s a perfectly sensible approach for Peercoin to simply count the blocks and select the longest one.
But Verge does use proof of work, and thus blocks do have their own difficulty-weight, and yet, unlike virtually every other proof-of-work based coin, they use the longest-chain, not strongest chain policy. Why?
It sure looks like it’s same reason that they ended up with a two hour time drift: they got it from Peercoin without realizing the risk it imposed. I.e., they messed up.
Implications for Attackers
Okay, so the canonical Verge chain is the one with the most blocks, which is not necessarily the one that requires the most work. How can our enterprising attacker best exploit this situation?
Here’s one way: the attacker picks a block at which to start his attack. When this block arrives, he starts mining “in the dark”; i.e., he doesn’t accept anyone else’s blocks, and he doesn’t try to broadcast any blocks he finds to the rest of the network, effectively creating his own, personal chain.
His goal is to build this chain out to the point that it’s longer than the network’s. This would normally be a daunting task, since he’s competing against the rest of the network as a whole, which, one presumes, is a lot of hash-power to race against. However, as loyal readers know from part one, our attacker can gradually decrease mining difficulty. And note that now, since his chain is “personal” and still not getting broadcast, this difficulty decrease only applies to himself, not to any other miners. As his difficulty decreases, his blocks-mined-per-second rate increases, and thus, it’s just a matter of time before his chain becomes longer than the network’s (since he’s forging timestamps anyway, the amount of time it actually takes for him to catch up is basically immaterial.)
At this point, the attacker broadcasts his new branch far and wide, which the rest of the network obligingly accepts. So NOW, to maintain network dominance, he just has to make sure his chain stays the longest. In theory, another miner could outpace and thwart him, but the situation he’s in gives him three inherent, additional advantages:
- Whenever a valid block is broadcast, it takes some time before a majority of nodes in the network receive it; for Bitcoin, it typically takes 7 to 10 seconds, for example. For a smaller network like Verge, propagation will happen faster, but one can safely estimate that it will still take at least a few seconds. Since the attacker is mining multiple blocks per second, by the time another node receives one of his blocks, the attacker has already mined the next (and the next, perhaps); in this way he perpetually stays at least one-ahead, forcing other miners to orphan any new block they’ve created (if they can even manage to create a block in the first place).
- Since he is (presumably) the only one forging timestamps, his one-(or more)-ahead chain will still always have the advantage of being slightly easier to mine on than any other competing chain-in-progress.
- The attacker decides to selfishly mine blocks with zero transactions [5], and thus the block creation process will be faster for him than for the other, honest miners, who waste precious moments gathering and hashing transactions in the mempool. He can increase this burden on them by spamming the network with a flurry of own transactions, which the other miners will slavishly try to include in their futile, soon-to-be orphaned-anyway blocks. [6]
So there you have it; add the ill-advised use of longest-chain selection to the list of issues. And note that as of writing, the chain selection code still has yet to be modified.
The Second Fix
So what has been changed then? We already covered the fix following the first hack; after the second hack, they finally lowered the time drift window from two hours down to 10 minutes. Whether 10 minutes is the appropriate drift is something I can’t claim to be qualified to answer. What I can confirm is that a third attack was clearly attempted on 5/29; the attacker was able to repeatedly create difficulty valleys, though he never did dominate the whole network this time:
In any case, one could be forgiven for wondering why it took six weeks (and another hack) for this simple, obvious change to be made, which brings us to the “fits and starts” alluded to earlier. While patching the first hack, they seem to have initially wanted to decrease the time drift to 15 minutes, but things kept… going wrong. First, they failed to convert 15 minutes into seconds, then they failed to convert 15 minutes into seconds again, then realizing that changing the time drift rules had retroactively made old blocks invalid and thus forced a hard fork in the chain, they made sure the rule only applied after a certain block (and alerted all clients that they had to immediately update again), until finally, they reverted all time-drift changes they’d made altogether and went with the “5 out of 10” patch described above.
After going through all of this riffraff, why did the time-drift fix end up getting ditched anyway? Perhaps they really thought that the “5 out of 10” patch would be enough; what this commit message seems to imply is that they simply forgot. Frankly, I’m not sure which is worse.
As for what will happen moving forward: in April, they indicated that they were working on a “a whole new method for block and transaction verification.” More recently, they’ve said that they are working on rebuilding the project in a new repository (which is private, as of writing), where they’ll be rebasing their code into that of Bitcoin core. So I suppose we’ll see how that goes.
Final Thoughts/FUD
What can I possibly say here? When I started investigating Verge, it was purely out of intrigue and curiosity about how such a hack could be accomplished. I truly had no interest in attacking the developers or the community of users, or in casting the project in a bad light. So, at the risk of putting the cart before the horse, I want to preempt any possible accusations impugning my motives, and make this crystal clear: this time, I am trying to spread FUD [7]. Sometimes, fear, uncertainty, and doubt are reasonable responses to a situation, and if you have any sort of investment in the success of Verge, and aren’t experiencing some combination of those three emotions, I can only conclude that you’re lying to yourself or aren’t paying attention.
Because there’s just no way around it — this shit is inexcusable. This level of irresponsible negligence would be deemed unacceptable in an undergraduate’s comp-sci 101 midterm project, let alone a project giving rise to a digital asset worth (by at least one metric) hundreds of millions of dollars.
Trust-minimized systems will always still have certain parties granted some degree of good-faith, and like it or not, programmers are inevitably one of those parties. Having specialized skills and knowledge makes them sort of pseudo-fiduciaries, and the only way to keep such actors honest is to hold their feet to the fire at all times and demand explanations when things go awry.
Instead, what we see in all too many of these crypto-communities (and no, I’m certainly not only talking about the #VergeFam here) are armies of cheerleading sycophants who seem to have actually convinced themselves that if they can maintain constant levels of hyper-jubilance about their project and confront any criticism by slandering and shaming it out of existence, then the ensuing hype-bubble they create and the accompanying value increase of their precious coins will be enough for them to retire on.
Well, this is what you get. You get a team that’s off issuing press releases about the latest big-name partnerships while technical issues that require only a basic understanding of cryptocurrency protocols and a few man-hours to fix sit exposed for some psychotically-focused hacker to have his way with. And until somebody decides to pressure somebody else to do some form of due diligence, it’ll just keep happening.
Because as far as Verge is concerned, I’m afraid the unavoidable conclusion is that this hacker is currently doing better due diligence on this codebase than the Verge Developers themselves. I’d poach him if I were them.
For inquiries: daniel@theabacus.io
Notes:
[1] Some bitcoin maximalist-types have a less dignified term for “smaller altcoins” that I myself am far too classy to use here.
[2] Whether the actual situation was better or worse than a 51% attack is really a matter of opinion; I’d argue for a lot worse.
[3] For the developers/ nit-pickers, here’s he commit in question. To save you some time and heartache: while the diff appears to show to timestamp drifting, these changes are actually just reverting other post-hack patches from prior commits; so indeed, no changes were ultimately made to timestamp logic.
[4] The lead dev seems to acknowledge this here, linking to the Peercoin constants page without explanation.
[5] There is no protocol rule preventing this since generally it’s in the miners’ best interests to include as many transactions as possible (for maximum fee-collection).
[6] Should these transactions eventually actually get included on the chain, this will impose a cost on our attacker in terms of transaction fees, but he’s making his payday on block rewards anyway, so he might as well go hog wild.
[7] For those fortunate enough to be unfamiliar with the term, FUD = “Fear, uncertainty, and doubt,” the spread of which one will inevitably be accused of being motivated by whenever one levels some form of critique at something crypto-related.
Special Thanks to r_sholes for his sleuthing.
