1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use ark_ec::{CurveGroup, VariableBaseMSM};
use ark_ff::{batch_inversion, One, PrimeField, UniformRand, Zero};
use poly_commitment::{
    commitment::{b_poly_coefficients, CommitmentCurve},
    ipa::SRS,
};
use rayon::prelude::*;

// TODO: Not compatible with variable rounds
pub fn batch_dlog_accumulator_check<G: CommitmentCurve>(
    urs: &SRS<G>,
    comms: &[G],
    chals: &[G::ScalarField],
) -> bool {
    let k = comms.len();

    if k == 0 {
        assert_eq!(chals.len(), 0);
        return true;
    }

    let rounds = chals.len() / k;
    assert_eq!(chals.len() % rounds, 0);

    let rs = {
        let r = G::ScalarField::rand(&mut rand::rngs::OsRng);
        let mut rs = vec![G::ScalarField::one(); k];
        for i in 1..k {
            rs[i] = r * rs[i - 1];
        }
        rs
    };

    let mut points = urs.g.clone();
    let n = points.len();
    points.extend(comms);

    let mut scalars = vec![G::ScalarField::zero(); n];
    scalars.extend(&rs[..]);

    let chal_invs = {
        let mut cs = chals.to_vec();
        batch_inversion(&mut cs);
        cs
    };

    let termss: Vec<_> = chals
        .par_iter()
        .zip(chal_invs)
        .chunks(rounds)
        .zip(rs)
        .map(|(chunk, r)| {
            let chals: Vec<_> = chunk.iter().map(|(c, _)| **c).collect();
            let mut s = b_poly_coefficients(&chals);
            s.iter_mut().for_each(|c| *c *= &r);
            s
        })
        .collect();

    for terms in termss {
        assert_eq!(terms.len(), n);
        for i in 0..n {
            scalars[i] -= &terms[i];
        }
    }

    let scalars: Vec<_> = scalars.iter().map(|x| x.into_bigint()).collect();
    G::Group::msm_bigint(&points, &scalars) == G::Group::zero()
}

pub fn batch_dlog_accumulator_generate<G: CommitmentCurve>(
    urs: &SRS<G>,
    num_comms: usize,
    chals: &Vec<G::ScalarField>,
) -> Vec<G> {
    let k = num_comms;

    if k == 0 {
        assert_eq!(chals.len(), 0);
        return vec![];
    }

    let rounds = chals.len() / k;
    assert_eq!(chals.len() % rounds, 0);

    let comms: Vec<_> = chals
        .into_par_iter()
        .chunks(rounds)
        .map(|chals| {
            let chals: Vec<G::ScalarField> = chals.into_iter().copied().collect();
            let scalars: Vec<_> = b_poly_coefficients(&chals)
                .into_iter()
                .map(|x| x.into_bigint())
                .collect();
            let points: Vec<_> = urs.g.clone();
            G::Group::msm_bigint(&points, &scalars).into_affine()
        })
        .collect();

    comms
}