The Cheater Checking Problem: Why the Verifier’s Dilemma is Harder Than You Think

A common design pattern in blockchain systems is to have one party do some work and escrow a bond for correct behavior, then invite others to verify the work and take the bond if they catch the worker cheating. You might call this the assert-challenge design pattern. We do this in Arbitrum, and it’s also seen in proposals like Optimistic Rollup which is in the news lately.

These systems can suffer from the Verifiers’ Dilemma, which is basically the observation that there’s no point in checking somebody’s work if you know they’re not going to cheat; but if you’re not going to check then they have an incentive to cheat. If you’re a designer, you want to argue that your system is incentive-compatible, meaning that if everybody acts consistent with their incentives, no cheating will occur. This is one of those areas where intuition can lead you wrong. This problem is much nastier than it looks — as we’ll see when we unpack the incentives of parties below.

A Super-Simple Model

Let’s start by building the simplest model we can. Assume there are two players. The Asserter makes a claim, which might be true or false. The Checker can check the Asserter’s claim, or the Checker can choose to do nothing, presumably on the assumption that the Asserter is probably telling the truth. Let’s assume that it costs the Checker C to check, and the Checker collects a reward of R if it checks and discovers the Asserter was cheating. (R includes all of the benefits the Checker gets for catching cheating. That includes benefits realized “outside the system” as well as any benefit from increasing others’ confidence in the system.) If the Asserter cheats without getting caught, the Checker suffers a loss of L, for example because the cheating Asserter can fraudulently take items of value from the Checker.

Now there are two threats we need to worry about: bribery and laziness. Bribery is the possibility that the Asserter will bribe the Checker not to check, allowing the Asserter to cheat without detection. We can prevent this by making sure that the Asserter escrows a very large deposit — larger than the total value at stake in the system, and payable to the Checker if cheating is detected— so that the Asserter won’t be willing to pay a bribe larger than the Checker’s reward R. This will prevent bribery, but it requires the system to be fully collateralized, which can be very expensive.

The other threat is laziness, the risk that the Checker will decide not to check the Asserter’s work. (Bear in mind that the Checker might say they’re checking but not actually do it.) Let’s look at the Checker’s incentives, to see if this is a rational strategy.

Suppose the Asserter is cheating with probability X. Now the Checker’s utility is as follows:

• If the Checker checks: R*X-C
• If the Checker doesn’t check: -X*L

Checking is worthwhile only if the utility of checking is greater than the utility of not checking, that is, if X > C/(R+L). And here’s the bad news: the Asserter can cheat randomly, with probability of cheating less than C/(R+L), and a rational Checker will never check, so the Asserter will never get caught cheating.

Let’s plug in some numbers. If checking costs $0.10 per transaction, the Checker collects a bounty of $75 if it detects cheating, but the Checker gets burned to the tune of $25 if it fails to detect cheating, then the Asserter can cheat up to one time in a thousand with impunity. If we want this system to run for thousands of transactions, then we have a big problem. There is nothing obvious that we can do, within this model, to drive the probability of cheating all the way to zero. All we can hope to do is over-collateralize the system in order to make the denominator of C/(R+L) bigger.

This is a surprisingly robust result — in a bad way. It doesn’t depend at all on the Asserter’s incentives. As long as the Asserter gains a nonzero advantage from successful cheating, it will be able to do so with some probability, safe in the knowledge that it’s not worth the Checker’s effort to do the work of checking. The result also doesn’t depend on how much time we give the Checker to do its work, or whether we pay the Checker for (claiming to) check.

Maybe you’re thinking, at this point, that the problem is that there is only one Checker. Does adding more Checkers reduce the likelihood of cheating? Surprisingly, it doesn’t.

Adding Checkers Doesn’t Help to Prevent Cheating

Again, let’s make the simplest possible model. Now there are two Checkers who act independently of each other. Each Checker pays C if it checks, and if somebody checks and catches the Asserter cheating, a reward of R is paid to the successful Checker, or split evenly between the two if they both checked. (If you prefer, in the case where they both check you can give the full reward of R to one of them at random. This doesn’t affect anyone’s strategies or outcomes.) As before, each Checker will suffer a loss of L if the Asserter cheats without getting caught.

Now it is still the case that if the Asserter cheats less than C/(R+L) fraction of the time, it is not worthwhile for either of the Checkers to check because the utility of checking is less than the utility of not checking. Indeed, the incentive problem is worse than before, because the cost of checking is still C for each Checker, but the expected reward for catching cheating is less than R because the reward will sometimes need to be split — the expected reward will be somewhere between R/2 and R. If the expected reward is b*R for some b between 0.5 and 1, then the Asserter can cheat up to C/(b*R+L) of the time — that’s more undetected cheating than if there were a single Checker! (The math gets a bit more complicated, because the value of b depends on the Checkers’ strategies, and their strategies depend on b, but it should be clear that they will have to split the reward sometimes. And also, the effective value of L is reduced because a Checker who doesn’t check might not lose their L due to the other Checker checking.)

The one place where multiple checkers is really helpful is in preventing bribery. With two checkers, the Asserter would have to pay a bribe of more than R to each Asserter, making bribery twice as expensive and therefore allowing 50% collateralization rather than full collateralization. But the tradeoff is that the amount of cheating goes up.

I won’t go through all of the math here, but going from one Checker to two under reasonable assumptions plausibly causes the level of undetected cheating to increase by 50%.

Adding Checkers Makes Things Worse!

You can add more checkers if you want, and things get even worse. As you add more Checkers, the Checkers need to worry more about having to split the reward multiple ways, so the expected reward for each successful Checker creeps downward, causing the safe cheating probability for the Asserter to creep upward. From this standpoint, the worst possible situation is one where everybody in the world is a possible Checker. That’s not infinitely bad, because things get worse more and more slowly as you add Checkers, but it definitely doesn’t help against cheating, even if it does effectively eliminate the risk of bribery.

Are You Sure Your System is Incentive-Compatible?

If you have a system that fits within this type of model, and you think it’s incentive-compatible, you need to think carefully about why that is so. In particular, you need to explain why Checkers would do the work of checking, even if they think Asserters are very unlikely to cheat. It’s not enough that there is a big penalty for cheating. It’s not enough that there is a reward for catching cheaters. It’s not enough that there are lots of Checkers — in fact that probably makes things worse. Why is your system immune?

This challenge applies to systems like Optimistic Rollup. It applies to us too, when we talk about Arbitrum.

The Way Out

But don’t give up hope. There’s a trick we’re building into Arbitrum that solves this problem by adding a new term to the Checkers’ incentives so they are better off checking in all cases, thereby making the Asserter’s optimal level of cheating zero. It’s easy to see what kind of term we might want to add to the utility equation — but it’s a lot harder to design a mechanism that produces that incentive. We’ll dig into the details in the next post.

Thanks to Karl Floersch for comments on an earlier draft of this post.