labrador/
prover.rs

1use crate::core::{
2    aggregate,
3    challenge_set::ChallengeSet,
4    crs::PublicPrams,
5    env_params::EnvironmentParameters,
6    jl::{ProjectionMatrix, Projections},
7    statement::Statement,
8};
9use crate::ring::poly::{PolyVector, ZqVector};
10use crate::ring::zq::Zq;
11use rand::rng;
12
13/// explicitly set the deg_bound_d to D == deg_bound_d, which is 64
14const D: usize = 64;
15
16#[derive(Debug)]
17pub enum ProverError {
18    /// Indicates that the L2 norm (squared) of the witness exceeded the allowed threshold.
19    WitnessL2NormViolated { norm_squared: Zq, allowed: Zq },
20    ProjectionError {
21        index: usize,
22        expected: Zq,
23        computed: Zq,
24    },
25}
26
27// Proof contains the parameters will be sent to verifier
28// All parameters are from tr, line 2 on page 18
29pub struct Proof {
30    pub u_1: PolyVector,
31    pub p: Projections,
32    pub b_ct_aggr: PolyVector,
33    pub u_2: PolyVector,
34    pub z: PolyVector,
35    pub t_i: Vec<PolyVector>,
36    pub g_ij: Vec<PolyVector>,
37    pub h_ij: Vec<PolyVector>,
38}
39
40// pub struct Challenges just for testing, should be replaced by the Transcript
41pub struct Challenges {
42    pub pi: Vec<Vec<ZqVector>>,
43    pub psi: Vec<ZqVector>,
44    pub omega: Vec<ZqVector>,
45    pub random_alpha: PolyVector,
46    pub random_beta: PolyVector,
47    pub random_c: PolyVector,
48}
49
50impl Challenges {
51    pub fn new(ep: &EnvironmentParameters) -> Self {
52        // generate random psi with size: k * constraint_l, each element is Zq
53        let psi: Vec<ZqVector> = (0..ep.k)
54            .map(|_| ZqVector::random(&mut rng(), ep.constraint_l))
55            .collect();
56
57        // generate randm omega is with size: k * lambda2, each element is Zq
58        let omega: Vec<ZqVector> = (0..ep.k)
59            .map(|_| ZqVector::random(&mut rng(), ep.lambda2))
60            .collect();
61
62        // \pi is from JL projection, pi contains r matrices and each matrix: security_level2 * (n*d), (security_level2 is 256 in the paper).
63        let pi: Vec<Vec<ZqVector>> = Self::get_pi(ep.r, ep.n);
64
65        // generate random alpha and beta from challenge set
66        let cs_alpha: ChallengeSet = ChallengeSet::new(ep.deg_bound_d);
67        let random_alpha: PolyVector = (0..ep.constraint_k)
68            .map(|_| cs_alpha.get_challenges().clone())
69            .collect();
70
71        let cs_beta: ChallengeSet = ChallengeSet::new(ep.deg_bound_d);
72        let random_beta: PolyVector = (0..ep.constraint_k)
73            .map(|_| cs_beta.get_challenges().clone())
74            .collect();
75
76        let cs_c: ChallengeSet = ChallengeSet::new(ep.deg_bound_d);
77        let random_c: PolyVector = (0..ep.r).map(|_| cs_c.get_challenges().clone()).collect();
78
79        Self {
80            pi,
81            psi,
82            omega,
83            random_alpha,
84            random_beta,
85            random_c,
86        }
87    }
88
89    pub fn get_pi(r: usize, n: usize) -> Vec<Vec<ZqVector>> {
90        (0..r)
91            .map(|_| ProjectionMatrix::<D>::new(n).get_matrix().clone())
92            .collect()
93    }
94}
95pub struct Witness {
96    pub s: Vec<PolyVector>,
97}
98
99impl Witness {
100    pub fn new(ep: &EnvironmentParameters) -> Self {
101        let s = (0..ep.r)
102            .map(|_| PolyVector::random_ternary(ep.n, ep.deg_bound_d))
103            .collect();
104        Self { s }
105    }
106}
107
108pub struct LabradorProver<'a> {
109    pub pp: &'a PublicPrams,
110    pub witness: &'a Witness,
111    pub st: &'a Statement,
112    pub tr: &'a Challenges,
113}
114
115impl<'a> LabradorProver<'a> {
116    pub fn new(
117        pp: &'a PublicPrams,
118        witness: &'a Witness,
119        st: &'a Statement,
120        tr: &'a Challenges,
121    ) -> Self {
122        Self {
123            pp,
124            witness,
125            st,
126            tr,
127        }
128    }
129
130    /// all prove steps are from page 17
131    pub fn prove(&self, ep: &EnvironmentParameters) -> Result<Proof, ProverError> {
132        // check the L2 norm of the witness
133        // not sure whether this should be handled during the proving or managed by the witness generator.
134        Self::check_witness_l2norm(self, ep).unwrap();
135        // Step 1: Outer commitments u_1 starts: --------------------------------------------
136
137        // Ajtai Commitments t_i = A * s_i
138        let matrix_a = &self.pp.matrix_a;
139        let t_i: Vec<PolyVector> = self.witness.s.iter().map(|s_i| s_i * matrix_a).collect();
140
141        // decompose t_i into t_i^(0) + ... + t_i^(t_1-1) * b_1^(t_1-1)
142        let t_ij: Vec<Vec<PolyVector>> = t_i
143            .iter()
144            .map(|i| PolyVector::decompose(i, ep.b, ep.t_1))
145            .collect();
146        // calculate garbage polynomial g = <s_i, s_j>
147        let g_gp: Vec<PolyVector> = aggregate::calculate_gij(&self.witness.s, ep.r);
148        // decompose g_gp into g_ij = g_ij^(0) + ... + g_ij^(t_2-1) * b_2^(t_2=1)
149        let g_ij: Vec<Vec<PolyVector>> = g_gp
150            .iter()
151            .map(|i| PolyVector::decompose(i, ep.b, ep.t_2))
152            .collect();
153        let matrix_b = &self.pp.matrix_b;
154        let matrix_c = &self.pp.matrix_c;
155        // calculate outer commitment u_1 = \sum(B_ik * t_i^(k)) + \sum(C_ijk * g_ij^(k))
156        let u_1 = aggregate::calculate_u_1(matrix_b, matrix_c, &t_ij, &g_ij, ep);
157
158        // Step 1: Outer commitments u_1 ends: ----------------------------------------------
159
160        // Step 2: JL projection starts: ----------------------------------------------------
161
162        // JL projection p_j + check p_j = ct(sum(<\sigma_{-1}(pi_i^(j)), s_i>))
163        let matrices = &self.tr.pi;
164        let p = Projections::new(matrices, &self.witness.s);
165
166        // Notice that this check is resource-intensive due to the multiplication of two ZqVector<256> instances,
167        // followed by the removal of high-degree terms. It might not be a necessary check.
168        Self::check_projection(self, p.get_projection()).unwrap();
169
170        // Step 2: JL projection ends: ------------------------------------------------------
171
172        // Step 3: Aggregation starts: --------------------------------------------------------------
173
174        // first aggregation
175        let aggr_1 = aggregate::AggregationOne::new(self.witness, self.st, ep, self.tr);
176        // second aggregation
177        let aggr_2 = aggregate::AggregationTwo::new(&aggr_1, self.st, ep, self.tr);
178
179        // Aggregation ends: ----------------------------------------------------------------
180
181        // Step 4: Calculate h_ij, u_2, and z starts: ---------------------------------------
182
183        let phi_i = aggr_2.phi_i;
184        let h_gp = aggregate::calculate_hij(&phi_i, &self.witness.s, ep);
185        // decompose h_gp into h_ij = h_ij^(0) + ... + h_ij^(t_1-1) * b_1^(t_1-1)
186        let h_ij: Vec<Vec<PolyVector>> = h_gp
187            .iter()
188            .map(|i| PolyVector::decompose(i, ep.b, ep.t_1))
189            .collect();
190        // Outer commitments: u_2
191        let matrix_d = &self.pp.matrix_d;
192        // calculate outer commitment u_2 = \sum(D_ijk * h_ij^(k))
193        let u_2 = aggregate::calculate_u_2(matrix_d, &h_ij, ep);
194        // calculate z = c_1*s_1 + ... + c_r*s_r
195        let z = aggregate::calculate_z(&self.witness.s, &self.tr.random_c);
196
197        // Step 4: Calculate h_ij, u_2, and z ends: -----------------------------------------
198
199        Ok(Proof {
200            u_1,
201            p,
202            b_ct_aggr: aggr_1.b_ct_aggr,
203            u_2,
204            z,
205            t_i,
206            g_ij: g_gp,
207            h_ij: h_gp,
208        })
209    }
210
211    /// check p_j? = ct(sum(<σ−1(pi_i^(j)), s_i>))
212    fn check_projection(&self, p: &ZqVector) -> Result<bool, ProverError> {
213        let s_coeffs: Vec<ZqVector> = self
214            .witness
215            .s
216            .iter()
217            .map(|s_i| {
218                s_i.iter()
219                    .flat_map(|s_i_p| s_i_p.get_coeffs().clone())
220                    .collect()
221            })
222            .collect();
223
224        for (j, &p_j) in p.iter().enumerate() {
225            let mut poly = ZqVector::zero(p.len());
226            for (i, s_i) in s_coeffs.iter().enumerate() {
227                let pi_ele = &self.tr.pi[i][j];
228                let pi_ele_ca = &pi_ele.conjugate_automorphism();
229                poly = &poly + &(pi_ele_ca * s_i);
230            }
231
232            if poly.get_coeffs()[0] != p_j {
233                return Err(ProverError::ProjectionError {
234                    index: j,
235                    expected: p_j,
236                    computed: poly.get_coeffs()[0],
237                });
238            }
239        }
240
241        Ok(true)
242    }
243
244    /// check the L2 norm of the witness, || s_i || <= beta
245    fn check_witness_l2norm(&self, ep: &EnvironmentParameters) -> Result<bool, ProverError> {
246        let beta2 = ep.beta * ep.beta;
247        for polys in &self.witness.s {
248            let witness_l2norm_squared = PolyVector::compute_norm_squared(polys);
249            if witness_l2norm_squared > beta2 {
250                return Err(ProverError::WitnessL2NormViolated {
251                    norm_squared: witness_l2norm_squared,
252                    allowed: beta2,
253                });
254            }
255        }
256        Ok(true)
257    }
258}
259
260#[cfg(test)]
261mod tests {
262    use super::*;
263
264    #[test]
265    fn test_prove() {
266        // set up example environment parameters, use default set for testing.
267        let ep_1 = EnvironmentParameters::default();
268        // generate a random witness based on environment parameters above
269        let witness_1 = Witness::new(&ep_1);
270        // generate public statement based on witness_1
271        let st: Statement = Statement::new(&witness_1, &ep_1);
272        // generate the common reference string matrices A, B, C, D
273        let pp = PublicPrams::new(&ep_1);
274        // generate random challenges used between prover and verifier.
275        let tr = Challenges::new(&ep_1);
276
277        // create a new prover
278        let prover = LabradorProver::new(&pp, &witness_1, &st, &tr);
279        let _proof = prover.prove(&ep_1).unwrap();
280    }
281}
labrador/prover.rs

labrador/
prover.rs
