The Dilemma That Shook the Blockchain World, a Decade On
A paper written at NUS Computing challenged one of the founding assumptions of blockchain technology, just as the idea of a planetary-scale decentralised computer was taking shape. 10 years on, it won one of cybersecurity’s most prestigious honours.
In 2015, the idea of building a planetary-scale decentralised computing platform was on the horizon, with plans for Ethereum being developed. This idea was bold, building well beyond Bitcoin’s decentralised virtual currency. Ethereum was proposing a general-purpose computational engine, where computers anywhere in the world, called miners, would compete to solve tasks in exchange for financial fees in virtual coins, running scripts called smart contracts coupled with payment transactions in their virtual currency.
There was a gospel assumption in the Bitcoin blockchain platform at the time, that a majority of CPU power is controlled by honest nodes. Associate Professor Prateek Saxena from the Department of Computer Science, and his co-authors Loi Luu, Jason Teutsch, and Raghav Kulkarni, challenged that assumption in a paper titled “Demystifying Incentives in the Consensus Computer”. They argued that nodes are rational, not necessarily honest. Nodes lack incentives to verify blocks they didn’t mine themselves, especially when doing so requires high computational costs, as was going to be the case with smart contract platforms. They defined this problem with a concept they called the verifier’s dilemma. This work became the prerequisite to much of the verification solutions that followed in the decade after, including the multi-billion dollar optimistic rollup industry.
On 4 July 2015, however, five days into the rebuttal period of their submitted paper, there was a fork on the Bitcoin network with unverified blocks that went 6 blocks deep, followed by another fork 3 blocks deep the following day. Vitalik Buterin, Ethereum’s founder, responded to the paper publicly around the same time, in a Reddit thread the authors later cited in their own reference list.
Two attacks fell out of this observation. A miner could stuff their own block with transactions that look expensive to verify but are actually meaningless, forcing everyone else to burn time checking them while gaining nothing themselves. Or a dishonest party could submit a wrong answer to an outsourced computation, betting that the cost of catching them exceeds anyone’s willingness to check.
From Critique to a Working Fix
Rather than argue for scrapping the incentive structure altogether, the authors built a model, the ε-consensus computer, that caps how much advantage any miner can gain from cheating. Keep that cap small, and honesty becomes the rational choice again almost by default. One version of their fix splits large computations into a chain of smaller, cheaply verifiable steps. A second version borrows from a field called property testing: check a random sample of a result rather than redoing the whole thing, and the odds of missing an error can be pushed arbitrarily low.
A Theory the Industry Couldn’t Ignore
What started as a critique of Bitcoin’s founding assumptions has, over the following decade, worked its way into a large share of blockchain scalability research, showing up in analyses of Ethereum sharding and, more recently, in work on optimistic rollups.
Co-author Jason Teutsch went on to found Truebit, a protocol built around the paper’s central wager: that a decentralised network only verifies what it’s actually paid to verify.
10 years later, that paper won the ACM CCS 2025 Test-of-Time Award, a fitting close to that arc. It is a reminder of what good systems research can do at its best: not chase a headline but ask an uncomfortable question early enough that the rest of the field spends the next 10 years answering it.
