curdleproofs/
same_multiscalar_argument.rs

1#![allow(non_snake_case)]
2use ark_bls12_381::{Fr, G1Affine, G1Projective};
3use ark_ec::AffineCurve;
4use ark_ec::ProjectiveCurve;
5use ark_ff::PrimeField;
6use ark_ff::{batch_inversion, Field, One};
7use ark_std::rand::RngCore;
8
9use crate::transcript::CurdleproofsTranscript;
10use merlin::Transcript;
11
12use crate::errors::ProofError;
13use crate::msm_accumulator::MsmAccumulator;
14use crate::util::{
15    generate_blinders, get_verification_scalars_bitstring, msm, msm_from_projective,
16};
17
18/// A $SameMsm$ proof object
19#[derive(Clone, Debug)]
20pub struct SameMultiscalarProof {
21    B_a: G1Projective,
22    B_t: G1Projective,
23    B_u: G1Projective,
24
25    vec_L_A: Vec<G1Projective>,
26    vec_L_T: Vec<G1Projective>,
27    vec_L_U: Vec<G1Projective>,
28    vec_R_A: Vec<G1Projective>,
29    vec_R_T: Vec<G1Projective>,
30    vec_R_U: Vec<G1Projective>,
31
32    x_final: Fr,
33}
34
35impl SameMultiscalarProof {
36    /// Create a $SameMsm$ proof
37    ///
38    /// # Arguments
39    ///
40    /// * `crs_G_vec` - $\bm{G}$ CRS vector
41    /// * `A` - commitment to `vec_x` under `crs_G_vec`
42    /// * `Z_t` - commitment to `vec_x` under `vec_T`
43    /// * `Z_u` - commitment to `vec_x` under `vec_U`
44    /// * `vec_T` - base points $\bm{T}$
45    /// * `vec_U` - base points $\bm{U}$
46    /// * `vec_x` - scalar vector (*witness*)
47    pub fn new<T: RngCore>(
48        mut crs_G_vec: Vec<G1Affine>,
49
50        A: G1Projective,
51        Z_t: G1Projective,
52        Z_u: G1Projective,
53        mut vec_T: Vec<G1Affine>,
54        mut vec_U: Vec<G1Affine>,
55
56        mut vec_x: Vec<Fr>,
57
58        transcript: &mut Transcript,
59        rng: &mut T,
60    ) -> SameMultiscalarProof {
61        let mut n = vec_x.len();
62        let lg_n = ark_std::log2(n) as usize;
63
64        let mut vec_L_T = Vec::with_capacity(lg_n);
65        let mut vec_R_T = Vec::with_capacity(lg_n);
66        let mut vec_L_U = Vec::with_capacity(lg_n);
67        let mut vec_R_U = Vec::with_capacity(lg_n);
68        let mut vec_L_A = Vec::with_capacity(lg_n);
69        let mut vec_R_A = Vec::with_capacity(lg_n);
70
71        let vec_r: Vec<Fr> = generate_blinders(rng, n);
72
73        let B_a = msm(&crs_G_vec, &vec_r);
74        let B_t = msm(&vec_T, &vec_r);
75        let B_u = msm(&vec_U, &vec_r);
76
77        transcript.append_list(b"same_msm_step1", &[&A, &Z_t, &Z_u]);
78        transcript.append_list(b"same_msm_step1", &[&vec_T, &vec_U]);
79        transcript.append_list(b"same_msm_step1", &[&B_a, &B_t, &B_u]);
80        let alpha = transcript.get_and_append_challenge(b"same_msm_alpha");
81
82        for i in 0..n {
83            vec_x[i] = vec_r[i] + (alpha * vec_x[i]);
84        }
85
86        let mut slice_x = &mut vec_x[..];
87        let mut slice_T = &mut vec_T[..];
88        let mut slice_U = &mut vec_U[..];
89        let mut slice_G = &mut crs_G_vec[..];
90
91        // Step 2: log(n) rounds of recursion
92        while slice_x.len() > 1 {
93            n /= 2;
94
95            let (x_L, x_R) = slice_x.split_at_mut(n);
96            let (T_L, T_R) = slice_T.split_at_mut(n);
97            let (U_L, U_R) = slice_U.split_at_mut(n);
98            let (G_L, G_R) = slice_G.split_at_mut(n);
99
100            let L_A = msm(G_R, x_L);
101            let L_T = msm(T_R, x_L);
102            let L_U = msm(U_R, x_L);
103            let R_A = msm(G_L, x_R);
104            let R_T = msm(T_L, x_R);
105            let R_U = msm(U_L, x_R);
106
107            vec_L_A.push(L_A);
108            vec_L_T.push(L_T);
109            vec_L_U.push(L_U);
110            vec_R_A.push(R_A);
111            vec_R_T.push(R_T);
112            vec_R_U.push(R_U);
113
114            transcript.append_list(b"same_msm_loop", &[&L_A, &L_T, &L_U, &R_A, &R_T, &R_U]);
115            let gamma = transcript.get_and_append_challenge(b"same_msm_gamma");
116            let gamma_inv = gamma.inverse().expect("gamma must have an inverse");
117
118            // Fold vectors and basis
119            for i in 0..n {
120                x_L[i] += gamma_inv * x_R[i];
121                T_L[i] = T_L[i] + T_R[i].mul(gamma.into_repr()).into_affine();
122                U_L[i] = U_L[i] + U_R[i].mul(gamma.into_repr()).into_affine();
123                G_L[i] = G_L[i] + G_R[i].mul(gamma.into_repr()).into_affine();
124            }
125            slice_x = x_L;
126            slice_T = T_L;
127            slice_U = U_L;
128            slice_G = G_L;
129        }
130
131        SameMultiscalarProof {
132            B_a,
133            B_t,
134            B_u,
135            vec_L_A,
136            vec_L_T,
137            vec_L_U,
138            vec_R_A,
139            vec_R_T,
140            vec_R_U,
141            x_final: slice_x[0],
142        }
143    }
144
145    /// Generate verification scalars for the $SameMsm$ [verifier optimization](crate::notes::optimizations)
146    fn verification_scalars(
147        &self,
148        n: usize,
149        transcript: &mut Transcript,
150    ) -> Result<(Vec<Fr>, Vec<Fr>, Vec<Fr>), ProofError> {
151        let lg_n = self.vec_L_A.len();
152        if lg_n >= 32 {
153            return Err(ProofError::VerificationError);
154        }
155        if n != (1 << lg_n) {
156            return Err(ProofError::VerificationError);
157        }
158
159        let bitstring = get_verification_scalars_bitstring(n, lg_n);
160
161        // 1. Recompute x_k,...,x_1 based on the proof transcript
162        let mut challenges: Vec<Fr> = Vec::with_capacity(lg_n);
163        for i in 0..self.vec_L_A.len() {
164            transcript.append_list(
165                b"same_msm_loop",
166                &[
167                    &self.vec_L_A[i],
168                    &self.vec_L_T[i],
169                    &self.vec_L_U[i],
170                    &self.vec_R_A[i],
171                    &self.vec_R_T[i],
172                    &self.vec_R_U[i],
173                ],
174            );
175            challenges.push(transcript.get_and_append_challenge(b"same_msm_gamma"));
176        }
177
178        // 2. Compute 1/(x_k...x_1) and 1/x_k, ..., 1/x_1
179        let mut challenges_inv: Vec<Fr> = challenges.clone();
180        batch_inversion(&mut challenges_inv);
181
182        // 3. Compute s values using the bitstring
183        let mut vec_s: Vec<Fr> = Vec::with_capacity(n);
184        for i in 0..n {
185            vec_s.push(Fr::one());
186            for j in 0..bitstring[i].len() {
187                vec_s[i] *= challenges[bitstring[i][j]]
188            }
189        }
190
191        Ok((challenges, challenges_inv, vec_s))
192    }
193
194    /// Verify a $SameMsm$ proof
195    ///
196    /// # Arguments
197    ///
198    /// * `crs_G_vec` - $\bm{G}$ CRS vector
199    /// * `A` - commitment to `vec_x` under `crs_G_vec`
200    /// * `Z_t` - commitment to `vec_x` under `vec_T`
201    /// * `Z_u` - commitment to `vec_x` under `vec_U`
202    /// * `vec_T` - base points $\bm{T}$
203    /// * `vec_U` - base points $\bm{U}$
204    pub fn verify<T: RngCore>(
205        &self,
206        crs_G_vec: &[G1Affine],
207
208        A: G1Projective,
209        Z_t: G1Projective,
210        Z_u: G1Projective,
211        vec_T: &Vec<G1Affine>,
212        vec_U: &Vec<G1Affine>,
213
214        transcript: &mut Transcript,
215        msm_accumulator: &mut MsmAccumulator,
216        rng: &mut T,
217    ) -> Result<(), ProofError> {
218        let n = vec_T.len();
219
220        // Step 1
221        transcript.append_list(b"same_msm_step1", &[&A, &Z_t, &Z_u]);
222        transcript.append_list(b"same_msm_step1", &[vec_T, vec_U]);
223        transcript.append_list(b"same_msm_step1", &[&self.B_a, &self.B_t, &self.B_u]);
224        let alpha = transcript.get_and_append_challenge(b"same_msm_alpha");
225
226        // Step 2
227        let (vec_gamma, vec_gamma_inv, vec_s) = self.verification_scalars(n, transcript)?;
228
229        // Cmopute vector x*vec_s for the right-hand-side
230        let vec_x_times_s: Vec<Fr> = vec_s.iter().map(|s_i| self.x_final * *s_i).collect();
231
232        // Step 3
233        let A_a = self.B_a + A.mul(alpha.into_repr());
234        let Z_t_a = self.B_t + Z_t.mul(alpha.into_repr());
235        let Z_u_a = self.B_u + Z_u.mul(alpha.into_repr());
236
237        let point_lhs = msm_from_projective(&self.vec_L_A, &vec_gamma)
238            + A_a
239            + msm_from_projective(&self.vec_R_A, &vec_gamma_inv);
240        msm_accumulator.accumulate_check(&point_lhs, &vec_x_times_s, crs_G_vec, rng);
241
242        let point_lhs = msm_from_projective(&self.vec_L_T, &vec_gamma)
243            + Z_t_a
244            + msm_from_projective(&self.vec_R_T, &vec_gamma_inv);
245        msm_accumulator.accumulate_check(&point_lhs, &vec_x_times_s, vec_T, rng);
246
247        let point_lhs = msm_from_projective(&self.vec_L_U, &vec_gamma)
248            + Z_u_a
249            + msm_from_projective(&self.vec_R_U, &vec_gamma_inv);
250        msm_accumulator.accumulate_check(&point_lhs, &vec_x_times_s, vec_U, rng);
251        Ok(())
252    }
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258    use ark_ec::ProjectiveCurve;
259    use ark_std::rand::{rngs::StdRng, Rng, SeedableRng};
260    use ark_std::UniformRand;
261    use core::iter;
262
263    #[test]
264    fn test_same_msm_argument() {
265        let mut rng = StdRng::seed_from_u64(0u64);
266        let mut transcript_prover = merlin::Transcript::new(b"same_msm");
267
268        let n = 128;
269
270        let crs_G_vec: Vec<_> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
271            .take(n)
272            .collect();
273
274        let vec_T: Vec<_> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
275            .take(n)
276            .collect();
277        let vec_U: Vec<_> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
278            .take(n)
279            .collect();
280
281        let vec_x: Vec<Fr> = iter::repeat_with(|| rng.gen()).take(n).collect();
282
283        let A = msm(&crs_G_vec, &vec_x);
284        let Z_t = msm(&vec_T, &vec_x);
285        let Z_u = msm(&vec_U, &vec_x);
286
287        let proof = SameMultiscalarProof::new(
288            crs_G_vec.clone(),
289            A.clone(),
290            Z_t.clone(),
291            Z_u.clone(),
292            vec_T.clone(),
293            vec_U.clone(),
294            vec_x,
295            &mut transcript_prover,
296            &mut rng,
297        );
298
299        // Reset the FS
300        let mut transcript_verifier = merlin::Transcript::new(b"same_msm");
301        let mut msm_accumulator = MsmAccumulator::new();
302
303        assert!(proof
304            .verify(
305                &crs_G_vec,
306                A,
307                Z_t,
308                Z_u,
309                &vec_T,
310                &vec_U,
311                &mut transcript_verifier,
312                &mut msm_accumulator,
313                &mut rng,
314            )
315            .is_ok());
316
317        assert!(msm_accumulator.verify().is_ok())
318    }
319}
curdleproofs/same_multiscalar_argument.rs

curdleproofs/
same_multiscalar_argument.rs
