kzg_commitment/
kzg.rs

1use num_bigint::BigInt;
2use ark_bls12_381::{Bls12_381, Config, Fr as F, G1Affine, G1Projective, G2Affine, G2Projective};
3use ark_ec::{
4    bls12::{G1Prepared, G2Prepared},
5    pairing::Pairing,
6    short_weierstrass::Affine,
7    AffineRepr, CurveGroup,
8};
9use ark_ff::{Field, UniformRand, Zero, BigInteger256};
10use ark_poly::{
11    polynomial,
12    univariate::{DenseOrSparsePolynomial, DensePolynomial},
13    DenseUVPolynomial, Polynomial,
14};
15use ark_std::{rand, One};
16// use num_traits::{Zero, One, FromPrimitive};
17
18use derive_more::Display;
19
20#[derive(Debug, Display)]
21pub enum ProofError {
22    #[display(fmt = "Cannot generate valid proof: division remainder is non-zero")]
23    InvalidProof,
24    #[display(fmt = "Polynomial division failed")]
25    DivisionError,
26}
27impl std::error::Error for ProofError {}
28
29pub struct KZGCommitment {
30    trusted_setup_g1: Vec<G1Affine>,
31    trusted_setup_g2: Vec<G2Affine>,
32}
33
34impl KZGCommitment {
35    pub fn new(degree: usize) -> Self {
36        let (trusted_setup_g1, trusted_setup_g2) = Self::trusted_setup(degree);
37        Self {
38            trusted_setup_g1,
39            trusted_setup_g2,
40        }
41    }
42
43    fn lagrange_interpolation(points: &Vec<(F, F)>) -> DensePolynomial<F> {
44        let mut result: DensePolynomial<F> = DensePolynomial::zero();
45        for (index, &(x_i, y_i)) in points.into_iter().enumerate() {
46            let mut term = DensePolynomial::from_coefficients_vec(vec![y_i]);
47            for (j, &(x_j, _)) in points.iter().enumerate() {
48                if j != index {
49                    let scalar = (x_i - x_j).inverse().unwrap();
50                    let numerator = DensePolynomial::from_coefficients_vec(vec![
51                        -x_j * scalar,
52                        F::one() * scalar,
53                    ]);
54                    term = &term * &numerator;
55                }
56            }
57
58            result += &term;
59        }
60        result
61    }
62
63    fn trusted_setup(degree: usize) -> (Vec<G1Affine>, Vec<G2Affine>) {
64        let mut rng = ark_std::test_rng();
65        let tau = F::rand(&mut rng);
66        let mut trusted_setup_g1: Vec<G1Affine> = Vec::new();
67        let mut trusted_setup_g2: Vec<G2Affine> = Vec::new();
68        for i in 0..degree {
69            let tau_i = tau.pow([i as u64]);
70            trusted_setup_g1.push((G1Affine::generator() * tau_i).into_affine());
71            trusted_setup_g2.push((G2Affine::generator() * tau_i).into_affine());
72        }
73
74        (trusted_setup_g1, trusted_setup_g2)
75    }
76
77    pub fn vector_to_polynomial(vector: &Vec<F>) -> DensePolynomial<F> {
78        let y_s: Vec<F> = vector.iter().map(|&y| F::from(y)).collect();
79        let x_s: Vec<F> = (0..vector.len()).map(|val| F::from(val as u32)).collect();
80        let points: Vec<(F, F)> = x_s.into_iter().zip(y_s.into_iter()).collect();
81        Self::lagrange_interpolation(&points)
82    }
83
84    fn evaluate_polynomial_at_g1_setup(&self, polynomial: &DensePolynomial<F>) -> G1Affine {
85        let mut result: G1Affine = G1Affine::zero();
86        let poly_coeffs = polynomial.coeffs();
87        for (index, coeff) in poly_coeffs.into_iter().enumerate() {
88            let temp = (self.trusted_setup_g1[index] * coeff).into_affine();
89            result = (result + temp).into_affine();
90        }
91        result
92    }
93
94    fn evaluate_polynomial_at_g2_setup(&self, polynomial: &DensePolynomial<F>) -> G2Affine {
95        let mut result: G2Affine = G2Affine::zero();
96        let poly_coeffs = polynomial.coeffs();
97        for (index, coeff) in poly_coeffs.into_iter().enumerate() {
98            let temp = (self.trusted_setup_g2[index] * coeff).into_affine();
99            result = (result + temp).into_affine();
100        }
101        result
102    }
103
104    pub fn commit_polynomial(&self, polynomial: &DensePolynomial<F>) -> G1Affine {
105        self.evaluate_polynomial_at_g1_setup(polynomial)
106    }
107
108    pub fn generate_proof(
109        &self,
110        polynomial: &DensePolynomial<F>,
111        points: &Vec<(F, F)>,
112    ) -> Result<G1Affine, ProofError> {
113        // lagrange interpolation
114        let points_ff: Vec<(F, F)> = points.into_iter().map(|&(x, y)| (F::from(x), F::from(y))).collect();
115        let point_polynomial = Self::lagrange_interpolation(&points_ff);
116        let numerator = polynomial - &point_polynomial;
117        let mut denominator = DensePolynomial::from_coefficients_vec(vec![F::from(1)]);
118        for (x, _) in points_ff {
119            denominator =
120                &denominator * &DensePolynomial::from_coefficients_vec(vec![-x, F::from(1)]);
121        }
122        let (q, r) = DenseOrSparsePolynomial::from(numerator)
123            .divide_with_q_and_r(&DenseOrSparsePolynomial::from(denominator))
124            .unwrap();
125
126        if r != DensePolynomial::zero() {
127            return Err(ProofError::InvalidProof);
128        }
129
130        Ok(self.evaluate_polynomial_at_g1_setup(&q))
131    }
132
133    pub fn verify_proof(
134        &self,
135        commitment: &G1Affine,
136        points: &Vec<(F, F)>,
137        proof: &G1Affine,
138    ) -> bool {
139        let points_ff: Vec<(F, F)> = points.into_iter().map(|&(x, y)| (F::from(x), F::from(y))).collect();
140        let point_polynomial = Self::lagrange_interpolation(&points_ff);
141        let mut vanishing_polynomial = DensePolynomial::from_coefficients_vec(vec![F::from(1)]);
142        for (x, _) in points_ff {
143            vanishing_polynomial = &vanishing_polynomial
144                * &DensePolynomial::from_coefficients_vec(vec![-x, F::from(1)]);
145        }
146
147        let z_s: G2Affine = self.evaluate_polynomial_at_g2_setup(&vanishing_polynomial);
148        let i_s: G1Affine = self.evaluate_polynomial_at_g1_setup(&point_polynomial);
149
150        let lhs = Bls12_381::pairing(proof, z_s);
151        let g1_lhs = *commitment - i_s;
152        let rhs = Bls12_381::pairing(g1_lhs.into_affine(), G2Affine::generator());
153
154        lhs == rhs
155    }
156}
157
158pub trait IntoField: Clone {
159  fn into_ff(self) -> F;
160}
161
162impl IntoField for i32 {
163  fn into_ff(self) -> F {
164      F::from(self)
165  }
166}
kzg_commitment/kzg.rs

kzg_commitment/
kzg.rs
