Module folding::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.

This module describes 3 different types of instance/witness pairs:

• Instance and Witness: the original instance and witness. These are the ones that the user must provide.
• ExtendedInstance and ExtendedWitness: the instance and witness extended by quadraticization.
• RelaxedInstance and RelaxedWitness: the instance and witness related to the relaxed/homogeneous polynomials.

Note that Instance, ExtendedInstance and RelaxedInstance are supposed to be used to encapsulate the public inputs and challenges. It is the common information the prover and verifier have. Witness, ExtendedWitness and RelaxedWitness are supposed to be used to encapsulate the private inputs. For instance, it is the evaluations of the polynomials.

A generic trait Foldable is defined to combine two objects of the same type using a challenge.

Structs

• ExtendedInstance
  An extended instance is an instance that has been extended with extra columns by quadraticization. The original instance is stored in the instance field. The extra columns are stored in the extended field. For instance, if the original instance has n columns, and the system is described by a degree 3 polynomial, an additional column will be added, and extended will contain 1 commitment.
• ExtendedWitness
  This structure represents a witness extended with extra columns that are added by quadraticization
• RelaxedInstance
  A relaxed instance is an instance that has been relaxed by the folding scheme. It contains the original instance, extended with the columns added by quadriticization, the scalar u and a commitment to the slack/error term. See page 15 of Nova.
• RelaxedWitness

Traits

• Foldable
• Instance
• RelaxableInstance
• RelaxablePair
• RelaxableWitness
  Trait to make a witness relaxable/homogenizable
• Witness