eth_state_diff/

randao_mixes.rs

//! Delta encoding for Ethereum RANDAO mix buffers.
//!
//! Ethereum consensus maintains historical RANDAO mixes in a fixed-capacity
//! circular buffer. Each epoch writes one mix, with the buffer index derived
//! from the epoch number modulo the buffer capacity.
//!
//! Rather than storing the complete RANDAO buffer, this module stores only the
//! sequence of mixes needed to reconstruct the target buffer over the epochs
//! covered by a slot transition. Applying the delta replays those epoch writes
//! using the same circular-buffer indexing rule.
//!
//! The delta therefore contains no buffer indices. Indices are reconstructed
//! deterministically from the starting slot and the destination buffer's
//! capacity.
//!
//! # Representation
//!
//! [`RandaoDiff`] stores one 32-byte RANDAO mix for each epoch in the inclusive
//! range from the epoch containing `base_slot` through the epoch containing
//! `target_slot`.
//!
//! For an epoch `e` and buffer capacity `N`, the mix is stored at:
//!
//! ```text
//! buffer_index = e % N
//! ```
//!
//! During application, the same indexing rule is used starting from the epoch
//! containing `base_slot`.
//!
//! # Correctness
//!
//! The source and destination buffers must have the same capacity. The delta
//! does not store explicit buffer indices; instead, indices are reconstructed
//! from the starting epoch and the destination buffer capacity.
//!
//! Consequently, applying a delta to a buffer with a different capacity can
//! write mixes to different positions and will not reconstruct the original
//! target state.
//!
//! The caller must also provide the same `base_slot` used when generating the
//! delta. Because the delta stores only the sequence of mixes, changing the
//! starting slot changes the epochs and therefore the destination indices at
//! which those mixes are written.
//!
//! # Workflow
//!
//! The typical workflow is:
//!
//! 1. Call [`diff_randao`] with the base slot, target slot, and target RANDAO
//!    buffer.
//! 2. Serialize the resulting [`RandaoDiff`] using `rkyv`.
//! 3. Store or compress the serialized delta.
//! 4. Deserialize/access the archived delta and apply it with
//!    [`apply_randao`] using the same `base_slot`.
//!
//! # Complexity
//!
//! If `E` is the number of epochs covered by the transition:
//!
//! - [`diff_randao`] runs in O(E) time and uses O(E) additional space.
//! - [`apply_randao`] runs in O(E) time and uses O(1) additional space.

use crate::{
    types::{ArchivedRandaoDiff, RandaoDiff, SLOTS_PER_EPOCH},
    Error,
};

/// Computes a RANDAO delta between two consensus slots.
///
/// The returned delta contains one RANDAO mix for every epoch in the inclusive
/// range from the epoch containing `base_slot` through the epoch containing
/// `target_slot`.
///
/// Each mix is read from `target_buffer` using the circular-buffer indexing
/// rule:
///
/// ```text
/// buffer_index = epoch % target_buffer.len()
/// ```
///
/// Only the mixes corresponding to the covered epochs are stored. The complete
/// target buffer is not copied.
///
/// # Arguments
///
/// * `base_slot` - Starting consensus slot. The epoch containing this slot is
///   the first epoch represented in the delta.
/// * `target_slot` - Ending consensus slot. The epoch containing this slot is
///   the final epoch represented in the delta.
/// * `target_buffer` - RANDAO mix buffer belonging to the target state.
///
/// # Returns
///
/// A [`RandaoDiff`] containing one mix for each epoch from the base epoch
/// through the target epoch, inclusive.
///
/// # Panics
///
/// Panics if `target_slot < base_slot`.
///
/// Panics if `target_buffer` is empty because circular-buffer indexing requires
/// a non-zero capacity.
///
/// # Correctness
///
/// The delta stores mixes in chronological epoch order rather than storing
/// their circular-buffer indices. During application, indices are reconstructed
/// using modulo arithmetic and the capacity of the destination buffer.
///
/// The buffer used with [`apply_randao`] must therefore have the same capacity
/// as `target_buffer`, and `apply_randao` must be given the same `base_slot`.
///
/// # Example
///
/// ```
/// use eth_state_diff::randao_mixes::diff_randao;
///
/// let base_slot = 0;
/// let target_slot = 64;
///
/// let target_buffer = vec![[0u8; 32]; 4];
///
/// let delta = diff_randao(base_slot, target_slot, &target_buffer);
///
/// // With 32 slots per epoch, slots 0 and 64 belong to epochs 0 and 2.
/// // The inclusive epoch range is therefore 0..=2.
/// assert_eq!(delta.mixes.len(), 3);
/// ```
///
/// # Complexity
///
/// If `E` is the number of epochs from the base epoch through the target
/// epoch, inclusive:
///
/// - Time: O(E)
/// - Additional space: O(E)
pub fn diff_randao(base_slot: u64, target_slot: u64, target_buffer: &[[u8; 32]]) -> RandaoDiff {
    assert!(
        target_slot >= base_slot,
        "target_slot must be greater than or equal to base_slot"
    );

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

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

    let epoch_count = (target_epoch - base_epoch)
        .checked_add(1)
        .expect("epoch count does not overflow u64");
    let mixes_cap = usize::try_from(epoch_count).expect("epoch count fits in usize");
    let mut mixes = Vec::with_capacity(mixes_cap);

    for epoch in base_epoch..=target_epoch {
        let idx = (epoch % capacity) as usize;
        mixes.push(
            *target_buffer
                .get(idx)
                .expect("modulo arithmetic guarantees index is within bounds"),
        );
    }

    RandaoDiff { mixes }
}

