snarkvm_algorithms/snark/varuna/data_structures/
proof.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{
17    SNARKError,
18    polycommit::sonic_pc,
19    snark::varuna::{CircuitId, ahp},
20};
21
22use ahp::prover::{FourthMessage, ThirdMessage};
23use snarkvm_curves::PairingEngine;
24use snarkvm_fields::PrimeField;
25use snarkvm_utilities::{FromBytes, ToBytes, error, serialize::*};
26use std::io::{self, Read, Write};
27
28use std::collections::BTreeMap;
29
30#[derive(Clone, Debug, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
31pub struct Commitments<E: PairingEngine> {
32    pub witness_commitments: Vec<WitnessCommitments<E>>,
33    /// Commitment to the masking polynomial.
34    pub mask_poly: Option<sonic_pc::Commitment<E>>,
35    /// Commitment to the `h_0` polynomial.
36    pub h_0: sonic_pc::Commitment<E>,
37    /// Commitment to the `g_1` polynomial.
38    pub g_1: sonic_pc::Commitment<E>,
39    /// Commitment to the `h_1` polynomial.
40    pub h_1: sonic_pc::Commitment<E>,
41    /// Commitment to the `g_a` polynomials.
42    pub g_a_commitments: Vec<sonic_pc::Commitment<E>>,
43    /// Commitment to the `g_b` polynomials.
44    pub g_b_commitments: Vec<sonic_pc::Commitment<E>>,
45    /// Commitment to the `g_c` polynomials.
46    pub g_c_commitments: Vec<sonic_pc::Commitment<E>>,
47    /// Commitment to the `h_2` polynomial.
48    pub h_2: sonic_pc::Commitment<E>,
49}
50
51impl<E: PairingEngine> Commitments<E> {
52    fn serialize_with_mode<W: snarkvm_utilities::Write>(
53        &self,
54        mut writer: W,
55        compress: Compress,
56    ) -> Result<(), snarkvm_utilities::SerializationError> {
57        serialize_vec_without_len(self.witness_commitments.iter(), &mut writer, compress)?;
58        CanonicalSerialize::serialize_with_mode(&self.mask_poly, &mut writer, compress)?;
59        CanonicalSerialize::serialize_with_mode(&self.h_0, &mut writer, compress)?;
60        CanonicalSerialize::serialize_with_mode(&self.g_1, &mut writer, compress)?;
61        CanonicalSerialize::serialize_with_mode(&self.h_1, &mut writer, compress)?;
62        serialize_vec_without_len(self.g_a_commitments.iter(), &mut writer, compress)?;
63        serialize_vec_without_len(self.g_b_commitments.iter(), &mut writer, compress)?;
64        serialize_vec_without_len(self.g_c_commitments.iter(), &mut writer, compress)?;
65        CanonicalSerialize::serialize_with_mode(&self.h_2, &mut writer, compress)?;
66        Ok(())
67    }
68
69    fn serialized_size(&self, compress: Compress) -> usize {
70        serialized_vec_size_without_len(&self.witness_commitments, compress)
71            .saturating_add(CanonicalSerialize::serialized_size(&self.mask_poly, compress))
72            .saturating_add(CanonicalSerialize::serialized_size(&self.h_0, compress))
73            .saturating_add(CanonicalSerialize::serialized_size(&self.g_1, compress))
74            .saturating_add(CanonicalSerialize::serialized_size(&self.h_1, compress))
75            .saturating_add(serialized_vec_size_without_len(&self.g_a_commitments, compress))
76            .saturating_add(serialized_vec_size_without_len(&self.g_b_commitments, compress))
77            .saturating_add(serialized_vec_size_without_len(&self.g_c_commitments, compress))
78            .saturating_add(CanonicalSerialize::serialized_size(&self.h_2, compress))
79    }
80
81    fn deserialize_with_mode<R: snarkvm_utilities::Read>(
82        batch_sizes: &[usize],
83        mut reader: R,
84        compress: Compress,
85        validate: Validate,
86    ) -> Result<Self, snarkvm_utilities::SerializationError> {
87        let mut w = Vec::new();
88        for batch_size in batch_sizes {
89            w.extend(deserialize_vec_without_len(&mut reader, compress, validate, *batch_size)?);
90        }
91        Ok(Commitments {
92            witness_commitments: w,
93            mask_poly: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
94            h_0: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
95            g_1: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
96            h_1: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
97            g_a_commitments: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
98            g_b_commitments: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
99            g_c_commitments: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
100            h_2: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
101        })
102    }
103}
104/// Commitments to the `w` polynomials.
105#[derive(Clone, Debug, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
106pub struct WitnessCommitments<E: PairingEngine> {
107    /// Commitment to the `w` polynomial.
108    pub w: sonic_pc::Commitment<E>,
109}
110
111#[derive(Clone, Debug, PartialEq, Eq)]
112pub struct Evaluations<F: PrimeField> {
113    /// Evaluation of `g_1` at `beta`.
114    pub g_1_eval: F,
115    /// Evaluation of `g_a_i`'s at `beta`.
116    pub g_a_evals: Vec<F>,
117    /// Evaluation of `g_b_i`'s at `gamma`.
118    pub g_b_evals: Vec<F>,
119    /// Evaluation of `g_c_i`'s at `gamma`.
120    pub g_c_evals: Vec<F>,
121}
122
123impl<F: PrimeField> Evaluations<F> {
124    fn serialize_with_mode<W: snarkvm_utilities::Write>(
125        &self,
126        mut writer: W,
127        compress: Compress,
128    ) -> Result<(), snarkvm_utilities::SerializationError> {
129        CanonicalSerialize::serialize_with_mode(&self.g_1_eval, &mut writer, compress)?;
130        serialize_vec_without_len(self.g_a_evals.iter(), &mut writer, compress)?;
131        serialize_vec_without_len(self.g_b_evals.iter(), &mut writer, compress)?;
132        serialize_vec_without_len(self.g_c_evals.iter(), &mut writer, compress)?;
133        Ok(())
134    }
135
136    fn serialized_size(&self, compress: Compress) -> usize {
137        CanonicalSerialize::serialized_size(&self.g_1_eval, compress)
138            .saturating_add(serialized_vec_size_without_len(&self.g_a_evals, compress))
139            .saturating_add(serialized_vec_size_without_len(&self.g_b_evals, compress))
140            .saturating_add(serialized_vec_size_without_len(&self.g_c_evals, compress))
141    }
142
143    fn deserialize_with_mode<R: snarkvm_utilities::Read>(
144        batch_sizes: &[usize],
145        mut reader: R,
146        compress: Compress,
147        validate: Validate,
148    ) -> Result<Self, snarkvm_utilities::SerializationError> {
149        Ok(Evaluations {
150            g_1_eval: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
151            g_a_evals: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
152            g_b_evals: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
153            g_c_evals: deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?,
154        })
155    }
156}
157
158impl<F: PrimeField> Evaluations<F> {
159    pub(crate) fn from_map(
160        map: &std::collections::BTreeMap<String, F>,
161        batch_sizes: BTreeMap<CircuitId, usize>,
162    ) -> Self {
163        let mut g_a_evals = Vec::with_capacity(batch_sizes.len());
164        let mut g_b_evals = Vec::with_capacity(batch_sizes.len());
165        let mut g_c_evals = Vec::with_capacity(batch_sizes.len());
166
167        for (label, value) in map {
168            if label == "g_1" {
169                continue;
170            }
171
172            if label.contains("g_a") {
173                g_a_evals.push(*value);
174            } else if label.contains("g_b") {
175                g_b_evals.push(*value);
176            } else if label.contains("g_c") {
177                g_c_evals.push(*value);
178            }
179        }
180        Self { g_1_eval: map["g_1"], g_a_evals, g_b_evals, g_c_evals }
181    }
182
183    pub(crate) fn get(&self, circuit_index: usize, label: &str) -> Option<F> {
184        if label == "g_1" {
185            return Some(self.g_1_eval);
186        }
187
188        if label.contains("g_a") {
189            self.g_a_evals.get(circuit_index).copied()
190        } else if label.contains("g_b") {
191            self.g_b_evals.get(circuit_index).copied()
192        } else if label.contains("g_c") {
193            self.g_c_evals.get(circuit_index).copied()
194        } else {
195            None
196        }
197    }
198
199    pub fn to_field_elements(&self) -> Vec<F> {
200        let mut result = Vec::with_capacity(1 + self.g_a_evals.len() + self.g_b_evals.len() + self.g_c_evals.len());
201        result.push(self.g_1_eval);
202        result.extend_from_slice(&self.g_a_evals);
203        result.extend_from_slice(&self.g_b_evals);
204        result.extend_from_slice(&self.g_c_evals);
205        result
206    }
207}
208
209impl<F: PrimeField> Valid for Evaluations<F> {
210    fn check(&self) -> Result<(), snarkvm_utilities::SerializationError> {
211        self.g_1_eval.check()?;
212        self.g_a_evals.check()?;
213        self.g_b_evals.check()?;
214        self.g_c_evals.check()
215    }
216}
217
218/// A zkSNARK proof.
219#[derive(Clone, Debug, PartialEq, Eq)]
220pub struct Proof<E: PairingEngine> {
221    /// The number of instances being proven in this proof.
222    batch_sizes: Vec<usize>,
223
224    /// Commitments to prover polynomials.
225    pub commitments: Commitments<E>,
226
227    /// Evaluations of some of the committed polynomials.
228    pub evaluations: Evaluations<E::Fr>,
229
230    /// Prover message: sum_a, sum_b, sum_c for each instance
231    pub third_msg: ThirdMessage<E::Fr>,
232
233    /// Prover message: sum_a, sum_b, sum_c for each circuit
234    pub fourth_msg: FourthMessage<E::Fr>,
235
236    /// An evaluation proof from the polynomial commitment.
237    pub pc_proof: sonic_pc::BatchLCProof<E>,
238}
239
240impl<E: PairingEngine> Proof<E> {
241    /// Construct a new proof.
242    pub fn new(
243        batch_sizes: BTreeMap<CircuitId, usize>,
244        commitments: Commitments<E>,
245        evaluations: Evaluations<E::Fr>,
246        third_msg: ThirdMessage<E::Fr>,
247        fourth_msg: FourthMessage<E::Fr>,
248        pc_proof: sonic_pc::BatchLCProof<E>,
249    ) -> Result<Self, SNARKError> {
250        let batch_sizes: Vec<usize> = batch_sizes.into_values().collect();
251        Ok(Self { batch_sizes, commitments, evaluations, third_msg, fourth_msg, pc_proof })
252    }
253
254    pub fn is_hiding(&self) -> bool {
255        self.pc_proof.is_hiding()
256    }
257
258    pub fn batch_sizes(&self) -> &[usize] {
259        &self.batch_sizes
260    }
261
262    /// Check that the number of messages is consistent with our batch size
263    pub fn check_batch_sizes(&self) -> Result<(), SNARKError> {
264        let total_instances = self
265            .batch_sizes
266            .iter()
267            .try_fold(0usize, |acc, &size| acc.checked_add(size))
268            .ok_or(SNARKError::BatchSizeMismatch)?;
269        if self.commitments.witness_commitments.len() != total_instances {
270            return Err(SNARKError::BatchSizeMismatch);
271        }
272        let g_comms =
273            [&self.commitments.g_a_commitments, &self.commitments.g_b_commitments, &self.commitments.g_c_commitments];
274        for comms in g_comms {
275            if comms.len() != self.batch_sizes.len() {
276                return Err(SNARKError::BatchSizeMismatch);
277            }
278        }
279        let g_evals = [&self.evaluations.g_a_evals, &self.evaluations.g_b_evals, &self.evaluations.g_c_evals];
280        for evals in g_evals {
281            if evals.len() != self.batch_sizes.len() {
282                return Err(SNARKError::BatchSizeMismatch);
283            }
284        }
285        if self.third_msg.sums.len() != self.batch_sizes.len() {
286            return Err(SNARKError::BatchSizeMismatch);
287        }
288        for (msg, &batch_size) in self.third_msg.sums.iter().zip(self.batch_sizes.iter()) {
289            if msg.len() != batch_size {
290                return Err(SNARKError::BatchSizeMismatch);
291            }
292        }
293        if self.fourth_msg.sums.len() != self.batch_sizes.len() {
294            return Err(SNARKError::BatchSizeMismatch);
295        }
296        Ok(())
297    }
298}
299
300impl<E: PairingEngine> CanonicalSerialize for Proof<E> {
301    fn serialize_with_mode<W: Write>(&self, mut writer: W, compress: Compress) -> Result<(), SerializationError> {
302        let batch_sizes: Vec<u64> = self.batch_sizes.iter().map(|x| u64::try_from(*x)).collect::<Result<_, _>>()?;
303        CanonicalSerialize::serialize_with_mode(&batch_sizes, &mut writer, compress)?;
304        Commitments::serialize_with_mode(&self.commitments, &mut writer, compress)?;
305        Evaluations::serialize_with_mode(&self.evaluations, &mut writer, compress)?;
306        for third_sums in self.third_msg.sums.iter() {
307            serialize_vec_without_len(third_sums.iter(), &mut writer, compress)?;
308        }
309        serialize_vec_without_len(self.fourth_msg.sums.iter(), &mut writer, compress)?;
310        CanonicalSerialize::serialize_with_mode(&self.pc_proof, &mut writer, compress)?;
311        Ok(())
312    }
313
314    fn serialized_size(&self, mode: Compress) -> usize {
315        let mut size = 0;
316        size += CanonicalSerialize::serialized_size(&self.batch_sizes, mode);
317        size += Commitments::serialized_size(&self.commitments, mode);
318        size += Evaluations::serialized_size(&self.evaluations, mode);
319        for third_sums in self.third_msg.sums.iter() {
320            size += serialized_vec_size_without_len(third_sums, mode);
321        }
322        size += serialized_vec_size_without_len(&self.fourth_msg.sums, mode);
323        size += CanonicalSerialize::serialized_size(&self.pc_proof, mode);
324        size
325    }
326}
327
328impl<E: PairingEngine> Valid for Proof<E> {
329    fn check(&self) -> Result<(), SerializationError> {
330        self.batch_sizes.check()?;
331        self.commitments.check()?;
332        self.evaluations.check()?;
333        self.third_msg.check()?;
334        self.fourth_msg.check()?;
335        self.pc_proof.check()
336    }
337}
338
339impl<E: PairingEngine> CanonicalDeserialize for Proof<E> {
340    fn deserialize_with_mode<R: Read>(
341        mut reader: R,
342        compress: Compress,
343        validate: Validate,
344    ) -> Result<Self, SerializationError> {
345        let batch_sizes: Vec<u64> = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
346        let batch_sizes: Vec<usize> = batch_sizes.into_iter().map(|x| x as usize).collect();
347        let commitments = Commitments::deserialize_with_mode(&batch_sizes, &mut reader, compress, validate)?;
348        let evaluations = Evaluations::deserialize_with_mode(&batch_sizes, &mut reader, compress, validate)?;
349        let third_msg_sums = batch_sizes
350            .iter()
351            .map(|&batch_size| deserialize_vec_without_len(&mut reader, compress, validate, batch_size))
352            .collect::<Result<Vec<_>, _>>()?;
353        let fourth_msg_sums = deserialize_vec_without_len(&mut reader, compress, validate, batch_sizes.len())?;
354        Ok(Proof {
355            commitments,
356            evaluations,
357            third_msg: ThirdMessage { sums: third_msg_sums },
358            fourth_msg: FourthMessage { sums: fourth_msg_sums },
359            pc_proof: CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?,
360            batch_sizes,
361        })
362    }
363}
364
365impl<E: PairingEngine> ToBytes for Proof<E> {
366    fn write_le<W: Write>(&self, mut w: W) -> io::Result<()> {
367        Self::serialize_compressed(self, &mut w).map_err(|_| error("could not serialize Proof"))
368    }
369}
370
371impl<E: PairingEngine> FromBytes for Proof<E> {
372    fn read_le<R: Read>(mut r: R) -> io::Result<Self> {
373        Self::deserialize_compressed(&mut r).map_err(|_| error("could not deserialize Proof"))
374    }
375}
376
377#[cfg(test)]
378mod test {
379    #![allow(non_camel_case_types)]
380
381    use super::*;
382
383    use crate::{
384        polycommit::{
385            kzg10::{KZGCommitment, KZGProof},
386            sonic_pc::BatchProof,
387        },
388        snark::varuna::prover::MatrixSums,
389    };
390    use snarkvm_curves::{
391        AffineCurve,
392        bls12_377::{Bls12_377, Fr, G1Affine},
393    };
394    use snarkvm_utilities::{TestRng, Uniform};
395
396    const fn modes() -> [(Compress, Validate); 4] {
397        [
398            (Compress::No, Validate::No),
399            (Compress::Yes, Validate::No),
400            (Compress::No, Validate::Yes),
401            (Compress::Yes, Validate::Yes),
402        ]
403    }
404
405    fn sample_commit() -> KZGCommitment<Bls12_377> {
406        let buf = G1Affine::prime_subgroup_generator().to_bytes_le().unwrap();
407        FromBytes::read_le(buf.as_slice()).unwrap()
408    }
409
410    fn rand_commitments(j: usize, i: usize, test_with_none: bool) -> Commitments<Bls12_377> {
411        assert!(i > 0);
412        assert!(j > 0);
413        let sample_commit = sample_commit();
414        let mask_poly = if test_with_none { None } else { Some(sample_commit) };
415        Commitments {
416            witness_commitments: vec![WitnessCommitments { w: sample_commit }; i * j],
417            mask_poly,
418            h_0: sample_commit,
419            g_1: sample_commit,
420            h_1: sample_commit,
421            g_a_commitments: vec![sample_commit; i],
422            g_b_commitments: vec![sample_commit; i],
423            g_c_commitments: vec![sample_commit; i],
424            h_2: sample_commit,
425        }
426    }
427
428    fn rand_evaluations<F: PrimeField>(rng: &mut TestRng, i: usize) -> Evaluations<F> {
429        Evaluations {
430            g_1_eval: F::rand(rng),
431            g_a_evals: (0..i).map(|_| F::rand(rng)).collect(),
432            g_b_evals: (0..i).map(|_| F::rand(rng)).collect(),
433            g_c_evals: (0..i).map(|_| F::rand(rng)).collect(),
434        }
435    }
436
437    fn rand_sums<F: PrimeField>(rng: &mut TestRng) -> MatrixSums<F> {
438        MatrixSums::<F> { sum_a: F::rand(rng), sum_b: F::rand(rng), sum_c: F::rand(rng) }
439    }
440
441    fn rand_kzg_proof(rng: &mut TestRng, test_with_none: bool) -> KZGProof<Bls12_377> {
442        let random_v = if test_with_none { None } else { Some(Fr::rand(rng)) };
443        KZGProof::<Bls12_377> { w: G1Affine::prime_subgroup_generator(), random_v }
444    }
445
446    #[test]
447    fn test_serializing_commitments() {
448        for i in 1..11 {
449            for j in 1..11 {
450                let test_with_none = i * j % 2 == 0;
451                let commitments = rand_commitments(j, i, test_with_none);
452                let batch_sizes = vec![j; i];
453                let combinations = modes();
454                for (compress, validate) in combinations {
455                    let size = Commitments::serialized_size(&commitments, compress);
456                    let mut serialized = vec![0; size];
457                    Commitments::serialize_with_mode(&commitments, &mut serialized[..], compress).unwrap();
458                    let de =
459                        Commitments::deserialize_with_mode(&batch_sizes, &serialized[..], compress, validate).unwrap();
460                    assert_eq!(commitments, de);
461                }
462            }
463        }
464    }
465
466    #[test]
467    fn test_serializing_evaluations() {
468        let rng = &mut TestRng::default();
469
470        for i in 1..11 {
471            for j in 1..11 {
472                let evaluations: Evaluations<Fr> = rand_evaluations(rng, i);
473                let batch_sizes = vec![j; i];
474                let combinations = modes();
475                for (compress, validate) in combinations {
476                    let size = Evaluations::serialized_size(&evaluations, compress);
477                    let mut serialized = vec![0; size];
478                    Evaluations::serialize_with_mode(&evaluations, &mut serialized[..], compress).unwrap();
479                    let de =
480                        Evaluations::deserialize_with_mode(&batch_sizes, &serialized[..], compress, validate).unwrap();
481                    assert_eq!(evaluations, de);
482                }
483            }
484        }
485    }
486
487    #[test]
488    fn test_serializing_proof() {
489        let rng = &mut snarkvm_utilities::rand::TestRng::default();
490
491        for i in 1..11 {
492            for j in 1..11 {
493                let test_with_none = i * j % 2 == 0;
494                let batch_sizes = vec![j; i];
495                let commitments = rand_commitments(j, i, test_with_none);
496                let evaluations: Evaluations<Fr> = rand_evaluations(rng, i);
497                let third_msg = ThirdMessage::<Fr> { sums: vec![vec![rand_sums(rng); j]; i] };
498                let fourth_msg = FourthMessage::<Fr> { sums: vec![rand_sums(rng); i] };
499                let pc_proof =
500                    sonic_pc::BatchLCProof { proof: BatchProof(vec![rand_kzg_proof(rng, test_with_none); j]) };
501                let proof = Proof { batch_sizes, commitments, evaluations, third_msg, fourth_msg, pc_proof };
502                let combinations = modes();
503                for (compress, validate) in combinations {
504                    let size = Proof::serialized_size(&proof, compress);
505                    let mut serialized = vec![0; size];
506                    Proof::serialize_with_mode(&proof, &mut serialized[..], compress).unwrap();
507                    let de = Proof::deserialize_with_mode(&serialized[..], compress, validate).unwrap();
508                    assert_eq!(proof, de);
509                }
510            }
511        }
512    }
513}
snarkvm_algorithms/snark/varuna/data_structures/proof.rs

snarkvm_algorithms/snark/varuna/data_structures/
proof.rs
