curdleproofs/
same_permutation_argument.rs

1#![allow(non_snake_case)]
2use core::iter;
3
4use ark_bls12_381::{Fr, G1Affine, G1Projective};
5use ark_ec::group::Group;
6use ark_ec::ProjectiveCurve;
7use ark_ff::PrimeField;
8use ark_std::rand::RngCore;
9
10use crate::transcript::CurdleproofsTranscript;
11use merlin::Transcript;
12
13use crate::errors::ProofError;
14use crate::grand_product_argument::GrandProductProof;
15use crate::msm_accumulator::MsmAccumulator;
16use crate::util::{get_permutation, msm};
17
18/// A same permutation proof object
19#[derive(Clone, Debug)]
20pub struct SamePermutationProof {
21    B: G1Projective,
22
23    grand_product_proof: GrandProductProof,
24}
25
26impl SamePermutationProof {
27    /// Create a same permutation proof
28    ///
29    /// # Arguments
30    ///
31    /// * `crs_G_vec` - $\bm{g}$ CRS vector
32    /// * `crs_H_vec` - $\bm{h}$ CRS vector
33    /// * `crs_U` - $\bm{H}$ CRS element
34    /// * `A` - commitment to permuted `vec_a`
35    /// * `M` - commitment to `permutation`
36    /// * `vec_a` - scalar vector
37    /// * `permutation` - shuffle permutation (*witness*)
38    /// * `vec_a_blinders` - blinders for `vec_a` (*witness*)
39    /// * `vec_m_blinders` - blinders for `vec_m` (*witness*)
40    pub fn new<T: RngCore>(
41        crs_G_vec: &Vec<G1Affine>,
42        crs_H_vec: &Vec<G1Affine>,
43        crs_U: &G1Projective, // This is actually H in the paper
44
45        A: G1Projective,
46        M: G1Projective,
47        vec_a: &Vec<Fr>,
48
49        permutation: Vec<u32>,
50        vec_a_blinders: Vec<Fr>, // vec_r_a in the paper
51        vec_m_blinders: Vec<Fr>, // vec_r_m in the paper
52
53        transcript: &mut Transcript,
54        rng: &mut T,
55    ) -> SamePermutationProof {
56        let n_blinders = vec_a_blinders.len();
57        let ell = crs_G_vec.len();
58
59        // Step 1
60        transcript.append_list(b"same_perm_step1", &[&A, &M]);
61        transcript.append_list(b"same_perm_step1", &[vec_a]);
62        let alpha = transcript.get_and_append_challenge(b"same_perm_alpha");
63        let beta = transcript.get_and_append_challenge(b"same_perm_beta");
64
65        // Step 2
66        let vec_a_permuted = get_permutation(vec_a, &permutation);
67        let permutation_as_fr = permutation.iter().map(|s| Fr::from(*s));
68        let permuted_polynomial_factors: Vec<Fr> = vec_a_permuted
69            .iter()
70            .zip(permutation_as_fr)
71            .map(|(a, m)| *a + m * alpha + beta)
72            .collect();
73        let gprod_result: Fr = permuted_polynomial_factors.iter().product();
74
75        let vec_beta_repeated: Vec<Fr> = iter::repeat(beta).take(ell).collect();
76        let B = A + M.mul(alpha.into_repr()) + msm(crs_G_vec, &vec_beta_repeated);
77
78        let mut vec_b_blinders = Vec::with_capacity(n_blinders);
79        for i in 0..n_blinders {
80            vec_b_blinders.push(vec_a_blinders[i] + alpha * vec_m_blinders[i]);
81        }
82
83        let grand_product_proof = GrandProductProof::new(
84            crs_G_vec,
85            crs_H_vec,
86            crs_U,
87            B,
88            gprod_result,
89            permuted_polynomial_factors,
90            vec_b_blinders,
91            transcript,
92            rng,
93        );
94
95        SamePermutationProof {
96            B,
97            grand_product_proof,
98        }
99    }
100
101    /// Verify a same permutation proof
102    ///
103    /// # Arguments
104    ///
105    /// * `crs_G_vec` - $\bm{g}$ CRS vector
106    /// * `crs_H_vec` - $\bm{h}$ CRS vector
107    /// * `crs_U` - $\bm{H}$ CRS element
108    /// * `A` - commitment to permuted `vec_a`
109    /// * `M` - commitment to `permutation`
110    /// * `vec_a` - scalar vector
111    pub fn verify<T: RngCore>(
112        &self,
113
114        crs_G_vec: &Vec<G1Affine>,
115        crs_H_vec: &Vec<G1Affine>,
116        crs_U: &G1Projective, // This is actually H in the paper
117        crs_G_sum: &G1Affine,
118        crs_H_sum: &G1Affine,
119
120        A: &G1Projective,
121        M: &G1Projective,
122        vec_a: &Vec<Fr>,
123
124        n_blinders: usize,
125        transcript: &mut Transcript,
126        msm_accumulator: &mut MsmAccumulator,
127
128        rng: &mut T,
129    ) -> Result<(), ProofError> {
130        let ell = crs_G_vec.len();
131
132        // Step 1
133        transcript.append_list(b"same_perm_step1", &[A, M]);
134        transcript.append_list(b"same_perm_step1", &[vec_a]);
135        let alpha = transcript.get_and_append_challenge(b"same_perm_alpha");
136        let beta = transcript.get_and_append_challenge(b"same_perm_beta");
137
138        // Step 2
139        let range_as_fr = (0..ell as u32).map(Fr::from);
140        let polynomial_factors = vec_a
141            .iter()
142            .zip(range_as_fr)
143            .map(|(a, i)| *a + i * alpha + beta);
144        let gprod_result: Fr = polynomial_factors.product();
145
146        let vec_beta_repeated: Vec<Fr> = iter::repeat(beta).take(ell).collect();
147
148        msm_accumulator.accumulate_check(
149            &(self.B - A - M.mul(&alpha)),
150            &vec_beta_repeated,
151            crs_G_vec,
152            rng,
153        );
154
155        self.grand_product_proof.verify(
156            crs_G_vec,
157            crs_H_vec,
158            crs_U,
159            crs_G_sum,
160            crs_H_sum,
161            self.B,
162            gprod_result,
163            n_blinders,
164            transcript,
165            msm_accumulator,
166            rng,
167        )?;
168
169        Ok(())
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176    use ark_ec::ProjectiveCurve;
177    use ark_std::rand::prelude::SliceRandom;
178    use ark_std::rand::{rngs::StdRng, Rng, SeedableRng};
179    use ark_std::UniformRand;
180    use core::iter;
181
182    use crate::util::generate_blinders;
183
184    #[test]
185    fn test_same_perm_argument() {
186        let mut rng = StdRng::seed_from_u64(0u64);
187        let mut transcript_prover = merlin::Transcript::new(b"sameperm");
188
189        let n = 128;
190        let n_blinders = 4;
191        let ell = n - n_blinders;
192
193        let crs_G_vec: Vec<_> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
194            .take(ell)
195            .collect();
196        let crs_H_vec: Vec<_> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
197            .take(n_blinders)
198            .collect();
199        let crs_U = G1Projective::rand(&mut rng);
200        let crs_G_sum: G1Affine = crs_G_vec.iter().sum();
201        let crs_H_sum: G1Affine = crs_H_vec.iter().sum();
202
203        let vec_a_blinders = generate_blinders(&mut rng, n_blinders);
204        let vec_m_blinders = generate_blinders(&mut rng, n_blinders);
205
206        let mut permutation: Vec<u32> = (0..ell as u32).collect();
207        permutation.shuffle(&mut rng);
208        let permutation_as_fr: Vec<Fr> = permutation.iter().map(|s| Fr::from(*s)).collect();
209
210        let vec_a: Vec<Fr> = iter::repeat_with(|| rng.gen()).take(ell).collect();
211        let vec_a_permuted = get_permutation(&vec_a, &permutation);
212
213        let A = msm(&crs_G_vec, &vec_a_permuted) + msm(&crs_H_vec, &vec_a_blinders);
214        let M = msm(&crs_G_vec, &permutation_as_fr) + msm(&crs_H_vec, &vec_m_blinders);
215
216        let same_perm_proof = SamePermutationProof::new(
217            &crs_G_vec,
218            &crs_H_vec,
219            &crs_U,
220            A,
221            M,
222            &vec_a,
223            permutation,
224            vec_a_blinders,
225            vec_m_blinders,
226            &mut transcript_prover,
227            &mut rng,
228        );
229
230        // Reset the FS
231        let mut transcript_verifier = merlin::Transcript::new(b"sameperm");
232        let mut msm_accumulator = MsmAccumulator::new();
233
234        assert!(same_perm_proof
235            .verify(
236                &crs_G_vec,
237                &crs_H_vec,
238                &crs_U,
239                &crs_G_sum,
240                &crs_H_sum,
241                &A,
242                &M,
243                &vec_a,
244                n_blinders,
245                &mut transcript_verifier,
246                &mut msm_accumulator,
247                &mut rng,
248            )
249            .is_ok());
250
251        assert!(msm_accumulator.verify().is_ok());
252
253        ////////////////////////////////////////////////////
254        // Reset the FS
255        let mut transcript_verifier = merlin::Transcript::new(b"sameperm");
256        let mut msm_accumulator = MsmAccumulator::new();
257
258        assert!(same_perm_proof
259            .verify(
260                &crs_G_vec,
261                &crs_H_vec,
262                &crs_U,
263                &crs_G_sum,
264                &crs_H_sum,
265                &A,
266                &M,
267                &vec_a,
268                n_blinders,
269                &mut transcript_verifier,
270                &mut msm_accumulator,
271                &mut rng,
272            )
273            .is_ok());
274
275        assert!(msm_accumulator.verify().is_ok())
276    }
277}
curdleproofs/same_permutation_argument.rs

curdleproofs/
same_permutation_argument.rs
