hash-chain-sonobe/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_camel_case_types)]
3#![allow(clippy::upper_case_acronyms)]
4///
5/// This example performs the full flow:
6/// - define the circuit to be folded
7/// - fold the circuit with Nova+CycleFold's IVC
8/// - generate a DeciderEthCircuit final proof
9/// - generate the Solidity contract that verifies the proof
10/// - verify the proof in the EVM
11///
12
13#[cfg(test)]
14mod tests {
15 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as G1};
16 use ark_grumpkin::{constraints::GVar as GVar2, Projective as G2};
17
18 use ark_crypto_primitives::snark::SNARK;
19 use ark_groth16::{Groth16, ProvingKey, VerifyingKey as G16VerifierKey};
20 use ark_poly_commit::kzg10::VerifierKey as KZGVerifierKey;
21
22 use ark_ff::{BigInteger, BigInteger256, PrimeField};
23 use ark_std::Zero;
24
25 use std::path::PathBuf;
26 use std::rc::Rc;
27 use std::time::Instant;
28
29 use folding_schemes::{
30 commitment::{
31 kzg::{ProverKey as KZGProverKey, KZG},
32 pedersen::Pedersen,
33 CommitmentScheme,
34 },
35 folding::nova::{
36 decider_eth::{prepare_calldata, Decider as DeciderEth},
37 decider_eth_circuit::DeciderEthCircuit,
38 get_r1cs, Nova, ProverParams, VerifierParams,
39 },
40 frontend::{circom::CircomFCircuit, FCircuit},
41 transcript::poseidon::poseidon_canonical_config,
42 Decider, Error, FoldingScheme,
43 };
44 use solidity_verifiers::{
45 utils::get_function_selector_for_nova_cyclefold_verifier,
46 verifiers::nova_cyclefold::get_decider_template_for_cyclefold_decider,
47 NovaCycleFoldVerifierKey,
48 };
49
50 // This method computes the Nova's Prover & Verifier parameters for the example.
51 // Warning: this method is only for testing purposes. For a real world use case those parameters
52 // should be generated carefully (both the PoseidonConfig and the PedersenParams).
53 #[allow(clippy::type_complexity)]
54 fn init_nova_ivc_params<FC: FCircuit<Fr>>(
55 F_circuit: FC,
56 ) -> (
57 ProverParams<G1, G2, KZG<'static, Bn254>, Pedersen<G2>>,
58 VerifierParams<G1, G2>,
59 KZGVerifierKey<Bn254>,
60 ) {
61 let mut rng = ark_std::test_rng();
62 let poseidon_config = poseidon_canonical_config::<Fr>();
63
64 // get the CM & CF_CM len
65 let (r1cs, cf_r1cs) =
66 get_r1cs::<G1, GVar, G2, GVar2, FC>(&poseidon_config, F_circuit).unwrap();
67 let cs_len = r1cs.A.n_rows;
68 let cf_cs_len = cf_r1cs.A.n_rows;
69
70 // let (pedersen_params, _) = Pedersen::<G1>::setup(&mut rng, cf_len).unwrap();
71 let (kzg_pk, kzg_vk): (KZGProverKey<G1>, KZGVerifierKey<Bn254>) =
72 KZG::<Bn254>::setup(&mut rng, cs_len).unwrap();
73 let (cf_pedersen_params, _) = Pedersen::<G2>::setup(&mut rng, cf_cs_len).unwrap();
74
75 let fs_prover_params = ProverParams::<G1, G2, KZG<Bn254>, Pedersen<G2>> {
76 poseidon_config: poseidon_config.clone(),
77 cs_params: kzg_pk.clone(),
78 cf_cs_params: cf_pedersen_params,
79 };
80 let fs_verifier_params = VerifierParams::<G1, G2> {
81 poseidon_config: poseidon_config.clone(),
82 r1cs,
83 cf_r1cs,
84 };
85 (fs_prover_params, fs_verifier_params, kzg_vk)
86 }
87
88 /// Initializes Nova parameters and DeciderEth parameters. Only for test purposes.
89 #[allow(clippy::type_complexity)]
90 fn init_ivc_and_decider_params<FC: FCircuit<Fr>>(
91 f_circuit: FC,
92 ) -> (
93 ProverParams<G1, G2, KZG<'static, Bn254>, Pedersen<G2>>,
94 KZGVerifierKey<Bn254>,
95 ProvingKey<Bn254>,
96 G16VerifierKey<Bn254>,
97 ) {
98 let mut rng = rand::rngs::OsRng;
99 let start = Instant::now();
100 let (fs_prover_params, _, kzg_vk) = init_nova_ivc_params::<FC>(f_circuit.clone());
101 println!("generated Nova folding params: {:?}", start.elapsed());
102
103 pub type NOVA<FC> = Nova<G1, GVar, G2, GVar2, FC, KZG<'static, Bn254>, Pedersen<G2>>;
104 let z_0 = vec![Fr::zero(); f_circuit.state_len()];
105 let nova = NOVA::init(&fs_prover_params, f_circuit, z_0.clone()).unwrap();
106
107 let decider_circuit =
108 DeciderEthCircuit::<G1, GVar, G2, GVar2, KZG<Bn254>, Pedersen<G2>>::from_nova::<FC>(
109 nova.clone(),
110 )
111 .unwrap();
112 let start = Instant::now();
113 let (g16_pk, g16_vk) =
114 Groth16::<Bn254>::circuit_specific_setup(decider_circuit.clone(), &mut rng).unwrap();
115 println!(
116 "generated G16 (Decider circuit) params: {:?}",
117 start.elapsed()
118 );
119 (fs_prover_params, kzg_vk, g16_pk, g16_vk)
120 }
121
122 fn f_vec_to_bits<F: PrimeField>(v: Vec<F>) -> Vec<bool> {
123 v.iter()
124 .map(|v_i| {
125 if v_i.is_one() {
126 return true;
127 }
128 return false;
129 })
130 .collect()
131 }
132 // returns the bytes representation of the given vector of finite field elements that represent
133 // bits
134 fn f_vec_to_bytes<F: PrimeField>(v: Vec<F>) -> Vec<u8> {
135 let b = f_vec_to_bits(v);
136 BigInteger256::from_bits_le(&b).to_bytes_le()
137 }
138 fn bytes_to_f_vec<F: PrimeField>(b: Vec<u8>) -> Result<Vec<F>, Error> {
139 use num_bigint::BigUint;
140 let bi = BigUint::from_bytes_le(&b);
141 let bi = BigInteger256::try_from(bi).unwrap();
142 let bits = bi.to_bits_le();
143 Ok(bits
144 .iter()
145 .map(|&e| if e == true { F::one() } else { F::zero() })
146 .collect())
147 }
148
149 // function to compute the next state of the folding via rust-native code (not Circom). Used to
150 // check the Circom values.
151 use tiny_keccak::{Hasher, Keccak};
152 fn rust_native_step<F: PrimeField>(
153 _i: usize,
154 z_i: Vec<F>,
155 _external_inputs: Vec<F>,
156 ) -> Result<Vec<F>, Error> {
157 let b = f_vec_to_bytes(z_i.to_vec());
158 let mut h = Keccak::v256();
159 h.update(&b);
160 let mut z_i1 = [0u8; 32];
161 h.finalize(&mut z_i1);
162 bytes_to_f_vec(z_i1.to_vec())
163 }
164
165 #[test]
166 fn full_flow() {
167 // set how many steps of folding we want to compute
168 let n_steps = 10;
169
170 // set the initial state
171 let z_0_aux: Vec<u32> = vec![0_u32; 32 * 8];
172 let z_0: Vec<Fr> = z_0_aux.iter().map(|v| Fr::from(*v)).collect::<Vec<Fr>>();
173
174 // initialize the Circom circuit
175 let r1cs_path = PathBuf::from("./circuit/keccak-chain.r1cs");
176 let wasm_path = PathBuf::from("./circuit/keccak-chain_js/keccak-chain.wasm");
177
178 let f_circuit_params = (r1cs_path, wasm_path, 32 * 8, 0);
179 let mut f_circuit = CircomFCircuit::<Fr>::new(f_circuit_params).unwrap();
180 // Note (optional): for more speed, we can set a custom rust-native logic, which will be
181 // used for the `step_native` method instead of extracting the values from the circom
182 // witness:
183 f_circuit.set_custom_step_native(Rc::new(rust_native_step));
184
185 // ----------------
186 // Sanity check
187 // check that the f_circuit produces valid R1CS constraints
188 use ark_r1cs_std::alloc::AllocVar;
189 use ark_r1cs_std::fields::fp::FpVar;
190 use ark_r1cs_std::R1CSVar;
191 use ark_relations::r1cs::ConstraintSystem;
192 let cs = ConstraintSystem::<Fr>::new_ref();
193 let z_0_var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_0.clone())).unwrap();
194 let z_1_var = f_circuit
195 .generate_step_constraints(cs.clone(), 1, z_0_var, vec![])
196 .unwrap();
197 // check z_1_var against the native z_1
198 let z_1_native = f_circuit.step_native(1, z_0.clone(), vec![]).unwrap();
199 assert_eq!(z_1_var.value().unwrap(), z_1_native);
200 // check that the constraint system is satisfied
201 assert!(cs.is_satisfied().unwrap());
202 // ----------------
203
204 let (fs_prover_params, kzg_vk, g16_pk, g16_vk) =
205 init_ivc_and_decider_params::<CircomFCircuit<Fr>>(f_circuit.clone());
206
207 pub type NOVA =
208 Nova<G1, GVar, G2, GVar2, CircomFCircuit<Fr>, KZG<'static, Bn254>, Pedersen<G2>>;
209 pub type DECIDERETH_FCircuit = DeciderEth<
210 G1,
211 GVar,
212 G2,
213 GVar2,
214 CircomFCircuit<Fr>,
215 KZG<'static, Bn254>,
216 Pedersen<G2>,
217 Groth16<Bn254>,
218 NOVA,
219 >;
220
221 // initialize the folding scheme engine, in our case we use Nova
222 let mut nova = NOVA::init(&fs_prover_params, f_circuit.clone(), z_0.clone()).unwrap();
223 // run n steps of the folding iteration
224 for _ in 0..n_steps {
225 let start = Instant::now();
226 nova.prove_step(vec![]).unwrap();
227 println!("Nova::prove_step {}: {:?}", nova.i, start.elapsed());
228 }
229
230 // perform the hash chain natively in rust (which uses a rust Keccak256 library)
231 let mut z_i_native = z_0.clone();
232 for i in 0..n_steps {
233 z_i_native = rust_native_step(i, z_i_native.clone(), vec![]).unwrap();
234 }
235 // check that the value of the last folding state (nova.z_i) computed through folding, is
236 // equal to the natively computed hash using the rust_native_step method
237 assert_eq!(nova.z_i, z_i_native);
238
239 // ----------------
240 // Sanity check
241 // The following lines contain a sanity check that checks the IVC proof (before going into
242 // the zkSNARK proof)
243 let verifier_params = VerifierParams::<G1, G2> {
244 poseidon_config: nova.poseidon_config.clone(),
245 r1cs: nova.clone().r1cs,
246 cf_r1cs: nova.clone().cf_r1cs,
247 };
248 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
249 NOVA::verify(
250 verifier_params,
251 z_0,
252 nova.z_i.clone(),
253 nova.i,
254 running_instance,
255 incoming_instance,
256 cyclefold_instance,
257 )
258 .unwrap();
259 // ----------------
260
261 let rng = rand::rngs::OsRng;
262 let start = Instant::now();
263 let proof = DECIDERETH_FCircuit::prove(
264 (g16_pk, fs_prover_params.cs_params.clone()),
265 rng,
266 nova.clone(),
267 )
268 .unwrap();
269 println!("generated Decider proof: {:?}", start.elapsed());
270
271 let verified = DECIDERETH_FCircuit::verify(
272 (g16_vk.clone(), kzg_vk.clone()),
273 nova.i,
274 nova.z_0.clone(),
275 nova.z_i.clone(),
276 &nova.U_i,
277 &nova.u_i,
278 &proof,
279 )
280 .unwrap();
281 assert!(verified);
282 println!("Decider proof verification: {}", verified);
283
284 // generate the Solidity code that verifies this Decider final proof
285 let function_selector =
286 get_function_selector_for_nova_cyclefold_verifier(nova.z_0.len() * 2 + 1);
287
288 let calldata: Vec<u8> = prepare_calldata(
289 function_selector,
290 nova.i,
291 nova.z_0,
292 nova.z_i,
293 &nova.U_i,
294 &nova.u_i,
295 proof,
296 )
297 .unwrap();
298
299 // prepare the setup params for the solidity verifier
300 let nova_cyclefold_vk =
301 NovaCycleFoldVerifierKey::from((g16_vk, kzg_vk, f_circuit.state_len()));
302
303 // generate the solidity code
304 let decider_solidity_code = get_decider_template_for_cyclefold_decider(nova_cyclefold_vk);
305
306 /*
307 * Note: since we're proving the Keccak256 (ie. 32 byte size, 256 bits), the number of
308 * inputs is too big for the contract. In a real world use case we would convert the binary
309 * representation into a couple of field elements which would be inputs of the Decider
310 * circuit, and in-circuit we would obtain the binary representation to be used for the
311 * final proof check.
312 *
313 * The following code is commented out for that reason.
314 // verify the proof against the solidity code in the EVM
315 use solidity_verifiers::evm::{compile_solidity, Evm};
316 let nova_cyclefold_verifier_bytecode =
317 compile_solidity(&decider_solidity_code, "NovaDecider");
318 let mut evm = Evm::default();
319 let verifier_address = evm.create(nova_cyclefold_verifier_bytecode);
320 let (_, output) = evm.call(verifier_address, calldata.clone());
321 assert_eq!(*output.last().unwrap(), 1);
322 */
323
324 // save smart contract and the calldata
325 println!("storing nova-verifier.sol and the calldata into files");
326 use std::fs;
327 fs::create_dir_all("./solidity").unwrap();
328 fs::write(
329 "./solidity/nova-verifier.sol",
330 decider_solidity_code.clone(),
331 )
332 .unwrap();
333 fs::write("./solidity/solidity-calldata.calldata", calldata.clone()).unwrap();
334 let s = solidity_verifiers::utils::get_formatted_calldata(calldata.clone());
335 fs::write("./solidity/solidity-calldata.inputs", s.join(",\n")).expect("");
336 }
337}