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!(diff.addresses.len() == diff.new_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        // Old values at `addresses`
64        let old_values_at_addr: Vec<_> = diff
65            .addresses
66            .iter()
67            .map(|idx| self.data[diff.region as usize * SRS_SIZE + *idx as usize])
68            .collect();
69
70        for (idx, value) in diff.addresses.iter().zip(diff.new_values.iter()) {
71            self.data[SRS_SIZE * diff.region as usize + *idx as usize] = *value;
72        }
73
74        // Lagrange commitment to the (new values-old values) at `addresses`
75        let delta_data_commitment_at_addr = ProjectiveCurve::msm(
76            address_basis.as_slice(),
77            old_values_at_addr
78                .iter()
79                .zip(diff.new_values.iter())
80                .map(|(old, new)| new - old)
81                .collect::<Vec<_>>()
82                .as_slice(),
83        )
84        .unwrap();
85
86        let new_commitment =
87            (self.commitments[diff.region as usize] + delta_data_commitment_at_addr).into();
88
89        self.commitments[diff.region as usize] = new_commitment;
90    }
91
92    pub fn from_data(srs: &SRS<Curve>, data: &[ScalarField]) -> FieldBlob {
93        let commitments = commit_to_field_elems(srs, data);
94        FieldBlob {
95            commitments,
96            data: Vec::from(data),
97        }
98    }
99
100    #[instrument(skip_all, level = "debug")]
101    pub fn from_bytes<D: EvaluationDomain<ScalarField>>(
102        srs: &SRS<Curve>,
103        domain: D,
104        bytes: &[u8],
105    ) -> FieldBlob {
106        let field_elements: Vec<ScalarField> = encode_for_domain(domain.size(), bytes)
107            .into_iter()
108            .flatten()
109            .collect();
110
111        let res = Self::from_data(srs, field_elements.as_slice());
112
113        debug!(
114            "Encoded {:.2} MB into {} polynomials",
115            bytes.len() as f32 / 1_000_000.0,
116            res.commitments.len()
117        );
118
119        res
120    }
121
122    /// Returns the byte representation of the `FieldBlob`. Note that
123    /// `bytes ≠ into_bytes(from_bytes(bytes))` if `bytes.len()` is not
124    /// divisible by 31*SRS_SIZE. In most cases `into_bytes` will return
125    /// more bytes than `from_bytes` created, so one has to truncate it
126    /// externally to achieve the expected result.
127    #[instrument(skip_all, level = "debug")]
128    pub fn into_bytes(blob: FieldBlob) -> Vec<u8> {
129        let intended_vec_len = encoding_size::<ScalarField>() * blob.commitments.len() * SRS_SIZE;
130        let bytes = decode_from_field_elements(blob.data);
131        assert!(bytes.len() == intended_vec_len);
132        bytes
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use super::*;
139
140    use crate::{diff::tests::*, utils::test_utils::*, Curve, ScalarField};
141    use ark_ec::AffineRepr;
142    use ark_ff::Zero;
143    use ark_poly::Radix2EvaluationDomain;
144    use once_cell::sync::Lazy;
145    use proptest::prelude::*;
146
147    static SRS: Lazy<SRS<Curve>> = Lazy::new(poly_commitment::precomputed_srs::get_srs_test);
148
149    static DOMAIN: Lazy<Radix2EvaluationDomain<ScalarField>> =
150        Lazy::new(|| Radix2EvaluationDomain::new(SRS.size()).unwrap());
151
152    // check that Vec<u8> -> FieldBlob<ScalarField> -> Vec<u8> is the identity function
153    proptest! {
154    #![proptest_config(ProptestConfig::with_cases(20))]
155    #[test]
156    fn test_round_trip_blob_encoding(UserData(xs) in UserData::arbitrary())
157        {
158            let mut xs = xs.clone();
159            let xs_len_chunks = xs.len() / (31 * SRS_SIZE);
160            xs.truncate(xs_len_chunks * 31 * SRS_SIZE);
161
162            let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &xs);
163            let bytes = rmp_serde::to_vec(&blob).unwrap();
164            let a = rmp_serde::from_slice(&bytes).unwrap();
165            // check that ark-serialize is behaving as expected
166            prop_assert_eq!(blob.clone(), a);
167            let ys = FieldBlob::into_bytes(blob);
168            // check that we get the byte blob back again
169            prop_assert_eq!(xs,ys);
170        }
171    }
172
173    proptest! {
174    #![proptest_config(ProptestConfig::with_cases(10))]
175    #[test]
176    fn test_user_and_storage_provider_commitments_equal(UserData(xs) in UserData::arbitrary())
177      { let elems: Vec<_> = encode_for_domain(DOMAIN.size(), &xs).into_iter().flatten().collect();
178        let user_commitments: Vec<_> = commit_to_field_elems(&SRS, &elems);
179        let blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, &xs);
180        prop_assert_eq!(user_commitments, blob.commitments);
181      }
182    }
183
184    fn encode_to_chunk_size(xs: &[u8], chunk_size: usize) -> FieldBlob {
185        let mut blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, xs);
186
187        assert!(blob.data.len() <= chunk_size * crate::SRS_SIZE);
188
189        blob.data.resize(chunk_size * crate::SRS_SIZE, Zero::zero());
190        blob.commitments.resize(chunk_size, Curve::zero());
191
192        blob
193    }
194
195    proptest! {
196        #![proptest_config(ProptestConfig::with_cases(10))]
197        #[test]
198
199        fn test_allow_legal_updates((UserData(xs), UserData(ys)) in
200            (UserData::arbitrary_with(DataSize::Medium).prop_flat_map(random_diff))
201        ) {
202            // equalize the length of input data
203            let min_len = xs.len().min(ys.len());
204            let (xs, ys) = (&xs[..min_len], &ys[..min_len]) ;
205
206            // start with some random user data
207            let mut xs_blob = FieldBlob::from_bytes::<_>(&SRS, *DOMAIN, xs);
208            let diffs = Diff::<ScalarField>::create_from_bytes(&*DOMAIN, xs, ys).unwrap();
209
210            // check that the user and SP agree on the data
211            let user_commitment: Vec<_> = {
212                let elems: Vec<_> = encode_for_domain(DOMAIN.size(), xs).into_iter().flatten().collect();
213                commit_to_field_elems(&SRS, &elems)
214
215            };
216            prop_assert_eq!(user_commitment.clone(), xs_blob.commitments.clone());
217
218            // Update the blob with the diff and check the user can match the commitment
219            for diff in diffs.iter() {
220                xs_blob.apply_diff(&SRS, &DOMAIN, diff);
221            }
222
223            // the updated blob should be the same as if we just start with the new data (with appropriate padding)
224            let ys_blob = encode_to_chunk_size(ys, xs_blob.data.len() / SRS_SIZE);
225
226            prop_assert_eq!(xs_blob, ys_blob);
227        }
228
229    }
230}
saffron/blob.rs

saffron/
blob.rs
