eth_state_diff/

recent_roots.rs

//! Delta encoding for fixed-capacity Ethereum consensus root buffers.
//!
//! Ethereum consensus stores historical roots, such as block roots and state
//! roots, in fixed-capacity circular buffers. As new slots are processed,
//! entries are written at positions derived from their slot number, eventually
//! wrapping around and overwriting older entries.
//!
//! Rather than storing the complete root buffer, this module records only the
//! roots written during a requested slot range. Applying the delta replays
//! those writes into another root buffer using the same slot-to-index mapping.
//!
//! The delta contains no explicit buffer indices. Each index is reconstructed
//! from the slot number and the buffer capacity:
//!
//! ```text
//! buffer_index = slot % buffer_capacity
//! ```
//!
//! # Representation
//!
//! [`RootsDiff`] stores one 32-byte root for every slot in the half-open range
//! `[base_slot, target_slot)`.
//!
//! For example, a transition from slot `100` to slot `103` records the roots
//! for slots:
//!
//! ```text
//! 100, 101, 102
//! ```
//!
//! The root for `target_slot` itself is not included.
//!
//! # Correctness
//!
//! The destination buffer must have the same capacity as the buffer supplied
//! to [`diff_roots`]. The delta does not store explicit buffer indices, so
//! changing the capacity changes the modulo mapping and can cause roots to be
//! written to different positions.
//!
//! The `base_slot` supplied to [`apply_roots`] must also be the same starting
//! slot used to generate the delta. Because the delta stores only the sequence
//! of roots, changing the starting slot changes the positions at which those
//! roots are written.
//!
//! The delta represents only the recorded slot writes. Contents at positions
//! not covered by the slot range are preserved when the delta is applied.
//!
//! # Complexity
//!
//! If `N = target_slot - base_slot`:
//!
//! - [`diff_roots`] runs in O(N) time and uses O(N) additional space.
//! - [`apply_roots`] runs in O(N) time and uses O(1) additional space.

use crate::{
    error::Error,
    types::{ArchivedRootsDiff, RootsDiff},
};

/// Computes the sequence of roots written during a slot range.
///
/// The returned delta contains one root for every slot in the half-open range
/// `[base_slot, target_slot)`.
///
/// For each slot `s`, the root is read from the circular buffer at:
///
/// ```text
/// buffer_index = s % buffer.len()
/// ```
///
/// The root corresponding to `target_slot` is not included.
///
/// # Arguments
///
/// * `base_slot` - The first slot whose root is included in the delta.
/// * `target_slot` - The slot immediately following the final recorded root.
/// * `buffer` - Circular root buffer belonging to the target state.
///
/// # Returns
///
/// A [`RootsDiff`] containing the target root for every slot in
/// `[base_slot, target_slot)`.
///
/// If `base_slot == target_slot`, the returned delta contains no roots.
///
/// # Panics
///
/// Panics if `target_slot < base_slot`.
///
/// Panics if `buffer` is empty because circular-buffer indexing requires a
/// non-zero capacity.
///
/// # Correctness
///
/// The buffer capacity is part of the implicit representation because root
/// indices are reconstructed using modulo arithmetic.
///
/// The buffer supplied to [`apply_roots`] must therefore have the same capacity
/// as `buffer`. The same `base_slot` must also be supplied when applying the
/// resulting delta.
///
/// # Example
///
/// ```
/// use eth_state_diff::recent_roots::diff_roots;
///
/// let mut target_buffer = vec![[0u8; 32]; 4];
/// target_buffer[0] = [1u8; 32];
/// target_buffer[1] = [2u8; 32];
/// target_buffer[2] = [3u8; 32];
///
/// let delta = diff_roots(0, 3, &target_buffer);
///
/// assert_eq!(delta.roots.len(), 3);
/// assert_eq!(delta.roots[0], [1u8; 32]);
/// assert_eq!(delta.roots[1], [2u8; 32]);
/// assert_eq!(delta.roots[2], [3u8; 32]);
/// ```
///
/// # Complexity
///
/// Let `N = target_slot - base_slot`.
///
/// - Time: O(N)
/// - Additional space: O(N)
pub fn diff_roots(base_slot: u64, target_slot: u64, buffer: &[[u8; 32]]) -> RootsDiff {
    assert!(
        target_slot >= base_slot,
        "target_slot must be greater than or equal to base_slot"
    );

    assert!(!buffer.is_empty(), "root buffer must not be empty");

    let capacity = buffer.len() as u64;

    let span = target_slot - base_slot;
    let roots_cap = usize::try_from(span).expect("root span exceeds usize capacity");
    let mut roots = Vec::with_capacity(roots_cap);

    for i in 0..span {
        let slot = base_slot + i;
        let idx = (slot % capacity) as usize;
        roots.push(
            *buffer
                .get(idx)
                .expect("modulo arithmetic guarantees index is within bounds"),
        );
    }

    RootsDiff { roots }
}

