Efficient PLONK IVC through Sangria

Sangria, an innovative folding scheme for the PLONK arithmetization, represents a significant advancement in the field of incrementally verifiable computation (IVC). This technical note explores the various aspects of Sangria technologies, including its capabilities, benefits, and potential for future developments.

Sangria is a groundbreaking approach to incrementally verifiable computation (IVC) that builds upon the concept of folding schemes to enhance the efficiency, flexibility, and security of verifiable computations based on the PLONK arithmetization. Introduced as an innovative development in the field of cryptographic research, Sangria offers a novel folding scheme tailored explicitly for the PLONK arithmetization, presenting new possibilities for custom gates and circuits with higher gate arity.

At its core, Sangria is characterized by a "relaxed" PLONK gate equation, denoted as C'Q,i(a, b, c, u, e), which forms the foundation for its unique verification process. This relaxed gate equation introduces a scaling factor u and an error vector e, both of which play crucial roles in accommodating custom gates and absorbing cross-terms in the computation.

Before delving into the details of Sangria, it is essential to understand the basic notation and preliminary knowledge related to the PLONK arithmetization and folding schemes. This includes defining column vectors, matrices, and the committed additively homomorphic commitment scheme for vectors in a finite field.

The PLONK arithmetization utilizes multi-purpose gates and selectors to define circuits. Each gate instantiation can be specialized to implement specific operations. The gate equation is defined by considering left and right inputs and an output, along with selector vectors. Copy constraints ensure correct gate connections within the circuit.

Leveraging the groundwork laid by previous research, Sangria introduces a novel folding scheme designed exclusively for the PLONK arithmetization. This scheme capitalizes on the power of random linear combinations of input instance-witness pairs, resulting in an efficient and secure verification process. Notably, Sangria presents a relaxed PLONK gate equation, which plays a critical role in accommodating custom gates of degree 2 and even circuits with higher gate arity, providing unprecedented flexibility and versatility.

Introducing the notion of a folding scheme, we explain how it reduces the task of checking two instances in a relation to a single instance. Nova's work on incrementally verifiable computation (IVC) in the random oracle model using a non-interactive folding scheme is also discussed.

We present the relaxed PLONK gate equation, which accommodates custom gates of degree 2. By introducing a scaling factor and an error vector, cross-terms are absorbed, making the scheme non-trivial. The relaxed PLONK trace is represented by a tuple of vectors: (a, b, c, u, e).

The Sangria folding scheme for the relaxed PLONK arithmetization is explained in detail. It involves random linear combinations of input instance-witness pairs, with cross terms being absorbed into the slack vector and scaling factor. The construction is proven to be a public-coin folding scheme with perfect completeness, knowledge soundness, and zero-knowledge properties.

We discuss a general strategy for implementing custom gates of degree 2 in the PLONK arithmetization. By breaking down the gate equation into monomials and adjusting the error term, we achieve a folding scheme that supports higher arity circuits while retaining the ability to fold higher degree gates.

Preserving the flexibility of PLONKish arithmetizations, we explore strategies for integrating lookup arguments into the folding scheme. Lookup gates enable versatile computation, and Sangria aims to support their seamless inclusion.

To achieve both succinctness and zero-knowledge in IVC proofs, a zkSNARK for the relaxed arithmetization needs to be developed. Possible approaches involve converting the Sangria trace into a PLONKish trace or modifying the IOP directly to handle the introduced u and e values.

Efforts to reduce the recursion overhead in the current construction are discussed. By flattening the witness matrix W into a single column vector, the verifier can work with a single witness commitment, albeit with increased reference string size.

The potential for supporting higher degree custom gates in the random linear combination strategy is explored. Strategies for degree 3 gates are suggested, with the additional computational cost analyzed.

Emphasizing the importance of maintaining support for lookup-enabled arithmetizations, we discuss potential folding schemes to accommodate lookup gates seamlessly.

Sangria represents a significant advancement in incrementally verifiable computation for the PLONK arithmetization. With its relaxed gate equation and folding scheme, Sangria opens doors to custom gates, higher arity circuits, and lookup-enabled arithmetizations. Future developments involving succinct IVC and optimized recursion overhead are promising. As the field of PLONK continues to evolve, Sangria holds the potential to revolutionize verifiable computation paradigms, making them more efficient, flexible, and secure.