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 the initial state
168 let z_0_aux: Vec<u32> = vec![0_u32; 32 * 8];
169 let z_0: Vec<Fr> = z_0_aux.iter().map(|v| Fr::from(*v)).collect::<Vec<Fr>>();
170
171 // initialize the Circom circuit
172 let r1cs_path = PathBuf::from("./circuit/keccak-chain.r1cs");
173 let wasm_path = PathBuf::from("./circuit/keccak-chain_js/keccak-chain.wasm");
174
175 let f_circuit_params = (r1cs_path, wasm_path, 32 * 8, 0);
176 let mut f_circuit = CircomFCircuit::<Fr>::new(f_circuit_params).unwrap();
177 // Note (optional): for more speed, we can set a custom rust-native logic, which will be
178 // used for the `step_native` method instead of extracting the values from the circom
179 // witness:
180 f_circuit.set_custom_step_native(Rc::new(rust_native_step));
181
182 // ----------------
183 // Sanity check
184 // check that the f_circuit produces valid R1CS constraints
185 use ark_r1cs_std::alloc::AllocVar;
186 use ark_r1cs_std::fields::fp::FpVar;
187 use ark_r1cs_std::R1CSVar;
188 use ark_relations::r1cs::ConstraintSystem;
189 let cs = ConstraintSystem::<Fr>::new_ref();
190 let z_0_var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_0.clone())).unwrap();
191 let z_1_var = f_circuit
192 .generate_step_constraints(cs.clone(), 1, z_0_var, vec![])
193 .unwrap();
194 // check z_1_var against the native z_1
195 let z_1_native = f_circuit.step_native(1, z_0.clone(), vec![]).unwrap();
196 assert_eq!(z_1_var.value().unwrap(), z_1_native);
197 // check that the constraint system is satisfied
198 assert!(cs.is_satisfied().unwrap());
199 // ----------------
200
201 let (fs_prover_params, kzg_vk, g16_pk, g16_vk) =
202 init_ivc_and_decider_params::<CircomFCircuit<Fr>>(f_circuit.clone());
203
204 pub type NOVA =
205 Nova<G1, GVar, G2, GVar2, CircomFCircuit<Fr>, KZG<'static, Bn254>, Pedersen<G2>>;
206 pub type DECIDERETH_FCircuit = DeciderEth<
207 G1,
208 GVar,
209 G2,
210 GVar2,
211 CircomFCircuit<Fr>,
212 KZG<'static, Bn254>,
213 Pedersen<G2>,
214 Groth16<Bn254>,
215 NOVA,
216 >;
217
218 // initialize the folding scheme engine, in our case we use Nova
219 let mut nova = NOVA::init(&fs_prover_params, f_circuit.clone(), z_0.clone()).unwrap();
220 // run n steps of the folding iteration
221 for _ in 0..3 {
222 let start = Instant::now();
223 nova.prove_step(vec![]).unwrap();
224 println!("Nova::prove_step {}: {:?}", nova.i, start.elapsed());
225 }
226
227 // perform the hash chain natively in rust (which uses a rust Keccak256 library)
228 let z_1 = rust_native_step(0, z_0.clone(), vec![]).unwrap();
229 let z_2 = rust_native_step(0, z_1, vec![]).unwrap();
230 let z_3 = rust_native_step(0, z_2, vec![]).unwrap();
231 // check that the value of the last folding state (nova.z_i) computed through folding, is
232 // equal to the natively computed hash using the rust_native_step method
233 assert_eq!(nova.z_i, z_3);
234
235 // ----------------
236 // Sanity check
237 // The following lines contain a sanity check that checks the IVC proof (before going into
238 // the zkSNARK proof)
239 let verifier_params = VerifierParams::<G1, G2> {
240 poseidon_config: nova.poseidon_config.clone(),
241 r1cs: nova.clone().r1cs,
242 cf_r1cs: nova.clone().cf_r1cs,
243 };
244 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
245 NOVA::verify(
246 verifier_params,
247 z_0,
248 nova.z_i.clone(),
249 nova.i,
250 running_instance,
251 incoming_instance,
252 cyclefold_instance,
253 )
254 .unwrap();
255 // ----------------
256
257 let rng = rand::rngs::OsRng;
258 let start = Instant::now();
259 let proof = DECIDERETH_FCircuit::prove(
260 (g16_pk, fs_prover_params.cs_params.clone()),
261 rng,
262 nova.clone(),
263 )
264 .unwrap();
265 println!("generated Decider proof: {:?}", start.elapsed());
266
267 let verified = DECIDERETH_FCircuit::verify(
268 (g16_vk.clone(), kzg_vk.clone()),
269 nova.i,
270 nova.z_0.clone(),
271 nova.z_i.clone(),
272 &nova.U_i,
273 &nova.u_i,
274 &proof,
275 )
276 .unwrap();
277 assert!(verified);
278 println!("Decider proof verification: {}", verified);
279
280 // generate the Solidity code that verifies this Decider final proof
281 let function_selector =
282 get_function_selector_for_nova_cyclefold_verifier(nova.z_0.len() * 2 + 1);
283
284 let calldata: Vec<u8> = prepare_calldata(
285 function_selector,
286 nova.i,
287 nova.z_0,
288 nova.z_i,
289 &nova.U_i,
290 &nova.u_i,
291 proof,
292 )
293 .unwrap();
294
295 // prepare the setup params for the solidity verifier
296 let nova_cyclefold_vk =
297 NovaCycleFoldVerifierKey::from((g16_vk, kzg_vk, f_circuit.state_len()));
298
299 // generate the solidity code
300 let decider_solidity_code = get_decider_template_for_cyclefold_decider(nova_cyclefold_vk);
301
302 /*
303 * Note: since we're proving the Keccak256 (ie. 32 byte size, 256 bits), the number of
304 * inputs is too big for the contract. In a real world use case we would convert the binary
305 * representation into a couple of field elements which would be inputs of the Decider
306 * circuit, and in-circuit we would obtain the binary representation to be used for the
307 * final proof check.
308 *
309 * The following code is commented out for that reason.
310 // verify the proof against the solidity code in the EVM
311 use solidity_verifiers::evm::{compile_solidity, Evm};
312 let nova_cyclefold_verifier_bytecode =
313 compile_solidity(&decider_solidity_code, "NovaDecider");
314 let mut evm = Evm::default();
315 let verifier_address = evm.create(nova_cyclefold_verifier_bytecode);
316 let (_, output) = evm.call(verifier_address, calldata.clone());
317 assert_eq!(*output.last().unwrap(), 1);
318 */
319
320 // save smart contract and the calldata
321 println!("storing nova-verifier.sol and the calldata into files");
322 use std::fs;
323 fs::create_dir_all("./solidity").unwrap();
324 fs::write(
325 "./solidity/nova-verifier.sol",
326 decider_solidity_code.clone(),
327 )
328 .unwrap();
329 fs::write("./solidity/solidity-calldata.calldata", calldata.clone()).unwrap();
330 let s = solidity_verifiers::utils::get_formatted_calldata(calldata.clone());
331 fs::write("./solidity/solidity-calldata.inputs", s.join(",\n")).expect("");
332 }
333}