sapling_crypto/verifier/
batch.rs

1use bellman::groth16;
2use bls12_381::Bls12;
3use group::GroupEncoding;
4use rand_core::{CryptoRng, Rng};
5
6use super::SaplingVerificationContextInner;
7use crate::{
8    bundle::{Authorized, Bundle},
9    circuit::{OutputVerifyingKey, SpendVerifyingKey},
10};
11
12#[cfg(feature = "multicore")]
13const MAX_JOINT_PROOFS_PER_KIND: usize = 1;
14
15/// Borrowed Sapling verifying keys for repeated [`BatchValidator`]s.
16///
17/// Each key retains its fixed G2 terms after first use. This wrapper keeps
18/// the existing prepared validation API for callers with both keys.
19pub struct PreparedBatchVerifyingKeys<'a> {
20    spend_vk: &'a SpendVerifyingKey,
21    output_vk: &'a OutputVerifyingKey,
22}
23
24impl<'a> PreparedBatchVerifyingKeys<'a> {
25    /// Borrows the Spend and Output verifying keys for batch validation.
26    pub fn new(spend_vk: &'a SpendVerifyingKey, output_vk: &'a OutputVerifyingKey) -> Self {
27        Self {
28            spend_vk,
29            output_vk,
30        }
31    }
32
33    fn spend(
34        &self,
35    ) -> Result<groth16::batch::PreparedBatchVerifyingKey<'_, Bls12>, bellman::VerificationError>
36    {
37        self.spend_vk.prepared_batch()
38    }
39
40    fn output(
41        &self,
42    ) -> Result<groth16::batch::PreparedBatchVerifyingKey<'_, Bls12>, bellman::VerificationError>
43    {
44        self.output_vk.prepared_batch()
45    }
46}
47
48/// Batch validation context for Sapling.
49///
50/// This batch-validates Spend and Output proofs, and RedJubjub signatures.
51///
52/// Signatures are verified assuming ZIP 216 is active.
53pub struct BatchValidator {
54    bundles_added: bool,
55    spend_proof_count: usize,
56    output_proof_count: usize,
57    spend_proofs: groth16::batch::Verifier<Bls12>,
58    output_proofs: groth16::batch::Verifier<Bls12>,
59    signatures: redjubjub::batch::Verifier,
60}
61
62impl Default for BatchValidator {
63    fn default() -> Self {
64        Self::new()
65    }
66}
67
68impl BatchValidator {
69    /// Constructs a new batch validation context.
70    pub fn new() -> Self {
71        BatchValidator {
72            bundles_added: false,
73            spend_proof_count: 0,
74            output_proof_count: 0,
75            spend_proofs: groth16::batch::Verifier::new(),
76            output_proofs: groth16::batch::Verifier::new(),
77            signatures: redjubjub::batch::Verifier::new(),
78        }
79    }
80
81    /// Checks the bundle against Sapling-specific consensus rules, and adds its proof and
82    /// signatures to the validator.
83    ///
84    /// Returns `false` if the bundle doesn't satisfy all of the consensus rules. This
85    /// `BatchValidator` can continue to be used regardless, but some or all of the proofs
86    /// and signatures from this bundle may have already been added to the batch even if
87    /// it fails other consensus rules.
88    pub fn check_bundle<V: Copy + Into<i64>>(
89        &mut self,
90        bundle: Bundle<Authorized, V>,
91        sighash: [u8; 32],
92    ) -> bool {
93        self.bundles_added = true;
94
95        let mut ctx = SaplingVerificationContextInner::new();
96
97        for spend in bundle.shielded_spends() {
98            // Deserialize the proof
99            let zkproof = match groth16::Proof::read(&spend.zkproof()[..]) {
100                Ok(p) => p,
101                Err(_) => return false,
102            };
103
104            // Check the Spend consensus rules, and batch its proof and spend
105            // authorization signature.
106            let consensus_rules_passed = ctx.check_spend(
107                spend.cv(),
108                *spend.anchor(),
109                &spend.nullifier().0,
110                spend.rk(),
111                zkproof,
112                self,
113                |this, rk| {
114                    this.signatures
115                        .queue(((*rk).into(), *spend.spend_auth_sig(), &sighash));
116                    true
117                },
118                |this, proof, public_inputs| {
119                    this.spend_proofs.queue((proof, public_inputs.to_vec()));
120                    this.spend_proof_count += 1;
121                    true
122                },
123            );
124            if !consensus_rules_passed {
125                return false;
126            }
127        }
128
129        for output in bundle.shielded_outputs() {
130            // Deserialize the ephemeral key
131            let epk = match jubjub::ExtendedPoint::from_bytes(&output.ephemeral_key().0).into() {
132                Some(p) => p,
133                None => return false,
134            };
135
136            // Deserialize the proof
137            let zkproof = match groth16::Proof::read(&output.zkproof()[..]) {
138                Ok(p) => p,
139                Err(_) => return false,
140            };
141
142            // Check the Output consensus rules, and batch its proof.
143            let consensus_rules_passed = ctx.check_output(
144                output.cv(),
145                *output.cmu(),
146                epk,
147                zkproof,
148                |proof, public_inputs| {
149                    self.output_proofs.queue((proof, public_inputs.to_vec()));
150                    self.output_proof_count += 1;
151                    true
152                },
153            );
154            if !consensus_rules_passed {
155                return false;
156            }
157        }
158
159        // Check the whole-bundle consensus rules, and batch the binding signature.
160        ctx.final_check(*bundle.value_balance(), |bvk| {
161            self.signatures
162                .queue((bvk.into(), bundle.authorization().binding_sig, &sighash));
163            true
164        })
165    }
166
167    /// Batch-validates the accumulated bundles.
168    ///
169    /// Returns `true` if every proof and signature in every bundle added to the batch
170    /// validator is valid, or `false` if one or more are invalid. No attempt is made to
171    /// figure out which of the accumulated bundles might be invalid; if that information
172    /// is desired, construct separate [`BatchValidator`]s for sub-batches of the bundles.
173    pub fn validate<R: Rng + CryptoRng>(
174        self,
175        spend_vk: &SpendVerifyingKey,
176        output_vk: &OutputVerifyingKey,
177        rng: R,
178    ) -> bool {
179        self.validate_prepared(&PreparedBatchVerifyingKeys::new(spend_vk, output_vk), rng)
180    }
181
182    /// Batch-validates using keys prepared across multiple validators.
183    ///
184    /// As with [`BatchValidator::validate`], this returns `true` only when
185    /// every queued proof and signature is valid. Preparation occurs after
186    /// signature verification and only for proof types present in the batch.
187    pub fn validate_prepared<R: Rng + CryptoRng>(
188        self,
189        keys: &PreparedBatchVerifyingKeys<'_>,
190        mut rng: R,
191    ) -> bool {
192        if !self.bundles_added {
193            return true;
194        }
195
196        if let Err(e) = self.signatures.verify(&mut rng) {
197            #[cfg(feature = "std")]
198            tracing::debug!("Signature batch validation failed: {}", e);
199            #[cfg(not(feature = "std"))]
200            tracing::debug!("Signature batch validation failed: {:?}", e);
201            return false;
202        }
203
204        // The joint path wins for one Spend and one Output proof. Larger
205        // batches can run faster through the parallel verifier.
206        #[cfg(feature = "multicore")]
207        let use_joint = self.spend_proof_count > 0
208            && self.output_proof_count > 0
209            && self.spend_proof_count <= MAX_JOINT_PROOFS_PER_KIND
210            && self.output_proof_count <= MAX_JOINT_PROOFS_PER_KIND;
211        #[cfg(not(feature = "multicore"))]
212        let use_joint = self.spend_proof_count > 0 && self.output_proof_count > 0;
213
214        if use_joint {
215            let (Ok(spend), Ok(output)) = (keys.spend(), keys.output()) else {
216                tracing::debug!("Sapling proof verifying key validation failed");
217                return false;
218            };
219            if self
220                .spend_proofs
221                .verify_joint_prepared(self.output_proofs, &mut rng, &spend, &output)
222                .is_err()
223            {
224                tracing::debug!("Sapling proof batch validation failed");
225                return false;
226            }
227            return true;
228        }
229
230        if self.spend_proof_count > 0 {
231            let Ok(spend) = keys.spend() else {
232                tracing::debug!("Spend proof verifying key validation failed");
233                return false;
234            };
235            #[cfg(feature = "multicore")]
236            let result = self.spend_proofs.verify_multicore_prepared(&spend);
237            #[cfg(not(feature = "multicore"))]
238            let result = self.spend_proofs.verify_prepared(&mut rng, &spend);
239
240            if result.is_err() {
241                tracing::debug!("Spend proof batch validation failed");
242                return false;
243            }
244        }
245
246        if self.output_proof_count > 0 {
247            let Ok(output) = keys.output() else {
248                tracing::debug!("Output proof verifying key validation failed");
249                return false;
250            };
251            #[cfg(feature = "multicore")]
252            let result = self.output_proofs.verify_multicore_prepared(&output);
253            #[cfg(not(feature = "multicore"))]
254            let result = self.output_proofs.verify_prepared(&mut rng, &output);
255
256            if result.is_err() {
257                tracing::debug!("Output proof batch validation failed");
258                return false;
259            }
260        }
261
262        true
263    }
264}
265
266#[cfg(test)]
267mod tests {
268    use super::super::{OUTPUT_PUBLIC_INPUT_COUNT, SPEND_PUBLIC_INPUT_COUNT};
269    use super::{BatchValidator, PreparedBatchVerifyingKeys};
270    use crate::circuit::{OutputVerifyingKey, SpendVerifyingKey};
271    use alloc::vec::Vec;
272    use bellman::{Circuit, ConstraintSystem, SynthesisError, groth16};
273    use bls12_381::{Bls12, G2Affine, Scalar};
274    use ff::Field;
275
276    struct PublicInputs<const N: usize> {
277        values: Option<[Scalar; N]>,
278    }
279
280    impl<const N: usize> Circuit<Scalar> for PublicInputs<N> {
281        fn synthesize<CS: ConstraintSystem<Scalar>>(
282            self,
283            cs: &mut CS,
284        ) -> Result<(), SynthesisError> {
285            let witness = cs.alloc(
286                || "witness",
287                || {
288                    self.values
289                        .map(|values| values[0])
290                        .ok_or(SynthesisError::AssignmentMissing)
291                },
292            )?;
293
294            for index in 0..N {
295                let input = cs.alloc_input(
296                    || format!("input {index}"),
297                    || {
298                        self.values
299                            .map(|values| values[index])
300                            .ok_or(SynthesisError::AssignmentMissing)
301                    },
302                )?;
303                let source = if index == 0 { witness } else { input };
304                cs.enforce(
305                    || format!("input {index} is correct"),
306                    |lc| lc + source,
307                    |lc| lc + CS::one(),
308                    |lc| lc + input,
309                );
310            }
311            Ok(())
312        }
313    }
314
315    fn proof<const N: usize>(
316        rng: &mut impl rand_core::CryptoRng,
317    ) -> (
318        groth16::VerifyingKey<Bls12>,
319        groth16::Proof<Bls12>,
320        Vec<Scalar>,
321    ) {
322        let values: [Scalar; N] = core::array::from_fn(|_| Scalar::random(&mut *rng));
323        let params = groth16::generate_random_parameters::<Bls12, _, _>(
324            PublicInputs::<N> { values: None },
325            &mut *rng,
326        )
327        .unwrap();
328        let proof = groth16::create_random_proof(
329            PublicInputs {
330                values: Some(values),
331            },
332            &params,
333            rng,
334        )
335        .unwrap();
336        (params.vk, proof, values.to_vec())
337    }
338
339    fn validator(
340        spend: Option<(&groth16::Proof<Bls12>, &[Scalar])>,
341        output: Option<(&groth16::Proof<Bls12>, &[Scalar])>,
342    ) -> BatchValidator {
343        let mut validator = BatchValidator::new();
344        validator.bundles_added = true;
345        if let Some((proof, inputs)) = spend {
346            validator
347                .spend_proofs
348                .queue((proof.clone(), inputs.to_vec()));
349            validator.spend_proof_count = 1;
350        }
351        if let Some((proof, inputs)) = output {
352            validator
353                .output_proofs
354                .queue((proof.clone(), inputs.to_vec()));
355            validator.output_proof_count = 1;
356        }
357        validator
358    }
359
360    #[test]
361    fn validation_reuses_key_owned_preparation() {
362        let mut rng = rand::rng();
363        let (spend_vk, spend_proof, spend_inputs) = proof::<SPEND_PUBLIC_INPUT_COUNT>(&mut rng);
364        let (output_vk, output_proof, output_inputs) = proof::<OUTPUT_PUBLIC_INPUT_COUNT>(&mut rng);
365        let mut spend_vk = SpendVerifyingKey::new(spend_vk);
366        let mut output_vk = OutputVerifyingKey::new(output_vk);
367        let keys = PreparedBatchVerifyingKeys::new(&spend_vk, &output_vk);
368
369        assert!(BatchValidator::new().validate(&spend_vk, &output_vk, &mut rng));
370        assert!(BatchValidator::new().validate_prepared(&keys, &mut rng));
371        assert!(validator(None, None).validate(&spend_vk, &output_vk, &mut rng));
372        assert!(validator(None, None).validate_prepared(&keys, &mut rng));
373
374        let spend = Some((&spend_proof, spend_inputs.as_slice()));
375        assert!(validator(spend, None).validate(&spend_vk, &output_vk, &mut rng));
376        assert!(validator(spend, None).validate_prepared(&keys, &mut rng));
377
378        let output = Some((&output_proof, output_inputs.as_slice()));
379        assert!(validator(None, output).validate(&spend_vk, &output_vk, &mut rng));
380        assert!(validator(None, output).validate_prepared(&keys, &mut rng));
381
382        assert!(validator(spend, output).validate(&spend_vk, &output_vk, &mut rng));
383        assert!(validator(spend, output).validate_prepared(&keys, &mut rng));
384
385        let mut invalid_inputs = spend_inputs.clone();
386        invalid_inputs[0] += Scalar::ONE;
387        let invalid_spend = Some((&spend_proof, invalid_inputs.as_slice()));
388        assert!(!validator(invalid_spend, output).validate(&spend_vk, &output_vk, &mut rng));
389        assert!(!validator(invalid_spend, output).validate_prepared(&keys, &mut rng));
390
391        let mut invalid_inputs = output_inputs.clone();
392        invalid_inputs[0] += Scalar::ONE;
393        let invalid_output = Some((&output_proof, invalid_inputs.as_slice()));
394        assert!(!validator(spend, invalid_output).validate(&spend_vk, &output_vk, &mut rng));
395        assert!(!validator(spend, invalid_output).validate_prepared(&keys, &mut rng));
396
397        let mut large = validator(spend, output);
398        for _ in 1..9 {
399            large
400                .spend_proofs
401                .queue((spend_proof.clone(), spend_inputs.clone()));
402            large
403                .output_proofs
404                .queue((output_proof.clone(), output_inputs.clone()));
405        }
406        large.spend_proof_count = 9;
407        large.output_proof_count = 9;
408        assert!(large.validate_prepared(&keys, &mut rng));
409
410        spend_vk.0.delta_g2 = G2Affine::identity();
411        assert!(matches!(
412            spend_vk.prepared_batch(),
413            Err(bellman::VerificationError::InvalidVerifyingKey)
414        ));
415        assert!(!validator(spend, None).validate(&spend_vk, &output_vk, &mut rng));
416
417        output_vk.0.delta_g2 = G2Affine::identity();
418        assert!(matches!(
419            output_vk.prepared_batch(),
420            Err(bellman::VerificationError::InvalidVerifyingKey)
421        ));
422        assert!(!validator(None, output).validate(&spend_vk, &output_vk, &mut rng));
423    }
424
425    #[test]
426    #[ignore = "release-mode performance measurement"]
427    fn bench_joint_prepared_validation() {
428        use std::{hint::black_box, time::Instant};
429
430        let mut rng = rand::rng();
431        let (spend_vk, spend_proof, spend_inputs) = proof::<SPEND_PUBLIC_INPUT_COUNT>(&mut rng);
432        let (output_vk, output_proof, output_inputs) = proof::<OUTPUT_PUBLIC_INPUT_COUNT>(&mut rng);
433        let spend_vk = SpendVerifyingKey::new(spend_vk);
434        let output_vk = OutputVerifyingKey::new(output_vk);
435        let keys = PreparedBatchVerifyingKeys::new(&spend_vk, &output_vk);
436        let spend = (&spend_proof, spend_inputs.as_slice());
437        let output = (&output_proof, output_inputs.as_slice());
438
439        let make_validator = |count| {
440            let mut validator = BatchValidator::new();
441            validator.bundles_added = true;
442            for _ in 0..count {
443                validator
444                    .spend_proofs
445                    .queue((spend.0.clone(), spend.1.to_vec()));
446                validator
447                    .output_proofs
448                    .queue((output.0.clone(), output.1.to_vec()));
449            }
450            validator.spend_proof_count = count;
451            validator.output_proof_count = count;
452            validator
453        };
454
455        // Warm key preparation and both verifier paths before measuring.
456        assert!(make_validator(1).validate_prepared(&keys, &mut rng));
457
458        for count in [1, 2, 8, 16] {
459            let mut separate = Vec::with_capacity(40);
460            let mut joint = Vec::with_capacity(40);
461            for iteration in 0..40 {
462                let measure_separate = |rng: &mut _, timings: &mut Vec<u128>| {
463                    let validator = make_validator(count);
464                    let start = Instant::now();
465                    assert!(validator.signatures.verify(&mut *rng).is_ok());
466                    #[cfg(feature = "multicore")]
467                    {
468                        assert!(
469                            validator
470                                .spend_proofs
471                                .verify_multicore_prepared(&keys.spend().unwrap())
472                                .is_ok()
473                        );
474                        assert!(
475                            validator
476                                .output_proofs
477                                .verify_multicore_prepared(&keys.output().unwrap())
478                                .is_ok()
479                        );
480                    }
481                    #[cfg(not(feature = "multicore"))]
482                    {
483                        assert!(
484                            validator
485                                .spend_proofs
486                                .verify_prepared(&mut *rng, &keys.spend().unwrap())
487                                .is_ok()
488                        );
489                        assert!(
490                            validator
491                                .output_proofs
492                                .verify_prepared(&mut *rng, &keys.output().unwrap())
493                                .is_ok()
494                        );
495                    }
496                    timings.push(black_box(start.elapsed().as_micros()));
497                };
498                let measure_joint = |rng: &mut _, timings: &mut Vec<u128>| {
499                    let validator = make_validator(count);
500                    let start = Instant::now();
501                    assert!(black_box(validator.validate_prepared(&keys, rng)));
502                    timings.push(black_box(start.elapsed().as_micros()));
503                };
504                if iteration % 2 == 0 {
505                    measure_separate(&mut rng, &mut separate);
506                    measure_joint(&mut rng, &mut joint);
507                } else {
508                    measure_joint(&mut rng, &mut joint);
509                    measure_separate(&mut rng, &mut separate);
510                }
511            }
512            separate.sort_unstable();
513            joint.sort_unstable();
514            std::println!(
515                "{count}+{count}: separate {} us, joint {} us",
516                separate[separate.len() / 2],
517                joint[joint.len() / 2],
518            );
519        }
520    }
521
522    #[test]
523    #[ignore = "release-mode performance measurement"]
524    fn bench_repeated_prepared_validation() {
525        use std::{hint::black_box, time::Instant};
526
527        let mut rng = rand::rng();
528        let (spend_vk, spend_proof, spend_inputs) = proof::<SPEND_PUBLIC_INPUT_COUNT>(&mut rng);
529        let (output_vk, output_proof, output_inputs) = proof::<OUTPUT_PUBLIC_INPUT_COUNT>(&mut rng);
530        let spend_vk = SpendVerifyingKey::new(spend_vk);
531        let output_vk = OutputVerifyingKey::new(output_vk);
532        let keys = PreparedBatchVerifyingKeys::new(&spend_vk, &output_vk);
533        let spend = Some((&spend_proof, spend_inputs.as_slice()));
534        let output = Some((&output_proof, output_inputs.as_slice()));
535
536        // Warm both keys before timing repeated validations.
537        assert!(validator(spend, output).validate(&spend_vk, &output_vk, &mut rng));
538
539        for (name, spend, output) in [
540            ("Spend only", spend, None),
541            ("Output only", None, output),
542            ("Spend + Output", spend, output),
543        ] {
544            let mut default = Vec::with_capacity(100);
545            let mut prepared = Vec::with_capacity(100);
546            let mut cold = Vec::with_capacity(100);
547            for iteration in 0..100 {
548                let measure_default = |rng: &mut _, timings: &mut Vec<u128>| {
549                    let start = Instant::now();
550                    assert!(black_box(
551                        validator(spend, output).validate(&spend_vk, &output_vk, rng)
552                    ));
553                    timings.push(start.elapsed().as_micros());
554                };
555                let measure_prepared = |rng: &mut _, timings: &mut Vec<u128>| {
556                    let start = Instant::now();
557                    assert!(black_box(
558                        validator(spend, output).validate_prepared(&keys, rng)
559                    ));
560                    timings.push(start.elapsed().as_micros());
561                };
562                if iteration % 2 == 0 {
563                    measure_default(&mut rng, &mut default);
564                    measure_prepared(&mut rng, &mut prepared);
565                } else {
566                    measure_prepared(&mut rng, &mut prepared);
567                    measure_default(&mut rng, &mut default);
568                }
569
570                let fresh_spend = SpendVerifyingKey::new(spend_vk.0.clone());
571                let fresh_output = OutputVerifyingKey::new(output_vk.0.clone());
572                let start = Instant::now();
573                assert!(black_box(validator(spend, output).validate(
574                    &fresh_spend,
575                    &fresh_output,
576                    &mut rng,
577                )));
578                cold.push(start.elapsed().as_micros());
579            }
580            default.sort_unstable();
581            prepared.sort_unstable();
582            cold.sort_unstable();
583            std::println!(
584                "{name}: default {} us, prepared {} us, cold {} us",
585                default[default.len() / 2],
586                prepared[prepared.len() / 2],
587                cold[cold.len() / 2],
588            );
589        }
590    }
591}
sapling_crypto/verifier/batch.rs

sapling_crypto/verifier/
batch.rs
