Skip to main content

jf_plonk/proof_system/
batch_arg.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! An argument system that proves/verifies multiple instances in a batch.
8use crate::{
9    errors::{PlonkError, SnarkError::ParameterError},
10    proof_system::{
11        structs::{BatchProof, OpenKey, ProvingKey, ScalarsAndBases, UniversalSrs, VerifyingKey},
12        verifier::Verifier,
13        PlonkKzgSnark, UniversalSNARK,
14    },
15    transcript::PlonkTranscript,
16};
17use ark_ec::{
18    pairing::Pairing,
19    short_weierstrass::{Affine, SWCurveConfig},
20};
21use ark_ff::One;
22use ark_std::{
23    format,
24    marker::PhantomData,
25    rand::{CryptoRng, RngCore},
26    string::ToString,
27    vec,
28    vec::Vec,
29};
30use jf_relation::{gadgets::ecc::SWToTEConParam, Circuit, MergeableCircuitType, PlonkCircuit};
31use jf_rescue::RescueParameter;
32use jf_utils::multi_pairing;
33
34/// A batching argument.
35pub struct BatchArgument<E: Pairing>(PhantomData<E>);
36
37/// A circuit instance that consists of the corresponding proving
38/// key/verification key/circuit.
39#[derive(Clone)]
40pub struct Instance<E: Pairing> {
41    // TODO: considering giving instance an ID
42    prove_key: ProvingKey<E>, // the verification key can be obtained inside the proving key.
43    circuit: PlonkCircuit<E::ScalarField>,
44    _circuit_type: MergeableCircuitType,
45}
46
47impl<E: Pairing> Instance<E> {
48    /// Get verification key by reference.
49    pub fn verify_key_ref(&self) -> &VerifyingKey<E> {
50        &self.prove_key.vk
51    }
52
53    /// Get mutable circuit by reference.
54    pub fn circuit_mut_ref(&mut self) -> &mut PlonkCircuit<E::ScalarField> {
55        &mut self.circuit
56    }
57}
58
59impl<E, F, P> BatchArgument<E>
60where
61    E: Pairing<BaseField = F, G1Affine = Affine<P>>,
62    F: RescueParameter + SWToTEConParam,
63    P: SWCurveConfig<BaseField = F>,
64{
65    /// Setup the circuit and the proving key for a (mergeable) instance.
66    pub fn setup_instance(
67        srs: &UniversalSrs<E>,
68        mut circuit: PlonkCircuit<E::ScalarField>,
69        circuit_type: MergeableCircuitType,
70    ) -> Result<Instance<E>, PlonkError> {
71        circuit.finalize_for_mergeable_circuit(circuit_type)?;
72        let (prove_key, _) = PlonkKzgSnark::preprocess(srs, &circuit)?;
73        Ok(Instance {
74            prove_key,
75            circuit,
76            _circuit_type: circuit_type,
77        })
78    }
79
80    /// Prove satisfiability of multiple instances in a batch.
81    pub fn batch_prove<R, T>(
82        prng: &mut R,
83        instances_type_a: &[Instance<E>],
84        instances_type_b: &[Instance<E>],
85    ) -> Result<BatchProof<E>, PlonkError>
86    where
87        R: CryptoRng + RngCore,
88        T: PlonkTranscript<F>,
89    {
90        if instances_type_a.len() != instances_type_b.len() {
91            return Err(ParameterError(format!(
92                "the number of type A instances {} is different from the number of type B instances {}.", 
93                instances_type_a.len(),
94                instances_type_b.len())
95            ).into());
96        }
97        let pks = instances_type_a
98            .iter()
99            .zip(instances_type_b.iter())
100            .map(|(pred_a, pred_b)| pred_a.prove_key.merge(&pred_b.prove_key))
101            .collect::<Result<Vec<_>, _>>()?;
102
103        let circuits = instances_type_a
104            .iter()
105            .zip(instances_type_b.iter())
106            .map(|(pred_a, pred_b)| pred_a.circuit.merge(&pred_b.circuit))
107            .collect::<Result<Vec<_>, _>>()?;
108        let pks_ref: Vec<&ProvingKey<E>> = pks.iter().collect();
109        let circuits_ref: Vec<&PlonkCircuit<E::ScalarField>> = circuits.iter().collect();
110
111        PlonkKzgSnark::batch_prove::<_, _, T>(prng, &circuits_ref, &pks_ref)
112    }
113
114    /// Partially verify a batched proof without performing the pairing. Return
115    /// the two group elements used in the final pairing.
116    pub fn partial_verify<T>(
117        beta_g: &E::G1Affine,
118        generator_g: &E::G1Affine,
119        merged_vks: &[VerifyingKey<E>],
120        shared_public_input: &[E::ScalarField],
121        batch_proof: &BatchProof<E>,
122        blinding_factor: E::ScalarField,
123    ) -> Result<(E::G1, E::G1), PlonkError>
124    where
125        T: PlonkTranscript<F>,
126    {
127        if merged_vks.is_empty() {
128            return Err(ParameterError("empty merged verification keys".to_string()).into());
129        }
130        if merged_vks.len() != batch_proof.len() {
131            return Err(ParameterError(format!(
132                "the number of verification keys {} is different from the number of instances {}.",
133                merged_vks.len(),
134                batch_proof.len()
135            ))
136            .into());
137        }
138        let domain_size = merged_vks[0].domain_size;
139        for (i, vk) in merged_vks.iter().skip(1).enumerate() {
140            if vk.domain_size != domain_size {
141                return Err(ParameterError(format!(
142                    "the {}-th verification key's domain size {} is different from {}.",
143                    i, vk.domain_size, domain_size
144                ))
145                .into());
146            }
147        }
148        let verifier = Verifier::new(domain_size)?;
149        // we need to copy the public input once after merging the circuit
150        let shared_public_input = [shared_public_input, shared_public_input].concat();
151        let public_inputs = vec![&shared_public_input[..]; merged_vks.len()];
152        let merged_vks_ref: Vec<&VerifyingKey<E>> = merged_vks.iter().collect();
153        let pcs_info =
154            verifier.prepare_pcs_info::<T>(&merged_vks_ref, &public_inputs, batch_proof, &None)?;
155
156        // inner1 = [open_proof] + u * [shifted_open_proof] + blinding_factor *
157        // [1]1
158        let mut scalars_and_bases = ScalarsAndBases::<E>::new();
159        scalars_and_bases.push(E::ScalarField::one(), pcs_info.opening_proof.0);
160        scalars_and_bases.push(pcs_info.u, pcs_info.shifted_opening_proof.0);
161        scalars_and_bases.push(blinding_factor, *generator_g);
162        let inner1 = scalars_and_bases.multi_scalar_mul();
163
164        // inner2 = eval_point * [open_proof] + next_eval_point * u *
165        // [shifted_open_proof] + [aggregated_comm] - aggregated_eval * [1]1 +
166        // blinding_factor * [beta]1
167        let mut scalars_and_bases = pcs_info.comm_scalars_and_bases;
168        scalars_and_bases.push(pcs_info.eval_point, pcs_info.opening_proof.0);
169        scalars_and_bases.push(
170            pcs_info.next_eval_point * pcs_info.u,
171            pcs_info.shifted_opening_proof.0,
172        );
173        scalars_and_bases.push(-pcs_info.eval, *generator_g);
174        scalars_and_bases.push(blinding_factor, *beta_g);
175        let inner2 = scalars_and_bases.multi_scalar_mul();
176
177        Ok((inner1, inner2))
178    }
179}
180
181impl<E> BatchArgument<E>
182where
183    E: Pairing,
184{
185    /// Aggregate verification keys
186    pub fn aggregate_verify_keys(
187        vks_type_a: &[&VerifyingKey<E>],
188        vks_type_b: &[&VerifyingKey<E>],
189    ) -> Result<Vec<VerifyingKey<E>>, PlonkError> {
190        if vks_type_a.len() != vks_type_b.len() {
191            return Err(ParameterError(format!(
192                "the number of type A verification keys {} is different from the number of type B verification keys {}.", 
193                vks_type_a.len(),
194                vks_type_b.len())
195            ).into());
196        }
197        vks_type_a
198            .iter()
199            .zip(vks_type_b.iter())
200            .map(|(vk_a, vk_b)| vk_a.merge(vk_b))
201            .collect::<Result<Vec<_>, PlonkError>>()
202    }
203
204    /// Perform the final pairing to verify the proof.
205    pub fn decide(open_key: &OpenKey<E>, inner1: E::G1, inner2: E::G1) -> Result<bool, PlonkError> {
206        // check e(elem1, [beta]2) ?= e(elem2, [1]2)
207        let g1_elems: Vec<<E as Pairing>::G1Affine> = vec![inner1.into(), (-inner2).into()];
208        let g2_elems = vec![open_key.beta_h, open_key.h];
209        Ok(multi_pairing::<E>(&g1_elems, &g2_elems).0 == E::TargetField::one())
210    }
211}
212
213pub(crate) fn new_mergeable_circuit_for_test<E: Pairing>(
214    shared_public_input: E::ScalarField,
215    i: usize,
216    circuit_type: MergeableCircuitType,
217) -> Result<PlonkCircuit<E::ScalarField>, PlonkError> {
218    let mut circuit = PlonkCircuit::new_turbo_plonk();
219    let shared_pub_var = circuit.create_public_variable(shared_public_input)?;
220    let mut var = shared_pub_var;
221    if circuit_type == MergeableCircuitType::TypeA {
222        // compute type A instances: add `shared_public_input` by i times
223        for _ in 0..i {
224            var = circuit.add(var, shared_pub_var)?;
225        }
226    } else {
227        // compute type B instances: mul `shared_public_input` by i times
228        for _ in 0..i {
229            var = circuit.mul(var, shared_pub_var)?;
230        }
231    }
232    Ok(circuit)
233}
234
235/// Create `num_instances` type A/B instance verifying keys and
236/// compute the corresponding batch proof. Only used for testing.
237#[allow(clippy::type_complexity)]
238pub fn build_batch_proof_and_vks_for_test<E, F, P, R, T>(
239    rng: &mut R,
240    srs: &UniversalSrs<E>,
241    num_instances: usize,
242    shared_public_input: E::ScalarField,
243) -> Result<(BatchProof<E>, Vec<VerifyingKey<E>>, Vec<VerifyingKey<E>>), PlonkError>
244where
245    E: Pairing<BaseField = F, G1Affine = Affine<P>>,
246    F: RescueParameter + SWToTEConParam,
247    P: SWCurveConfig<BaseField = F>,
248    R: CryptoRng + RngCore,
249    T: PlonkTranscript<F>,
250{
251    let mut instances_type_a = vec![];
252    let mut instances_type_b = vec![];
253    let mut vks_type_a = vec![];
254    let mut vks_type_b = vec![];
255    for i in 10..10 + num_instances {
256        let circuit = new_mergeable_circuit_for_test::<E>(
257            shared_public_input,
258            i,
259            MergeableCircuitType::TypeA,
260        )?;
261        let instance = BatchArgument::setup_instance(srs, circuit, MergeableCircuitType::TypeA)?;
262        vks_type_a.push(instance.verify_key_ref().clone());
263        instances_type_a.push(instance);
264
265        let circuit = new_mergeable_circuit_for_test::<E>(
266            shared_public_input,
267            i,
268            MergeableCircuitType::TypeB,
269        )?;
270        let instance = BatchArgument::setup_instance(srs, circuit, MergeableCircuitType::TypeB)?;
271        vks_type_b.push(instance.verify_key_ref().clone());
272        instances_type_b.push(instance);
273    }
274
275    let batch_proof =
276        BatchArgument::batch_prove::<_, T>(rng, &instances_type_a, &instances_type_b)?;
277    Ok((batch_proof, vks_type_a, vks_type_b))
278}
279
280#[cfg(test)]
281mod test {
282    use super::*;
283    use crate::transcript::RescueTranscript;
284    use ark_bls12_377::{Bls12_377, Fq as Fq377};
285    use ark_std::UniformRand;
286    use jf_utils::test_rng;
287
288    #[test]
289    fn test_batch_argument() -> Result<(), PlonkError> {
290        test_batch_argument_helper::<Bls12_377, Fq377, _, RescueTranscript<_>>()
291    }
292
293    fn test_batch_argument_helper<E, F, P, T>() -> Result<(), PlonkError>
294    where
295        E: Pairing<BaseField = F, G1Affine = Affine<P>>,
296        F: RescueParameter + SWToTEConParam,
297        P: SWCurveConfig<BaseField = F>,
298        T: PlonkTranscript<F>,
299    {
300        // 1. Simulate universal setup
301        let rng = &mut test_rng();
302        let n = 128;
303        let max_degree = n + 2;
304        let srs = PlonkKzgSnark::<E>::universal_setup_for_testing(max_degree, rng)?;
305
306        // 2. Setup instances
307        let shared_public_input = E::ScalarField::rand(rng);
308        let mut instances_type_a = vec![];
309        let mut instances_type_b = vec![];
310        for i in 32..50 {
311            let circuit = new_mergeable_circuit_for_test::<E>(
312                shared_public_input,
313                i,
314                MergeableCircuitType::TypeA,
315            )?;
316            let instance =
317                BatchArgument::setup_instance(&srs, circuit, MergeableCircuitType::TypeA)?;
318            instances_type_a.push(instance);
319
320            let circuit = new_mergeable_circuit_for_test::<E>(
321                shared_public_input,
322                i,
323                MergeableCircuitType::TypeB,
324            )?;
325            let instance =
326                BatchArgument::setup_instance(&srs, circuit, MergeableCircuitType::TypeB)?;
327            instances_type_b.push(instance);
328        }
329
330        // 3. Batch Proving
331        let batch_proof =
332            BatchArgument::batch_prove::<_, T>(rng, &instances_type_a, &instances_type_b)?;
333        // error path: inconsistent length between instances_type_a and
334        // instances_type_b
335        assert!(
336            BatchArgument::batch_prove::<_, T>(rng, &instances_type_a[1..], &instances_type_b)
337                .is_err()
338        );
339
340        // 4. Aggregate verification keys
341        let vks_type_a: Vec<&VerifyingKey<E>> = instances_type_a
342            .iter()
343            .map(|pred| pred.verify_key_ref())
344            .collect();
345        let vks_type_b: Vec<&VerifyingKey<E>> = instances_type_b
346            .iter()
347            .map(|pred| pred.verify_key_ref())
348            .collect();
349        let merged_vks = BatchArgument::aggregate_verify_keys(&vks_type_a, &vks_type_b)?;
350        // error path: inconsistent length between vks_type_a and vks_type_b
351        assert!(BatchArgument::aggregate_verify_keys(&vks_type_a[1..], &vks_type_b).is_err());
352
353        // 5. Verification
354        let open_key_ref = &vks_type_a[0].open_key;
355        let beta_g_ref = &srs.powers_of_g[1];
356        let blinding_factor = E::ScalarField::rand(rng);
357        let (inner1, inner2) = BatchArgument::partial_verify::<T>(
358            beta_g_ref,
359            &open_key_ref.g,
360            &merged_vks,
361            &[shared_public_input],
362            &batch_proof,
363            blinding_factor,
364        )?;
365        assert!(BatchArgument::decide(open_key_ref, inner1, inner2)?);
366        // error paths
367        // empty merged_vks
368        assert!(BatchArgument::partial_verify::<T>(
369            beta_g_ref,
370            &open_key_ref.g,
371            &[],
372            &[shared_public_input],
373            &batch_proof,
374            blinding_factor
375        )
376        .is_err());
377        // the number of vks is different the number of instances
378        assert!(BatchArgument::partial_verify::<T>(
379            beta_g_ref,
380            &open_key_ref.g,
381            &merged_vks[1..],
382            &[shared_public_input],
383            &batch_proof,
384            blinding_factor
385        )
386        .is_err());
387        // inconsistent domain size between verification keys
388        let mut bad_merged_vks = merged_vks;
389        bad_merged_vks[0].domain_size /= 2;
390        assert!(BatchArgument::partial_verify::<T>(
391            beta_g_ref,
392            &open_key_ref.g,
393            &bad_merged_vks,
394            &[shared_public_input],
395            &batch_proof,
396            blinding_factor
397        )
398        .is_err());
399
400        Ok(())
401    }
402}