saffron/
storage_proof.rs

1//! This module defines the storage proof prover and verifier. Given a
2//! set of commitments C_i and a challenge α the storage proof is just
3//! an opening to the combined commitment ∑α^i C_i. Given that α is
4//! computed by hashing some external challenge secret (e.g. derived
5//! from a hash of a block), and from a hash of the commitments
6//! itself, this in essense proves knowledge of the opening to all the
7//! commitments C_i simultaneously. Given that α is computed by
8//! hashing some external challenge secret (e.g. derived from a hash
9//! of a block), and from a hash of the commitments itself, this in
10//! essense proves knowledge of the opening to all the commitments C_i
11//! simultaneously.
12
13use crate::{
14    blob::FieldBlob, utils, Curve, CurveScalarSponge, CurveSponge, ScalarField, Sponge, SRS_SIZE,
15};
16use ark_ec::AffineRepr;
17use ark_ff::{One, Zero};
18use ark_poly::{
19    EvaluationDomain, Evaluations, Polynomial, Radix2EvaluationDomain as D, Radix2EvaluationDomain,
20};
21use kimchi::{curve::KimchiCurve, plonk_sponge::FrSponge};
22use poly_commitment::{
23    commitment::{BatchEvaluationProof, CommitmentCurve, Evaluation},
24    ipa::{OpeningProof, SRS},
25    utils::DensePolynomialOrEvaluations,
26    PolyComm,
27};
28use rand::rngs::OsRng;
29use rayon::iter::{IndexedParallelIterator, IntoParallelRefMutIterator, ParallelIterator};
30use serde::{Deserialize, Serialize};
31use serde_with::serde_as;
32use tracing::instrument;
33
34#[serde_as]
35#[derive(Debug, Serialize, Deserialize, Clone)]
36pub struct StorageProof {
37    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
38    pub combined_data_eval: ScalarField,
39    pub opening_proof: OpeningProof<Curve>,
40}
41
42#[instrument(skip_all, level = "debug")]
43pub fn prove(
44    srs: &SRS<Curve>,
45    group_map: &<Curve as CommitmentCurve>::Map,
46    blob: FieldBlob,
47    challenge: ScalarField,
48    rng: &mut OsRng,
49) -> StorageProof {
50    // TODO: Cache this somewhere
51    let domain = Radix2EvaluationDomain::new(SRS_SIZE).unwrap();
52
53    let final_chunk = (blob.data.len() / SRS_SIZE) - 1;
54    assert!(blob.data.len() % SRS_SIZE == 0);
55
56    // ∑_{i=1} com_i^{challenge^i}
57    let combined_data_commitment =
58        utils::aggregate_commitments(challenge, blob.commitments.as_slice());
59
60    // Computes ∑_j chal^{j} data[j*SRS_SIZE + i]
61    // where j ∈ [0..final_chunk], so the power corresponding to
62    // the first chunk is 0 (chal^0 = 1).
63    let combined_data: Vec<ScalarField> = {
64        let mut initial: Vec<ScalarField> =
65            blob.data[final_chunk * SRS_SIZE..(final_chunk + 1) * SRS_SIZE].to_vec();
66
67        (0..final_chunk).rev().for_each(|chunk_ix| {
68            initial.par_iter_mut().enumerate().for_each(|(idx, acc)| {
69                *acc *= challenge;
70                *acc += blob.data[chunk_ix * SRS_SIZE + idx];
71            });
72        });
73
74        initial
75    };
76
77    let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
78    curve_sponge.absorb_g(&[combined_data_commitment]);
79    let evaluation_point = curve_sponge.squeeze(2);
80
81    let combined_data_poly = Evaluations::from_vec_and_domain(combined_data, domain).interpolate();
82    let combined_data_eval = combined_data_poly.evaluate(&evaluation_point);
83
84    // TODO: Do we need to use scalar_sponge? Can't we just use curve_sponge for everything?
85    let curve_sponge_before_evaluations = curve_sponge.clone();
86    let mut scalar_sponge = CurveScalarSponge::new(Curve::sponge_params());
87    scalar_sponge.absorb(&curve_sponge.digest());
88
89    // TODO: check and see if we need to also absorb the absorb the poly cm
90    // see https://github.com/o1-labs/proof-systems/blob/feature/test-data-storage-commitments/data-storage/src/main.rs#L265-L269
91    scalar_sponge.absorb(&combined_data_eval);
92
93    let opening_proof =
94        srs.open(
95            group_map,
96            &[
97                (
98                    DensePolynomialOrEvaluations::<
99                        <Curve as AffineRepr>::ScalarField,
100                        D<ScalarField>,
101                    >::DensePolynomial(&combined_data_poly),
102                    PolyComm {
103                        chunks: vec![ScalarField::zero()],
104                    },
105                ),
106            ],
107            &[evaluation_point],
108            ScalarField::one(), // Single evaluation, so we don't care
109            ScalarField::one(), // Single evaluation, so we don't care
110            curve_sponge_before_evaluations,
111            rng,
112        );
113
114    StorageProof {
115        combined_data_eval,
116        opening_proof,
117    }
118}
119
120#[instrument(skip_all, level = "debug")]
121pub fn verify_wrt_combined_data_commitment(
122    srs: &SRS<Curve>,
123    group_map: &<Curve as CommitmentCurve>::Map,
124    combined_data_commitment: Curve,
125    proof: &StorageProof,
126    rng: &mut OsRng,
127) -> bool {
128    let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
129    let evaluation_point = {
130        curve_sponge.absorb_g(&[combined_data_commitment]);
131        curve_sponge.squeeze(2)
132    };
133
134    let curve_sponge_before_evaluations = curve_sponge.clone();
135    let mut scalar_sponge = CurveScalarSponge::new(Curve::sponge_params());
136    scalar_sponge.absorb(&curve_sponge.digest());
137
138    // TODO: check and see if we need to also absorb the absorb the poly cm
139    // see https://github.com/o1-labs/proof-systems/blob/feature/test-data-storage-commitments/data-storage/src/main.rs#L265-L269
140    scalar_sponge.absorb(&proof.combined_data_eval);
141
142    srs.verify(
143        group_map,
144        &mut [BatchEvaluationProof {
145            sponge: curve_sponge_before_evaluations,
146            evaluation_points: vec![evaluation_point],
147            polyscale: ScalarField::one(),
148            evalscale: ScalarField::one(),
149            evaluations: vec![Evaluation {
150                commitment: PolyComm {
151                    chunks: vec![combined_data_commitment],
152                },
153                evaluations: vec![vec![proof.combined_data_eval]],
154            }],
155            opening: &proof.opening_proof,
156            combined_inner_product: proof.combined_data_eval,
157        }],
158        rng,
159    )
160}
161
162#[instrument(skip_all, level = "debug")]
163pub fn verify(
164    srs: &SRS<Curve>,
165    group_map: &<Curve as CommitmentCurve>::Map,
166    commitments: &[Curve],
167    challenge: ScalarField, // this could be merkle tree root
168    proof: &StorageProof,
169    rng: &mut OsRng,
170) -> bool {
171    // combined data commitment is ∑_{i=1} com_i^{challenge^i} for all chunks
172    let combined_data_commitment = utils::aggregate_commitments(challenge, commitments);
173    verify_wrt_combined_data_commitment(srs, group_map, combined_data_commitment, proof, rng)
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179    use crate::{
180        commitment::{combine_commitments, commit_to_field_elems},
181        encoding::encode_for_domain,
182        utils::test_utils::UserData,
183    };
184
185    use crate::{Curve, ScalarField};
186    use ark_ff::UniformRand;
187    use ark_poly::{EvaluationDomain, Radix2EvaluationDomain};
188    use kimchi::groupmap::GroupMap;
189    use once_cell::sync::Lazy;
190    use poly_commitment::{commitment::CommitmentCurve, ipa::SRS, SRS as _};
191    use proptest::prelude::*;
192
193    // Lazy variables used because proptest does not trivially accept
194    // test precomputes.
195    static SRS: Lazy<SRS<Curve>> = Lazy::new(poly_commitment::precomputed_srs::get_srs_test);
196
197    static DOMAIN: Lazy<Radix2EvaluationDomain<ScalarField>> =
198        Lazy::new(|| Radix2EvaluationDomain::new(SRS.size()).unwrap());
199
200    static GROUP_MAP: Lazy<<Curve as CommitmentCurve>::Map> =
201        Lazy::new(<Curve as CommitmentCurve>::Map::setup);
202
203    proptest! {
204    #![proptest_config(ProptestConfig::with_cases(5))]
205    #[test]
206    fn test_storage_prove_verify(UserData(data) in UserData::arbitrary()) {
207        let mut rng = OsRng;
208        let commitments = {
209              let field_elems: Vec<_> = encode_for_domain(DOMAIN.size(), &data).into_iter().flatten().collect();
210              commit_to_field_elems(&SRS, &field_elems)
211        };
212
213        // extra seed
214        let challenge_seed: ScalarField = ScalarField::rand(&mut rng);
215
216        let mut sponge = CurveSponge::new(Curve::other_curve_sponge_params());
217        sponge.absorb_fr(&[challenge_seed]);
218        let (combined_data_commitment, challenge) =
219            combine_commitments(&mut sponge, commitments.as_slice());
220
221        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &data);
222
223        let proof = prove(&SRS, &GROUP_MAP, blob, challenge, &mut rng);
224        let res = verify_wrt_combined_data_commitment(
225            &SRS,
226            &GROUP_MAP,
227            combined_data_commitment,
228            &proof,
229            &mut rng,
230        );
231        prop_assert!(res);
232      }
233    }
234
235    proptest! {
236    #![proptest_config(ProptestConfig::with_cases(5))]
237    #[test]
238    fn test_storage_soundness(UserData(data) in UserData::arbitrary()) {
239        let mut rng = OsRng;
240        let commitments = {
241              let field_elems: Vec<_> = encode_for_domain(DOMAIN.size(), &data).into_iter().flatten().collect();
242              commit_to_field_elems(&SRS, &field_elems)
243        };
244
245        // extra seed
246        let challenge_seed: ScalarField = ScalarField::rand(&mut rng);
247
248        let mut sponge = CurveSponge::new(Curve::other_curve_sponge_params());
249        sponge.absorb_fr(&[challenge_seed]);
250        let (combined_data_commitment, challenge) =
251            combine_commitments(&mut sponge, commitments.as_slice());
252
253        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &data);
254
255        let proof = prove(&SRS, &GROUP_MAP, blob, challenge, &mut rng);
256
257        let proof_malformed_1 = {
258            StorageProof {
259                combined_data_eval: proof.combined_data_eval + ScalarField::one(),
260                opening_proof: proof.opening_proof.clone(),
261            }
262        };
263
264        let res_1 = verify_wrt_combined_data_commitment(
265            &SRS,
266            &GROUP_MAP,
267            combined_data_commitment,
268            &proof_malformed_1,
269            &mut rng,
270        );
271
272        prop_assert!(!res_1);
273
274        let proof_malformed_2 = {
275            let mut opening_proof = proof.opening_proof.clone();
276            opening_proof.z1 = ScalarField::one();
277            StorageProof {
278                combined_data_eval: proof.combined_data_eval,
279                opening_proof,
280            }
281        };
282
283        let res_2 = verify_wrt_combined_data_commitment(
284            &SRS,
285            &GROUP_MAP,
286            combined_data_commitment,
287            &proof_malformed_2,
288            &mut rng,
289        );
290
291        prop_assert!(!res_2);
292      }
293    }
294}
saffron/storage_proof.rs

saffron/
storage_proof.rs
