International Association
for Cryptologic Research

We present a framework for building efficient folding-based SNARKs. First we develop a new ``uniformizing'' compiler for NP statements that converts any poly-time computation to a sequence of identical simple steps. The resulting uniform computation is especially well-suited to be processed by a folding-based IVC scheme. Second, we develop two optimizations to folding-based IVC. The first reduces the recursive overhead of the IVC by restructuring the relation to which folding is applied. The second employs a ``commit-and-fold'' strategy to further simplify the relation. Together, these optimizations result in a folding-based SNARK that has a number of attractive features. First, the scheme uses a constant-size transparent common reference string (CRS). Second, the prover has (i) low memory footprint, (ii) makes only two passes over the data, (iii) is highly parallelizable, and (iv) is concretely efficient. Proving time is comparable to leading monolithic SNARKs, and is significantly faster than other streaming SNARKs. For example, for proving $2^{24}$ constraints, we estimate that a Mangrove prover takes about $64$ seconds, $10$ times faster than Spartan SNARK, while using less than 160MB of memory.

Verifying where and when a digital image was taken has become increasingly difficult; this issue of image provenance is especially concerning in the realm of news media. While fact-checking services can identify misinformation, enabling individuals to personally verify the provenance of photos would prevent them from having to rely on third-parties and empower them to protect themselves. The Coalition for Content Provenance and Authenticity (C2PA) has developed a standard to verify image provenance that relies on digital signatures produced by cameras; however, photos are often edited (cropped, resized, converted to grayscale, etc.) before being included in a news story, and the public cannot validate signatures on the original photo given only the published image. The C2PA standard addresses this issue by having C2PA-enabled editing applications sign the edits that have taken place, but this solution requires trusting the C2PA applications. In contrast, we propose using zk-SNARKs to prove which edits have been applied to a given photo. The completeness and soundness of these proofs mean that the verifier need not trust the prover, which solves the trust problem posed by the C2PA standard. We implemented Circom programs to generate proofs for various common photo edits, and we demonstrate the practicality of these proofs through timing experiments. Witness and proof generation take only a few minutes for realistically sized pictures; verification time is around 10 ms; and proof sizes are around 800 bytes.