Low-level API for SNARK trait

[Pratyush]

Summary

Introduce a low-level API for setup, indexing, proving, and verifying that directly reasons about the relation, instead of going via our ConstraintSystem API.

Problem Definition

Right now, for proving R1CS via our SNARK traits, we have to go via the ConstraintSynthesizer (and hence ConstraintSystem) trait. This is unsatisfactory for a couple of reasons:

1. Using our libraries with external R1CS formats like zkinterface incurs performance overheads because we have to convert to ConstraintSystem and then back to matrices, instead of directly reading the matrices from the external format.
2. The relations crate is at the moment more about data structures for working with a particular relation (R1CS) rather than about the relation itself. For example, the R1CS relation consists of (i, x, w) where i consists of the R1CS matrices, and x and w are the public input and witness, respectively. However, the current ark_relations::r1cs module doesn't have any data structure reflecting these, and only has data structures like ConstraintSystemRef.

Proposal

• Add a Relation trait in relations that looks like:

pub trait Relation {
	type Index;
	type Instance;
	type Witness;
	
	fn check_membership(i: &Self::Index, x: &Self::Instance, w: &Self::Witness) -> bool;
}

• Modify the SNARK trait as follows:

pub trait SNARK<R: Relation> {
	fn index(pp: &Self::Parameters, i: &R::Index) -> (Self::ProvingKey, Self::VerifyingKey);
	// same for proving and verifying
}

Additionally, we add a new R1CS-specific trait:

pub trait R1CSSnark: SNARK<R1CS> {
	fn index_from_cs<CS: ConstraintSynthesizer>(pp: &Self::Parameters, cs: CS) -> (Self::ProvingKey, Self::VerifyingKey) {
		// default impl using the `SNARK::index`, by `calling cs.into_matrices()`. 
	}
}

(We might need equivalents for PreprocessingSNARK.)

---

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

[weikengchen]

One question:

For the index function, you mentioned "same for proving and verifying".

Do you mean that they remain unchanged? Or that you will add an index to it (which seems unnecessary, since the PK and VK suffice).

[Pratyush]

For the index function, you mentioned "same for proving and verifying".

By that I mean that proving will take in the ipk and assignment (x, w) explicitly, instead of taking in ipk and CS: ConstraintSynthesizer