eth-state-diff 0.2.3

//! Delta encoding for Ethereum slashing vectors.
//!
//! Ethereum consensus stores slashing totals in a fixed-capacity circular
//! buffer indexed by epoch.
//!
//! Unlike root and RANDAO buffers, where every slot or epoch transition may
//! require recording a new value, slashing totals are comparatively sparse.
//! This module therefore records only ring-buffer entries whose values differ
//! between the base and target states at the ring positions touched by the
//! epoch transition.
//!
//! The delta stores `(ring_index, value)` pairs. Applying the delta writes only
//! those recorded values into the destination buffer; all other entries remain
//! untouched.
//!
//! # Epoch Mapping
//!
//! Ring-buffer indices are derived from the epoch number:
//!
//! ```text
//! ring_index = epoch % buffer_capacity
//! ```
//!
//! [`diff_slashings`] examines the ring positions corresponding to the epoch
//! boundaries crossed between `base_slot` and `target_slot`. The base epoch
//! itself is not examined. For a transition from `base_epoch` to
//! `target_epoch`, the epochs mapped to ring positions are:
//!
//! ```text
//! base_epoch + 1, ..., target_epoch
//! ```
//!
//! If both slots belong to the same epoch, no ring positions are examined and
//! the resulting delta is empty.
//!
//! If the transition spans more than one complete ring cycle, the same
//! ring-buffer index may be examined more than once. Each occurrence compares
//! the current values at that index in the base and target buffers. Applying
//! the resulting updates in order still reconstructs the target buffer.
//!
//! # Correctness
//!
//! The base and target buffers must have the same capacity and represent the
//! same logical slashing ring. The delta stores ring indices rather than epoch
//! numbers, so the buffer capacity is part of the implicit representation.
//!
//! Applying a delta to a buffer with a different capacity, layout, or unrelated
//! state can write values to incorrect positions.
//!
//! The delta only records positions whose base and target values differ among
//! the ring positions examined by the transition. Positions omitted from the
//! delta are expected to already contain their target values.
//!
//! # Complexity
//!
//! If `E` is the number of epoch boundaries crossed by the transition:
//!
//! - [`diff_slashings`] runs in O(E) time and O(U) additional space, where `U`
//!   is the number of recorded updates.
//! - [`apply_slashings`] runs in O(U) time and O(1) additional space.

use crate::{
    error::Error,
    types::{ArchivedSlashingsDiff, SlashingsDiff, SLOTS_PER_EPOCH},
};

/// Computes a sparse delta between two slashing ring buffers.
///
/// The function examines the ring-buffer positions corresponding to epoch
/// boundaries crossed between `base_slot` and `target_slot`.
///
/// For a base epoch `B` and target epoch `T`, the examined epochs are:
///
/// ```text
/// B + 1, B + 2, ..., T
/// ```
///
/// For each examined epoch `E`, its ring-buffer position is:
///
/// ```text
/// index = E % buffer_capacity
/// ```
///
/// The values at that position are then compared between `base_buffer` and
/// `target_buffer`. If they differ, the target value is recorded in the
/// returned [`SlashingsDiff`].
///
/// If the transition spans multiple complete ring cycles, a ring index may be
/// examined multiple times. In that case, the same index may produce multiple
/// updates containing the same target value. This is redundant but remains
/// correct because applying the updates leaves the destination with the target
/// value at that index.
///
/// # Arguments
///
/// * `base_slot` - Slot belonging to the base state.
/// * `target_slot` - Slot belonging to the target state.
/// * `base_buffer` - Slashing ring buffer belonging to the base state.
/// * `target_buffer` - Slashing ring buffer belonging to the target state.
///
/// # Returns
///
/// A [`SlashingsDiff`] containing updates for ring-buffer positions whose base
/// and target values differ at one or more epoch boundaries crossed by the
/// transition.
///
/// If `base_slot` and `target_slot` belong to the same epoch, the returned
/// delta contains no updates.
///
/// # Panics
///
/// Panics if `target_slot < base_slot`.
///
/// Panics if `base_buffer` or `target_buffer` is empty.
///
/// Panics if `base_buffer` and `target_buffer` have different lengths.
///
/// # Correctness
///
/// The two buffers must have the same capacity and correspond to the same
/// logical slashing ring.
///
/// The delta stores ring indices rather than epoch numbers. Consequently, the
/// buffer capacity and logical layout are part of the implicit encoding and
/// must remain unchanged when applying the resulting delta.
///
/// # Example
///
/// ```
/// use eth_state_diff::slashings::diff_slashings;
///
/// let base_buffer = vec![0u64; 4];
/// let mut target_buffer = vec![0u64; 4];
///
/// // The transition crosses from epoch 0 to epoch 1.
/// target_buffer[1] = 100;
///
/// let delta = diff_slashings(
///     0,
///     eth_state_diff::types::SLOTS_PER_EPOCH,
///     &base_buffer,
///     &target_buffer,
/// );
///
/// assert_eq!(delta.updates.len(), 1);
/// assert_eq!(delta.updates[0], (1, 100));
/// ```
///
/// # Complexity
///
/// If `E` epoch boundaries are crossed and `U` updates are recorded:
///
/// - Time: O(E)
/// - Additional space: O(U)
pub fn diff_slashings(
    base_slot: u64,
    target_slot: u64,
    base_buffer: &[u64],
    target_buffer: &[u64],
) -> SlashingsDiff {
    assert!(
        target_slot >= base_slot,
        "target_slot must be greater than or equal to base_slot"
    );

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

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

    assert_eq!(
        base_buffer.len(),
        target_buffer.len(),
        "base and target slashing buffers must have the same capacity"
    );

    let base_epoch = base_slot / SLOTS_PER_EPOCH;
    let target_epoch = target_slot / SLOTS_PER_EPOCH;
    let capacity = base_buffer.len() as u64;

    let mut updates = Vec::new();
    let mut current_epoch = base_epoch;

    while current_epoch < target_epoch {
        current_epoch += 1;

        let idx = (current_epoch % capacity) as usize;

        let base_value = *base_buffer
            .get(idx)
            .expect("modulo arithmetic guarantees index is within bounds");
        let target_value = *target_buffer
            .get(idx)
            .expect("modulo arithmetic guarantees index is within bounds");

        if base_value != target_value {
            let idx_u16 = u16::try_from(idx).expect("slashing buffer capacity exceeds u16");
            updates.push((idx_u16, target_value));
        }
    }

    SlashingsDiff { updates }
}

