1// Copyright (c) 2023 Espresso Systems (espressosys.com)
  2// This file is part of the HyperPlonk library.
  3
  4// You should have received a copy of the MIT License
  5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  6
  7//! Implementing Structured Reference Strings for univariate polynomial KZG
  8
  9use crate::pcs::{PCSError, StructuredReferenceString};
 10use ark_ec::{pairing::Pairing, scalar_mul::fixed_base::FixedBase, AffineRepr, CurveGroup};
 11use ark_ff::PrimeField;
 12use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
 13use ark_std::{end_timer, rand::Rng, start_timer, vec, vec::Vec, One, UniformRand};
 14use derivative::Derivative;
 15use std::ops::Mul;
 16
 17/// `UniversalParams` are the universal parameters for the KZG10 scheme.
 18// Adapted from
 19// https://github.com/arkworks-rs/poly-commit/blob/master/src/kzg10/data_structures.rs#L20
 20#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize, Default)]
 21pub struct UnivariateUniversalParams<E: Pairing> {
 22    /// Group elements of the form `{ \beta^i G }`, where `i` ranges from 0 to
 23    /// `degree`.
 24    pub powers_of_g: Vec<E::G1Affine>,
 25    /// The generator of G2.
 26    pub h: E::G2Affine,
 27    /// \beta times the above generator of G2.
 28    pub beta_h: E::G2Affine,
 29}
 30
 31impl<E: Pairing> UnivariateUniversalParams<E> {
 32    /// Returns the maximum supported degree
 33    pub fn max_degree(&self) -> usize {
 34        self.powers_of_g.len()
 35    }
 36}
 37
 38/// `UnivariateProverParam` is used to generate a proof
 39#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, Eq, PartialEq, Default)]
 40pub struct UnivariateProverParam<C: AffineRepr> {
 41    /// Parameters
 42    pub powers_of_g: Vec<C>,
 43}
 44
 45/// `UnivariateVerifierParam` is used to check evaluation proofs for a given
 46/// commitment.
 47#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
 48#[derivative(
 49    Default(bound = ""),
 50    Clone(bound = ""),
 51    Copy(bound = ""),
 52    Debug(bound = ""),
 53    PartialEq(bound = ""),
 54    Eq(bound = "")
 55)]
 56pub struct UnivariateVerifierParam<E: Pairing> {
 57    /// The generator of G1.
 58    pub g: E::G1Affine,
 59    /// The generator of G2.
 60    pub h: E::G2Affine,
 61    /// \beta times the above generator of G2.
 62    pub beta_h: E::G2Affine,
 63}
 64
 65impl<E: Pairing> StructuredReferenceString<E> for UnivariateUniversalParams<E> {
 66    type ProverParam = UnivariateProverParam<E::G1Affine>;
 67    type VerifierParam = UnivariateVerifierParam<E>;
 68
 69    /// Extract the prover parameters from the public parameters.
 70    fn extract_prover_param(&self, supported_size: usize) -> Self::ProverParam {
 71        let powers_of_g = self.powers_of_g[..=supported_size].to_vec();
 72
 73        Self::ProverParam { powers_of_g }
 74    }
 75
 76    /// Extract the verifier parameters from the public parameters.
 77    fn extract_verifier_param(&self, _supported_size: usize) -> Self::VerifierParam {
 78        Self::VerifierParam {
 79            g: self.powers_of_g[0],
 80            h: self.h,
 81            beta_h: self.beta_h,
 82        }
 83    }
 84
 85    /// Trim the universal parameters to specialize the public parameters
 86    /// for univariate polynomials to the given `supported_size`, and
 87    /// returns committer key and verifier key. `supported_size` should
 88    /// be in range `1..params.len()`
 89    fn trim(
 90        &self,
 91        supported_size: usize,
 92    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
 93        let powers_of_g = self.powers_of_g[..=supported_size].to_vec();
 94
 95        let pk = Self::ProverParam { powers_of_g };
 96        let vk = Self::VerifierParam {
 97            g: self.powers_of_g[0],
 98            h: self.h,
 99            beta_h: self.beta_h,
100        };
101        Ok((pk, vk))
102    }
103
104    /// Build SRS for testing.
105    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
106    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
107    fn gen_srs_for_testing<R: Rng>(rng: &mut R, max_degree: usize) -> Result<Self, PCSError> {
108        let setup_time = start_timer!(|| format!("KZG10::Setup with degree {}", max_degree));
109        let beta = E::ScalarField::rand(rng);
110        let g = E::G1::rand(rng);
111        let h = E::G2::rand(rng);
112
113        let mut powers_of_beta = vec![E::ScalarField::one()];
114
115        let mut cur = beta;
116        for _ in 0..max_degree {
117            powers_of_beta.push(cur);
118            cur *= &beta;
119        }
120
121        let window_size = FixedBase::get_mul_window_size(max_degree + 1);
122
123        let scalar_bits = E::ScalarField::MODULUS_BIT_SIZE as usize;
124        let g_time = start_timer!(|| "Generating powers of G");
125        // TODO: parallelization
126        let g_table = FixedBase::get_window_table(scalar_bits, window_size, g);
127        let powers_of_g =
128            FixedBase::msm::<E::G1>(scalar_bits, window_size, &g_table, &powers_of_beta);
129        end_timer!(g_time);
130
131        let powers_of_g = E::G1::normalize_batch(&powers_of_g);
132
133        let h = h.into_affine();
134        let beta_h = h.mul(beta).into_affine();
135
136        let pp = Self {
137            powers_of_g,
138            h,
139            beta_h,
140        };
141        end_timer!(setup_time);
142        Ok(pp)
143    }
144}