eth-state-diff 0.2.2

//! 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::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[idx];
        let target_value = target_buffer[idx];

        if base_value != target_value {
            updates.push((idx as 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).unwrap();
/// let archived = unsafe {
///     rkyv::access_unchecked::<ArchivedSlashingsDiff>(&bytes)
/// };
///
/// let mut reconstructed = base_buffer.clone();
/// apply_slashings(&mut reconstructed, archived);
///
/// 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) {
    for update in delta.updates.iter() {
        let idx = update.0.to_native() as usize;
        let value = update.1.to_native();

        base_buffer[idx] = value;
    }
}