/// Applies a sparse slashing delta to a circular slashing buffer in place.
///
/// Each update in `delta` contains a ring-buffer index and its replacement
/// value. Only the recorded indices are modified; all other entries in
/// `base_buffer` remain unchanged.
///
/// The delta already contains the ring-buffer indices, so no epoch calculation
/// is required during application.
///
/// # Arguments
///
/// * `base_buffer` - Destination slashing ring buffer. It is modified in place.
/// * `delta` - Archived [`SlashingsDiff`] containing the sparse updates.
///
/// # Correctness
///
/// The destination buffer must have the same capacity and logical ring layout
/// as the buffer used to create the delta.
///
/// After successful application, every index represented by the delta contains
/// its recorded target value. Entries omitted from the delta retain their
/// existing values.
///
/// # Panics
///
/// Panics if an update contains an index outside `base_buffer`.
///
/// # Example
///
/// ```
/// use eth_state_diff::slashings::{apply_slashings, diff_slashings};
/// use eth_state_diff::types::ArchivedSlashingsDiff;
///
/// let base_buffer = vec![0u64; 4];
/// let mut target_buffer = vec![0u64; 4];
/// target_buffer[1] = 100;
///
/// let delta = diff_slashings(
///     0,
///     eth_state_diff::types::SLOTS_PER_EPOCH,
///     &base_buffer,
///     &target_buffer,
/// );
///
/// let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("failed to serialize");
/// let archived = rkyv::access::<ArchivedSlashingsDiff, rkyv::rancor::Error>(&bytes)
///     .expect("failed to access");
///
/// let mut reconstructed = base_buffer.clone();
/// apply_slashings(&mut reconstructed, archived).expect("failed to apply");
///
/// assert_eq!(reconstructed, target_buffer);
/// ```
///
/// # Complexity
///
/// If `U` updates are stored in the delta:
///
/// - Time: O(U)
/// - Additional space: O(1)
pub fn apply_slashings(
    base_buffer: &mut [u64],
    delta: &ArchivedSlashingsDiff,
) -> Result<(), Error> {
    for update in delta.updates.iter() {
        let idx = update.0.to_native() as usize;
        let value = update.1.to_native();

        let Some(target) = base_buffer.get_mut(idx) else {
            return Err(Error::MalformedDelta(format!(
                "slashing index {idx} is out of bounds for buffer of length {}",
                base_buffer.len()
            )));
        };
        *target = value;
    }
    Ok(())
}

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

    fn archive(diff: &SlashingsDiff) -> rkyv::util::AlignedVec {
        rkyv::to_bytes::<rkyv::rancor::Error>(diff).expect("test setup: failed to serialize delta")
    }

    fn archived(bytes: &[u8]) -> &ArchivedSlashingsDiff {
        rkyv::access::<ArchivedSlashingsDiff, rkyv::rancor::Error>(bytes)
            .expect("test setup: failed to access archived delta")
    }

    #[test]
    fn diff_same_epoch_is_empty() {
        let base = vec![0u64; 4];
        let target = vec![0u64; 4];

        // Same epoch (epoch 0)
        let delta = diff_slashings(0, SLOTS_PER_EPOCH - 1, &base, &target);
        assert!(delta.updates.is_empty());

        // Same epoch (epoch 1)
        let delta = diff_slashings(SLOTS_PER_EPOCH, 2 * SLOTS_PER_EPOCH - 1, &base, &target);
        assert!(delta.updates.is_empty());
    }

    #[test]
    fn diff_single_epoch_transition() {
        let base = vec![0u64; 4];
        let mut target = vec![0u64; 4];
        // Epoch 0 to 1 touches index 1
        target[1] = 100;

        let delta = diff_slashings(0, SLOTS_PER_EPOCH, &base, &target);

        assert_eq!(delta.updates.len(), 1);
        assert_eq!(delta.updates[0], (1, 100));
    }

    #[test]
    fn diff_ignores_untouched_indices() {
        let base = vec![0u64; 4];
        let mut target = vec![0u64; 4];

        // Epoch 0 to 1 only touches index 1
        target[1] = 100; // Touched and modified
        target[2] = 99; // Untouched, but modified in target

        let delta = diff_slashings(0, SLOTS_PER_EPOCH, &base, &target);

        // Should only record the update for index 1
        assert_eq!(delta.updates.len(), 1);
        assert_eq!(delta.updates[0], (1, 100));
    }

    #[test]
    fn diff_wraps_around_capacity() {
        let base = vec![0u64; 4];
        let mut target = vec![0u64; 4];

        // Epoch 2 to 6 -> touches epochs 3, 4, 5, 6
        // Indices: 3 % 4 = 3, 4 % 4 = 0, 5 % 4 = 1, 6 % 4 = 2
        target[3] = 10;
        target[0] = 20;
        target[1] = 30;
        target[2] = 40;

        let delta = diff_slashings(2 * SLOTS_PER_EPOCH, 6 * SLOTS_PER_EPOCH, &base, &target);

        assert_eq!(delta.updates.len(), 4);
        assert_eq!(delta.updates[0], (3, 10));
        assert_eq!(delta.updates[1], (0, 20));
        assert_eq!(delta.updates[2], (1, 30));
        assert_eq!(delta.updates[3], (2, 40));
    }

    #[test]
    fn diff_multiple_cycles_produces_redundant_updates() {
        let base = vec![0u64; 4];
        let mut target = vec![0u64; 4];

        // Epoch 0 to 10 -> touches 10 epoch boundaries
        // Indices touched: 1, 2, 3, 0, 1, 2, 3, 0, 1, 2
        target[0] = 99;
        target[1] = 88;
        target[2] = 77;
        target[3] = 66;

        let delta = diff_slashings(0, 10 * SLOTS_PER_EPOCH, &base, &target);

        // All 10 touched epochs differ from base, yielding 10 updates.
        assert_eq!(delta.updates.len(), 10);

        // Verify that the same index is recorded multiple times.
        assert_eq!(delta.updates[0], (1, 88)); // Epoch 1
        assert_eq!(delta.updates[4], (1, 88)); // Epoch 5
        assert_eq!(delta.updates[8], (1, 88)); // Epoch 9
    }

    #[test]
    fn diff_omits_unchanged_indices() {
        let mut base = vec![0u64; 4];
        let mut target = vec![0u64; 4];

        // Epoch 0 to 2 -> touches indices 1 and 2
        base[1] = 10;
        base[2] = 20;

        target[1] = 10; // Unchanged
        target[2] = 99; // Changed

        let delta = diff_slashings(0, 2 * SLOTS_PER_EPOCH, &base, &target);

        assert_eq!(delta.updates.len(), 1);
        assert_eq!(delta.updates[0], (2, 99));
    }

    #[test]
    fn apply_reconstructs_target() {
        let base = vec![0u64; 4];
        let mut target = vec![0u64; 4];

        // Epoch 0 to 10
        target[0] = 99;
        target[1] = 88;
        target[2] = 77;
        target[3] = 66;

        let delta = diff_slashings(0, 10 * SLOTS_PER_EPOCH, &base, &target);
        let bytes = archive(&delta);

        let mut reconstructed = base.clone();
        apply_slashings(&mut reconstructed, archived(&bytes)).expect("test setup: apply");

        assert_eq!(reconstructed, target);
    }

    #[test]
    fn apply_no_op_when_empty() {
        let base = vec![0u64; 4];
        let target = vec![0u64; 4];

        // Same epoch -> empty delta
        let delta = diff_slashings(0, SLOTS_PER_EPOCH - 1, &base, &target);
        let bytes = archive(&delta);

        let mut reconstructed = base.clone();
        apply_slashings(&mut reconstructed, archived(&bytes)).expect("test setup: apply");

        assert_eq!(reconstructed, base);
    }

    #[test]
    #[should_panic(expected = "target_slot must be greater than or equal to base_slot")]
    fn diff_panics_on_target_before_base() {
        let base = vec![0u64; 4];
        let target = vec![0u64; 4];
        diff_slashings(SLOTS_PER_EPOCH, 0, &base, &target);
    }

    #[test]
    #[should_panic(expected = "slashing buffer must not be empty")]
    fn diff_panics_on_empty_base_buffer() {
        diff_slashings(0, SLOTS_PER_EPOCH, &[], &[0u64]);
    }

    #[test]
    #[should_panic(expected = "slashing buffer must not be empty")]
    fn diff_panics_on_empty_target_buffer() {
        diff_slashings(0, SLOTS_PER_EPOCH, &[0u64], &[]);
    }

    #[test]
    #[should_panic(expected = "base and target slashing buffers must have the same capacity")]
    fn diff_panics_on_mismatched_capacity() {
        diff_slashings(0, SLOTS_PER_EPOCH, &[0u64; 4], &[0u64; 8]);
    }
}