saffron/
blob.rs

1use crate::{
2    commitment::commit_to_field_elems,
3    diff::Diff,
4    encoding::{decode_from_field_elements, encode_for_domain, encoding_size},
5    Curve, ProjectiveCurve, ScalarField, SRS_SIZE,
6};
7use ark_ec::{AffineRepr, VariableBaseMSM};
8use ark_ff::Zero;
9use ark_poly::{EvaluationDomain, Radix2EvaluationDomain};
10use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
11use poly_commitment::{ipa::SRS, SRS as _};
12use rayon::prelude::*;
13use serde::{Deserialize, Serialize};
14use serde_with::serde_as;
15use tracing::{debug, instrument};
16
17/// A `FieldBlob<F>` is what Storage Provider stores per user's
18/// contract: a list of `SRS_SIZE * num_chunks` field elements, where
19/// num_chunks is how much the client allocated.
20///
21/// It can be seen as the encoding of a `Vec<u8>`, where each field
22/// element contains 31 bytes.
23#[serde_as]
24#[derive(Clone, Debug, Serialize, Deserialize, PartialEq)]
25#[serde(bound = "ScalarField : CanonicalDeserialize + CanonicalSerialize")]
26pub struct FieldBlob {
27    #[serde_as(as = "Vec<o1_utils::serialization::SerdeAs>")]
28    pub data: Vec<ScalarField>,
29    #[serde_as(as = "Vec<o1_utils::serialization::SerdeAs>")]
30    pub commitments: Vec<Curve>,
31}
32
33impl FieldBlob {
34    pub fn alloc_empty(num_chunks: usize) -> FieldBlob {
35        let data = vec![ScalarField::zero(); num_chunks * SRS_SIZE];
36
37        let commitments = vec![Curve::zero(); num_chunks];
38
39        FieldBlob { data, commitments }
40    }
41
42    pub fn apply_diff(
43        &mut self,
44        srs: &SRS<Curve>,
45        domain: &Radix2EvaluationDomain<ScalarField>,
46        diff: &Diff<ScalarField>,
47    ) {
48        assert_eq!(diff.addresses.len(), diff.diff_values.len());
49
50        let lagrange_basis = srs
51            .get_lagrange_basis(*domain)
52            .iter()
53            .map(|x| x.chunks[0])
54            .collect::<Vec<_>>();
55        let basis = lagrange_basis.as_slice();
56
57        let address_basis: Vec<_> = diff
58            .addresses
59            .par_iter()
60            .map(|idx| basis[*idx as usize])
61            .collect();
62
63        for (idx, value) in diff.addresses.iter().zip(diff.diff_values.iter()) {
64            self.data[SRS_SIZE * diff.region as usize + *idx as usize] += *value;
65        }
66
67        // Lagrange commitment to the (new values-old values) at `addresses`
68        let delta_data_commitment_at_addr =
69            ProjectiveCurve::msm(address_basis.as_slice(), diff.diff_values.as_slice()).unwrap();
70
71        let new_commitment =
72            (self.commitments[diff.region as usize] + delta_data_commitment_at_addr).into();
73
74        self.commitments[diff.region as usize] = new_commitment;
75    }
76
77    pub fn from_data(srs: &SRS<Curve>, data: &[ScalarField]) -> FieldBlob {
78        let commitments = commit_to_field_elems(srs, data);
79        FieldBlob {
80            commitments,
81            data: Vec::from(data),
82        }
83    }
84
85    #[instrument(skip_all, level = "debug")]
86    pub fn from_bytes<D: EvaluationDomain<ScalarField>>(
87        srs: &SRS<Curve>,
88        domain: D,
89        bytes: &[u8],
90    ) -> FieldBlob {
91        let field_elements: Vec<ScalarField> = encode_for_domain(domain.size(), bytes)
92            .into_iter()
93            .flatten()
94            .collect();
95
96        let res = Self::from_data(srs, field_elements.as_slice());
97
98        debug!(
99            "Encoded {:.2} MB into {} polynomials",
100            bytes.len() as f32 / 1_000_000.0,
101            res.commitments.len()
102        );
103
104        res
105    }
106
107    /// Returns the byte representation of the `FieldBlob`. Note that
108    /// `bytes ≠ into_bytes(from_bytes(bytes))` if `bytes.len()` is not
109    /// divisible by 31*SRS_SIZE. In most cases `into_bytes` will return
110    /// more bytes than `from_bytes` created, so one has to truncate it
111    /// externally to achieve the expected result.
112    #[instrument(skip_all, level = "debug")]
113    pub fn into_bytes(blob: FieldBlob) -> Vec<u8> {
114        let intended_vec_len = encoding_size::<ScalarField>() * blob.commitments.len() * SRS_SIZE;
115        let bytes = decode_from_field_elements(blob.data);
116        assert!(bytes.len() == intended_vec_len);
117        bytes
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124
125    use crate::{diff::tests::*, utils::test_utils::*, Curve, ScalarField};
126    use ark_ec::AffineRepr;
127    use ark_ff::Zero;
128    use ark_poly::Radix2EvaluationDomain;
129    use once_cell::sync::Lazy;
130    use proptest::prelude::*;
131
132    static SRS: Lazy<SRS<Curve>> = Lazy::new(poly_commitment::precomputed_srs::get_srs_test);
133
134    static DOMAIN: Lazy<Radix2EvaluationDomain<ScalarField>> =
135        Lazy::new(|| Radix2EvaluationDomain::new(SRS.size()).unwrap());
136
137    // check that Vec<u8> -> FieldBlob<ScalarField> -> Vec<u8> is the identity function
138    proptest! {
139    #![proptest_config(ProptestConfig::with_cases(20))]
140    #[test]
141    fn test_round_trip_blob_encoding(UserData(xs) in UserData::arbitrary())
142        {
143            let mut xs = xs.clone();
144            let xs_len_chunks = xs.len() / (31 * SRS_SIZE);
145            xs.truncate(xs_len_chunks * 31 * SRS_SIZE);
146
147            let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &xs);
148            let bytes = rmp_serde::to_vec(&blob).unwrap();
149            let a = rmp_serde::from_slice(&bytes).unwrap();
150            // check that ark-serialize is behaving as expected
151            prop_assert_eq!(blob.clone(), a);
152            let ys = FieldBlob::into_bytes(blob);
153            // check that we get the byte blob back again
154            prop_assert_eq!(xs,ys);
155        }
156    }
157
158    proptest! {
159    #![proptest_config(ProptestConfig::with_cases(10))]
160    #[test]
161    fn test_user_and_storage_provider_commitments_equal(UserData(xs) in UserData::arbitrary())
162      { let elems: Vec<_> = encode_for_domain(DOMAIN.size(), &xs).into_iter().flatten().collect();
163        let user_commitments: Vec<_> = commit_to_field_elems(&SRS, &elems);
164        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &xs);
165        prop_assert_eq!(user_commitments, blob.commitments);
166      }
167    }
168
169    fn encode_to_chunk_size(xs: &[u8], chunk_size: usize) -> FieldBlob {
170        let mut blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, xs);
171
172        assert!(blob.data.len() <= chunk_size * crate::SRS_SIZE);
173
174        blob.data.resize(chunk_size * crate::SRS_SIZE, Zero::zero());
175        blob.commitments.resize(chunk_size, Curve::zero());
176
177        blob
178    }
179
180    proptest! {
181        #![proptest_config(ProptestConfig::with_cases(10))]
182        #[test]
183
184        fn test_allow_legal_updates((UserData(xs), UserData(ys)) in
185            (UserData::arbitrary_with(DataSize::Medium).prop_flat_map(random_diff))
186        ) {
187            // equalize the length of input data
188            let min_len = xs.len().min(ys.len());
189            let (xs, ys) = (&xs[..min_len], &ys[..min_len]) ;
190
191            // start with some random user data
192            let mut xs_blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, xs);
193            let diffs = Diff::<ScalarField>::create_from_bytes(&*DOMAIN, xs, ys).unwrap();
194
195            // check that the user and SP agree on the data
196            let user_commitment: Vec<_> = {
197                let elems: Vec<_> = encode_for_domain(DOMAIN.size(), xs).into_iter().flatten().collect();
198                commit_to_field_elems(&SRS, &elems)
199
200            };
201            prop_assert_eq!(user_commitment.clone(), xs_blob.commitments.clone());
202
203            // Update the blob with the diff and check the user can match the commitment
204            for diff in diffs.iter() {
205                xs_blob.apply_diff(&SRS, &DOMAIN, diff);
206            }
207
208            // the updated blob should be the same as if we just start with the new data (with appropriate padding)
209            let ys_blob = encode_to_chunk_size(ys, xs_blob.data.len() / SRS_SIZE);
210
211            prop_assert_eq!(xs_blob, ys_blob);
212        }
213
214    }
215}