eth_state_diff/

historical_log.rs

//! Delta encoding for append-only historical logs.
//!
//! Both `historical_roots` (Phase0 through Bellatrix) and
//! `historical_summaries` (Capella and later) are append-only logs that grow
//! according to the historical-period boundary defined by the consensus
//! protocol.
//!
//! This module uses the base and target slots to determine how many historical
//! items must have been appended. It therefore avoids comparing the complete
//! serialized log contents.
//!
//! The resulting delta contains only the newly appended SSZ items.

use crate::types::{ArchivedHistoricalLogDiff, HistoricalLogDiff};

/// Number of slots in one historical period.
const SLOTS_PER_HISTORICAL_PERIOD: u64 = 8192;

/// Calculates the expected number of historical log items at a given slot.
///
/// When `activation_slot` is provided, the log is considered inactive through
/// that slot and begins accumulating items afterwards. When no activation slot
/// is provided, the calculation starts from genesis.
///
/// This helper follows the historical-period calculation used by the
/// corresponding consensus state field.
#[inline]
fn calculate_log_count(slot: u64, activation_slot: Option<u64>) -> u64 {
    match activation_slot {
        Some(act_slot) if slot <= act_slot => 0,
        Some(act_slot) => (slot - act_slot) / SLOTS_PER_HISTORICAL_PERIOD,
        None => (slot + 1) / SLOTS_PER_HISTORICAL_PERIOD,
    }
}

/// Computes a delta between two historical log states.
///
/// The number of appended items is derived from `base_slot` and `target_slot`
/// using the protocol-defined historical period rather than by comparing the
/// serialized base and target logs.
///
/// Only the newly appended portion of `target_ssz` is stored in the returned
/// [`HistoricalLogDiff`].
///
/// # Arguments
///
/// * `base_slot` - Slot corresponding to the base state.
/// * `target_slot` - Slot corresponding to the target state.
/// * `target_ssz` - Complete serialized SSZ representation of the target
///   historical log.
/// * `item_ssz_size` - Serialized SSZ size of one historical log item.
/// * `activation_slot` - Optional slot at which the historical log becomes
///   active. This is used for logs introduced by a later fork.
///
/// # Returns
///
/// - [`HistoricalLogDiff::Unchanged`] if the protocol-derived log length has
///   not increased between the two slots.
/// - [`HistoricalLogDiff::Append`] containing the newly appended serialized
///   items otherwise.
///
/// # Panics
///
/// This function does not intentionally panic in release builds. In debug
/// builds, it asserts that `target_ssz` contains enough bytes for the number
/// of items derived from the slot calculation.
///
/// The caller must provide a non-zero `item_ssz_size` and a target SSZ buffer
/// consistent with the protocol-derived log length.
///
/// # Complexity
///
/// O(k) time and O(k) additional space, where *k* is the number of newly
/// appended serialized bytes. The number of existing log entries does not
/// affect the computation.
///
/// # Example
///
/// ```
/// use eth_state_diff::historical_log::diff_historical_log;
/// use eth_state_diff::types::HistoricalLogDiff;
///
/// const ITEM_SIZE: usize = 32;
///
/// // One historical period has elapsed, so one item is appended.
/// let target = vec![0u8; ITEM_SIZE];
///
/// let delta = diff_historical_log(
///     0,
///     8192,
///     &target,
///     ITEM_SIZE,
///     None,
/// );
///
/// assert_eq!(
///     delta,
///     HistoricalLogDiff::Append(target),
/// );
/// ```
pub fn diff_historical_log(
    base_slot: u64,
    target_slot: u64,
    target_ssz: &[u8],
    item_ssz_size: usize,
    activation_slot: Option<u64>,
) -> HistoricalLogDiff {
    let base_count = calculate_log_count(base_slot, activation_slot);
    let target_count = calculate_log_count(target_slot, activation_slot);

    // The consensus protocol strictly progresses forward in slots, meaning
    // `target_count` should always be >= `base_count`. A smaller target count
    // indicates an invalid state transition by the caller.
    let Some(items_to_append) = target_count.checked_sub(base_count) else {
        // If the caller violates the forward-progress invariant, we treat it
        // as no items appended to avoid panicking on underflow.
        return HistoricalLogDiff::Unchanged;
    };

    if items_to_append == 0 {
        return HistoricalLogDiff::Unchanged;
    }

    // Safely calculate the required bytes, guarding against usize overflow
    // on 32-bit systems if a caller provides an absurd `target_slot`.
    let required_bytes = usize::try_from(items_to_append)
        .ok()
        .and_then(|count| count.checked_mul(item_ssz_size))
        .expect("items_to_append * item_ssz_size fits in usize");

    debug_assert!(
        target_ssz.len() >= required_bytes,
        "Historical log math expects {required_bytes} bytes, but target_ssz is too short",
    );

    let start_byte = target_ssz.len().checked_sub(required_bytes).expect(
        "target_ssz must be large enough to hold the derived items, as guaranteed by caller",
    );

    let appended_bytes = target_ssz
        .get(start_byte..)
        .expect("start_byte is valid as it is derived from target_ssz.len()");

    HistoricalLogDiff::Append(appended_bytes.to_vec())
}

