Expand description
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;
Modules
- 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.
- 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.
- Implement a library to represent expressions/multivariate polynomials that can be used with folding schemes like Nova.
- A library to reduce constraints into degree 2.
Structs
Enums
- 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.
- This type refers to the two instances to be folded
Traits
- Describe a folding environment. The type parameters are: