Paper 2020/1426

Linear-Time Arguments with Sublinear Verification from Tensor Codes

Jonathan Bootle, Alessandro Chiesa, and Jens Groth


Minimizing the computational cost of the prover is a central goal in the area of succinct arguments. In particular, it remains a challenging open problem to construct a succinct argument where the prover runs in linear time and the verifier runs in polylogarithmic time. We make progress towards this goal by presenting a new linear-time probabilistic proof. For any fixed $\epsilon > 0$, we construct an interactive oracle proof (IOP) that, when used for the satisfiability of an $N$-gate arithmetic circuit, has a prover that uses $O(N)$ field operations and a verifier that uses $O(N^{\epsilon})$ field operations. The sublinear verifier time is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-size encoding of the circuit that is computable in linear time). When combined with a linear-time collision-resistant hash function, our IOP immediately leads to an argument system where the prover performs $O(N)$ field operations and hash computations, and the verifier performs $O(N^{\epsilon})$ field operations and hash computations (given a short digest of the $N$-gate circuit).

Note: Added full version.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2020
interactive oracle proofstensor codessuccinct arguments
Contact author(s)
jbt @ zurich ibm com
alexch @ berkeley edu
2020-12-28: revised
2020-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Alessandro Chiesa and Jens Groth},
      title = {Linear-Time Arguments with Sublinear Verification from Tensor Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1426},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.