[Resource Topic] 2024/1364: FLIP-and-prove R1CS

Welcome to the resource topic for 2024/1364

Title:
FLIP-and-prove R1CS

Authors: Anca Nitulescu, Nikitas Paslis, Carla Ràfols

Abstract:

In this work, we consider the setting where one or more users with low computational resources would lie to outsource the task of proof generation for SNARKs to one external entity, named Prover. We study the scenario in which Provers have access to all statements and witnesses to be proven beforehand. We take a different approach to proof aggregation and design a new protocol that reduces simultaneously proving time and communication complexity, without going through recursive proof composition.
Our two main contributions: We first design FLIP, a communication efficient folding scheme where we apply the Inner Pairing Product Argument to fold R1CS instances of the same language into a single relaxed R1CS instance. Then, any proof system for relaxed R1CS language can be applied to prove the final instance. As a second contribution, we build a novel variation of Groth16 with the same communication complexity for relaxed R1CS and two extra pairings for verification, with an adapted trusted setup.
Compared to SnarkPack - a prior solution addressing scaling for multiple Groth16 proofs - our scheme improves in prover complexity by orders of magnitude, if we consider the total cost to generated the SNARK proofs one by one and the aggregation effort.
An immediate application of our solution is Filecoin, a decentralized storage network based on incentives that generates more than 6 million SNARKs for large circuits of 100 million constraints per day.

ePrint: https://eprint.iacr.org/2024/1364

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .