Module pending_queue 

Delta encoding for SSZ lists that behave as FIFO queues.

This module computes compact deltas between serialized SSZ queues by identifying items that have been consumed from the front of the queue and items that have been appended to the back.

The encoding supports two representations:

• QueueDiff::Fifo records the number of items consumed from the front and the serialized items appended to the back.
• QueueDiff::FullReplacement stores the complete target queue when the FIFO relationship cannot be established safely.

The FIFO representation is suitable for consensus-layer queues whose logical behavior is append-at-the-back and consume-from-the-front, such as pending withdrawals and consolidations. It also supports queues such as pending deposits where reordering may occur: when the FIFO relationship cannot be proven from the serialized representation, the algorithm falls back to QueueDiff::FullReplacement rather than producing an unsafe delta.

Candidate detection and validation

To identify a candidate overlap, the encoder searches for the first item of the target queue within the base queue. Matching is performed only at valid SSZ item boundaries determined by item_ssz_size.

Finding an item alone is not sufficient to establish a FIFO transition. After a candidate overlap is found, the encoder verifies that the remaining bytes of the base queue exactly match the corresponding prefix of the target queue. Only after this validation succeeds is a QueueDiff::Fifo emitted.

If no valid overlap is found, or the remaining queue contents do not match, the encoder emits QueueDiff::FullReplacement containing the complete target queue.

This conservative fallback ensures that an ambiguous or reordered queue is never represented as an incorrect FIFO delta.

Representation

For a valid FIFO transition:

base:   [A, B, C, D]
target: [C, D, E, F]
                ^--- appended

consumed_count = 2
appended_items = [E, F]

Applying the delta removes A and B, then appends E and F.

Requirements

item_ssz_size must be the fixed serialized SSZ size of one queue item and must be greater than zero. The input buffers are expected to contain complete items, so their lengths should be exact multiples of item_ssz_size.

The module operates directly on serialized SSZ bytes and does not require deserializing individual queue items during diff generation.

Complexity

diff_queue performs a linear scan of the base queue for the target head, followed by a linear validation of the candidate overlap. The resulting algorithm is O(n) in the size of the serialized queues.

apply_queue performs O(n) work proportional to the bytes consumed and appended for a FIFO delta, or O(n) in the target queue size for a full replacement.

Example

const ITEM_SIZE: usize = 4;

let base = b"AAAABBBBCCCC";
let target = b"CCCCDDDDEEEE";

let delta = diff_queue(base, target, ITEM_SIZE);

assert_eq!(
    delta,
    QueueDiff::Fifo {
        consumed_count: 2,
        appended_items: b"DDDDEEEE".to_vec(),
    }
);

Functions

apply_queue

Applies a queue delta to a serialized SSZ queue in place.

diff_queue

Computes a delta between two serialized SSZ queues.