plonky2-semaphore/src/ivc.rs
src/ivc.rsRaw
1/// Experimental IVC (Incremental Verifiable Computation) using Plonky2
2///
3/// w_1 w_2 w_3 w_4
4/// │ │ │ │
5/// ▼ ▼ ▼ ▼
6/// ┌─┐ ┌─┐ ┌─┐ ┌─┐
7/// ─────►│F├────►│F├────►│F├────►│F├────►
8/// z_1 └─┘ z_2 └─┘ z_3 └─┘ z_4 └─┘ z_5
9///
10///
11/// where each F is:
12/// w_i
13/// │ ┌───────────────────────────────┐
14/// │ │ │
15/// │ │ verify previous plonky2 proof │
16/// └────►│ + │
17/// ────────►│ verify current semaphore proof├───────►
18/// z_i │ │ z_{i+1}
19/// │ │
20/// └───────────────────────────────┘
21///
22/// where each w_i value are the values of the new instance being verified at the step i.
23///
24/// The last state z_i is used together with the external input w_i as inputs to compute the new
25/// state z_{i+1}.
26///
27/// To run the test that checks this logic:
28/// cargo test --release test_ivc -- --nocapture
29///
30use anyhow::Result;
31use plonky2::field::types::Field;
32use plonky2::hash::poseidon::PoseidonHash;
33use plonky2::iop::target::Target;
34use plonky2::iop::witness::{PartialWitness, WitnessWrite};
35use plonky2::plonk::circuit_builder::CircuitBuilder;
36use plonky2::plonk::circuit_data::{CircuitConfig, VerifierCircuitData};
37use plonky2::plonk::config::Hasher;
38use plonky2::plonk::proof::ProofWithPublicInputs;
39use std::time::Instant;
40
41use crate::access_set::AccessSet;
42use crate::signal::{Digest, PlonkyProof, C, F};
43
44#[derive(Debug, Clone)]
45pub struct IVC {
46 // current step of the recursion
47 i: u64,
48 // previous IVC proof values
49 prev_nullifiers: Vec<Digest>,
50 prev_topics: Vec<Digest>,
51 // previous IVC proof
52 prev_ivc_proof: Option<PlonkyProof>,
53 // verifier data for the prev_ivc_proof
54 verifier_data: Option<VerifierCircuitData<F, C, 2>>,
55}
56
57impl IVC {
58 pub fn new() -> Self {
59 Self {
60 i: 0_u64,
61 prev_nullifiers: vec![],
62 prev_topics: vec![],
63 prev_ivc_proof: None,
64 verifier_data: None,
65 }
66 }
67
68 // `public_inputs` returns
69 // [
70 // 0, merkle_root, nullifier[0], topic[0],
71 // 1, merkle_root, nullifier[1], topic[1],
72 // 2, merkle_root, nullifier[2], topic[2],
73 // ...
74 // ].rev()
75 pub fn public_inputs(&self, merkle_root: Vec<F>) -> Vec<F> {
76 self.prev_nullifiers
77 .iter()
78 .enumerate()
79 .rev()
80 .zip(self.prev_topics.iter().rev())
81 .flat_map(|((i, n), t)| {
82 vec![
83 vec![F::from_canonical_u64((i + 1) as u64)],
84 merkle_root.clone(),
85 n.to_vec(),
86 t.to_vec(),
87 ]
88 .concat()
89 })
90 .collect()
91 }
92
93 pub fn prove_step(
94 &mut self,
95 // merkle proof membership values
96 access_set: &AccessSet,
97 private_key: Digest,
98 public_key_index: usize,
99 topic: Digest,
100 ) -> Result<()> {
101 let config = CircuitConfig::standard_recursion_zk_config();
102 let mut builder = CircuitBuilder::new(config);
103 let mut pw = PartialWitness::new();
104
105 // ivc_i, as public input
106 let i1_F = F::from_canonical_u64(self.i + 1); // next i
107 let i_target: Target = builder.add_virtual_target();
108 builder.register_public_input(i_target);
109 pw.set_target(i_target, i1_F)?;
110
111 let nullifier = PoseidonHash::hash_no_pad(&[private_key, topic].concat()).elements;
112 // semaphore gadget. Notice that internally it registers public inputs:
113 // merkle_root, nullifier, topic
114 let semaphore_targets = access_set.semaphore_circuit(&mut builder);
115 access_set.fill_semaphore_targets(
116 &mut pw,
117 private_key,
118 topic,
119 public_key_index,
120 semaphore_targets,
121 )?;
122
123 // verify the previous IVC proof in-circuit when we're not at the first iteration
124 if self.i != 0 {
125 let verifier_data = self.verifier_data.clone().unwrap();
126
127 let merkle_root: Vec<F> = access_set.0.cap.0.iter().flat_map(|h| h.elements).collect();
128 let public_inputs = self.public_inputs(merkle_root);
129
130 // verify the proof natively in rust before doing the in-circuit verification
131 #[cfg(test)]
132 verifier_data.clone().verify(ProofWithPublicInputs {
133 proof: self.prev_ivc_proof.clone().unwrap(),
134 public_inputs: public_inputs.clone(),
135 })?;
136
137 // ivc proof verification gadget
138 let proof_target = builder.add_virtual_proof_with_pis(&verifier_data.common);
139 builder.register_public_inputs(&proof_target.public_inputs);
140 pw.set_proof_with_pis_target(
141 &proof_target,
142 &ProofWithPublicInputs {
143 proof: self.prev_ivc_proof.clone().unwrap(),
144 public_inputs,
145 },
146 )?;
147 let vd_target = builder
148 .add_virtual_verifier_data(verifier_data.common.config.fri_config.cap_height);
149 pw.set_verifier_data_target(&vd_target, &verifier_data.verifier_only)?;
150
151 pw.set_cap_target(
152 &vd_target.constants_sigmas_cap,
153 &verifier_data.verifier_only.constants_sigmas_cap,
154 )?;
155
156 builder.verify_proof::<C>(&proof_target, &vd_target, &verifier_data.common);
157 dbg!("in-circuit prev_ivc_proof verification added");
158 }
159
160 dbg!(builder.num_public_inputs());
161
162 // Build the actual proof, notice that:
163 // - if i==0: prove only the semaphore data
164 // - if i>0: prove the semaphore data + the verification of the previous IVC proof
165 let start = Instant::now();
166 let data = builder.build::<C>();
167 println!("builder.build(): {:?}", start.elapsed());
168 let start = Instant::now();
169 let new_ivc_proof = data.prove(pw)?;
170 println!("generate new_ivc_proof: {:?}", start.elapsed());
171
172 let start = Instant::now();
173 data.verify(new_ivc_proof.clone())?;
174 println!("verify new_ivc_proof: {:?}", start.elapsed());
175
176 #[cfg(test)]
177 data.verifier_data().verify(ProofWithPublicInputs {
178 proof: new_ivc_proof.proof.clone(),
179 public_inputs: new_ivc_proof.public_inputs.clone(),
180 })?;
181
182 self.prev_nullifiers.push(nullifier);
183 self.prev_topics.push(topic);
184 self.prev_ivc_proof = Some(new_ivc_proof.proof);
185 // store the verifier data of the generated plonky2 proof, which will be used for the
186 // last proof verification
187 self.verifier_data = Some(data.verifier_data());
188
189 #[cfg(test)]
190 if self.i > 0 {
191 let merkle_root: Vec<F> = access_set.0.cap.0.iter().flat_map(|h| h.elements).collect();
192 let public_inputs = self.public_inputs(merkle_root);
193 data.verifier_data().verify(ProofWithPublicInputs {
194 proof: self.prev_ivc_proof.clone().unwrap(),
195 public_inputs: public_inputs.clone(),
196 })?;
197 }
198
199 self.i += 1;
200
201 Ok(())
202 }
203}
204
205#[cfg(test)]
206mod tests {
207 use anyhow::Result;
208 use plonky2::field::types::{Field, Sample};
209 use plonky2::hash::merkle_tree::MerkleTree;
210 use plonky2::hash::poseidon::PoseidonHash;
211 use plonky2::plonk::config::Hasher;
212 use plonky2::plonk::proof::ProofWithPublicInputs;
213 use std::time::Instant;
214
215 use crate::access_set::AccessSet;
216 use crate::ivc::IVC;
217 use crate::signal::{Digest, F};
218
219 /// to run:
220 /// cargo test --release test_ivc -- --nocapture
221 #[test]
222 fn test_ivc() -> Result<()> {
223 let n = 1 << 20;
224 let private_keys: Vec<Digest> = (0..n).map(|_| F::rand_array()).collect();
225 let public_keys: Vec<Vec<F>> = private_keys
226 .iter()
227 .map(|&sk| {
228 PoseidonHash::hash_no_pad(&[sk, [F::ZERO; 4]].concat())
229 .elements
230 .to_vec()
231 })
232 .collect();
233 let access_set = AccessSet(MerkleTree::new(public_keys, 0));
234 let merkle_root: Vec<F> = access_set.0.cap.0.iter().flat_map(|h| h.elements).collect();
235 let topic0 = F::rand_array();
236
237 let mut ivc = IVC::new();
238 dbg!(&ivc.i);
239 dbg!(&ivc);
240
241 // 1st recursive step
242 println!("\n----- ivc.prove_step i=0");
243 let key_index = 42;
244 ivc.prove_step(&access_set, private_keys[key_index], key_index, topic0)?;
245 // verify the proof at i=0 (now ivc.i=1, but the proof is for ivc.i=0)
246 let i_F = F::from_canonical_u64(ivc.i);
247 dbg!(&i_F);
248 let public_inputs: Vec<F> = vec![i_F]
249 .into_iter()
250 .chain(access_set.0.cap.0.iter().flat_map(|h| h.elements)) // merkle_root
251 .chain(ivc.prev_nullifiers[0])
252 .chain(ivc.prev_topics[0])
253 .collect();
254 dbg!(&public_inputs);
255 ivc.verifier_data
256 .clone()
257 .unwrap()
258 .verify(ProofWithPublicInputs {
259 proof: ivc.prev_ivc_proof.clone().unwrap(),
260 public_inputs,
261 })?;
262
263 // 2nd recursive step
264 println!("\n----- ivc.prove_step i=1");
265 let key_index = 24;
266 ivc.prove_step(&access_set, private_keys[key_index], key_index, topic0)?;
267 dbg!(&ivc.i);
268 let prev_i_F = F::from_canonical_u64(ivc.i - 1);
269 let i_F = F::from_canonical_u64(ivc.i);
270 // notice, here public_inputs will contain
271 // - the current step values that are verified in the current circuit
272 // - the previous step values in order to verify the previous plonky2 proof in-circuit
273 let public_inputs: Vec<F> = vec![i_F]
274 .into_iter()
275 .chain(access_set.0.cap.0.iter().flat_map(|h| h.elements)) // merkle_root
276 .chain(ivc.prev_nullifiers[1])
277 .chain(ivc.prev_topics[1])
278 .chain(vec![prev_i_F])
279 .chain(access_set.0.cap.0.iter().flat_map(|h| h.elements)) // merkle_root
280 .chain(ivc.prev_nullifiers[0])
281 .chain(ivc.prev_topics[0])
282 .collect();
283 dbg!(&public_inputs);
284 ivc.verifier_data
285 .clone()
286 .unwrap()
287 .verify(ProofWithPublicInputs {
288 proof: ivc.prev_ivc_proof.clone().unwrap(),
289 public_inputs,
290 })?;
291
292 // 3rd step
293 println!("\n----- ivc.prove_step i=2");
294 let key_index = 25;
295 ivc.prove_step(&access_set, private_keys[key_index], key_index, topic0)?;
296 dbg!(&ivc.i);
297 let public_inputs = ivc.public_inputs(merkle_root.clone());
298 dbg!(&public_inputs);
299 ivc.verifier_data
300 .clone()
301 .unwrap()
302 .verify(ProofWithPublicInputs {
303 proof: ivc.prev_ivc_proof.clone().unwrap(),
304 public_inputs,
305 })?;
306
307 for i in 0..10 {
308 println!("\n----- ivc.prove_step i={}", 3 + i);
309 let key_index = i;
310 let start = Instant::now();
311 ivc.prove_step(&access_set, private_keys[key_index], key_index, topic0)?;
312 println!("prove_step (i={}) took: {:?}", 3 + i, start.elapsed());
313 let public_inputs = ivc.public_inputs(merkle_root.clone());
314 dbg!(&public_inputs);
315 ivc.verifier_data
316 .clone()
317 .unwrap()
318 .verify(ProofWithPublicInputs {
319 proof: ivc.prev_ivc_proof.clone().unwrap(),
320 public_inputs,
321 })?;
322 // TODO: print (bytes length) proof size, verifier_data size, public inputs size
323 }
324
325 Ok(())
326 }
327}