eth_state_diff/
attestations.rs

1//! Delta encoding for Phase 0 pending attestation lists.
2//!
3//! Phase 0 maintains two attestation lists with different update semantics:
4//!
5//! - `current_epoch_attestations` grows by appending new attestations during an
6//!   epoch.
7//! - `previous_epoch_attestations` is replaced when the epoch transitions.
8//!
9//! This module provides a single diff function that selects the most compact
10//! supported representation for both cases. If the target list starts with the
11//! exact byte sequence of the base list, only the appended bytes are stored.
12//! Otherwise, the complete target list is stored as a full replacement.
13//!
14//! Both representations use [`AttestationsDiff`] and can be applied with
15//! [`apply_attestations`] without deserializing individual attestations.
16
17use crate::types::{ArchivedAttestationsDiff, AttestationsDiff};
18
19/// Computes a compact delta between two serialized SSZ attestation lists.
20///
21/// The function automatically selects between the supported delta
22/// representations:
23///
24/// - If the lists are identical, [`AttestationsDiff::Unchanged`] is returned.
25/// - If the target list starts with the exact byte sequence of the base list,
26///   only the trailing bytes are stored in [`AttestationsDiff::Append`].
27/// - Otherwise, the complete target list is stored in
28///   [`AttestationsDiff::FullReplacement`].
29///
30/// This covers both append-only updates, such as growth of
31/// `current_epoch_attestations`, and epoch-boundary replacement of
32/// `previous_epoch_attestations`.
33///
34/// An empty base list is naturally represented as an append of the complete
35/// target list.
36///
37/// # Arguments
38///
39/// * `base_ssz` - Serialized SSZ representation of the base attestation list.
40/// * `target_ssz` - Serialized SSZ representation of the target attestation list.
41///
42/// # Returns
43///
44/// A compact [`AttestationsDiff`] representing the transition from `base_ssz`
45/// to `target_ssz`.
46///
47/// # Complexity
48///
49/// The prefix comparison takes O(min(n, m)) time, where *n* and *m* are the
50/// lengths of `base_ssz` and `target_ssz`, respectively. Additional space is
51/// proportional to the selected delta payload.
52///
53/// # Example
54///
55/// ```
56/// # use eth_state_diff::attestations::diff_attestations;
57/// # use eth_state_diff::types::AttestationsDiff;
58///
59/// let base = b"AAAA";
60///
61/// // Append case.
62/// let target = b"AAAABBBB";
63/// assert_eq!(
64///     diff_attestations(base, target),
65///     AttestationsDiff::Append(b"BBBB".to_vec())
66/// );
67///
68/// // Replacement case.
69/// let target = b"CCCC";
70/// assert_eq!(
71///     diff_attestations(base, target),
72///     AttestationsDiff::FullReplacement(b"CCCC".to_vec())
73/// );
74/// ```
75pub fn diff_attestations(base_ssz: &[u8], target_ssz: &[u8]) -> AttestationsDiff {
76    if base_ssz == target_ssz {
77        return AttestationsDiff::Unchanged;
78    }
79
80    if target_ssz.starts_with(base_ssz) {
81        let appended = &target_ssz[base_ssz.len()..];
82        AttestationsDiff::Append(appended.to_vec())
83    } else {
84        AttestationsDiff::FullReplacement(target_ssz.to_vec())
85    }
86}
87
88/// Applies an attestation delta to a serialized SSZ list in place.
89///
90/// [`AttestationsDiff::Unchanged`] leaves the base buffer untouched.
91///
92/// [`AttestationsDiff::Append`] appends the serialized bytes stored in the
93/// delta to the existing buffer.
94///
95/// [`AttestationsDiff::FullReplacement`] clears the existing buffer and
96/// replaces it with the serialized target bytes.
97///
98/// # Complexity
99///
100/// - [`AttestationsDiff::Unchanged`][]: O(1).
101/// - [`AttestationsDiff::Append`]: O(k), where *k* is the number of appended
102///   bytes.
103/// - [`AttestationsDiff::FullReplacement`]: O(n), where *n* is the size of the
104///   replacement list.
105///
106/// # Example
107///
108/// ```
109/// # use eth_state_diff::attestations::{apply_attestations, diff_attestations};
110/// # use eth_state_diff::types::AttestationsDiff;
111///
112/// let mut base = b"AAAA".to_vec();
113/// let delta = diff_attestations(&base, b"AAAABBBB");
114///
115/// match delta {
116///     AttestationsDiff::Unchanged => {}
117///     AttestationsDiff::Append(bytes) => base.extend_from_slice(&bytes),
118///     AttestationsDiff::FullReplacement(bytes) => {
119///         base.clear();
120///         base.extend_from_slice(&bytes);
121///     }
122/// }
123///
124/// assert_eq!(base, b"AAAABBBB");
125/// ```
126pub fn apply_attestations(base: &mut Vec<u8>, delta: &ArchivedAttestationsDiff) {
127    match delta {
128        ArchivedAttestationsDiff::Unchanged => {}
129        ArchivedAttestationsDiff::Append(bytes) => {
130            base.extend_from_slice(bytes.as_slice());
131        }
132        ArchivedAttestationsDiff::FullReplacement(bytes) => {
133            base.clear();
134            base.extend_from_slice(bytes.as_slice());
135        }
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142    use crate::types::{ArchivedAttestationsDiff, AttestationsDiff};
143    use rkyv::Archive;
144
145    fn archive(diff: &AttestationsDiff) -> rkyv::util::AlignedVec {
146        rkyv::to_bytes::<rkyv::rancor::Error>(diff).expect("failed to archive diff")
147    }
148
149    fn archived(bytes: &[u8]) -> &ArchivedAttestationsDiff {
150        rkyv::access::<ArchivedAttestationsDiff, rkyv::rancor::Error>(bytes)
151            .expect("bytes are a valid rkyv payload generated by `archive`")
152    }
153
154    #[test]
155    fn diff_identical_lists_is_unchanged() {
156        assert_eq!(
157            diff_attestations(b"AAAA", b"AAAA"),
158            AttestationsDiff::Unchanged
159        );
160    }
161
162    #[test]
163    fn diff_target_extends_base_is_append() {
164        assert_eq!(
165            diff_attestations(b"AAAA", b"AAAABBBB"),
166            AttestationsDiff::Append(b"BBBB".to_vec()),
167        );
168    }
169
170    #[test]
171    fn diff_target_diverges_is_full_replacement() {
172        assert_eq!(
173            diff_attestations(b"AAAA", b"CCCC"),
174            AttestationsDiff::FullReplacement(b"CCCC".to_vec()),
175        );
176    }
177
178    #[test]
179    fn diff_target_diverges_mid_item_is_full_replacement() {
180        let base = b"AAAA-BBBB-CCCC-DDDD";
181        let target = b"AAAA-BBBB-XXXX-DDDD";
182        assert_eq!(
183            diff_attestations(base, target),
184            AttestationsDiff::FullReplacement(target.to_vec()),
185        );
186    }
187
188    #[test]
189    fn diff_empty_base_to_nonempty_is_append() {
190        assert_eq!(
191            diff_attestations(b"", b"AAAABBBB"),
192            AttestationsDiff::Append(b"AAAABBBB".to_vec()),
193        );
194    }
195
196    #[test]
197    fn diff_both_empty_is_unchanged() {
198        assert_eq!(diff_attestations(b"", b""), AttestationsDiff::Unchanged);
199    }
200
201    #[test]
202    fn diff_nonempty_base_to_empty_is_replacement_with_empty_payload() {
203        assert_eq!(
204            diff_attestations(b"AAAA", b""),
205            AttestationsDiff::FullReplacement(Vec::new()),
206        );
207    }
208
209    #[test]
210    fn apply_unchanged_leaves_buffer_untouched() {
211        let buf = archive(&AttestationsDiff::Unchanged);
212        let mut base = b"AAAA".to_vec();
213        apply_attestations(&mut base, archived(&buf));
214        assert_eq!(base, b"AAAA");
215    }
216
217    #[test]
218    fn apply_append_extends_buffer_in_place() {
219        let buf = archive(&AttestationsDiff::Append(b"BBBB".to_vec()));
220        let mut base = b"AAAA".to_vec();
221        apply_attestations(&mut base, archived(&buf));
222        assert_eq!(base, b"AAAABBBB");
223    }
224
225    #[test]
226    fn apply_full_replacement_clears_then_writes() {
227        let buf = archive(&AttestationsDiff::FullReplacement(b"CCCC".to_vec()));
228        let mut base = b"AAAA".to_vec();
229        apply_attestations(&mut base, archived(&buf));
230        assert_eq!(base, b"CCCC");
231
232        let buf = archive(&AttestationsDiff::FullReplacement(Vec::new()));
233        apply_attestations(&mut base, archived(&buf));
234        assert!(base.is_empty());
235    }
236
237    fn round_trip(base: &[u8], target: &[u8]) {
238        let diff = diff_attestations(base, target);
239        let buf = archive(&diff);
240        let mut current = base.to_vec();
241        apply_attestations(&mut current, archived(&buf));
242        assert_eq!(
243            current, target,
244            "round-trip failed for base={base:?} target={target:?}"
245        );
246    }
247
248    #[test]
249    fn round_trip_covers_all_branches() {
250        round_trip(b"AAAA", b"AAAA");
251        round_trip(b"AAAA", b"AAAABBBB");
252        round_trip(b"AAAA", b"CCCC");
253        round_trip(b"", b"AAAABBBB");
254        round_trip(b"", b"");
255        round_trip(b"AAAA", b"");
256        round_trip(b"AAAA-BBBB-CCCC-DDDD", b"AAAA-BBBB-XXXX-DDDD");
257    }
258
259    #[test]
260    fn round_trip_epoch_lifecycle_appends_then_replaces() {
261        let mut state: Vec<u8> = Vec::new();
262        let mut expected = Vec::new();
263
264        for chunk in [b"att1".as_slice(), b"att2", b"att3"] {
265            expected.extend_from_slice(chunk);
266            let buf = archive(&diff_attestations(&state, &expected));
267            apply_attestations(&mut state, archived(&buf));
268            assert_eq!(state, expected);
269        }
270
271        // Epoch boundary: replace previous_epoch_attestations wholesale.
272        let new_epoch = b"prev1-prev2";
273        let diff = diff_attestations(&state, new_epoch);
274        assert!(
275            matches!(diff, AttestationsDiff::FullReplacement(_)),
276            "epoch transition must be a full replacement, got {diff:?}"
277        );
278        let buf = archive(&diff);
279        apply_attestations(&mut state, archived(&buf));
280        assert_eq!(state, new_epoch);
281
282        // New epoch appends again.
283        let mut expected = new_epoch.to_vec();
284        expected.extend_from_slice(b"-att4");
285        let diff = diff_attestations(&state, &expected);
286        assert!(
287            matches!(diff, AttestationsDiff::Append(_)),
288            "intra-epoch update must be an append, got {diff:?}"
289        );
290        let buf = archive(&diff);
291        apply_attestations(&mut state, archived(&buf));
292        assert_eq!(state, expected);
293    }
294
295    #[test]
296    fn round_trip_large_payloads() {
297        let one_att = b"AAAAAAAA-BBBBBBBB-CCCCCCCC-DDDDDDDD-EEEEEEEE";
298        let mut base = Vec::new();
299        for _ in 0..32 {
300            base.extend_from_slice(one_att);
301        }
302
303        let mut target = base.clone();
304        target.extend_from_slice(one_att);
305        target.extend_from_slice(one_att);
306
307        let diff = diff_attestations(&base, &target);
308        assert!(matches!(diff, AttestationsDiff::Append(_)));
309        let buf = archive(&diff);
310        let mut current = base.clone();
311        apply_attestations(&mut current, archived(&buf));
312        assert_eq!(current, target);
313
314        // Diverge at first byte -> full replacement.
315        let mut divergent = target.clone();
316        *divergent.get_mut(0).expect("target vector is non-empty") ^= 0xFF;
317        let diff = diff_attestations(&current, &divergent);
318        assert!(matches!(diff, AttestationsDiff::FullReplacement(_)));
319        let buf = archive(&diff);
320        apply_attestations(&mut current, archived(&buf));
321        assert_eq!(current, divergent);
322    }
323
324    #[test]
325    fn archived_alias_matches_attestations_diff() {
326        fn _assert_archived<T: Archive<Archived = ArchivedAttestationsDiff>>() {}
327        _assert_archived::<AttestationsDiff>();
328    }
329}
eth_state_diff/attestations.rs

eth_state_diff/
attestations.rs
