labrador/
prover.rs

1use crate::commitments::ajtai_commitment;
2use crate::commitments::common_instances::AjtaiInstances;
3use crate::commitments::outer_commitments;
4use crate::commitments::outer_commitments::DecompositionParameters;
5use crate::commitments::CommitError;
6use crate::core::aggregate::FunctionsAggregation;
7use crate::core::aggregate::ZeroConstantFunctionsAggregation;
8use crate::core::garbage_polynomials;
9use crate::core::inner_product;
10use crate::core::jl::Projection;
11use crate::relation::env_params;
12use crate::relation::witness::Witness;
13use crate::relation::{env_params::EnvironmentParameters, statement::Statement};
14use crate::ring::rq_matrix::RqMatrix;
15use crate::ring::rq_vector::RqVector;
16use crate::ring::zq::Zq;
17use crate::transcript::LabradorTranscript;
18use crate::transcript::Sponge;
19use thiserror::Error;
20
21#[derive(Debug, Error)]
22pub enum ProverError {
23    /// Indicates that the L2 norm (squared) of the witness exceeded the allowed threshold.
24    #[error("invalid witness size: norm_squared {norm_squared}, allowed {allowed}")]
25    WitnessL2NormViolated { norm_squared: Zq, allowed: Zq },
26    #[error("Invalid Projection of index {index}. Expected {expected}, got {computed}")]
27    ProjectionError {
28        index: usize,
29        expected: Zq,
30        computed: Zq,
31    },
32    #[error("commitment failure")]
33    CommitError(#[from] ajtai_commitment::CommitError),
34    #[error("decomposition failure")]
35    DecompositionError(#[from] outer_commitments::DecompositionError),
36}
37
38pub struct LabradorProver<'a> {
39    params: &'a EnvironmentParameters,
40    crs: &'a AjtaiInstances,
41    witness: &'a Witness,
42    st: &'a Statement,
43    // Aggregation instances
44    constant_aggregator: ZeroConstantFunctionsAggregation<'a>,
45    funcs_aggregator: FunctionsAggregation<'a>,
46}
47
48impl<'a> LabradorProver<'a> {
49    pub fn new(
50        params: &'a EnvironmentParameters,
51        crs: &'a AjtaiInstances,
52        witness: &'a Witness,
53        st: &'a Statement,
54    ) -> Self {
55        Self {
56            params,
57            crs,
58            witness,
59            st,
60            constant_aggregator: ZeroConstantFunctionsAggregation::new(params),
61            funcs_aggregator: FunctionsAggregation::new(params),
62        }
63    }
64
65    fn compute_vector_ti(&self) -> Result<RqMatrix, CommitError> {
66        // Ajtai Commitments t_i = A * s_i
67        let commitments = self
68            .witness
69            .s
70            .iter()
71            .cloned()
72            .map(|s_i| self.crs.commitment_scheme_a.commit(&s_i))
73            .collect::<Result<Vec<_>, CommitError>>()?;
74
75        Ok(RqMatrix::new(commitments, false))
76    }
77
78    fn compute_u1<S: Sponge>(
79        &mut self,
80        transcript: &mut LabradorTranscript<S>,
81    ) -> Result<(RqMatrix, RqMatrix), ProverError> {
82        let t_i = self.compute_vector_ti()?;
83        // g_ij = <s_i, s_j>
84        let garbage_polynomial_g = garbage_polynomials::compute_g(&self.witness.s);
85        // calculate outer commitment u_1 = \sum(B_ik * t_i^(k)) + \sum(C_ijk * g_ij^(k))
86        let commitment_u1 = outer_commitments::compute_u1(
87            self.crs,
88            &t_i,
89            DecompositionParameters::new(self.params.b, self.params.t_1)?,
90            &garbage_polynomial_g,
91            DecompositionParameters::new(self.params.b, self.params.t_2)?,
92        );
93        transcript.set_u1(commitment_u1);
94        Ok((t_i, garbage_polynomial_g))
95    }
96
97    fn compute_p<S: Sponge>(&self, transcript: &mut LabradorTranscript<S>) -> Projection {
98        let projections = transcript.generate_projections(
99            env_params::SECURITY_PARAMETER,
100            self.params.rank,
101            self.params.multiplicity,
102        );
103        let vector_p = projections.compute_batch_projection(&self.witness.s);
104        transcript.set_vector_p(vector_p);
105        projections
106    }
107
108    fn compute_b_double_prime<S: Sponge>(
109        &mut self,
110        transcript: &mut LabradorTranscript<S>,
111        projections: &Projection,
112    ) {
113        let vector_psi =
114            transcript.generate_vector_psi(self.params.const_agg_length, self.params.constraint_l);
115        let vector_omega = transcript
116            .generate_vector_omega(self.params.const_agg_length, env_params::SECURITY_PARAMETER);
117        // first aggregation
118        self.constant_aggregator
119            .calculate_agg_a_double_prime(&vector_psi, &self.st.a_ct);
120        self.constant_aggregator.calculate_agg_phi_double_prime(
121            &self.st.phi_ct,
122            &projections.get_conjugated_projection_matrices(),
123            &vector_psi,
124            &vector_omega,
125        );
126        let b_ct_aggr = self
127            .constant_aggregator
128            .calculate_agg_b_double_prime(&self.witness.s);
129        transcript.set_vector_b_ct_aggr(b_ct_aggr);
130    }
131
132    fn compute_u2<S: Sponge>(
133        &mut self,
134        transcript: &mut LabradorTranscript<S>,
135    ) -> Result<RqMatrix, ProverError> {
136        let alpha_vector = transcript.generate_rq_vector(self.params.constraint_k);
137        let beta_vector = transcript.generate_rq_vector(self.params.const_agg_length);
138        self.funcs_aggregator.calculate_aggr_phi(
139            &self.st.phi_constraint,
140            self.constant_aggregator.get_phi_double_prime(),
141            &alpha_vector,
142            &beta_vector,
143        );
144
145        // Step 4: Calculate h_ij, u_2, and z starts: ---------------------------------------
146        let garbage_polynomial_h =
147            garbage_polynomials::compute_h(&self.witness.s, self.funcs_aggregator.get_appr_phi());
148        let commitment_u2 = outer_commitments::compute_u2(
149            self.crs,
150            &garbage_polynomial_h,
151            DecompositionParameters::new(self.params.b, self.params.t_1)?,
152        );
153        transcript.set_u2(commitment_u2);
154        Ok(garbage_polynomial_h)
155    }
156
157    // calculate z = c_1*s_1 + ... + c_r*s_r
158    fn compute_z<S: Sponge>(&mut self, transcript: &mut LabradorTranscript<S>) -> RqVector {
159        let challenges =
160            transcript.generate_challenges(env_params::OPERATOR_NORM, self.params.multiplicity);
161        let z =
162            inner_product::compute_linear_combination(&self.witness.s, challenges.get_elements());
163        z
164    }
165
166    /// all prove steps are from page 17
167    pub fn prove<S: Sponge>(&mut self) -> Result<LabradorTranscript<S>, ProverError> {
168        // Generate random challenges used between prover and verifier
169        let mut transcript = LabradorTranscript::new(S::default());
170
171        // Step 1: Outer commitments u_1 starts: --------------------------------------------
172        let (t_i, garbage_polynomial_g) = self.compute_u1(&mut transcript)?;
173        // Step 1: Outer commitments u_1 ends: ----------------------------------------------
174
175        // Step 2: JL projection starts: ----------------------------------------------------
176        let projections = self.compute_p(&mut transcript);
177        // Step 2: JL projection ends: ------------------------------------------------------
178
179        // Step 3: Aggregation starts: --------------------------------------------------------------
180        self.compute_b_double_prime(&mut transcript, &projections);
181
182        // second aggregation
183
184        // Aggregation ends: ----------------------------------------------------------------
185        let garbage_polynomial_h = self.compute_u2(&mut transcript)?;
186
187        let z = self.compute_z(&mut transcript);
188
189        transcript.set_recursive_part(z, t_i, garbage_polynomial_g, garbage_polynomial_h);
190
191        // Step 4: Calculate h_ij, u_2, and z ends: -----------------------------------------
192
193        Ok(transcript)
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use super::*;
200    use crate::transcript::sponges::shake::ShakeSponge;
201
202    #[test]
203    fn test_prove() {
204        // set up example environment parameters, use default set for testing.
205        let ep_1 = EnvironmentParameters::default();
206        // generate a random witness based on environment parameters above
207        let witness_1 = Witness::new(ep_1.rank, ep_1.multiplicity, ep_1.beta);
208        // generate public statement based on witness_1
209        let st: Statement = Statement::new(&witness_1, &ep_1);
210        // generate the common reference string matrices A, B, C, D
211        let crs: AjtaiInstances = AjtaiInstances::new(&ep_1);
212
213        // create a new prover
214        let mut prover = LabradorProver::new(&ep_1, &crs, &witness_1, &st);
215        let _: LabradorTranscript<ShakeSponge> = prover.prove().unwrap();
216    }
217}
labrador/prover.rs

labrador/
prover.rs
