Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost

Abstract

We describe a zero-knowledge proof system in which a prover holds a large dataset M and can repeatedly prove NP relations about that dataset. That is, for any (public) relation R and x, the prover can prove that ∃w: R(M,x,w) = 1. After an initial setup phase (which depends only on M), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a random-access machine (RAM) implementation of R, up to poly-logarithmic factors. In particular, the cost per proof in many applications is sublinear in |M |. Additionally, the storage requirement between proofs for the verifier is constant. 1