jf_pcs/
lib.rs

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//! Polynomial Commitment Scheme
8
9#![cfg_attr(not(feature = "std"), no_std)]
10#![deny(missing_docs)]
11#[cfg(test)]
12extern crate std;
13
14#[cfg(any(not(feature = "std"), target_has_atomic = "ptr"))]
15#[doc(hidden)]
16extern crate alloc;
17
18pub mod errors;
19pub mod multilinear_kzg;
20mod poly;
21pub mod prelude;
22mod structs;
23mod toeplitz;
24pub mod transcript;
25pub mod univariate_kzg;
26
27pub use errors::PCSError;
28
29use ark_ff::{FftField, Field};
30use ark_poly::{EvaluationDomain, Radix2EvaluationDomain};
31use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
32use ark_std::{
33    borrow::Borrow,
34    cmp,
35    fmt::Debug,
36    hash::Hash,
37    rand::{CryptoRng, RngCore},
38    vec::Vec,
39};
40
41/// This trait defines APIs for polynomial commitment schemes.
42/// Note that for our usage, this PCS is not hiding.
43/// TODO(#187): add hiding property.
44pub trait PolynomialCommitmentScheme {
45    /// Structured reference string
46    type SRS: Clone + Debug + StructuredReferenceString;
47    /// Polynomial and its associated types
48    type Polynomial: Clone + Debug + Hash + PartialEq + Eq;
49    /// Polynomial input domain
50    type Point: Clone + Ord + Debug + Sync + Hash + PartialEq + Eq;
51    /// Polynomial Evaluation
52    type Evaluation: Field;
53    /// Commitments
54    type Commitment: Clone
55        + CanonicalSerialize
56        + CanonicalDeserialize
57        + Debug
58        + PartialEq
59        + Eq
60        + Hash;
61    /// Batch commitments
62    type BatchCommitment: Clone + CanonicalSerialize + CanonicalDeserialize + Debug + PartialEq + Eq;
63    /// Proofs
64    type Proof: Clone + CanonicalSerialize + CanonicalDeserialize + Debug + PartialEq + Eq + Hash;
65    /// Batch proofs
66    type BatchProof: Clone + CanonicalSerialize + CanonicalDeserialize + Debug + PartialEq + Eq;
67
68    /// Setup for testing.
69    ///
70    /// - For univariate polynomials, `supported_degree` is the maximum degree.
71    /// - For multilinear polynomials, `supported_degree` is the number of
72    ///   variables.
73    ///
74    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
75    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
76    #[cfg(any(test, feature = "test-srs"))]
77    fn gen_srs_for_testing<R: RngCore + CryptoRng>(
78        rng: &mut R,
79        supported_degree: usize,
80    ) -> Result<Self::SRS, PCSError> {
81        Self::SRS::gen_srs_for_testing(rng, supported_degree)
82    }
83
84    /// Setup for testing.
85    ///
86    /// - For univariate polynomials, `prover/verifier_supported_degree` is the
87    ///   maximum degree.
88    /// - For multilinear polynomials, `supported_degree` is the number of
89    ///   variables.
90    ///
91    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
92    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
93    #[cfg(any(test, feature = "test-srs"))]
94    fn gen_srs_for_testing_with_verifier_degree<R: RngCore + CryptoRng>(
95        rng: &mut R,
96        prover_supported_degree: usize,
97        verifier_supported_degree: usize,
98    ) -> Result<Self::SRS, PCSError> {
99        Self::SRS::gen_srs_for_testing_with_verifier_degree(
100            rng,
101            prover_supported_degree,
102            verifier_supported_degree,
103        )
104    }
105
106    /// Load public parameter in production environment.
107    /// These parameters are loaded from files with serialized `pp` bytes, and
108    /// the actual setup is usually carried out via MPC and should be
109    /// implemented else where. We only load them into memory here.
110    ///
111    /// If `file=None`, we load the default choice of SRS.
112    fn load_srs_from_file(
113        supported_degree: usize,
114        file: Option<&str>,
115    ) -> Result<Self::SRS, PCSError> {
116        Self::SRS::load_srs_from_file(supported_degree, file)
117    }
118
119    /// Trim the universal parameters to specialize the public parameters.
120    /// Input both `supported_degree` for univariate and
121    /// `supported_num_vars` for multilinear.
122    /// ## Note on function signature
123    /// Usually, data structure like SRS and ProverParam are huge and users
124    /// might wish to keep them in heap using different kinds of smart pointers
125    /// (instead of only in stack) therefore our `impl Borrow<_>` interface
126    /// allows for passing in any pointer type, e.g.: `trim(srs: &Self::SRS,
127    /// ..)` or `trim(srs: Box<Self::SRS>, ..)` or `trim(srs: Arc<Self::SRS>,
128    /// ..)` etc.
129    #[allow(clippy::type_complexity)]
130    fn trim(
131        srs: impl Borrow<Self::SRS>,
132        supported_degree: usize,
133        supported_num_vars: Option<usize>,
134    ) -> Result<
135        (
136            <Self::SRS as StructuredReferenceString>::ProverParam,
137            <Self::SRS as StructuredReferenceString>::VerifierParam,
138        ),
139        PCSError,
140    >;
141
142    /// Generate a binding (but not hiding) commitment for a polynomial
143    fn commit(
144        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
145        poly: &Self::Polynomial,
146    ) -> Result<Self::Commitment, PCSError>;
147
148    /// Batch commit a list of polynomials
149    fn batch_commit(
150        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
151        polys: &[Self::Polynomial],
152    ) -> Result<Self::BatchCommitment, PCSError>;
153
154    /// On input a polynomial `p` and a point `point`, outputs a proof for the
155    /// same.
156    fn open(
157        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
158        polynomial: &Self::Polynomial,
159        point: &Self::Point,
160    ) -> Result<(Self::Proof, Self::Evaluation), PCSError>;
161
162    /// Input a list of polynomials, and a same number of points,
163    /// compute a batch opening for all the polynomials.
164    fn batch_open(
165        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
166        batch_commitment: &Self::BatchCommitment,
167        polynomials: &[Self::Polynomial],
168        points: &[Self::Point],
169    ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSError>;
170
171    /// Open a single polynomial at multiple points.
172    /// The naive default implementation just open them individually.
173    #[allow(clippy::type_complexity)]
174    fn multi_open(
175        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
176        polynomial: &Self::Polynomial,
177        points: &[Self::Point],
178    ) -> Result<(Vec<Self::Proof>, Vec<Self::Evaluation>), PCSError> {
179        Ok(points
180            .iter()
181            .map(|point| Self::open(prover_param.borrow(), polynomial, point))
182            .collect::<Result<Vec<_>, _>>()?
183            .into_iter()
184            .unzip())
185    }
186
187    /// Verifies that `value` is the evaluation at `x` of the polynomial
188    /// committed inside `comm`.
189    fn verify(
190        verifier_param: &<Self::SRS as StructuredReferenceString>::VerifierParam,
191        commitment: &Self::Commitment,
192        point: &Self::Point,
193        value: &Self::Evaluation,
194        proof: &Self::Proof,
195    ) -> Result<bool, PCSError>;
196
197    /// Verifies that `value_i` is the evaluation at `x_i` of the polynomial
198    /// `poly_i` committed inside `comm`.
199    fn batch_verify<R: RngCore + CryptoRng>(
200        verifier_param: &<Self::SRS as StructuredReferenceString>::VerifierParam,
201        multi_commitment: &Self::BatchCommitment,
202        points: &[Self::Point],
203        values: &[Self::Evaluation],
204        batch_proof: &Self::BatchProof,
205        rng: &mut R,
206    ) -> Result<bool, PCSError>;
207}
208
209/// API definitions for structured reference string
210pub trait StructuredReferenceString: Sized {
211    /// Prover parameters
212    type ProverParam;
213    /// Verifier parameters
214    type VerifierParam;
215
216    /// Extract the prover parameters from the public parameters.
217    fn extract_prover_param(&self, supported_degree: usize) -> Self::ProverParam;
218    /// Extract the verifier parameters from the public parameters.
219    fn extract_verifier_param(&self, supported_degree: usize) -> Self::VerifierParam;
220
221    /// Trim the universal parameters to specialize the public parameters
222    /// for polynomials to the given `supported_degree`, and
223    /// returns committer key and verifier key.
224    ///
225    /// - For univariate polynomials, `supported_degree` is the maximum degree.
226    /// - For multilinear polynomials, `supported_degree` is 2 to the number of
227    ///   variables.
228    ///
229    /// `supported_log_size` should be in range `1..=params.log_size`
230    fn trim(
231        &self,
232        supported_degree: usize,
233    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError>;
234
235    /// Trim the universal parameters to specialize the public parameters
236    /// for polynomials to the given `prover/verifier_supported_degree`, and
237    /// returns committer key and verifier key.
238    ///
239    /// - For univariate polynomials, `prover_/verifier_supported_degree` is the
240    ///   maximum degree.
241    /// - For multilinear polynomials, `supported_degree` is 2 to the number of
242    ///   variables.
243    ///
244    /// `supported_log_size` should be in range `1..=params.log_size`
245    fn trim_with_verifier_degree(
246        &self,
247        prover_supported_degree: usize,
248        verifier_supported_degree: usize,
249    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError>;
250
251    /// Build SRS for testing.
252    ///
253    /// - For univariate polynomials, `supported_degree` is the maximum degree.
254    /// - For multilinear polynomials, `supported_degree` is the number of
255    ///   variables.
256    ///
257    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
258    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
259    #[cfg(any(test, feature = "test-srs"))]
260    fn gen_srs_for_testing<R: RngCore + CryptoRng>(
261        rng: &mut R,
262        supported_degree: usize,
263    ) -> Result<Self, PCSError>;
264
265    /// Build SRS for testing.
266    ///
267    /// - For univariate polynomials, `prover/verifier_supported_degree` is the
268    ///   maximum degree.
269    /// - For multilinear polynomials, `supported_degree` is the number of
270    ///   variables.
271    ///
272    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
273    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
274    #[cfg(any(test, feature = "test-srs"))]
275    fn gen_srs_for_testing_with_verifier_degree<R: RngCore + CryptoRng>(
276        rng: &mut R,
277        prover_supported_degree: usize,
278        verifier_supported_degree: usize,
279    ) -> Result<Self, PCSError>;
280
281    /// Load public parameter in production environment.
282    /// These parameters are loaded from files with serialized `pp` bytes, and
283    /// the actual setup is usually carried out via MPC and should be
284    /// implemented else where. We only load them into memory here.
285    ///
286    /// If `file=None`, we load the default choice of SRS.
287    fn load_srs_from_file(_supported_degree: usize, _file: Option<&str>) -> Result<Self, PCSError> {
288        unimplemented!("TODO: implement loading SRS from files");
289    }
290}
291
292/// Super-trait specific for univariate polynomial commitment schemes.
293pub trait UnivariatePCS: PolynomialCommitmentScheme
294where
295    Self::Evaluation: FftField,
296{
297    /// Similar to [`PolynomialCommitmentScheme::trim()`], but trim to support
298    /// the FFT operations, such as [`Self::multi_open_rou()`] or other
299    /// operations that involves roots of unity.
300    #[allow(clippy::type_complexity)]
301    fn trim_fft_size(
302        srs: impl Borrow<Self::SRS>,
303        supported_degree: usize,
304    ) -> Result<
305        (
306            <Self::SRS as StructuredReferenceString>::ProverParam,
307            <Self::SRS as StructuredReferenceString>::VerifierParam,
308        ),
309        PCSError,
310    > {
311        let fft_degree = checked_fft_size(supported_degree)?;
312        srs.borrow().trim(fft_degree).map_err(|e| {
313            PCSError::InvalidParameters(ark_std::format!(
314                "Requesting degree of {} for FFT:\n\t\t{:?}",
315                fft_degree,
316                e
317            ))
318        })
319    }
320
321    /// Given `degree` of the committed polynomial and `num_points` to open,
322    /// return the evaluation domain for faster computation of opening proofs
323    /// and evaluations (both using FFT).
324    fn multi_open_rou_eval_domain(
325        degree: usize,
326        num_points: usize,
327    ) -> Result<Radix2EvaluationDomain<Self::Evaluation>, PCSError> {
328        // reason for zero-padding: https://github.com/EspressoSystems/jellyfish/pull/231#issuecomment-1526488659
329        let padded_degree = checked_fft_size(degree)?;
330
331        let domain_size = cmp::max(padded_degree + 1, num_points);
332        let domain = Radix2EvaluationDomain::new(domain_size).ok_or_else(|| {
333            PCSError::UpstreamError(ark_std::format!(
334                "Fail to init eval domain of size {}",
335                domain_size
336            ))
337        })?;
338
339        Ok(domain)
340    }
341
342    /// Same task as [`PolynomialCommitmentScheme::multi_open()`], except the
343    /// points are [roots of unity](https://en.wikipedia.org/wiki/Root_of_unity).
344    /// The first `num_points` of roots will be evaluated (in canonical order).
345    #[allow(clippy::type_complexity)]
346    fn multi_open_rou(
347        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
348        polynomial: &Self::Polynomial,
349        num_points: usize,
350        domain: &Radix2EvaluationDomain<Self::Evaluation>,
351    ) -> Result<(Vec<Self::Proof>, Vec<Self::Evaluation>), PCSError> {
352        let evals = Self::multi_open_rou_evals(polynomial, num_points, domain)?;
353        let proofs = Self::multi_open_rou_proofs(prover_param, polynomial, num_points, domain)?;
354        Ok((proofs, evals))
355    }
356
357    /// Compute the opening proofs in [`Self::multi_open_rou()`].
358    fn multi_open_rou_proofs(
359        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
360        polynomial: &Self::Polynomial,
361        num_points: usize,
362        domain: &Radix2EvaluationDomain<Self::Evaluation>,
363    ) -> Result<Vec<Self::Proof>, PCSError>;
364
365    /// Compute the evaluations in [`Self::multi_open_rou()`].
366    fn multi_open_rou_evals(
367        polynomial: &Self::Polynomial,
368        num_points: usize,
369        domain: &Radix2EvaluationDomain<Self::Evaluation>,
370    ) -> Result<Vec<Self::Evaluation>, PCSError>;
371
372    /// Input a polynomial, and multiple evaluation points,
373    /// compute a *single* opening proof for the multiple points of the same
374    /// polynomial.
375    fn multi_point_open(
376        prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>,
377        polynomial: &Self::Polynomial,
378        points: &[Self::Point],
379    ) -> Result<(Self::Proof, Vec<Self::Evaluation>), PCSError>;
380
381    /// Verifies that `values` are the evaluation at the `points` of the
382    /// polynomial committed inside `comm`.
383    fn multi_point_verify(
384        verifier_param: impl Borrow<<Self::SRS as StructuredReferenceString>::VerifierParam>,
385        commitment: &Self::Commitment,
386        points: &[Self::Point],
387        values: &[Self::Evaluation],
388        proof: &Self::Proof,
389    ) -> Result<bool, PCSError>;
390}
391
392/// compute the fft size (i.e. `num_coeffs`) given a degree.
393#[inline]
394pub fn checked_fft_size(degree: usize) -> Result<usize, PCSError> {
395    let err = || {
396        PCSError::InvalidParameters(ark_std::format!(
397            "Next power of two overflows! Got: {}",
398            degree
399        ))
400    };
401    if degree.is_power_of_two() {
402        degree.checked_mul(2).ok_or_else(err)
403    } else {
404        degree.checked_next_power_of_two().ok_or_else(err)
405    }
406}
407
408/// dependencies required for ICICLE-related code, group import for convenience
409#[cfg(feature = "icicle")]
410pub mod icicle_deps {
411    use anyhow::anyhow;
412    pub use icicle_core::{
413        curve::{Affine as IcicleAffine, Curve as IcicleCurve, Projective as IcicleProjective},
414        msm::{MSMConfig, MSM},
415    };
416    pub use icicle_cuda_runtime::{memory::HostOrDeviceSlice, stream::CudaStream};
417
418    /// curve-specific types both from arkworks and from ICICLE
419    /// including Pairing, CurveCfg, Fr, Fq etc.
420    pub mod curves {
421        pub use ark_bn254::Bn254;
422        pub use icicle_bn254::curve::CurveCfg as IcicleBn254;
423    }
424
425    pub use crate::univariate_kzg::icicle::GPUCommittable;
426
427    // TODO: remove this after `warmup()` is added upstream
428    // https://github.com/ingonyama-zk/icicle/pull/422#issuecomment-1980881638
429    /// Create a new stream and warmup
430    pub fn warmup_new_stream() -> anyhow::Result<CudaStream> {
431        let stream = CudaStream::create().map_err(|e| anyhow!("{:?}", e))?;
432        let _warmup_bytes = HostOrDeviceSlice::<'_, u8>::cuda_malloc_async(1024, &stream)
433            .map_err(|e| anyhow!("{:?}", e))?;
434        Ok(stream)
435    }
436}
jf_pcs/lib.rs

jf_pcs/
lib.rs
