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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
//! Verifiers for polynomial commitment schemes.
use crate::{
loader::{native::NativeLoader, Loader},
util::{
arithmetic::{CurveAffine, Rotation},
msm::Msm,
transcript::{TranscriptRead, TranscriptWrite},
},
Error,
};
use rand::Rng;
use std::{fmt::Debug, marker::PhantomData};
pub mod ipa;
pub mod kzg;
/// Query to an oracle.
/// It assumes all queries are based on the same point, but with some `shift`.
#[derive(Clone, Debug)]
pub struct Query<S, T = ()> {
/// Index of polynomial to query
pub poly: usize,
/// Shift of the query point.
pub shift: S,
/// Shift loaded as either constant or witness. It is user's job to ensure this is correctly constrained to have value equal to `shift`
pub loaded_shift: T,
/// Evaluation read from transcript.
pub eval: T,
}
impl<S> Query<S> {
/// Initialize [`Query`] without evaluation.
pub fn new(poly: usize, shift: S) -> Self {
Self { poly, shift, loaded_shift: (), eval: () }
}
/// Returns [`Query`] with evaluation and optionally the shift are loaded as.
pub fn with_evaluation<T>(self, loaded_shift: T, eval: T) -> Query<S, T> {
Query { poly: self.poly, shift: self.shift, loaded_shift, eval }
}
}
/// Polynomial commitment scheme verifier.
pub trait PolynomialCommitmentScheme<C, L>: Clone + Debug
where
C: CurveAffine,
L: Loader<C>,
{
/// Verifying key.
type VerifyingKey: Clone + Debug;
/// Structured proof read from transcript.
type Proof: Clone + Debug;
/// Output of verification.
type Output: Clone + Debug;
/// Read [`PolynomialCommitmentScheme::Proof`] from transcript.
fn read_proof<T>(
vk: &Self::VerifyingKey,
queries: &[Query<Rotation>],
transcript: &mut T,
) -> Result<Self::Proof, Error>
where
T: TranscriptRead<C, L>;
/// Verify [`PolynomialCommitmentScheme::Proof`] and output [`PolynomialCommitmentScheme::Output`].
fn verify(
vk: &Self::VerifyingKey,
commitments: &[Msm<C, L>],
point: &L::LoadedScalar,
queries: &[Query<Rotation, L::LoadedScalar>],
proof: &Self::Proof,
) -> Result<Self::Output, Error>;
}
/// Accumulation scheme verifier.
pub trait AccumulationScheme<C, L>
where
C: CurveAffine,
L: Loader<C>,
{
/// Accumulator to be accumulated.
type Accumulator: Clone + Debug;
/// Verifying key.
type VerifyingKey: Clone + Debug;
/// Structured proof read from transcript.
type Proof: Clone + Debug;
/// Read a [`AccumulationScheme::Proof`] from transcript.
fn read_proof<T>(
vk: &Self::VerifyingKey,
instances: &[Self::Accumulator],
transcript: &mut T,
) -> Result<Self::Proof, Error>
where
T: TranscriptRead<C, L>;
/// Verify old [`AccumulationScheme::Accumulator`]s are accumulated properly
/// into a new one with the [`AccumulationScheme::Proof`], and returns the
/// new one as output.
fn verify(
vk: &Self::VerifyingKey,
instances: &[Self::Accumulator],
proof: &Self::Proof,
) -> Result<Self::Accumulator, Error>;
}
/// Accumulation scheme decider.
/// When accumulation is going to end, the decider will perform the check if the
/// final accumulator is valid or not, where the check is usually much more
/// expensive than accumulation verification.
pub trait AccumulationDecider<C, L>: AccumulationScheme<C, L>
where
C: CurveAffine,
L: Loader<C>,
{
/// Deciding key. The key for decider for perform the final accumulator
/// check.
type DecidingKey: Clone + Debug;
/// Decide if a [`AccumulationScheme::Accumulator`] is valid.
fn decide(dk: &Self::DecidingKey, accumulator: Self::Accumulator) -> Result<(), Error>;
/// Decide if all [`AccumulationScheme::Accumulator`]s are valid.
fn decide_all(
dk: &Self::DecidingKey,
accumulators: Vec<Self::Accumulator>,
) -> Result<(), Error>;
}
/// Accumulation scheme prover.
pub trait AccumulationSchemeProver<C>: AccumulationScheme<C, NativeLoader>
where
C: CurveAffine,
{
/// Proving key.
type ProvingKey: Clone + Debug;
/// Create a proof that argues if old [`AccumulationScheme::Accumulator`]s
/// are properly accumulated into the new one, and returns the new one as
/// output.
fn create_proof<T, R>(
pk: &Self::ProvingKey,
instances: &[Self::Accumulator],
transcript: &mut T,
rng: R,
) -> Result<Self::Accumulator, Error>
where
T: TranscriptWrite<C>,
R: Rng;
}
/// Accumulator encoding.
pub trait AccumulatorEncoding<C, L>: Clone + Debug
where
C: CurveAffine,
L: Loader<C>,
{
/// Accumulator to be encoded.
type Accumulator: Clone + Debug;
/// Decode an [`AccumulatorEncoding::Accumulator`] from serveral
/// [`crate::loader::ScalarLoader::LoadedScalar`]s.
fn from_repr(repr: &[&L::LoadedScalar]) -> Result<Self::Accumulator, Error>;
}
impl<C, L, PCS> AccumulatorEncoding<C, L> for PhantomData<PCS>
where
C: CurveAffine,
L: Loader<C>,
PCS: PolynomialCommitmentScheme<C, L>,
{
type Accumulator = PCS::Output;
fn from_repr(_: &[&L::LoadedScalar]) -> Result<Self::Accumulator, Error> {
unimplemented!()
}
}