saffron/
blob.rs

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

saffron/
blob.rs