/// Applies a RANDAO delta to a circular mix buffer in place.
///
/// Each mix stored in `delta` is written to the destination buffer at the
/// position corresponding to its epoch. The first mix is written to the epoch
/// containing `base_slot`; each subsequent mix advances by one epoch.
///
/// The destination index is reconstructed using:
///
/// ```text
/// buffer_index = epoch % base_buffer.len()
/// ```
///
/// No allocation is performed while applying the delta.
///
/// # Arguments
///
/// * `base_slot` - Starting consensus slot corresponding to the first mix in
///   `delta`. This must be the same starting slot used by [`diff_randao`].
/// * `base_buffer` - Destination RANDAO circular buffer. It is modified in
///   place and must have the same capacity as the buffer used to generate
///   `delta`.
/// * `delta` - Archived [`RandaoDiff`] containing the mixes to replay.
///
/// # Correctness
///
/// This function is the application counterpart to [`diff_randao`].
///
/// For correct reconstruction, `base_buffer` must have the same capacity as
/// the target buffer supplied to [`diff_randao`], and `base_slot` must be the
/// same starting slot used when generating the delta.
///
/// The delta does not contain explicit buffer indices. The indices are derived
/// from the starting epoch and the buffer capacity. Changing either value
/// changes where the recorded mixes are written.
///
/// # Errors
///
/// Returns [`Error::InvalidDelta`] if `base_buffer` is empty.
///
/// # Example
///
/// ```
/// use eth_state_diff::randao_mixes::{apply_randao, diff_randao};
/// use eth_state_diff::types::ArchivedRandaoDiff;
///
/// let base_slot = 0;
/// let target_slot = 64;
///
/// // With 32 slots per epoch, epochs 0, 1, and 2 are covered.
/// 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_randao(base_slot, target_slot, &target_buffer);
///
/// let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&delta).expect("valid delta");
/// let archived = rkyv::access::<ArchivedRandaoDiff, rkyv::rancor::Error>(&bytes)
///     .expect("test setup: failed to access archived delta");
///
/// let mut reconstructed = vec![[0u8; 32]; 4];
/// apply_randao(base_slot, &mut reconstructed, archived).expect("valid delta");
///
/// assert_eq!(reconstructed, target_buffer);
/// ```
///
/// # Complexity
///
/// If `E` is the number of mixes stored in `delta`:
///
/// - Time: O(E)
/// - Additional space: O(1)
pub fn apply_randao(
    base_slot: u64,
    base_buffer: &mut [[u8; 32]],
    delta: &ArchivedRandaoDiff,
) -> Result<(), Error> {
    if base_buffer.is_empty() {
        return Err(Error::InvalidDelta(
            "RANDAO buffer must not be empty".into(),
        ));
    }

    let capacity = base_buffer.len() as u64;
    let mut current_epoch = base_slot / SLOTS_PER_EPOCH;

    for mix in delta.mixes.iter() {
        let idx = (current_epoch % capacity) as usize;

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

        *value = *mix;
        current_epoch += 1;
    }

    Ok(())
}

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

    /// 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_randao(base_slot, target_slot, target_buffer);

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

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

        assert_eq!(initial_buffer, target_buffer);
    }

    #[test]
    fn test_diff_and_apply_single_epoch() {
        // Slots 0 to 31 are all epoch 0
        let mut target_buffer = vec![[0u8; 32]; 4];
        target_buffer[0] = [1u8; 32];

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

    #[test]
    fn test_diff_and_apply_multiple_epochs() {
        // Slots 0 to 64 span epochs 0, 1, and 2.
        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, 64, &mut base_buffer, &target_buffer);
    }

    #[test]
    fn test_diff_and_apply_with_wrap() {
        // Capacity 2. Slots 0 to 95 span epochs 0, 1, and 2.
        // Indices: 0 % 2 = 0, 1 % 2 = 1, 2 % 2 = 0.
        let mut target_buffer = vec![[0u8; 32]; 2];
        target_buffer[0] = [3u8; 32]; // Overwritten by epoch 2
        target_buffer[1] = [2u8; 32]; // Overwritten by epoch 1

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

    #[test]
    fn test_diff_exact_slot_boundaries() {
        // Slot 32 is the exact start of epoch 1. Slot 63 is the end of epoch 1.
        let buffer = vec![[0u8; 32]; 4];

        let delta = diff_randao(32, 63, &buffer);
        // Should record exactly 1 mix (epoch 1)
        assert_eq!(delta.mixes.len(), 1);
    }

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

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

        let mut buffer: Vec<[u8; 32]> = vec![];
        let result = apply_randao(0, &mut buffer, archived);

        assert!(result.is_err());
        let err_str = format!("{}", result.expect_err("test setup"));
        assert!(err_str.contains("RANDAO buffer must not be empty"));
    }
}