saffron/
diff.rs

1use crate::utils::encode_for_domain;
2use ark_ff::PrimeField;
3use ark_poly::EvaluationDomain;
4use rayon::prelude::*;
5use thiserror::Error;
6use tracing::instrument;
7
8/// Diff request pointing to a single commitment.
9#[derive(Clone, Debug, PartialEq)]
10pub struct Diff<F: PrimeField> {
11    /// Which commitment within a group of commitments representing
12    /// the data is the diff for.
13    pub region: u64,
14    /// A list of unique addresses, each ∈ [0, SRS_SIZE]
15    pub addresses: Vec<u64>,
16    /// A list of new values, each corresponding to address in `addresses`
17    pub new_values: Vec<F>,
18}
19
20#[derive(Debug, Error, Clone, PartialEq)]
21pub enum DiffError {
22    #[error("Capacity Mismatch: maximum number of chunks is {max_number_chunks}, attempted to create {attempted}")]
23    CapacityMismatch {
24        max_number_chunks: usize,
25        attempted: usize,
26    },
27}
28
29impl<F: PrimeField> Diff<F> {
30    #[instrument(skip_all, level = "debug")]
31    pub fn create_from_field_elements(
32        old: &Vec<Vec<F>>,
33        new: &Vec<Vec<F>>,
34    ) -> Result<Vec<Diff<F>>, DiffError> {
35        if old.len() != new.len() {
36            return Err(DiffError::CapacityMismatch {
37                max_number_chunks: old.len(),
38                attempted: new.len(),
39            });
40        }
41        let diffs: Vec<Diff<_>> = old
42            .par_iter()
43            .zip(new)
44            .enumerate()
45            .filter_map(|(region, (o, n))| {
46                let mut addresses: Vec<u64> = vec![];
47                let mut new_values: Vec<F> = vec![];
48                for (index, (o_elem, n_elem)) in o.iter().zip(n.iter()).enumerate() {
49                    if o_elem != n_elem {
50                        addresses.push(index as u64);
51                        new_values.push(*n_elem);
52                    }
53                }
54
55                if !addresses.is_empty() {
56                    Some(Diff {
57                        region: region as u64,
58                        addresses,
59                        new_values,
60                    })
61                } else {
62                    // do not record a diff with empty changes
63                    None
64                }
65            })
66            .collect();
67
68        Ok(diffs)
69    }
70
71    #[instrument(skip_all, level = "debug")]
72    pub fn create_from_bytes<D: EvaluationDomain<F>>(
73        domain: &D,
74        old: &[u8],
75        new: &[u8],
76    ) -> Result<Vec<Diff<F>>, DiffError> {
77        let old_elems: Vec<Vec<F>> = encode_for_domain(domain.size(), old);
78        let new_elems: Vec<Vec<F>> = encode_for_domain(domain.size(), new);
79        Self::create_from_field_elements(&old_elems, &new_elems)
80    }
81
82    /// Updates the data with the provided diff, replacing old values at
83    /// specified addresses by corresponding new ones
84    pub fn apply_inplace(data: &mut [Vec<F>], diff: &Diff<F>) {
85        for (addr, new_value) in diff.addresses.iter().zip(diff.new_values.iter()) {
86            data[diff.region as usize][*addr as usize] = *new_value;
87        }
88    }
89
90    /// Returns a new vector that contains the data updated with the specified
91    /// diff
92    pub fn apply(data: &[Vec<F>], diff: &Diff<F>) -> Vec<Vec<F>> {
93        let mut data = data.to_vec();
94        Self::apply_inplace(&mut data, diff);
95        data
96    }
97}
98
99#[cfg(test)]
100pub mod tests {
101    use super::*;
102    use crate::utils::{chunk_size_in_bytes, min_encoding_chunks, test_utils::UserData};
103    use ark_poly::{EvaluationDomain, Radix2EvaluationDomain};
104    use mina_curves::pasta::Fp;
105    use once_cell::sync::Lazy;
106    use proptest::prelude::*;
107    use rand::Rng;
108
109    static DOMAIN: Lazy<Radix2EvaluationDomain<Fp>> =
110        Lazy::new(|| Radix2EvaluationDomain::new(1 << 16).unwrap());
111
112    pub fn randomize_data(threshold: f64, data: &[u8]) -> Vec<u8> {
113        let mut rng = rand::thread_rng();
114        data.iter()
115            .map(|b| {
116                let n = rng.gen::<f64>();
117                if n < threshold {
118                    rng.gen::<u8>()
119                } else {
120                    *b
121                }
122            })
123            .collect()
124    }
125
126    pub fn random_diff(UserData(xs): UserData) -> BoxedStrategy<(UserData, UserData)> {
127        let n_chunks = min_encoding_chunks(&*DOMAIN, &xs);
128        let max_byte_len = n_chunks * chunk_size_in_bytes(&*DOMAIN);
129        (0.0..=1.0, 0..=max_byte_len)
130            .prop_flat_map(move |(threshold, n)| {
131                let mut ys = randomize_data(threshold, &xs);
132                // NOTE: n could be less than xs.len(), in which case this is just truncation
133                ys.resize_with(n, rand::random);
134                Just((UserData(xs.clone()), UserData(ys)))
135            })
136            .boxed()
137    }
138
139    proptest! {
140        #![proptest_config(ProptestConfig::with_cases(20))]
141        #[test]
142
143        fn test_allow_legal_diff((UserData(xs), UserData(ys)) in
144            (UserData::arbitrary().prop_flat_map(random_diff))
145        ) {
146            let min_len = xs.len().min(ys.len());
147            let (xs, ys) = (&xs[..min_len], &ys[..min_len]) ;
148            let diffs = Diff::<Fp>::create_from_bytes(&*DOMAIN, xs, ys);
149            prop_assert!(diffs.is_ok());
150            let diffs = diffs.unwrap();
151
152            let xs_elems = encode_for_domain(DOMAIN.size(), xs);
153            let ys_elems = encode_for_domain(DOMAIN.size(), ys);
154            assert!(xs_elems.len() == ys_elems.len());
155
156            let mut result = xs_elems.clone();
157            for diff in diffs.into_iter() {
158                Diff::apply_inplace(&mut result, &diff);
159            }
160            prop_assert_eq!(result, ys_elems);
161        }
162    }
163
164    // Check that we CAN'T construct a diff that requires more polynomial chunks than the original data
165    proptest! {
166        #![proptest_config(ProptestConfig::with_cases(10))]
167        #[test]
168        fn test_cannot_construct_bad_diff(
169            (threshold, (UserData(data), UserData(mut extra))) in (
170                0.0..1.0,
171                UserData::arbitrary().prop_flat_map(|UserData(d1)| {
172                    UserData::arbitrary()
173                        .prop_filter_map(
174                            "length constraint", {
175                            move |UserData(d2)| {
176                                let combined = &[d1.as_slice(), d2.as_slice()].concat();
177                                if min_encoding_chunks(&*DOMAIN, &d1) <
178                                   min_encoding_chunks(&*DOMAIN,  combined) {
179                                    Some((UserData(d1.clone()), UserData(d2)))
180                                } else {
181                                    None
182                                }
183                            }
184                        }
185                    )
186                })
187            )
188        ) {
189            let mut ys = randomize_data(threshold, &data);
190            ys.append(&mut extra);
191            let diff = Diff::<Fp>::create_from_bytes(&*DOMAIN, &data, &ys);
192            prop_assert!(diff.is_err());
193        }
194    }
195}
saffron/diff.rs

saffron/
diff.rs
