labrador/
verifier.rs

1#![allow(clippy::result_large_err)]
2
3use crate::commitments::common_instances::AjtaiInstances;
4use crate::commitments::outer_commitments::{DecompositionParameters, OuterCommitment};
5use crate::core::{aggregate, env_params::EnvironmentParameters, statement::Statement};
6use crate::prover::{Challenges, Proof};
7use crate::ring::rq::Rq;
8use crate::ring::rq_matrix::RqMatrix;
9use crate::ring::rq_vector::RqVector;
10use crate::ring::zq::{Zq, ZqVector};
11
12#[derive(Debug)]
13pub enum VerifierError {
14    NotSymmetric {
15        i: usize,
16        j: usize,
17        expected: Rq,
18        found: Rq,
19    },
20    B0Mismatch {
21        index: usize,
22        expected: Zq,
23        computed: Zq,
24    },
25    NormSumExceeded {
26        norm: Zq,
27        allowed: Zq,
28    },
29    AzError {
30        computed: RqVector,
31        expected: RqVector,
32    },
33    ZInnerError {
34        computed: Rq,
35        expected: Rq,
36    },
37    PhiError {
38        computed: Rq,
39        expected: Rq,
40    },
41    RelationCheckFailed,
42    OuterCommitError {
43        computed: RqVector,
44        expected: RqVector,
45    },
46}
47pub struct LabradorVerifier<'a> {
48    pub pp: &'a AjtaiInstances,
49    pub st: &'a Statement,
50    pub tr: &'a Challenges,
51}
52
53impl<'a> LabradorVerifier<'a> {
54    pub fn new(pp: &'a AjtaiInstances, st: &'a Statement, tr: &'a Challenges) -> Self {
55        Self { pp, st, tr }
56    }
57
58    /// All check conditions are from page 18
59    pub fn verify(&self, proof: &Proof, ep: &EnvironmentParameters) -> Result<bool, VerifierError> {
60        // check b_0^{''(k)} ?= <omega^(k),p> + \sum(psi_l^(k) * b_0^{'(l)})
61        Self::check_b_0_aggr(self, proof, ep).unwrap();
62
63        // 3. line 14: check norm_sum(z, t, g, h) <= (beta')^2
64
65        // decompose z into z = z^(0) + z^(1) * b, only two parts.
66        let z_ij = RqVector::decompose(&proof.z, ep.b, 2);
67        let t_ij: Vec<Vec<RqVector>> = proof
68            .t_i
69            .iter()
70            .map(|i| RqVector::decompose(i, ep.b, ep.t_1))
71            .collect();
72        let g_ij: Vec<Vec<RqVector>> = proof
73            .g_ij
74            .get_elements()
75            .iter()
76            .map(|i| RqVector::decompose(i, ep.b, ep.t_2))
77            .collect();
78        let h_ij: Vec<Vec<RqVector>> = proof
79            .h_ij
80            .get_elements()
81            .iter()
82            .map(|i| RqVector::decompose(i, ep.b, ep.t_1))
83            .collect();
84        let norm_z_ij = z_ij
85            .iter()
86            .fold(Zq::ZERO, |acc, p| acc + p.compute_norm_squared());
87        let norm_t_ij = Self::norm_squared(&t_ij);
88        let norm_g_ij = Self::norm_squared(&g_ij);
89        let norm_h_ij = Self::norm_squared(&h_ij);
90        let norm_sum = norm_z_ij + norm_t_ij + norm_g_ij + norm_h_ij;
91
92        if norm_sum > ep.beta * ep.beta {
93            return Err(VerifierError::NormSumExceeded {
94                norm: norm_sum,
95                allowed: ep.beta * ep.beta,
96            });
97        }
98
99        // 4. line 15: check Az ?= c_1 * t_1 + ... + c_r * t_r
100
101        let az = self.pp.commitment_scheme_a.matrix() * &proof.z;
102        let ct_sum = aggregate::calculate_z(&proof.t_i, &self.tr.random_c);
103
104        if az != ct_sum {
105            return Err(VerifierError::AzError {
106                computed: az,
107                expected: ct_sum,
108            });
109        }
110
111        // 5. lne 16: check <z, z> ?= \sum(g_ij * c_i * c_j)
112
113        let z_inner = proof.z.inner_product_poly_vector(&proof.z);
114        let sum_gij_cij = Self::calculate_gh_ci_cj(&proof.g_ij, &self.tr.random_c, ep.r);
115
116        if z_inner != sum_gij_cij {
117            return Err(VerifierError::ZInnerError {
118                computed: z_inner,
119                expected: sum_gij_cij,
120            });
121        }
122
123        // 6. line 17: check \sum(<\phi_i, z>c_i) ?= \sum(h_ij * c_i * c_j)
124
125        let phi_ct_aggr = aggregate::AggregationOne::get_phi_ct_aggr(
126            &self.st.phi_ct,
127            &self.tr.pi,
128            &self.tr.psi,
129            &self.tr.omega,
130            ep,
131        );
132        let phi_i = aggregate::AggregationTwo::get_phi_i(
133            &self.st.phi_constraint,
134            &phi_ct_aggr,
135            &self.tr.random_alpha,
136            &self.tr.random_beta,
137            ep,
138        );
139        let sum_phi_z_c = Self::calculate_phi_z_c(&phi_i, &self.tr.random_c, &proof.z);
140        let sum_hij_cij = Self::calculate_gh_ci_cj(&proof.h_ij, &self.tr.random_c, ep.r);
141
142        // Left side multiple by 2 because of when we calculate h_ij, we didn't apply the division (divided by 2)
143        if &sum_phi_z_c * &Zq::TWO != sum_hij_cij {
144            return Err(VerifierError::PhiError {
145                computed: &sum_phi_z_c * &Zq::TWO,
146                expected: sum_hij_cij,
147            });
148        }
149
150        // 7. line 18: check \sum(a_ij * g_ij) + \sum(h_ii) - b ?= 0
151
152        let a_ct_aggr = aggregate::AggregationOne::get_a_ct_aggr(&self.tr.psi, &self.st.a_ct, ep);
153        let a_primes = aggregate::AggregationTwo::get_a_i(
154            &self.st.a_constraint,
155            &a_ct_aggr,
156            &self.tr.random_alpha,
157            &self.tr.random_beta,
158            ep,
159        );
160        let b_primes = aggregate::AggregationTwo::get_b_i(
161            &self.st.b_constraint,
162            &proof.b_ct_aggr,
163            &self.tr.random_alpha,
164            &self.tr.random_beta,
165            ep,
166        );
167
168        if !Self::check_relation(
169            &RqMatrix::new(a_primes),
170            &b_primes,
171            &proof.g_ij,
172            &proof.h_ij,
173        ) {
174            return Err(VerifierError::RelationCheckFailed);
175        }
176
177        // 8. line 19: u_1 ?= \sum(\sum(B_ik * t_i^(k))) + \sum(\sum(C_ijk * g_ij^(k)))
178
179        let u_1 = &proof.u_1;
180        let mut outer_commitments = OuterCommitment::new(self.pp);
181        outer_commitments.compute_u1(
182            RqMatrix::new(proof.t_i.clone()),
183            DecompositionParameters::new(ep.b, ep.t_1).unwrap(),
184            proof.g_ij.clone(),
185            DecompositionParameters::new(ep.b, ep.t_2).unwrap(),
186        );
187
188        if proof.u_1 != outer_commitments.u_1 {
189            return Err(VerifierError::OuterCommitError {
190                computed: u_1.clone(),
191                expected: outer_commitments.u_1,
192            });
193        }
194
195        // 9. line 20: u_2 ?= \sum(\sum(D_ijk * h_ij^(k)))
196        outer_commitments.compute_u2(
197            proof.h_ij.clone(),
198            DecompositionParameters::new(ep.b, ep.t_1).unwrap(),
199        );
200
201        if proof.u_2 != outer_commitments.u_2 {
202            return Err(VerifierError::OuterCommitError {
203                computed: outer_commitments.u_2.clone(),
204                expected: proof.u_2.clone(),
205            });
206        }
207
208        Ok(true)
209    }
210
211    /// calculate the right hand side of line 16 or line 17, \sum(g_ij * c_i * c_j) or \sum(h_ij * c_i * c_j)
212    fn calculate_gh_ci_cj(x_ij: &RqMatrix, random_c: &RqVector, r: usize) -> Rq {
213        (0..r)
214            .map(|i| {
215                (0..r)
216                    .map(|j| {
217                        (x_ij.get_cell_symmetric(i, j) * random_c.get_elements()[i].clone())
218                            * random_c.get_elements()[j].clone()
219                    })
220                    .fold(Rq::zero(), |acc, x| acc + x)
221            })
222            .fold(Rq::zero(), |acc, x| acc + x)
223    }
224
225    /// calculate the left hand side of line 17, \sum(<\phi_z, z> * c_i)
226    fn calculate_phi_z_c(phi: &[RqVector], c: &RqVector, z: &RqVector) -> Rq {
227        phi.iter()
228            .zip(c.iter())
229            .map(|(phi_i, c_i)| &(phi_i.inner_product_poly_vector(z)) * c_i)
230            .fold(Rq::zero(), |acc, x| acc + x)
231    }
232
233    fn norm_squared(polys: &[Vec<RqVector>]) -> Zq {
234        polys.iter().fold(Zq::ZERO, |acc, poly| {
235            acc + poly
236                .iter()
237                .fold(Zq::ZERO, |acc, p| acc + p.compute_norm_squared())
238        })
239    }
240
241    /// line 18, page 18: check if \sum(a_{ij} * g_{ij}) + \sum(h_{ii}) - b ?= 0
242    /// in the verifier process, page 18 from the paper.
243    ///
244    /// param: a_primes: a_{ij}^{''(k)}
245    /// param: b_primes: b^{''(k)}
246    /// param: g: g_{ij}
247    /// param: h: h_{ii}
248    ///
249    /// return: true if the relation holds, false otherwise
250    pub fn check_relation(a_primes: &RqMatrix, b_primes: &Rq, g: &RqMatrix, h: &RqMatrix) -> bool {
251        let r = a_primes.get_elements().len();
252
253        let mut sum_a_primes_g = Rq::zero();
254        // walk only over the stored half: i ≤ j
255        for i in 0..r {
256            for j in 0..r {
257                sum_a_primes_g += a_primes.get_elements()[i].get_elements()[j].clone()
258                    * g.get_cell_symmetric(i, j);
259            }
260        }
261
262        let sum_h_ii = (0..r).fold(Rq::zero(), |acc, i| acc + h.get_cell_symmetric(i, i));
263
264        let b_primes2 = b_primes * &Zq::TWO;
265        let sum_a_primes_g2 = &sum_a_primes_g * &Zq::TWO;
266
267        sum_a_primes_g2 + sum_h_ii == b_primes2
268    }
269
270    fn check_b_0_aggr(
271        &self,
272        proof: &Proof,
273        ep: &EnvironmentParameters,
274    ) -> Result<bool, VerifierError> {
275        for k in 0..ep.kappa {
276            let b_0_poly = proof.b_ct_aggr.get_elements()[k].get_coefficients()[0];
277            let mut b_0: Zq = (0..ep.constraint_l)
278                .map(|l| self.tr.psi[k][l] * self.st.b_0_ct[l])
279                .sum();
280            let inner_omega_p = self.tr.omega[k].inner_product(proof.p.get_projection());
281            b_0 += inner_omega_p;
282            if b_0 != b_0_poly {
283                return Err(VerifierError::B0Mismatch {
284                    index: k,
285                    expected: b_0_poly,
286                    computed: b_0,
287                });
288            }
289        }
290
291        Ok(true)
292    }
293}
294
295#[cfg(test)]
296mod tests {
297    use super::*;
298    use crate::prover::{LabradorProver, Witness};
299
300    #[test]
301    fn test_verify() {
302        // set up example environment, use default set for testing.
303        let ep_1 = EnvironmentParameters::default();
304        // generate a random witness based on ep above
305        let witness_1 = Witness::new(&ep_1);
306        // generate public statements based on witness_1
307        let st: Statement = Statement::new(&witness_1, &ep_1);
308        // generate the common reference string matrices
309        let pp = AjtaiInstances::new(&ep_1);
310        // generate random challenges
311        let tr = Challenges::new(&ep_1);
312
313        // create a new prover
314        let prover = LabradorProver::new(&pp, &witness_1, &st, &tr);
315        let proof = prover.prove(&ep_1).unwrap();
316
317        // create a new verifier
318        let verifier = LabradorVerifier::new(&pp, &st, &tr);
319        let result = verifier.verify(&proof, &ep_1);
320        assert!(result.unwrap());
321    }
322}
labrador/verifier.rs

labrador/
verifier.rs
