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

snarkvm_algorithms/snark/varuna/data_structures/
proof.rs
