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

saffron/
storage_proof.rs
