Crate folding

This library implements basic components to fold computations expressed as multivariate polynomials of any degree. It is based on the “folding scheme” described in the Nova paper. It implements different components to achieve it:

• quadraticization: a submodule to reduce multivariate polynomials to degree 2.
• decomposable_folding: a submodule to “parallelize” folded computations.

Examples can be found in the directory examples.

The folding library is meant to be used in harmony with the library ivc. To use the library, the user has to define first a “folding configuration” described in the trait FoldingConfig. After that, the user can provide folding compatible expressions and build a folding scheme FoldingScheme. The process is described in the module expressions.

Re-exports

pub use expressions::ExpExtension;

pub use expressions::FoldingCompatibleExpr;

pub use instance_witness::Instance;

pub use instance_witness::RelaxedInstance;

pub use instance_witness::RelaxedWitness;

pub use instance_witness::Witness;

Modules

checker

Define the different structures required for the examples (both internal and external) A kind of pseudo-prover, will compute the expressions over the witness a check row by row for a zero result.

columns

This module contains description of the additional columns used by our folding scheme implementation. The columns are the base layer of the folding scheme as they describe the basic expressiveness of the system.

decomposable_folding

This variant of folding is designed to efficiently handle cases where certain assumptions about the witness can be made. Specifically, an alternative is provided such that the scheme is created from a set of list of constraints, each set associated with a particular selector, as opposed to a single list of constraints.

eval_leaf

expressions

Implement a library to represent expressions/multivariate polynomials that can be used with folding schemes like Nova.

instance_witness

This module defines a list of traits and structures that are used by the folding scheme. The folding library is built over generic traits like Instance and Witness that defines the NP relation R.

quadraticization

A library to reduce constraints into degree 2.

standard_config

This module offers a standard implementation of FoldingConfig supporting many use cases

Structs

FoldingOutput

Output of the folding prover

FoldingScheme

Enums

Alphas

Combinators that will be used to fold the constraints, called the “alphas”. The alphas are exceptional, their number cannot be known ahead of time as it will be defined by folding. The values will be computed as powers in new instances, but after folding each alpha will be a linear combination of other alphas, instand of a power of other element. This type represents that, allowing to also recognize which case is present.

Side

This type refers to the two instances to be folded

Traits

FoldingConfig

FoldingEnv

Describe a folding environment. The type parameters are: