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 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: