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        assert!(
36            old.len() == new.len(),
37            "Input 'old' and 'new' must have the same number of chunks"
38        );
39
40        let diffs: Vec<Diff<_>> = old
41            .par_iter()
42            .zip(new)
43            .enumerate()
44            .filter_map(|(region, (o, n))| {
45                let mut addresses: Vec<u64> = vec![];
46                let mut new_values: Vec<F> = vec![];
47                for (index, (o_elem, n_elem)) in o.iter().zip(n.iter()).enumerate() {
48                    if o_elem != n_elem {
49                        addresses.push(index as u64);
50                        new_values.push(*n_elem);
51                    }
52                }
53
54                if !addresses.is_empty() {
55                    Some(Diff {
56                        region: region as u64,
57                        addresses,
58                        new_values,
59                    })
60                } else {
61                    // do not record a diff with empty changes
62                    None
63                }
64            })
65            .collect();
66
67        Ok(diffs)
68    }
69
70    #[instrument(skip_all, level = "debug")]
71    pub fn create_from_bytes<D: EvaluationDomain<F>>(
72        domain: &D,
73        old: &[u8],
74        new: &[u8],
75    ) -> Result<Vec<Diff<F>>, DiffError> {
76        let old_elems: Vec<Vec<F>> = encode_for_domain(domain.size(), old);
77        let mut new_elems: Vec<Vec<F>> = encode_for_domain(domain.size(), new);
78        if old_elems.len() < new_elems.len() {
79            return Err(DiffError::CapacityMismatch {
80                max_number_chunks: old_elems.len(),
81                attempted: new_elems.len(),
82            });
83        }
84        if old_elems.len() > new_elems.len() {
85            let padding = vec![F::zero(); domain.size()];
86            new_elems.resize(old_elems.len(), padding);
87        }
88
89        Self::create_from_field_elements(&old_elems, &new_elems)
90    }
91}
92
93#[cfg(test)]
94pub mod tests {
95    use super::*;
96    use crate::utils::{chunk_size_in_bytes, min_encoding_chunks, test_utils::UserData};
97    use ark_ff::Zero;
98    use ark_poly::{EvaluationDomain, Radix2EvaluationDomain};
99    use mina_curves::pasta::Fp;
100    use once_cell::sync::Lazy;
101    use proptest::prelude::*;
102    use rand::Rng;
103
104    static DOMAIN: Lazy<Radix2EvaluationDomain<Fp>> =
105        Lazy::new(|| Radix2EvaluationDomain::new(1 << 16).unwrap());
106
107    pub fn randomize_data(threshold: f64, data: &[u8]) -> Vec<u8> {
108        let mut rng = rand::thread_rng();
109        data.iter()
110            .map(|b| {
111                let n = rng.gen::<f64>();
112                if n < threshold {
113                    rng.gen::<u8>()
114                } else {
115                    *b
116                }
117            })
118            .collect()
119    }
120
121    pub fn random_diff(UserData(xs): UserData) -> BoxedStrategy<(UserData, UserData)> {
122        let n_chunks = min_encoding_chunks(&*DOMAIN, &xs);
123        let max_byte_len = n_chunks * chunk_size_in_bytes(&*DOMAIN);
124        (0.0..=1.0, 0..=max_byte_len)
125            .prop_flat_map(move |(threshold, n)| {
126                let mut ys = randomize_data(threshold, &xs);
127                // NOTE: n could be less than xs.len(), in which case this is just truncation
128                ys.resize_with(n, rand::random);
129                Just((UserData(xs.clone()), UserData(ys)))
130            })
131            .boxed()
132    }
133
134    // Adds diff to data
135    fn add_diff_to_data(data: &mut [Vec<Fp>], diff: &Diff<Fp>) {
136        for (addr, new_value) in diff.addresses.iter().zip(diff.new_values.iter()) {
137            data[diff.region as usize][*addr as usize] = *new_value;
138        }
139    }
140
141    proptest! {
142        #![proptest_config(ProptestConfig::with_cases(20))]
143        #[test]
144
145        fn test_allow_legal_diff((UserData(xs), UserData(ys)) in
146            (UserData::arbitrary().prop_flat_map(random_diff))
147        ) {
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 = {
154                let pad = vec![Fp::zero(); DOMAIN.size()];
155                let mut elems = encode_for_domain(DOMAIN.size(), &ys);
156                elems.resize(xs_elems.len(), pad);
157                elems
158            };
159            assert!(xs_elems.len() == ys_elems.len());
160
161            let mut result = xs_elems.clone();
162            for diff in diffs.into_iter() {
163                add_diff_to_data(&mut result, &diff);
164            }
165            prop_assert_eq!(result, ys_elems);
166        }
167    }
168
169    // Check that we CAN'T construct a diff that requires more polynomial chunks than the original data
170    proptest! {
171        #![proptest_config(ProptestConfig::with_cases(10))]
172        #[test]
173        fn test_cannot_construct_bad_diff(
174            (threshold, (UserData(data), UserData(mut extra))) in (
175                0.0..1.0,
176                UserData::arbitrary().prop_flat_map(|UserData(d1)| {
177                    UserData::arbitrary()
178                        .prop_filter_map(
179                            "length constraint", {
180                            move |UserData(d2)| {
181                                let combined = &[d1.as_slice(), d2.as_slice()].concat();
182                                if min_encoding_chunks(&*DOMAIN, &d1) <
183                                   min_encoding_chunks(&*DOMAIN,  combined) {
184                                    Some((UserData(d1.clone()), UserData(d2)))
185                                } else {
186                                    None
187                                }
188                            }
189                        }
190                    )
191                })
192            )
193        ) {
194            let mut ys = randomize_data(threshold, &data);
195            ys.append(&mut extra);
196            let diff = Diff::<Fp>::create_from_bytes(&*DOMAIN, &data, &ys);
197            prop_assert!(diff.is_err());
198        }
199    }
200}
saffron/diff.rs

saffron/
diff.rs