/// Applies a root delta to a circular root buffer in place.
///
/// Each root stored in `delta` is written to the destination buffer using the
/// same slot-to-index mapping used by [`diff_roots`]:
///
/// ```text
/// buffer_index = slot % buffer_capacity
/// ```
///
/// The first root in the delta corresponds to `base_slot`. Each subsequent
/// root corresponds to the next slot.
///
/// # Arguments
///
/// * `base_slot` - The slot corresponding to the first root stored in `delta`.
///   This must be the same starting slot used to generate the delta.
/// * `base_buffer` - Destination circular root buffer. It is modified in place
///   and must have the same capacity as the buffer used to generate the delta.
/// * `delta` - Archived [`RootsDiff`] containing the roots to replay.
///
/// # Correctness
///
/// This function is the application counterpart to [`diff_roots`].
///
/// For correct reconstruction, `base_buffer` must have the same capacity as
/// the buffer supplied to [`diff_roots`], and `base_slot` must be the same
/// starting slot used when generating the delta.
///
/// The delta does not contain explicit buffer indices. Indices are derived
/// from `base_slot` and the destination buffer capacity. Contents at positions
/// outside the recorded slot range are preserved.
///
/// # Errors
///
/// Returns [`Error::InvalidDelta`] if `base_buffer` is empty.
///
/// # Example
///
/// ```
/// use eth_state_diff::recent_roots::{apply_roots, diff_roots};
/// use eth_state_diff::types::ArchivedRootsDiff;
///
/// let mut target_buffer = vec![[0u8; 32]; 4];
/// target_buffer[0] = [1u8; 32];
/// target_buffer[1] = [2u8; 32];
/// target_buffer[2] = [3u8; 32];
///
/// let delta = diff_roots(0, 3, &target_buffer);
///
/// let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("valid delta");
/// let archived = rkyv::access::<ArchivedRootsDiff, rkyv::rancor::Error>(&bytes)
///     .expect("test setup: failed to access archived delta");
///
/// let mut reconstructed = vec![[0u8; 32]; 4];
/// apply_roots(0, &mut reconstructed, archived).expect("valid delta");
///
/// assert_eq!(reconstructed, target_buffer);
/// ```
///
/// # Complexity
///
/// If `N` roots are stored in `delta`:
///
/// - Time: O(N)
/// - Additional space: O(1)
pub fn apply_roots(
    base_slot: u64,
    base_buffer: &mut [[u8; 32]],
    delta: &ArchivedRootsDiff,
) -> Result<(), Error> {
    if base_buffer.is_empty() {
        return Err(Error::InvalidDelta("root buffer must not be empty".into()));
    }

    let capacity = base_buffer.len() as u64;

    for (i, root) in delta.roots.iter().enumerate() {
        let slot = base_slot + i as u64;
        let idx = (slot % capacity) as usize;

        let Some(value) = base_buffer.get_mut(idx) else {
            return Err(Error::InvalidDelta(format!(
                "root index {idx} is out of bounds for buffer capacity {capacity}",
            )));
        };

        *value = *root;
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::ArchivedRootsDiff;

    /// Helper to perform a full roundtrip: diff -> rkyv serialize -> rkyv access -> apply
    fn assert_roundtrip(
        base_slot: u64,
        target_slot: u64,
        initial_buffer: &mut [[u8; 32]],
        target_buffer: &[[u8; 32]],
    ) {
        let delta = diff_roots(base_slot, target_slot, target_buffer);

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedRootsDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        apply_roots(base_slot, initial_buffer, archived).expect("test setup: apply");

        assert_eq!(initial_buffer, target_buffer);
    }

    #[test]
    fn test_diff_empty_span() {
        let buffer = vec![[0u8; 32]; 4];
        let delta = diff_roots(5, 5, &buffer);
        assert!(delta.roots.is_empty());
    }

    #[test]
    fn test_diff_and_apply_single_slot() {
        let mut target_buffer = vec![[0u8; 32]; 4];
        target_buffer[0] = [1u8; 32];

        let mut base_buffer = vec![[0u8; 32]; 4];
        assert_roundtrip(0, 1, &mut base_buffer, &target_buffer);
    }

    #[test]
    fn test_diff_and_apply_no_wrap() {
        let mut target_buffer = vec![[0u8; 32]; 4];
        target_buffer[0] = [1u8; 32];
        target_buffer[1] = [2u8; 32];
        target_buffer[2] = [3u8; 32];

        let mut base_buffer = vec![[0u8; 32]; 4];
        assert_roundtrip(0, 3, &mut base_buffer, &target_buffer);
    }

    #[test]
    fn test_diff_and_apply_with_wrap() {
        // Capacity 4. Slots 2, 3, 4.
        // Indices: 2 % 4 = 2, 3 % 4 = 3, 4 % 4 = 0.
        let mut target_buffer = vec![[0u8; 32]; 4];
        target_buffer[1] = [55u8; 32]; // Untouched index
        target_buffer[2] = [10u8; 32];
        target_buffer[3] = [11u8; 32];
        target_buffer[0] = [12u8; 32]; // Wrapped around

        // Base buffer must match the untouched index!
        let mut base_buffer = vec![[0u8; 32]; 4];
        base_buffer[1] = [55u8; 32];

        assert_roundtrip(2, 5, &mut base_buffer, &target_buffer);
    }

    #[test]
    fn test_diff_and_apply_multiple_wraps() {
        // Capacity 2. Slots 0, 1, 2, 3, 4.
        // Indices: 0, 1, 0, 1, 0.
        let mut target_buffer = vec![[0u8; 32]; 2];
        target_buffer[0] = [4u8; 32]; // Overwritten by slot 4
        target_buffer[1] = [3u8; 32]; // Overwritten by slot 3

        let mut base_buffer = vec![[0u8; 32]; 2];
        assert_roundtrip(0, 5, &mut base_buffer, &target_buffer);
    }

    #[test]
    fn test_apply_errors_on_empty_buffer() {
        let delta = RootsDiff {
            roots: vec![[0u8; 32]],
        };

        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("test setup: serialize");
        let archived = rkyv::access::<ArchivedRootsDiff, rkyv::rancor::Error>(&bytes)
            .expect("test setup: failed to access archived delta");

        let mut buffer: Vec<[u8; 32]> = vec![];
        let result = apply_roots(0, &mut buffer, archived);
        assert!(result.is_err());
        let err_str = format!("{}", result.expect_err("test setup"));
        assert!(err_str.contains("root buffer must not be empty"));
    }
}