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

jf_pcs/
lib.rs
