/// N-arity tree of recursion with conditionals. /// /// p_root /// ▲ /// │ /// ┌────────┐ /// │ F │ /// └────────┘ /// ▲ ▲ ▲ ▲ /// ┌─┘ │ │ └─┐ /// ┌────┘ ┌─┘ └┐ └───┐ /// │ │ ... │ │ /// ┌────────┐┌┴┐┌─┐┌┴┐ ┌────────┐ /// │ F ││.││.││.│ │ F │ /// └────────┘└─┘└─┘└─┘ └────────┘ /// ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ /// ┌─┘ │ └┐ └─┐ ┌─┘┌┘ └┐ └┐ /// │ │ │ │ │ │ │ │ /// p_1 p_2 ... p_n p'_1 p'_2... p'_n /// /// /// where each p_i is either /// - signature verification /// - recursive plonky2 proof (proof that verifies previous proof) /// (generated by `RecursiveCircuit::prove_step` method) /// in other words, each p_i is checking: /// `(signature proof OR recursive proof)` /// /// Each node of the recursion tree, ie. each F, verifies the N incoming p_i's, that is /// `(signature proof OR recursive proof) AND ... AND (signature proof OR recursive proof)` /// and produces a new proof. /// /// /// For example, if N is set to N=2, then we work with a binary recursion tree: /// p_root /// ▲ /// │ /// ┌─┴─┐ /// │ F │ /// └───┘ /// ▲ ▲ /// ┌─┘ └─┐ /// ┌───┘ └───┐ /// │p_5 │p_6 /// ┌─┴─┐ ┌─┴─┐ /// │ F │ │ F │ /// └───┘ └───┘ /// ▲ ▲ ▲ ▲ /// ┌─┘ └─┐ ┌─┘ └─┐ /// │ │ │ │ /// p_1 p_2 p_3 p_4 /// /// So that each node (F box) is verifying 2 p_i's, ie: /// `(signature proof OR recursive proof) AND (signature proof OR recursive proof)` /// /// /// With N=3, each node will be verifying 3 p_i's. /// `(signature proof OR recursive proof) AND (signature proof OR recursive proof) AND (signature proof OR recursive proof)` /// /// /// /// Also, notice that if we set N=1, it is directly a linear chain of recursive proofs ('tree' of /// arity 1): /// ┌─┐ ┌─┐ ┌─┐ ┌─┐ /// ─────►│F├────►│F├────►│F├────►│F├────► /// p_1 └─┘ p_2 └─┘ p_3 └─┘ p_4 └─┘ p_5 /// /// where each p_i is proving: `(signature proof OR recursive proof)`. /// /// /// To run the tests that checks this logic: /// cargo test --release test_tree_recursion -- --nocapture use anyhow::{anyhow, Result}; use plonky2::field::types::Field; use plonky2::gates::noop::NoopGate; use plonky2::iop::witness::{PartialWitness, WitnessWrite}; use plonky2::plonk::circuit_builder::CircuitBuilder; use plonky2::plonk::circuit_data::{ CircuitConfig, CircuitData, VerifierCircuitData, VerifierCircuitTarget, }; use plonky2::plonk::proof::{ProofWithPublicInputs, ProofWithPublicInputsTarget}; use std::time::Instant; use sch::schnorr::*; use sch::schnorr_prover::*; use super::{sig_gadget::SignatureGadgetTargets, PlonkyProof, C, D, F}; /// Contains the methods to `build` (ie. create the targets, the logic of the circuit), and /// `fill_targets` (ie. set the specific values to be used for the previously created targets). pub struct RecursiveCircuit { msg_targ: MessageTarget, sigs_targ: Vec, proofs_targ: Vec>, // the next two are common for all the given proofs. It is the data for this circuit itself // (cyclic circuit). verifier_data_targ: VerifierCircuitTarget, verifier_data: VerifierCircuitData, } impl RecursiveCircuit { pub fn prepare_public_inputs( verifier_data: VerifierCircuitData, msg: Vec, ) -> Vec { [ msg.clone(), // add verifier_data as public inputs: verifier_data.verifier_only.circuit_digest.elements.to_vec(), verifier_data .verifier_only .constants_sigmas_cap .0 .iter() .flat_map(|e| e.elements) .collect(), ] .concat() } // notice that this method does not fill the targets, which is done in the method // `fill_recursive_circuit_targets` pub fn build( builder: &mut CircuitBuilder, verifier_data: VerifierCircuitData, msg_len: usize, ) -> Result { let msg_targ = MessageTarget::new_with_size(builder, msg_len); // set msg as public input builder.register_public_inputs(&msg_targ.msg); // build the signature verification logic let mut sigs_targ: Vec = vec![]; for _ in 0..N { let sig_targets = SignatureGadgetTargets::build(builder, &msg_targ)?; sigs_targ.push(sig_targets); } // proof verification: let common_data = verifier_data.common.clone(); let verifier_data_targ = builder.add_verifier_data_public_inputs(); let mut proofs_targ: Vec> = vec![]; for i in 0..N { let proof_targ = builder.add_virtual_proof_with_pis(&common_data); builder.conditionally_verify_cyclic_proof_or_dummy::( sigs_targ[i].selector_booltarg, &proof_targ, &common_data, )?; proofs_targ.push(proof_targ); } Ok(Self { msg_targ, sigs_targ, proofs_targ, verifier_data_targ, verifier_data, }) } pub fn fill_targets( &mut self, pw: &mut PartialWitness, msg: &Vec, selectors: Vec, // 1=proof, 0=sig pks: &Vec, sigs: &Vec, recursive_proofs: &Vec, ) -> Result<()> { // set the msg value (used by all N sig gadgets) self.msg_targ.set_witness(pw, &msg).unwrap(); // set the signature related values for i in 0..N { self.sigs_targ[i].fill_targets(pw, selectors[i], &pks[i], &sigs[i])?; } // set proof related values: // recursive proofs verification pw.set_verifier_data_target(&self.verifier_data_targ, &self.verifier_data.verifier_only)?; let public_inputs = RecursiveCircuit::::prepare_public_inputs(self.verifier_data.clone(), msg.clone()); for i in 0..N { pw.set_proof_with_pis_target( &self.proofs_targ[i], &ProofWithPublicInputs { proof: recursive_proofs[i].clone(), public_inputs: public_inputs.clone(), }, )?; } Ok(()) } } #[derive(Debug, Clone)] pub struct Recursion {} pub fn common_data_for_recursion(msg_len: usize) -> Result> { // 1st let config = CircuitConfig::standard_recursion_config(); let builder = CircuitBuilder::::new(config); let data = builder.build::(); // 2nd let config = CircuitConfig::standard_recursion_config(); let mut builder = CircuitBuilder::::new(config.clone()); let verifier_data = builder.add_virtual_verifier_data(data.common.config.fri_config.cap_height); // proofs for _ in 0..N { let proof = builder.add_virtual_proof_with_pis(&data.common); builder.verify_proof::(&proof, &verifier_data, &data.common); } // let n_gates = builder.num_gates(); let data = builder.build::(); // 3rd let config = CircuitConfig::standard_recursion_config(); let mut builder = CircuitBuilder::::new(config.clone()); let msg_targ = MessageTarget::new_with_size(&mut builder, msg_len); // sigs verify builder.register_public_inputs(&msg_targ.msg); builder.add_gate( // add a ConstantGate, because without this, when later generating the `dummy_circuit` // (inside the `conditionally_verify_cyclic_proof_or_dummy`), it fails due the // `CommonCircuitData` of the generated circuit not matching the given `CommonCircuitData` // to create it. Without this it fails because it misses a ConstantGate. plonky2::gates::constant::ConstantGate::new(config.num_constants), vec![], ); let _ = SignatureGadgetTargets::build(&mut builder, &msg_targ).unwrap(); let _ = SignatureGadgetTargets::build(&mut builder, &msg_targ).unwrap(); // proofs verify let verifier_data = builder.add_verifier_data_public_inputs(); // proofs for _ in 0..N { let proof = builder.add_virtual_proof_with_pis(&data.common); builder.verify_proof::(&proof, &verifier_data, &data.common); } // pad min gates let n_gates = compute_num_gates::()?; while builder.num_gates() < n_gates { builder.add_gate(NoopGate, vec![]); } dbg!(builder.num_gates()); Ok(builder.build::()) } fn compute_num_gates() -> Result { // Note: the following numbers are WIP, obtained by trial-error by running different // configurations in the tests. let n_gates = match N { 1 => 1 << 12, 2 => 1 << 13, 3..=5 => 1 << 14, 6 => 1 << 15, _ => 0, }; if n_gates == 0 { return Err(anyhow!( "arity of N={} not supported yet. Currently supported N from 1 to 6 (both included)", N )); } Ok(n_gates) } impl Recursion { /// returns the full-recursive CircuitData pub fn circuit_data(msg_len: usize) -> Result> { let mut data = common_data_for_recursion::(msg_len)?; // build the actual RecursiveCircuit circuit data let config = CircuitConfig::standard_recursion_config(); let mut builder = CircuitBuilder::new(config); let _ = RecursiveCircuit::::build(&mut builder, data.verifier_data(), msg_len)?; dbg!(builder.num_gates()); data = builder.build::(); Ok(data) } pub fn prove_step( verifier_data: VerifierCircuitData, msg: &Vec, selectors: Vec, // 1=proof, 0=sig pks: &Vec, sigs: &Vec, recursive_proofs: &Vec, ) -> Result { println!("prove_step:"); for i in 0..N { if selectors[i].is_nonzero() { println!(" (selectors[{}]==1), verify {}-th proof", i, i); } else { println!(" (selectors[{}]==0), verify {}-th signature", i, i); } } let config = CircuitConfig::standard_recursion_config(); let mut builder = CircuitBuilder::new(config); // assign the targets let start = Instant::now(); let mut circuit = RecursiveCircuit::::build(&mut builder, verifier_data.clone(), msg.len())?; println!("RecursiveCircuit::build(): {:?}", start.elapsed()); // fill the targets let mut pw = PartialWitness::new(); let start = Instant::now(); circuit.fill_targets(&mut pw, msg, selectors, pks, sigs, recursive_proofs)?; println!("circuit.fill_targets(): {:?}", start.elapsed()); let start = Instant::now(); let data = builder.build::(); println!("builder.build(): {:?}", start.elapsed()); let start = Instant::now(); let new_proof = data.prove(pw)?; println!("generate new_proof: {:?}", start.elapsed()); let start = Instant::now(); data.verify(new_proof.clone())?; println!("verify new_proof: {:?}", start.elapsed()); #[cfg(test)] data.verifier_data().verify(ProofWithPublicInputs { proof: new_proof.proof.clone(), public_inputs: new_proof.public_inputs.clone(), })?; #[cfg(test)] verifier_data.verify(ProofWithPublicInputs { proof: new_proof.proof.clone(), public_inputs: new_proof.public_inputs.clone(), })?; Ok(new_proof.proof) } } #[cfg(test)] mod tests { use anyhow::Result; use hashbrown::HashMap; use plonky2::field::types::Field; use plonky2::plonk::proof::ProofWithPublicInputs; use plonky2::recursion::dummy_circuit::cyclic_base_proof; use rand; use std::time::Instant; use super::*; // this sets the plonky2 internal logs level fn set_log() { let _ = env_logger::builder() .filter_level(log::LevelFilter::Warn) .is_test(true) .try_init(); } /// to run: /// cargo test --release test_tree_recursion -- --nocapture #[test] fn test_tree_recursion() -> Result<()> { // For testing: change the following `N` value to try different arities of the recursion tree: test_tree_recursion_opt::<2>()?; // N=2 test_tree_recursion_opt::<3>()?; // N=3 Ok(()) } fn test_tree_recursion_opt() -> Result<()> { set_log(); println!("\n--------------------------------------------------"); println!("\n--------------------------------------------------"); println!( "\nrunning test:\n test_tree_recursion_opt with N={} (arity)", N ); let l: u32 = 2; // levels of the recursion (binary) tree let k = (N as u32).pow(l) as usize; // number of leafs in the recursion tree, N^l println!( "Testing a {}-arity recursion tree, of {} levels, with {} leaves", N, l, k ); let mut rng: rand::rngs::ThreadRng = rand::thread_rng(); let schnorr = SchnorrSigner::new(); const MSG_LEN: usize = 5; let msg: Vec = schnorr.u64_into_goldilocks_vec(vec![1500, 1600, 2, 2, 2]); assert_eq!(msg.len(), MSG_LEN); // generate k key pairs let sk_vec: Vec = (0..k).map(|i| SchnorrSecretKey { sk: i as u64 }).collect(); let pk_vec: Vec = sk_vec.iter().map(|&sk| schnorr.keygen(&sk)).collect(); let sig_vec: Vec = sk_vec .iter() .map(|&sk| schnorr.sign(&msg, &sk, &mut rng)) .collect(); // build the circuit_data & verifier_data for the recursive circuit let circuit_data = Recursion::::circuit_data(MSG_LEN)?; let verifier_data = circuit_data.verifier_data(); let dummy_proof_pis = cyclic_base_proof( &circuit_data.common, &verifier_data.verifier_only, HashMap::new(), ); let dummy_proof = dummy_proof_pis.proof; // we start with k dummy proofs, since at the leafs level we don't have proofs yet and we // just verify the signatures let mut proofs_at_level_i: Vec = (0..k).into_iter().map(|_| dummy_proof.clone()).collect(); // loop over the recursion levels for i in 0..l { println!("\n=== recursion level i={}", i); let mut next_level_proofs: Vec = vec![]; // loop over the nodes of each recursion tree level for j in (0..proofs_at_level_i.len()).into_iter().step_by(N) { println!( "\n------ recursion node: (level) i={}, (node in level) j={}", i, j ); // - if we're at the first level of the recursion tree: // proof_enabled=false=0, so that the circuit verifies the signature and not the proof. // - else: // proof_enabled=true=1, so that the circuit verifies the proof and not the signature. // // In future tests we will try other cases (eg. some sigs and some proofs in a // node), but for the moment we just do base_case: sig verify, other cases: proof // verify. let proof_enabled = if i == 0 { F::ZERO } else { F::ONE }; // prepare the inputs for the `Recursion::prove_step` call let proofs_selectors = (0..N).into_iter().map(|_| proof_enabled.clone()).collect(); let pks = (0..N) .into_iter() .enumerate() .map(|(k, _)| pk_vec[j + k].clone()) .collect(); let sigs = (0..N) .into_iter() .enumerate() .map(|(k, _)| sig_vec[j + k].clone()) .collect(); let proofs = (0..N) .into_iter() .enumerate() .map(|(k, _)| proofs_at_level_i[j + k].clone()) .collect(); // do the recursive step let start = Instant::now(); let new_proof = Recursion::::prove_step( verifier_data.clone(), &msg, proofs_selectors, &pks, &sigs, &proofs, )?; println!( "Recursion::prove_step (level: i={}, node: j={}) took: {:?}", i, j, start.elapsed() ); // verify the recursive proof let public_inputs = RecursiveCircuit::::prepare_public_inputs( verifier_data.clone(), msg.clone(), ); verifier_data.clone().verify(ProofWithPublicInputs { proof: new_proof.clone(), public_inputs: public_inputs.clone(), })?; // set new_proof for next iteration next_level_proofs.push(new_proof); } proofs_at_level_i = next_level_proofs.clone(); } assert_eq!(proofs_at_level_i.len(), 1); let last_proof = proofs_at_level_i[0].clone(); // verify the last proof let public_inputs = RecursiveCircuit::::prepare_public_inputs(verifier_data.clone(), msg.clone()); verifier_data.clone().verify(ProofWithPublicInputs { proof: last_proof.clone(), public_inputs: public_inputs.clone(), })?; Ok(()) } }