New paper alert: Naysayer proofs
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.
***
István András Seres is a PhD student in the Computer Science department of Eotvos Lorand University, under the supervision of Peter Burcsi and Daniel A. Nagy, and was a research intern at a16z crypto during the summer of ‘23. His research interests include Security & Privacy, particularly security and privacy of blockchains; privacy-enhancing technologies; zero-knowledge protocols; and blockchain scalability.
Noemi Glaeser is a PhD student in Computer Science at the University of Maryland and the Max Planck Institute for Security & Privacy and was a research intern at a16z crypto during the summer of ‘23. She is interested broadly in applied cryptography. She is a recipient of the NSF Graduate Research Fellowship, and was previously a research intern at NTT Research.
Joseph Bonneau is a Research Partner at a16z crypto. His research focuses on applied cryptography and blockchain security. He has taught cryptocurrency courses at the University of Melbourne, NYU, Stanford, and Princeton, and received a PhD in computer science from the University of Cambridge and BS/MS degrees from Stanford.
***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investment-list/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures/ for additional important information.