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        encoding::encode_for_domain,
181        utils::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    // Lazy variables used because proptest does not trivially accept
193    // test precomputes.
194    static SRS: Lazy<SRS<Vesta>> = Lazy::new(poly_commitment::precomputed_srs::get_srs_test);
195
196    static DOMAIN: Lazy<Radix2EvaluationDomain<Fp>> =
197        Lazy::new(|| Radix2EvaluationDomain::new(SRS.size()).unwrap());
198
199    static GROUP_MAP: Lazy<<Vesta as CommitmentCurve>::Map> =
200        Lazy::new(<Vesta as CommitmentCurve>::Map::setup);
201
202    proptest! {
203    #![proptest_config(ProptestConfig::with_cases(5))]
204    #[test]
205    fn test_storage_prove_verify(UserData(data) in UserData::arbitrary()) {
206        let mut rng = OsRng;
207        let commitments = {
208              let field_elems: Vec<_> = encode_for_domain(DOMAIN.size(), &data).into_iter().flatten().collect();
209              commit_to_field_elems(&SRS, &field_elems)
210        };
211
212        // extra seed
213        let challenge_seed: ScalarField = ScalarField::rand(&mut rng);
214
215        let mut sponge = CurveFqSponge::new(Curve::other_curve_sponge_params());
216        sponge.absorb_fr(&[challenge_seed]);
217        let (combined_data_commitment, challenge) =
218            combine_commitments(&mut sponge, commitments.as_slice());
219
220        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &data);
221
222        let proof = prove(&SRS, &GROUP_MAP, blob, challenge, &mut rng);
223        let res = verify_wrt_combined_data_commitment(
224            &SRS,
225            &GROUP_MAP,
226            combined_data_commitment,
227            &proof,
228            &mut rng,
229        );
230        prop_assert!(res);
231      }
232    }
233
234    proptest! {
235    #![proptest_config(ProptestConfig::with_cases(5))]
236    #[test]
237    fn test_storage_soundness(UserData(data) in UserData::arbitrary()) {
238        let mut rng = OsRng;
239        let commitments = {
240              let field_elems: Vec<_> = encode_for_domain(DOMAIN.size(), &data).into_iter().flatten().collect();
241              commit_to_field_elems(&SRS, &field_elems)
242        };
243
244        // extra seed
245        let challenge_seed: ScalarField = ScalarField::rand(&mut rng);
246
247        let mut sponge = CurveFqSponge::new(Curve::other_curve_sponge_params());
248        sponge.absorb_fr(&[challenge_seed]);
249        let (combined_data_commitment, challenge) =
250            combine_commitments(&mut sponge, commitments.as_slice());
251
252        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &data);
253
254        let proof = prove(&SRS, &GROUP_MAP, blob, challenge, &mut rng);
255
256        let proof_malformed_1 = {
257            StorageProof {
258                combined_data_eval: proof.combined_data_eval + ScalarField::one(),
259                opening_proof: proof.opening_proof.clone(),
260            }
261        };
262
263        let res_1 = verify_wrt_combined_data_commitment(
264            &SRS,
265            &GROUP_MAP,
266            combined_data_commitment,
267            &proof_malformed_1,
268            &mut rng,
269        );
270
271        prop_assert!(!res_1);
272
273        let proof_malformed_2 = {
274            let mut opening_proof = proof.opening_proof.clone();
275            opening_proof.z1 = ScalarField::one();
276            StorageProof {
277                combined_data_eval: proof.combined_data_eval,
278                opening_proof,
279            }
280        };
281
282        let res_2 = verify_wrt_combined_data_commitment(
283            &SRS,
284            &GROUP_MAP,
285            combined_data_commitment,
286            &proof_malformed_2,
287            &mut rng,
288        );
289
290        prop_assert!(!res_2);
291      }
292    }
293}
saffron/storage_proof.rs

saffron/
storage_proof.rs
