# Naysayer Proofs
The "Naysayer Proofs" paradigm presents an cost efficient approach to on chain proof verification. The on chain proof verification is almost wastefull as most of the proofs are already valid, verifying a valid proof incurs a lot more resource-intensive checks than validating that the provided proof was invalid.

## The System Model
The original system, which verifies all proofs immediately, will shift to an optimistic model with a challenge period (T~nay~), similar to the way optimistic rollups function. In this model, proofs are accepted optimistically, allowing anyone to verify them. If a proof is found to be invalid, an individual can challenge it by "naysaying." The naysayer must then submit a counter-proof(Naysayer Proof) on-chain before the challenge period (T~nay~) expires.


The proposer proposes a transaction and submits its Zero-Knowledge (ZK) proof along with the corresponding verification trace. The Naysayer(validator) then assesses the ZK proof for validity. If the proof is valid, the validator does not contest the transaction and it is optimistically accepted by the verifier. Conversely, if the validator identifies the proof as invalid, they issue a challenge by providing a counterproof called Naysayer proof. This counterproof details the specific error in the verification trace, thereby undermining the ZK proof's validity by pinpointing the exact erroneous step or gate. The validator then evaluates the Naysayer proof. If the Naysayer proof is valid, the transaction is rejected; if not, the transaction is accepted.

## Zero Knowledge
Naysayer proofs inherently provide zero knowledge due to their design, as the interaction of the validator and the verifier is limited to the exchange and verification of computational proofs, which can be ZK. This setup ensures that the witness to the computation remains private.

## Storage
The original proofs of computation can be stored via off chain data availability services and commitment of that data is stored on chain, so when ever proofs are sent on chain as call data they can be verified against the commitment.
* When the proofs are valid, they do not need to be stored on-chain as expensive call data or in persistent storage within the smart contract. The commitment alone is sufficient to confirm the proof's validity, thus saving on-chain resources and reducing costs.
* If there is suspicion that a proof is invalid, a challenger (referred to as the "naysayer") can verify the data provided by the off-chain data availability service against the on-chain commitment. If the naysayer finds discrepancies or evidence of fraud, they generate a naysayer proof. This proof demonstrates that the original proof was incorrect or malicious. The naysayer proof is then submitted on-chain, where it undergoes a final verification process. If the naysayer proof is validated, the original proof is rejected, and penalties may be imposed on the entity that submitted the invalid proof. This two-step process ensures data integrity and encourages honest behavior by allowing challenges while minimizing on-chain storage and computation costs.

## Applications

### Roll ups

Integrating naysayer proofs with rollups could significantly enhance the settlement-cost. Here's a concise overview of how this integration might work:

1. Batch Submission: Rollup operators would submit transaction batches and proof of correctness on chain, but instead of immediate verification, the on chain smart contract would accept the batch optimistically without verifying the proof, reducing on-chain computation.
2. Challenge Period: A set time window (T~nay~) would allow observers to verify the proofs, after which they would be considered final.
3. Naysayer Proofs: If an invalid state transition is detected, a challenger can submit a naysayer proof demonstrating the incorrectness.
4. On-chain Verification: The smart contract would only need to verify naysayer proofs, significantly reducing computational load in the common case where batches are valid.
5. Economic Incentives: A reward system for successful challengers and penalties for invalid batch submitters would maintain security through game theory. Challengers might require to stake deposits, deterring DoS attacks on verifiers and ensuring only legitimate challenges are submitted.
6. Increased Decentralization: In a conventional rollup, validator nodes or challengers need to run a full node that maintains the entire state of the rollup. This involves storing all historical transaction data, state transitions, and actively processing every transaction to compute the state of the rollup from scratch. With zero-knowledge proofs and transaction data posted to data availability layer, challengers do not need to maintain a complete replica of the rollup’s state or process every transaction themselves. Instead, they rely on succinct proofs that confirm the correctness of the state transitions. Challengers can operate with minimal computational power and storage, making it feasible for a broader range of participants to get involved in the verification process.

The primary benefit of naysayer-based rollups over rollups that rely on zk-fraud proofs lies in their ability to decentralize the block validation, However, this approach comes with the cost of generating a proof of correctness for every block, leading to higher overall proving costs while zk-fraud proof-based rollups only genarate proofs in pessimistic cases.