sonobe/examples/external_inputs.rs
examples/external_inputs.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_upper_case_globals)]
3#![allow(non_camel_case_types)]
4#![allow(clippy::upper_case_acronyms)]
5
6use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
7use ark_crypto_primitives::{
8 crh::{
9 poseidon::constraints::{CRHGadget, CRHParametersVar},
10 poseidon::CRH,
11 CRHScheme, CRHSchemeGadget,
12 },
13 sponge::{poseidon::PoseidonConfig, Absorb},
14};
15use ark_ff::PrimeField;
16use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
17use ark_r1cs_std::alloc::AllocVar;
18use ark_r1cs_std::fields::fp::FpVar;
19use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
20use core::marker::PhantomData;
21use std::time::Instant;
22
23use folding_schemes::commitment::{kzg::KZG, pedersen::Pedersen};
24use folding_schemes::folding::nova::{Nova, PreprocessorParam};
25use folding_schemes::frontend::FCircuit;
26use folding_schemes::transcript::poseidon::poseidon_canonical_config;
27use folding_schemes::{Error, FoldingScheme};
28
29/// This is the circuit that we want to fold, it implements the FCircuit trait. The parameter z_i
30/// denotes the current state which contains 1 element, and z_{i+1} denotes the next state which we
31/// get by applying the step.
32///
33/// In this example we set the state to be the previous state together with an external input, and
34/// the new state is an array which contains the new state.
35///
36/// This is useful for example if we want to fold multiple verifications of signatures, where the
37/// circuit F checks the signature and is folded for each of the signatures and public keys. To
38/// keep things simpler, the following example does not verify signatures but does a similar
39/// approach with a chain of hashes, where each iteration hashes the previous step output (z_i)
40/// together with an external input (w_i).
41///
42/// w_1 w_2 w_3 w_4
43/// │ │ │ │
44/// ▼ ▼ ▼ ▼
45/// ┌─┐ ┌─┐ ┌─┐ ┌─┐
46/// ─────►│F├────►│F├────►│F├────►│F├────►
47/// z_1 └─┘ z_2 └─┘ z_3 └─┘ z_4 └─┘ z_5
48///
49///
50/// where each F is:
51/// w_i
52/// │ ┌────────────────────┐
53/// │ │FCircuit │
54/// │ │ │
55/// └────►│ h =Hash(z_i[0],w_i)│
56/// ────────►│ │ ├───────►
57/// z_i │ └──►z_{i+1}=[h] │ z_{i+1}
58/// │ │
59/// └────────────────────┘
60///
61/// where each w_i value is set at the external_inputs array.
62///
63/// The last state z_i is used together with the external input w_i as inputs to compute the new
64/// state z_{i+1}.
65#[derive(Clone, Debug)]
66pub struct ExternalInputsCircuit<F: PrimeField>
67where
68 F: Absorb,
69{
70 _f: PhantomData<F>,
71 poseidon_config: PoseidonConfig<F>,
72}
73impl<F: PrimeField> FCircuit<F> for ExternalInputsCircuit<F>
74where
75 F: Absorb,
76{
77 type Params = PoseidonConfig<F>;
78
79 fn new(params: Self::Params) -> Result<Self, Error> {
80 Ok(Self {
81 _f: PhantomData,
82 poseidon_config: params,
83 })
84 }
85 fn state_len(&self) -> usize {
86 1
87 }
88 fn external_inputs_len(&self) -> usize {
89 1
90 }
91
92 /// computes the next state value for the step of F for the given z_i and external_inputs
93 /// z_{i+1}
94 fn step_native(
95 &self,
96 _i: usize,
97 z_i: Vec<F>,
98 external_inputs: Vec<F>,
99 ) -> Result<Vec<F>, Error> {
100 let hash_input: [F; 2] = [z_i[0], external_inputs[0]];
101 let h = CRH::<F>::evaluate(&self.poseidon_config, hash_input).unwrap();
102 Ok(vec![h])
103 }
104
105 /// generates the constraints and returns the next state value for the step of F for the given
106 /// z_i and external_inputs
107 fn generate_step_constraints(
108 &self,
109 cs: ConstraintSystemRef<F>,
110 _i: usize,
111 z_i: Vec<FpVar<F>>,
112 external_inputs: Vec<FpVar<F>>,
113 ) -> Result<Vec<FpVar<F>>, SynthesisError> {
114 let crh_params =
115 CRHParametersVar::<F>::new_constant(cs.clone(), self.poseidon_config.clone())?;
116 let hash_input: [FpVar<F>; 2] = [z_i[0].clone(), external_inputs[0].clone()];
117 let h = CRHGadget::<F>::evaluate(&crh_params, &hash_input)?;
118 Ok(vec![h])
119 }
120}
121
122/// cargo test --example external_inputs
123#[cfg(test)]
124pub mod tests {
125 use super::*;
126 use ark_r1cs_std::R1CSVar;
127 use ark_relations::r1cs::ConstraintSystem;
128
129 // test to check that the ExternalInputsCircuit computes the same values inside and outside the circuit
130 #[test]
131 fn test_f_circuit() {
132 let poseidon_config = poseidon_canonical_config::<Fr>();
133
134 let cs = ConstraintSystem::<Fr>::new_ref();
135
136 let circuit = ExternalInputsCircuit::<Fr>::new(poseidon_config).unwrap();
137 let z_i = vec![Fr::from(1_u32)];
138 let external_inputs = vec![Fr::from(3_u32)];
139
140 let z_i1 = circuit
141 .step_native(0, z_i.clone(), external_inputs.clone())
142 .unwrap();
143
144 let z_iVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_i)).unwrap();
145 let external_inputsVar =
146 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(external_inputs)).unwrap();
147
148 let computed_z_i1Var = circuit
149 .generate_step_constraints(cs.clone(), 0, z_iVar, external_inputsVar)
150 .unwrap();
151 assert_eq!(computed_z_i1Var.value().unwrap(), z_i1);
152 }
153}
154
155/// cargo run --release --example external_inputs
156fn main() {
157 let num_steps = 5;
158 let initial_state = vec![Fr::from(1_u32)];
159
160 // prepare the external inputs to be used at each folding step
161 let external_inputs = vec![
162 vec![Fr::from(3_u32)],
163 vec![Fr::from(33_u32)],
164 vec![Fr::from(73_u32)],
165 vec![Fr::from(103_u32)],
166 vec![Fr::from(125_u32)],
167 ];
168 assert_eq!(external_inputs.len(), num_steps);
169
170 let poseidon_config = poseidon_canonical_config::<Fr>();
171 let F_circuit = ExternalInputsCircuit::<Fr>::new(poseidon_config.clone()).unwrap();
172
173 /// The idea here is that eventually we could replace the next line chunk that defines the
174 /// `type N = Nova<...>` by using another folding scheme that fulfills the `FoldingScheme`
175 /// trait, and the rest of our code would be working without needing to be updated.
176 type N = Nova<
177 Projective,
178 GVar,
179 Projective2,
180 GVar2,
181 ExternalInputsCircuit<Fr>,
182 KZG<'static, Bn254>,
183 Pedersen<Projective2>,
184 >;
185
186 let mut rng = rand::rngs::OsRng;
187
188 println!("Prepare Nova's ProverParams & VerifierParams");
189 let nova_preprocess_params = PreprocessorParam::new(poseidon_config, F_circuit.clone());
190 let (nova_pp, nova_vp) = N::preprocess(&mut rng, &nova_preprocess_params).unwrap();
191
192 println!("Initialize FoldingScheme");
193 let mut folding_scheme = N::init(&nova_pp, F_circuit, initial_state.clone()).unwrap();
194
195 // compute a step of the IVC
196 for (i, external_inputs_at_step) in external_inputs.iter().enumerate() {
197 let start = Instant::now();
198 folding_scheme
199 .prove_step(rng, external_inputs_at_step.clone())
200 .unwrap();
201 println!("Nova::prove_step {}: {:?}", i, start.elapsed());
202 }
203 println!(
204 "state at last step (after {} iterations): {:?}",
205 num_steps,
206 folding_scheme.state()
207 );
208
209 let (running_instance, incoming_instance, cyclefold_instance) = folding_scheme.instances();
210
211 println!("Run the Nova's IVC verifier");
212 N::verify(
213 nova_vp,
214 initial_state.clone(),
215 folding_scheme.state(), // latest state
216 Fr::from(num_steps as u32),
217 running_instance,
218 incoming_instance,
219 cyclefold_instance,
220 )
221 .unwrap();
222}