w3f_pcs/aggregation/
single.rs

1use ark_ec::{AffineRepr, CurveGroup};
2use ark_ff::{PrimeField, Zero};
3use ark_poly::Polynomial;
4use ark_std::vec::Vec;
5
6use crate::pcs::{Commitment, PCS};
7use crate::utils::ec::small_multiexp_affine;
8use crate::Poly;
9
10/// A tuple (c, x, y) of the form (G, F, F). Represents a claim that {f(x) = y, for a polynomial f such that commit(f) = c}.
11/// In other words, it is am instance in some language of "correct polynomial evaluations".
12/// Soundness properties of a claim are defined by that of the argument.
13#[derive(Clone, Debug)]
14pub struct Claim<F: PrimeField, C: Commitment<F>> {
15    pub c: C,
16    pub x: F,
17    pub y: F,
18}
19
20impl<F: PrimeField, C: Commitment<F>> Claim<F, C> {
21    pub fn new<CS>(ck: &CS::CK, poly: &Poly<F>, at: F) -> Claim<F, C>
22    where
23        CS: PCS<F, C = C>,
24    {
25        Claim {
26            c: CS::commit(ck, poly).unwrap(),
27            x: at,
28            y: poly.evaluate(&at),
29        }
30    }
31}
32
33/// Aggregates claims for different polynomials evaluated at the same point.
34///
35/// Claims `[(Ci, xi, yi)]`, such that `xi = x` for any `i`,
36/// can be aggregated using randomness `r` to a claim `(C', x, y')`,
37/// where `C' = r_agg([Ci], r)` and `y' = r_agg([yi], r)`.
38///
39/// If CS is knowledge-sound than an aggregate opening is a proof of knowledge for
40/// `{[(C_i, x, y_i)]; [f_i]): fi(x) = yi and CS::commit(fi) = ci}`.
41pub fn aggregate_claims<F: PrimeField, CS: PCS<F>>(
42    claims: &[Claim<F, CS::C>],
43    rs: &[F],
44) -> Claim<F, CS::C> {
45    assert_eq!(claims.len(), rs.len());
46
47    let mut iter_over_xs = claims.iter().map(|cl| cl.x);
48    let same_x = iter_over_xs.next().expect("claims is empty");
49    assert!(
50        iter_over_xs.all(|x| x == same_x),
51        "multiple evaluation points"
52    );
53
54    // TODO: Detect duplicate claims?
55    // Consider (Cf, x, y1) and (Cf, x, y2).
56    // If y1 = y2 = f(x) both claims are valid
57    // If y1 != y2, at least one of the 2 claims is invalid
58
59    let (rcs, rys): (Vec<CS::C>, Vec<F>) = claims
60        .iter()
61        .zip(rs.iter())
62        .map(|(cl, &r)| (cl.c.mul(r), r * cl.y))
63        .unzip();
64
65    Claim {
66        c: rcs.into_iter().sum(),
67        x: same_x,
68        y: rys.iter().sum(),
69    }
70}
71
72pub fn aggregate_claims_multiexp<F, C>(cs: Vec<C>, ys: Vec<F>, rs: &[F]) -> (C, F)
73where
74    F: PrimeField,
75    C: AffineRepr<ScalarField = F>,
76{
77    assert_eq!(cs.len(), rs.len());
78    assert_eq!(ys.len(), rs.len());
79
80    let agg_c = small_multiexp_affine(rs, &cs);
81    let agg_y = ys.into_iter().zip(rs.iter()).map(|(y, r)| y * r).sum();
82
83    (agg_c.into_affine(), agg_y)
84}
85
86// for opening in a single point, the aggregate polynomial doesn't depend on the point.
87pub fn aggregate_polys<F: PrimeField>(polys: &[Poly<F>], rs: &[F]) -> Poly<F> {
88    assert_eq!(polys.len(), rs.len());
89    polys
90        .iter()
91        .zip(rs.iter())
92        .map(|(p, &r)| p * r)
93        .fold(Poly::zero(), |acc, p| acc + p)
94}
95
96#[cfg(test)]
97mod tests {
98    use ark_poly::DenseUVPolynomial;
99    use ark_std::test_rng;
100
101    use crate::pcs::IdentityCommitment;
102    use crate::pcs::PcsParams;
103    use crate::tests::{TestField, TestKzg};
104
105    use super::*;
106
107    fn _test_aggregation<F: PrimeField, CS: PCS<F>>() {
108        let rng = &mut test_rng();
109        let d = 15;
110        let t = 4;
111        let params = CS::setup(d, rng);
112        let ck = params.ck();
113
114        assert!(aggregate_polys::<F>(&[], &[]).is_zero());
115
116        // common randomness
117        let rs = (0..t).map(|_| F::rand(rng)).collect::<Vec<_>>();
118
119        let polys = (0..t).map(|_| Poly::<F>::rand(d, rng)).collect::<Vec<_>>();
120        let agg_poly = aggregate_polys(&polys, &rs);
121
122        let same_x = F::rand(rng);
123        let claims_at_same_x = polys
124            .iter()
125            .map(|p| Claim::new::<CS>(&ck, p, same_x))
126            .collect::<Vec<_>>();
127        let agg_claim = aggregate_claims::<F, CS>(&claims_at_same_x, &rs);
128
129        assert_eq!(CS::commit(&ck, &agg_poly).unwrap(), agg_claim.c);
130        assert_eq!(same_x, agg_claim.x);
131        assert_eq!(agg_poly.evaluate(&same_x), agg_claim.y);
132    }
133
134    #[test]
135    fn test_aggregation() {
136        _test_aggregation::<TestField, IdentityCommitment>();
137        _test_aggregation::<TestField, TestKzg>();
138    }
139}
w3f_pcs/aggregation/single.rs

w3f_pcs/aggregation/
single.rs
