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