How Not to Solve the Verifiers’ Dilemma
Our team at Offchain Labs was happy to see that the new Flow blockchain proposed by Dapper Labs tried to address the Verifiers’ Dilemma. We think that’s an important problem. Unfortunately their solution fails to solve the Verifier’s Dilemma, for two separate reasons I’ll explain below.
SPoCKs Are Not Logical
Before getting to the biggest problem, let’s talk about a serious error in Flow’s cryptography: their “SPoCK” primitive doesn’t work.
A SPoCK (Specialized Proof of Confidential Knowledge) is a new primitive defined in the Flow papers. They claim that a SPoCK is a kind of proof of knowledge (p. 10):
Formally, the SPoCK protocol provides two central guarantees:
1. An arbitrary number of parties can prove that they have knowledge of a shared secret ζ without revealing the secret itself.
2. The proofs can be full revealed, in an arbitrary order, without allowing any additional party to pretend knowledge of ζ.
Per guarantee 1, the purpose of a SPoCK is to prove that a particular party has knowledge of ζ. But a SPoCK proves no such thing.
To see why, let’s review how a SPoCK is computed. First, “use ζ (or a cryptographic hash of ζ) as the seed for a deterministic key generation process, generating a public/private key pair (pk, sk).” Then use sk “to sign your public identity (such as a node ID), and publish the signature along with with the deterministically generated public key pk.” The SPoCK for an ID is (pk, sign_sk(ID)).
Notice that there is nothing about this process that requires the participation of the party whose ID appears in the SPoCK. Anybody can make a SPoCK containing Alice’s public ID — so a SPoCK containing Alice’s public ID proves nothing about Alice’s knowledge of ζ.
In short, the “central guarantees” of the SPoCK primitive are both false. A SPoCK does not prove that the named party has knowledge of ζ; and parties can in fact pretend knowledge of ζ.
Even If SPoCKs Were Sound, Flow Wouldn’t Solve the Verifiers’ Dilemma
Here’s the bigger problem: even if we set aside the problems with SPoCKs, and pretended that some SPoCK-like primitive did provide the two central guarantees, the Flow protocol would still fail to solve the Verifier’s Dilemma.
To see why, let’s first review the Verifiers’ Dilemma, then turn to the problems with Flow.
We’ll review the Verifier’s Dilemma using a version of the simple model from my previous post. There is a single Asserter who is supposed to compute a function f(x). The Asserter publishes a claim as to the correct result. Two Checkers, Alice and Bob, are supposed to say whether the Asserter’s claimed result is right or wrong. If a Checker catches the Asserter giving an incorrect result, the Checker takes a deposit from the Asserter.
What we would hope for is an equilibrium where the Asserter doesn’t cheat. An equilibrium is a situation where each player has chosen a (possibly randomized) strategy, and everybody is happy with their strategy — nobody, knowing what the others’ strategies are, wants to change strategy. But in the simple scenario above, there is no equilibrium where the Asserter always tells the truth. If the Asserter never cheats, then Alice and Bob will want to stop checking, but then the Asserter will want to start cheating. Indeed, as I showed in the previous post, if the Asserter cheats at random, with a probability below some threshold, then it’s not worth Alice and Bob’s while to check the Asserter’s claims, because the occasional reward from catching cheating will be outweighed by the cost of checking every single time. That’s the Verifiers’ Dilemma in a nutshell.
A previous post explains the solution we’re building in Arbitrum, which has a unique equilibrium in which the Asserter never lies and the Checkers always check the Asserter’s work.
Flow’s approach is different. They have the two Checkers (they use the term “verification node” but I’ll use “Checker” for consistency) each compute a value ζ which summarizes the computation that the Asserter is supposed to have done. Then each checker publishes on-chain a SPoCK which is meant to be a sort of commitment by a specific checker to ζ.
The problem with Flow’s system is that it doesn’t force anybody to verify any computation; it just requires the parties to agree on a value for ζ. If the Asserter tells Alice and Bob a value for ζ (or announces a value), they have to decide whether they are going to take the Asserter’s word for it, or do the computation for themselves. That’s exactly the Verifier’s Dilemma — a strategy decision to either check at some expense, or just take the Asserter’s word for a claim.
Flow doesn’t prevent Checkers from being lazy — they just hope that it won’t happen. Here’s footnote 4 from their paper (page 10): “We assume that honest nodes will not accept unproved values for ζ, because they would be slashed if the ζ value was incorrect.” But that doesn’t follow. Flow doesn’t slash Checkers for being wrong; they slash for being in the minority. Which means that if others are going to accept a sketchy value, then your incentive is to accept it too. That’s a bad equilibrium.
The Dapper Labs’ team responded to us saying that this is collusion and they assume there’s no collusion.
But collusion is when parties agree on what they will do. If Alice sends information to Bob, that’s not collusion, that’s a unilateral action by Alice. You can’t redefine incentive-driven unilateral actions that you don’t like as collusion.
Consider a simplified situation where there are three incentive-driven parties, Alice, Bob, and Charlie, and anyone who ends up in the minority will get slashed. Alice tells the others (or announces publicly) that she is going to commit to the value Z, and she submits a result consistent with Z. Now that Alice is committed to Z, what should Bob do? If he also goes with Z, he knows he will be in the majority. But if he goes with a different value, then he risks being in the minority if Charlie sides with Alice. So the best move is for Bob is to go with Z — and this is true regardless of whether Z is correct, so Bob has no reason to expend resources to figure out if it is correct. Charlie doesn’t want to be slashed either, so he will follow suit. The result is that Z is accepted unanimously, with neither Bob nor Charlie checking whether it is correct. And if Alice knows the other players will follow their incentives, she knows it’s safe to announce whatever Z she wants. In other words, there is an equilibrium where Alice decides on a result and nobody else checks it.
(Notice that this three-player example didn’t involve any collusion. Each player is making an independent decision according to their incentives. So a no-collusion assumption doesn’t rule out this kind of bad equilibrium.)
Can this be fixed? Yes, but only by a significant redesign of the protocol. Crypto is hard.
