Cross-posted from the a16z crypto blog.

Our new paper, presented at Financial Crypto 2024, introduces the notion of “naysayer proofs,” where a verifier optimistically accepts a submitted proof without verifying its correctness. Instead, any observer can check the proof off-chain and, if needed, prove its incorrectness to the verifier by submitting a naysayer proof. The verifier then checks the naysayer proof and, if it is correct, rejects the original proof. This can be far more efficient than checking the original proof.

We prove that every NP language has logarithmic-size and constant-time naysayer proofs, and also show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles. Naysayer proofs enable an interesting new paradigm for resource-constrained verifiers, such as smart contracts. It is a point on the design space between the most well-known strategies today: full proof validation (as in ZK rollups) or interactive fraud proving (as in optimistic rollups). Naysayer proofs offer some of the advantages of each.

Background

In most blockchains with programming capabilities – Ethereum, for example – developers are incentivized to minimize the storage and computation complexity of on-chain programs. Applications requiring significant computation or storage incur high fees (gas) to compensate validators in the network. These costs often are passed on to users of an application.

Gas costs have motivated many applications to use verifiable computation, off-loading expensive operations to powerful but untrusted off-chain entities who perform arbitrary computation and provide a succinct non-interactive proof (SNARK) that the claimed result is correct.

In this approach, smart contracts, which are capable of arbitrary computation, act primarily as verifiers and outsource all significant computation off-chain. Rollups, for example, combine transactions from many users into a single smart contract that verifies a proof that each transaction has been executed correctly. But verifying these proofs can still be costly. Some projects have spent hundreds of thousands of dollars to verify FRI polynomial commitment opening proofs.

This proof verification can be seen as wasteful. In most applications, provers have strong incentives to only post correct proofs, suffering direct financial penalties (in the form of a lost security deposit) or costs to their reputation and business for posting incorrect proofs. As a result, a significant fraction of a typical layer-1 blockchain’s storage and computation is expended verifying proofs that are virtually always correct.

The naysayer proof

The naysayer proof seeks to improve this state of affairs. The verifier (e.g., a rollup smart contract) optimistically accepts a submitted proof without verifying its correctness. Instead, any observer can check the proof off-chain and, if needed, submit a naysayer proof to prove its incorrectness. The verifier then checks the naysayer proof and, if it is correct, rejects the original proof. Otherwise, if no party can successfully naysay the original proof before the end of the dispute period, the original proof is accepted. To deter denial of service, naysayers may be required to post collateral, which they forfeit if their naysayer proof is incorrect.

This potentially saves the verifier work in two ways. First, in the optimistic case, where the proof is not challenged, the verifier does no work at all. We expect this to almost always be the case in practice. Second, in the pessimistic case, checking the naysayer proof may be much more efficient than checking the original proof. The naysayer acts as a helper to the verifier by reducing the cost of the verification procedure in fraudulent cases. At worst, checking the naysayer proof is equivalent to verifying the original proof.

Naysayer proofs also enable other interesting trade-offs. For instance, naysayer proofs might be run at a lower security level than the original proof system. A violation of the naysayer proof system’s soundness undermines the completeness of the original proof system. For an application like a rollup service, this results only in a loss of liveness; the rollup users’ funds would remain secure. Liveness could be restored by falling back to full proof verification.

The naysayer proof paradigm is generally applicable for proof systems with multi-round amplification, repetitive structure (e.g., multiple bilinear pairing checks), or recursive reduction (e.g., Pietrzak’s proof of exponentiation).

Future work

Future work might include a thorough game-theoretical analysis of naysayer proofs (e.g., deposits and the length of the challenge period), which would be crucial for real-world deployments. Another direction is to better understand the complexity theoretic properties of naysayer proofs: Is it possible to create a universal black-box naysayer proof for all non-interactive proof systems? Finally, one might consider several extensions of naysayer proofs, including interactive naysayer proofs or naysayer proofs with non-negligible soundness error.

For details, proofs, and citations, read the paper.