# Time-Optimal Interactive Proofs for Circuit Evaluation

arXiv: https://arxiv.org/abs/1304.3812 · HTML: https://mlsanity.com/paper/1304.3812/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2013.

## Built on by (most cited first, 14 of 14)

- [zkLLM: Zero Knowledge Proofs for Large Language Models](https://mlsanity.com/paper/2404.16109/) (2024)
- [Scaling up Trustless DNN Inference with Zero-Knowledge Proofs](https://mlsanity.com/paper/2210.08674/) (2022)
- [pvCNN: Privacy-Preserving and Verifiable Convolutional Neural Network Testing](https://mlsanity.com/paper/2201.09186/) (2022)
- [zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training](https://mlsanity.com/paper/2307.16273/) (2023)
- [SoK: Machine Learning Governance](https://mlsanity.com/paper/2109.10870/) (2021)
- [Models That Prove Their Own Correctness](https://mlsanity.com/paper/2405.15722/) (2024)
- [SVIP: Towards Verifiable Inference of Open-source Large Language Models](https://mlsanity.com/paper/2410.22307/) (2024)
- [FairZK: A Scalable System to Prove Machine Learning Fairness in Zero-Knowledge](https://mlsanity.com/paper/2505.07997/) (2025)
- [All Rivers Run to the Sea: Private Learning with Asymmetric Flows](https://mlsanity.com/paper/2312.05264/) (2023)
- [Blockchain and Artificial Intelligence: Synergies and Conflicts](https://mlsanity.com/paper/2405.13462/) (2024)
- [Fine-Tuning Integrity for Modern Neural Networks: Structured Drift Proofs via Norm, Rank, and Sparsity Certificates](https://mlsanity.com/paper/2604.04738/) (2026)
- [Agree on the Model, Verify the Inference: GKR Protocols for HND-Based Transformer Inference](https://mlsanity.com/paper/2607.21162/) (2026)
- [Certified but Private: Scalable Zero-Knowledge Proofs for Neural Network Guarantees](https://mlsanity.com/paper/2608.17070/) (2026)
- [Maverick: Private and Verifiable LLM Inference Made Practical via Matrix-Vector Multiplication Delegation](https://mlsanity.com/paper/2609.10264/) (2026)

## Abstract (arXiv)

Recently, researchers have been working toward the development of practical general-purpose protocols for verifiable computation. These protocols enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the computations correctly. Despite substantial progress, existing implementations are not yet practical. The main bottleneck is typically the extra effort required by the prover to return an answer with a guarantee of correctness, compared to returning an answer with no guarantee. We describe a refinement of a powerful interactive proof protocol originally due to Goldwasser, Kalai, and Rothblum. Cormode, Mitzenmacher, and Thaler show how to implement the prover in this protocol in time O(S log S), where S is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits whose wiring pattern is sufficiently "regular"; for these circuits, we bring the runtime of the prover down to O(S). That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee. We argue that our refinements capture a large class of circuits, and prove some theorems formalizing this. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than 10x slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right. Our final contribution is a protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many pieces of data.