/// Applies a historical log delta to a serialized historical log in place.
///
/// [`HistoricalLogDiff::Unchanged`] leaves the existing log untouched.
///
/// [`HistoricalLogDiff::Append`] appends the serialized historical items
/// contained in the delta to the existing log.
///
/// The delta is assumed to have been generated for the supplied base state.
/// This function does not validate that the base log corresponds to the
/// state from which the delta was created.
///
/// # Complexity
///
/// - [`HistoricalLogDiff::Unchanged`][]: O(1).
/// - [`HistoricalLogDiff::Append`]: O(k), where *k* is the number of appended
///   bytes.
///
/// # Example
///
/// ```
/// use eth_state_diff::historical_log::{
///     apply_historical_log,
///     diff_historical_log,
/// };
/// use eth_state_diff::types::ArchivedHistoricalLogDiff;
///
/// const ITEM_SIZE: usize = 4;
///
/// let mut base = vec![1u8, 2, 3, 4];
/// let target = vec![1u8, 2, 3, 4, 5, 6, 7, 8];
///
/// let delta = diff_historical_log(
///     8191,
///     16384,
///     &target,
///     ITEM_SIZE,
///     None,
/// );
///
/// let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("failed to serialize");
/// let archived = rkyv::access::<ArchivedHistoricalLogDiff, rkyv::rancor::Error>(&bytes)
///     .expect("failed to access");
///
/// apply_historical_log(&mut base, archived);
///
/// assert_eq!(base, target);
/// ```
pub fn apply_historical_log(base: &mut Vec<u8>, delta: &ArchivedHistoricalLogDiff) {
    match delta {
        ArchivedHistoricalLogDiff::Unchanged => {}

        ArchivedHistoricalLogDiff::Append(bytes) => {
            base.extend_from_slice(bytes.as_slice());
        }
    }
}

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

    const ITEM_SIZE: usize = 32;

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

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

    #[test]
    fn test_calculate_log_count_genesis() {
        assert_eq!(calculate_log_count(0, None), 0);
    }

    #[test]
    fn test_calculate_log_count_first_period_end() {
        // Slot 8191 is the last slot of the first period.
        assert_eq!(calculate_log_count(8191, None), 1);
    }

    #[test]
    fn test_calculate_log_count_second_period_start() {
        // Slot 8192 is the first slot of the second period.
        assert_eq!(calculate_log_count(8192, None), 1);
    }

    #[test]
    fn test_calculate_log_count_exact_multiple() {
        // Slot 16383 is the last slot of the second period.
        assert_eq!(calculate_log_count(16383, None), 2);
    }

    #[test]
    fn test_calculate_log_count_before_activation() {
        assert_eq!(calculate_log_count(0, Some(1000)), 0);
        assert_eq!(calculate_log_count(1000, Some(1000)), 0);
    }

    #[test]
    fn test_calculate_log_count_just_after_activation() {
        // 1 slot after activation isn't enough for a full period
        assert_eq!(calculate_log_count(1001, Some(1000)), 0);
    }

    #[test]
    fn test_calculate_log_count_first_period_after_activation() {
        // Exactly 8192 slots after activation slot 1000 is slot 9192
        assert_eq!(calculate_log_count(9192, Some(1000)), 1);
    }

    #[test]
    fn test_diff_unchanged_within_period() {
        let target = vec![0u8; ITEM_SIZE * 2]; // Target has 2 items
                                               // Both slots are strictly inside the first period, no new boundary
                                               // crossed
        let delta = diff_historical_log(100, 200, &target, ITEM_SIZE, None);
        assert!(matches!(delta, HistoricalLogDiff::Unchanged));
    }

    #[test]
    fn test_diff_append_crosses_one_period() {
        // Base at 0 (0 items). Target at 8192 (1 item).
        let target = vec![1u8; ITEM_SIZE];
        let delta = diff_historical_log(0, 8192, &target, ITEM_SIZE, None);

        match delta {
            HistoricalLogDiff::Append(bytes) => assert_eq!(bytes, vec![1u8; ITEM_SIZE]),
            _ => panic!("test setup: expected Append"),
        }
    }

    #[test]
    fn test_diff_append_crosses_two_periods() {
        // Base at 8192 (1 item). Target at 16384 (2 items). Appends 1 item.
        let target = vec![0u8; ITEM_SIZE * 2];
        let delta = diff_historical_log(8191, 16383, &target, ITEM_SIZE, None);

        match delta {
            HistoricalLogDiff::Append(bytes) => {
                // Crucial test: ensure it ONLY grabs the appended slice, not the whole buffer
                assert_eq!(bytes.len(), ITEM_SIZE);
                assert_eq!(bytes, vec![0u8; ITEM_SIZE]);
            }
            _ => panic!("test setup: expected Append"),
        }
    }

    #[test]
    fn test_diff_unchanged_with_activation_slot() {
        let target = vec![0u8; ITEM_SIZE];
        let delta = diff_historical_log(0, 100, &target, ITEM_SIZE, Some(1000));
        assert!(matches!(delta, HistoricalLogDiff::Unchanged));
    }

    #[test]
    fn test_diff_append_with_activation_slot() {
        let target = vec![1u8; ITEM_SIZE];
        let delta = diff_historical_log(1000, 9192, &target, ITEM_SIZE, Some(1000));

        match delta {
            HistoricalLogDiff::Append(bytes) => assert_eq!(bytes, vec![1u8; ITEM_SIZE]),
            _ => panic!("test setup: expected Append"),
        }
    }

    #[test]
    fn test_apply_unchanged() {
        let mut base = vec![0u8; ITEM_SIZE];
        let delta = HistoricalLogDiff::Unchanged;

        let bytes = archive(&delta);
        let archived = archived(&bytes);

        apply_historical_log(&mut base, archived);
        assert_eq!(base, vec![0u8; ITEM_SIZE]);
    }

    #[test]
    fn test_apply_append() {
        let mut base = vec![0u8; ITEM_SIZE];
        let delta = HistoricalLogDiff::Append(vec![1u8; ITEM_SIZE]);

        let bytes = archive(&delta);
        let archived = archived(&bytes);

        apply_historical_log(&mut base, archived);

        let mut expected = vec![0u8; ITEM_SIZE];
        expected.extend_from_slice(&[1u8; ITEM_SIZE]);
        assert_eq!(base, expected);
    }

    #[test]
    fn test_full_roundtrip_no_change() {
        // Both slots are inside the same period, so 0 items are appended
        let base_slot = 100;
        let target_slot = 200;
        let target_ssz = vec![0u8; ITEM_SIZE]; // 1 item exists, but no new ones

        let delta = diff_historical_log(base_slot, target_slot, &target_ssz, ITEM_SIZE, None);

        let bytes = archive(&delta);
        let archived = archived(&bytes);

        let mut base_ssz = vec![0u8; ITEM_SIZE];
        apply_historical_log(&mut base_ssz, archived);

        assert_eq!(base_ssz, target_ssz);
    }

    #[test]
    fn test_full_roundtrip_with_append() {
        // Crossing the first boundary (slot 8191 is the end of the first period)
        let base_slot = 0;
        let target_slot = 8191;
        let target_ssz = vec![0u8; ITEM_SIZE]; // 1 item appended

        let delta = diff_historical_log(base_slot, target_slot, &target_ssz, ITEM_SIZE, None);

        let bytes = archive(&delta);
        let archived = archived(&bytes);

        let mut base_ssz = vec![]; // Base had 0 items
        apply_historical_log(&mut base_ssz, archived);

        assert_eq!(base_ssz, target_ssz);
    }
}