You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
arnaucube c6d42a8356 rm unused methods, some more polishing 11 months ago
.github/workflows add GHA 11 months ago
src rm unused methods, some more polishing 11 months ago
.gitignore init repo 1 year ago
Cargo.toml rm unused methods, some more polishing 11 months ago
LICENSE add eval_f & check_instance methods, add initial Folding prover structure 1 year ago rm unused methods, some more polishing 11 months ago

protogalaxy-poc Test

Proof of concept implementation of ProtoGalaxy ( using arkworks.

Experimental code, do not use in production.

Thanks to Liam Eagen and Ariel Gabizon for their kind explanations.

This code has been done in the context of the research on folding schemes in 0xPARC.

protogalaxy img from Wikipedia

(img: protogalaxies colliding, from Wikipedia)


Implementation of ProtoGalaxy's scheme described in section 4 of the paper.

Current version implements the folding on prover & verifier and it works for k-to-1 instances and with multiple iterations, but it is not optimized. Next steps in terms of implementation include: F(X) O(n) construction following Claim 4.4, compute K(X) in O(kd log(kd)M + ndkC) as described in Claim 4.5, add tests folding in multiple iterations and also in a tree approach, add the decider and integrate with some existing R1CS tooling for the R1CS & witness generation.


Example of folding k+1 instances:

// assume we have:
// an R1CS instance 'r1cs'
// a valid witness 'w' from our running instance
// k valid 'witnesses' to be fold

// compute the committed instance for our running witness
let phi = Pedersen::<G1Projective>::commit(&pedersen_params, &witness.w, &witness.r_w);
let instance = CommittedInstance::<G1Projective> {
    betas: betas.clone(),
    e: Fr::zero(),

// compute the k committed instances to be fold
let mut instances: Vec<CommittedInstance<G1Projective>> = Vec::new();
for i in 0..k {
    let phi_i =
	Pedersen::<G1Projective>::commit(&pedersen_params, &witnesses[i].w, &witnesses[i].r_w);
    let instance_i = CommittedInstance::<G1Projective> {
	phi: phi_i,
	betas: betas.clone(),
	e: Fr::zero(),

// set the initial random betas
let beta = Fr::rand(&mut rng);
let betas = powers_of_beta(beta, t);

// Prover folds the instances and witnesses
let (F_coeffs, K_coeffs, folded_instance, folded_witness) = Folding::<G1Projective>::prover(
    &mut transcript_p,
    // running instance
    // incomming instances

// verifier folds the instances
let folded_instance_v = Folding::<G1Projective>::verifier(
    &mut transcript_v,
    instance, // running instance
    instances, // incomming instances

// check that the folded instance satisfies the relation
assert!(check_instance(&r2cs, folded_instance, folded_witness));

// now, the folded instance & witness can be folded again with k other instances.

(see the actual code for more details)