w3f-pcs 0.0.6

Collection of tools for augmenting polynomial commitment schemes
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

use ark_ff::PrimeField;
use ark_poly::Evaluations;
use ark_serialize::*;
use ark_std::fmt::Debug;
use ark_std::iter::Sum;
use ark_std::ops::{Add, Mul, Sub};
use ark_std::rand::Rng;
use ark_std::vec::Vec;

pub use id::IdentityCommitment;

use crate::Poly;

mod id;
pub mod kzg;

pub trait Commitment<F: PrimeField>:
    Eq
    + Sized
    + Clone
    + Debug
    + Add<Self, Output = Self>
    + Mul<F, Output = Self>
    + Sub<Self, Output = Self>
    + Sum<Self>
    + CanonicalSerialize
    + CanonicalDeserialize
{
    fn mul(&self, by: F) -> Self;
    fn combine(coeffs: &[F], commitments: &[Self]) -> Self;
}

/// Can be used to commit and open commitments to DensePolynomial<F> of degree up to max_degree.
pub trait CommitterKey: Clone + Debug + CanonicalSerialize + CanonicalDeserialize {
    /// Maximal degree of a polynomial supported.
    fn max_degree(&self) -> usize;

    /// Maximal number of evaluations supported when committing in the Lagrangian base.
    fn max_evals(&self) -> usize {
        self.max_degree() + 1
    }
}

/// Can be used to verify openings to commitments.
pub trait VerifierKey: Clone + Debug {
    /// Maximal number of openings that can be verified.
    fn max_points(&self) -> usize {
        1
    }
}

/// Generates a `VerifierKey`, serializable
pub trait RawVerifierKey:
    Clone + Debug + Eq + PartialEq + CanonicalSerialize + CanonicalDeserialize
{
    type VK: VerifierKey;

    fn prepare(&self) -> Self::VK;
}

pub trait PcsParams {
    type CK: CommitterKey;
    type VK: VerifierKey;
    type RVK: RawVerifierKey<VK = Self::VK>;

    fn ck(&self) -> Self::CK;
    fn vk(&self) -> Self::VK;
    fn raw_vk(&self) -> Self::RVK;

    fn ck_with_lagrangian(&self, _domain_size: usize) -> Self::CK {
        unimplemented!();
    }
}

/// Polynomial commitment scheme.
pub trait PCS<F: PrimeField> {
    type C: Commitment<F>;

    type Proof: Clone + CanonicalSerialize + CanonicalDeserialize;

    type CK: CommitterKey;

    // vk needs to be convertible to a ck that is only required to commit to the p=1 constant polynomial,
    // see https://eprint.iacr.org/archive/2020/1536/1629188090.pdf, section 4.2
    type VK: VerifierKey + Into<Self::CK>;

    type Params: PcsParams<CK = Self::CK, VK = Self::VK>;

    fn setup<R: Rng>(max_degree: usize, rng: &mut R) -> Self::Params;

    fn commit(ck: &Self::CK, p: &Poly<F>) -> Result<Self::C, ()>;

    fn commit_evals(ck: &Self::CK, evals: &Evaluations<F>) -> Result<Self::C, ()> {
        let poly = evals.interpolate_by_ref();
        Self::commit(ck, &poly)
    }

    fn open(ck: &Self::CK, p: &Poly<F>, x: F) -> Result<Self::Proof, ()>;

    fn verify(vk: &Self::VK, c: Self::C, x: F, z: F, proof: Self::Proof) -> Result<(), ()>;

    // TODO: is the default implementation useful?
    fn batch_verify<R: Rng>(
        vk: &Self::VK,
        c: Vec<Self::C>,
        x: Vec<F>,
        y: Vec<F>,
        proof: Vec<Self::Proof>,
        _rng: &mut R,
    ) -> Result<(), ()> {
        assert_eq!(c.len(), x.len());
        assert_eq!(c.len(), y.len());
        c.into_iter()
            .zip(x.into_iter())
            .zip(y.into_iter())
            .zip(proof.into_iter())
            .all(|(((c, x), y), proof)| Self::verify(vk, c, x, y, proof).is_ok())
            .then(|| ())
            .ok_or(())
    }
}