“How to Prove False Statements: Practical Attacks on Fiat-Shamir” (Khovratovich, Rothblum, Soukhanov; 2025) constructs families of circuits for which the GKR protocol, when made non-interactive by Fiat-Shamir heuristic, will prove false statements. It’s a great paper and is so well written that I won’t attempt to do better by paraphrasing their constructions. What I’d like to look at here is instead the consequences of the result for real-world applications of non-interactive proofs.
The Fiat-Shamir heuristic attempts to simulate, in the non-interactive setting, random challenges that the verifier would have issued in an interactive setting. It does so by replacing the information-theoretic assumption of the random oracle model with a cryptographic assumption about deterministic hash functions. Fiat-Shamir is crucial to real-world cryptographic applications (and blockchains, in particular) because it enables non-interactive proofs: a non-interactive proof can be checked by any number of verifiers, present and future. Moreover these verifiers don’t need to trust one another. They can check the validity of the proof for themselves.
How does Fiat-Shamir work? The prover (and any future verifiers), replace each random message from the verifier with the result of applying a cryptographic hash function to all of the messages from the prover up to that point. Intuitively, the cryptographic assumptions on the hash function should then prevent a computationally-bounded malicious prover from choosing their messages to obtain a desired (Fiat-Shamir generated) message from the verifier and thereby prove a false statement. This has never been proven, however, and indeed earlier work had demonstrated somewhat contrived protocols where it fails.
The current paper shows that the Fiat-Shamir heuristic fails for the very natural and useful GKR protocol. In my assessment, this paper is very impactful in a social sense, in that it reminds us all of the fallibility of cryptographic conjectures. It is a blow to the confidence of those building blockchain applications, and also to those who use blockchains as a store of wealth. However, this is not because this specific attack can be carried out in meaningful applications, but simply because it reminds us how we tend to build castles on sand. Moreover, the result “breaks the promise” of GKR in that it illustrates how GKR can, for certain maliciously constructed circuits, prove false statements. Importantly, however, the paper demonstrates failure of non-interactive GKR only for a contrived family of circuits, and so there is a strong sense in which this result has no practical consequences whatsoever. A verifying party is not simply checking “is this a valid proof of the satisfaction of some circuit?” but rather “is this a valid proof of satisfaction of the circuit XYZ known to me”. Any verifying party that doesn’t care which circuit is satisfied before it releases the funds (or performs some critical function) was already vulnerable to deception, irrespective of this result. Why would you trust a circuit that you hadn’t audited?
It has also been suggested that this paper signals the end of recursive verification of GKR circuits. The reason for this being that both this attack and recursive verification rely on being able to circuitize the hash function used in the transcript, and so facilitating one facilitates the other. This concern evaporates however when we again remember that the only circuits used in production are ones upon which the prover and verifying parties have agreed, and this includes circuits for recursive verification. Why would a verifying party accept the use of a recursive verifier circuit with a backdoor in it? They simply wouldn’t.