halo2_proofs/poly/commitment/
verifier.rs

Help
1use group::{
2    ff::{BatchInvert, Field},
3    Curve,
4};
5
6use super::super::Error;
7use super::{Params, MSM};
8use crate::transcript::{EncodedChallenge, TranscriptRead};
9
10use crate::arithmetic::{best_multiexp, CurveAffine};
11
12/// A guard returned by the verifier
13#[derive(Debug, Clone)]
14pub struct Guard<'a, C: CurveAffine, E: EncodedChallenge<C>> {
15    msm: MSM<'a, C>,
16    neg_c: C::Scalar,
17    u: Vec<C::Scalar>,
18    u_packed: Vec<E>,
19}
20
21/// An accumulator instance consisting of an evaluation claim and a proof.
22#[derive(Debug, Clone)]
23pub struct Accumulator<C: CurveAffine, E: EncodedChallenge<C>> {
24    /// The claimed output of the linear-time polycommit opening protocol
25    pub g: C,
26
27    /// A vector of challenges u_0, ..., u_{k - 1} sampled by the verifier, to
28    /// be used in computing G'_0.
29    pub u_packed: Vec<E>,
30}
31
32impl<'a, C: CurveAffine, E: EncodedChallenge<C>> Guard<'a, C, E> {
33    /// Lets caller supply the challenges and obtain an MSM with updated
34    /// scalars and points.
35    pub fn use_challenges(mut self) -> MSM<'a, C> {
36        let s = compute_s(&self.u, self.neg_c);
37        self.msm.add_to_g_scalars(&s);
38
39        self.msm
40    }
41
42    /// Lets caller supply the purported G point and simply appends
43    /// [-c] G to return an updated MSM.
44    pub fn use_g(mut self, g: C) -> (MSM<'a, C>, Accumulator<C, E>) {
45        self.msm.append_term(self.neg_c, g);
46
47        let accumulator = Accumulator {
48            g,
49            u_packed: self.u_packed,
50        };
51
52        (self.msm, accumulator)
53    }
54
55    /// Computes G = ⟨s, params.g⟩
56    pub fn compute_g(&self) -> C {
57        let s = compute_s(&self.u, C::Scalar::one());
58
59        best_multiexp(&s, &self.msm.params.g).to_affine()
60    }
61}
62
63/// Checks to see if the proof represented within `transcript` is valid, and a
64/// point `x` that the polynomial commitment `P` opens purportedly to the value
65/// `v`. The provided `msm` should evaluate to the commitment `P` being opened.
66pub fn verify_proof<'a, C: CurveAffine, E: EncodedChallenge<C>, T: TranscriptRead<C, E>>(
67    params: &'a Params<C>,
68    mut msm: MSM<'a, C>,
69    transcript: &mut T,
70    x: C::Scalar,
71    v: C::Scalar,
72) -> Result<Guard<'a, C, E>, Error> {
73    let k = params.k as usize;
74
75    // P' = P - [v] G_0 + [ξ] S
76    msm.add_constant_term(-v); // add [-v] G_0
77    let s_poly_commitment = transcript.read_point().map_err(|_| Error::OpeningError)?;
78    let xi = *transcript.squeeze_challenge_scalar::<()>();
79    msm.append_term(xi, s_poly_commitment);
80
81    let z = *transcript.squeeze_challenge_scalar::<()>();
82
83    let mut rounds = vec![];
84    for _ in 0..k {
85        // Read L and R from the proof and write them to the transcript
86        let l = transcript.read_point().map_err(|_| Error::OpeningError)?;
87        let r = transcript.read_point().map_err(|_| Error::OpeningError)?;
88
89        let u_j_packed = transcript.squeeze_challenge();
90        let u_j = *u_j_packed.as_challenge_scalar::<()>();
91
92        rounds.push((l, r, u_j, /* to be inverted */ u_j, u_j_packed));
93    }
94
95    rounds
96        .iter_mut()
97        .map(|&mut (_, _, _, ref mut u_j, _)| u_j)
98        .batch_invert();
99
100    // This is the left-hand side of the verifier equation.
101    // P' + \sum([u_j^{-1}] L_j) + \sum([u_j] R_j)
102    let mut u = Vec::with_capacity(k);
103    let mut u_packed: Vec<E> = Vec::with_capacity(k);
104    for (l, r, u_j, u_j_inv, u_j_packed) in rounds {
105        msm.append_term(u_j_inv, l);
106        msm.append_term(u_j, r);
107
108        u.push(u_j);
109        u_packed.push(u_j_packed);
110    }
111
112    // Our goal is to check that the left hand side of the verifier
113    // equation
114    //     P' + \sum([u_j^{-1}] L_j) + \sum([u_j] R_j)
115    // equals (given b = \mathbf{b}_0, and the prover's values c, f),
116    // the right-hand side
117    //   = [c] (G'_0 + [b * z] U) + [f] W
118    // Subtracting the right-hand side from both sides we get
119    //   P' + \sum([u_j^{-1}] L_j) + \sum([u_j] R_j)
120    //   + [-c] G'_0 + [-cbz] U + [-f] W
121    //   = 0
122
123    let c = transcript.read_scalar().map_err(|_| Error::SamplingError)?;
124    let neg_c = -c;
125    let f = transcript.read_scalar().map_err(|_| Error::SamplingError)?;
126    let b = compute_b(x, &u);
127
128    msm.add_to_u_scalar(neg_c * &b * &z);
129    msm.add_to_w_scalar(-f);
130
131    let guard = Guard {
132        msm,
133        neg_c,
134        u,
135        u_packed,
136    };
137
138    Ok(guard)
139}
140
141/// Computes $\prod\limits_{i=0}^{k-1} (1 + u_{k - 1 - i} x^{2^i})$.
142fn compute_b<F: Field>(x: F, u: &[F]) -> F {
143    let mut tmp = F::one();
144    let mut cur = x;
145    for u_j in u.iter().rev() {
146        tmp *= F::one() + &(*u_j * &cur);
147        cur *= cur;
148    }
149    tmp
150}
151
152/// Computes the coefficients of $g(X) = \prod\limits_{i=0}^{k-1} (1 + u_{k - 1 - i} X^{2^i})$.
153fn compute_s<F: Field>(u: &[F], init: F) -> Vec<F> {
154    assert!(!u.is_empty());
155    let mut v = vec![F::zero(); 1 << u.len()];
156    v[0] = init;
157
158    for (len, u_j) in u.iter().rev().enumerate().map(|(i, u_j)| (1 << i, u_j)) {
159        let (left, right) = v.split_at_mut(len);
160        let right = &mut right[0..len];
161        right.copy_from_slice(left);
162        for v in right {
163            *v *= u_j;
164        }
165    }
166
167    v
168}
halo2_proofs/poly/commitment/verifier.rs

halo2_proofs/poly/commitment/
verifier.rs
