kimchi_stubs/
urs_utils.rs

1use ark_ec::{CurveGroup, VariableBaseMSM};
2use ark_ff::{batch_inversion, One, PrimeField, UniformRand, Zero};
3use poly_commitment::{
4    commitment::{b_poly_coefficients, CommitmentCurve},
5    ipa::SRS,
6};
7use rayon::prelude::*;
8
9// TODO: Not compatible with variable rounds
10pub fn batch_dlog_accumulator_check<G: CommitmentCurve>(
11    urs: &SRS<G>,
12    comms: &[G],
13    chals: &[G::ScalarField],
14) -> bool {
15    let k = comms.len();
16
17    if k == 0 {
18        assert_eq!(chals.len(), 0);
19        return true;
20    }
21
22    let rounds = chals.len() / k;
23    assert_eq!(chals.len() % rounds, 0);
24
25    let rs = {
26        let r = G::ScalarField::rand(&mut rand::rngs::OsRng);
27        let mut rs = vec![G::ScalarField::one(); k];
28        for i in 1..k {
29            rs[i] = r * rs[i - 1];
30        }
31        rs
32    };
33
34    let mut points = urs.g.clone();
35    let n = points.len();
36    points.extend(comms);
37
38    let mut scalars = vec![G::ScalarField::zero(); n];
39    scalars.extend(&rs[..]);
40
41    let chal_invs = {
42        let mut cs = chals.to_vec();
43        batch_inversion(&mut cs);
44        cs
45    };
46
47    let termss: Vec<_> = chals
48        .par_iter()
49        .zip(chal_invs)
50        .chunks(rounds)
51        .zip(rs)
52        .map(|(chunk, r)| {
53            let chals: Vec<_> = chunk.iter().map(|(c, _)| **c).collect();
54            let mut s = b_poly_coefficients(&chals);
55            s.iter_mut().for_each(|c| *c *= &r);
56            s
57        })
58        .collect();
59
60    for terms in termss {
61        assert_eq!(terms.len(), n);
62        for i in 0..n {
63            scalars[i] -= &terms[i];
64        }
65    }
66
67    let scalars: Vec<_> = scalars.iter().map(|x| x.into_bigint()).collect();
68    G::Group::msm_bigint(&points, &scalars) == G::Group::zero()
69}
70
71pub fn batch_dlog_accumulator_generate<G: CommitmentCurve>(
72    urs: &SRS<G>,
73    num_comms: usize,
74    chals: &Vec<G::ScalarField>,
75) -> Vec<G> {
76    let k = num_comms;
77
78    if k == 0 {
79        assert_eq!(chals.len(), 0);
80        return vec![];
81    }
82
83    let rounds = chals.len() / k;
84    assert_eq!(chals.len() % rounds, 0);
85
86    let comms: Vec<_> = chals
87        .into_par_iter()
88        .chunks(rounds)
89        .map(|chals| {
90            let chals: Vec<G::ScalarField> = chals.into_iter().copied().collect();
91            let scalars: Vec<_> = b_poly_coefficients(&chals)
92                .into_iter()
93                .map(|x| x.into_bigint())
94                .collect();
95            let points: Vec<_> = urs.g.clone();
96            G::Group::msm_bigint(&points, &scalars).into_affine()
97        })
98        .collect();
99
100    comms
101}
kimchi_stubs/urs_utils.rs

kimchi_stubs/
urs_utils.rs
