1# protogalaxy-poc [![Test](https://github.com/arnaucube/protogalaxy-poc/workflows/Test/badge.svg)](https://github.com/arnaucube/protogalaxy-poc/actions?query=workflow%3ATest)
 2
 3Proof of concept implementation of ProtoGalaxy (https://eprint.iacr.org/2023/1106.pdf) using [arkworks](https://github.com/arkworks-rs).
 4
 5> Do not use in production.
 6
 7Thanks to [Liam Eagen](https://twitter.com/LiamEagen) and [Ariel Gabizon](https://twitter.com/rel_zeta_tech) for their kind explanations.
 8
 9This code has been done in the context of the research on folding schemes in [0xPARC](https://0xparc.org).
10
11![protogalaxy img from Wikipedia](https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/Stellar_Fireworks_Finale.jpg/303px-Stellar_Fireworks_Finale.jpg)
12
13(img: protogalaxies colliding, [from Wikipedia](https://en.wikipedia.org/wiki/File:Stellar_Fireworks_Finale.jpg))
14
15## Details
16Implementation of ProtoGalaxy's scheme described in section 4 of the paper.
17
18Current version implements the folding on prover & verifier and it works for k-to-1 instances and with multiple iterations, but it is not optimized.
19Next 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.
20
21### Usage
22
23Example of folding k+1 instances:
24```rust
25// assume we have:
26// an R1CS instance 'r1cs'
27// a valid witness 'w' from our running instance
28// k valid 'witnesses' to be fold
29
30// compute the committed instance for our running witness
31let phi = Pedersen::<G1Projective>::commit(&pedersen_params, &witness.w, &witness.r_w);
32let instance = CommittedInstance::<G1Projective> {
33    phi,
34    betas: betas.clone(),
35    e: Fr::zero(),
36};
37
38// compute the k committed instances to be fold
39let mut instances: Vec<CommittedInstance<G1Projective>> = Vec::new();
40for i in 0..k {
41    let phi_i =
42	Pedersen::<G1Projective>::commit(&pedersen_params, &witnesses[i].w, &witnesses[i].r_w);
43    let instance_i = CommittedInstance::<G1Projective> {
44	phi: phi_i,
45	betas: betas.clone(),
46	e: Fr::zero(),
47    };
48    instances.push(instance_i);
49}
50
51// set the initial random betas
52let beta = Fr::rand(&mut rng);
53let betas = powers_of_beta(beta, t);
54
55// Prover folds the instances and witnesses
56let (F_coeffs, K_coeffs, folded_instance, folded_witness) = Folding::<G1Projective>::prover(
57    &mut transcript_p,
58    &r1cs,
59    instance.clone(),
60    witness,
61    instances.clone(),
62    witnesses,
63);
64
65// verifier folds the instances
66let folded_instance_v = Folding::<G1Projective>::verifier(
67    &mut transcript_v,
68    &r1cs,
69    instance,
70    instances,
71    F_coeffs,
72    K_coeffs,
73);
74
75// check that the folded instance satisfies the relation
76assert!(check_instance(&r2cs, folded_instance, folded_witness));
77
78// now, the folded instance & witness can be folded again with n other instances.
79```
80(see the actual code for more details)