Let's imagine a CSM deposit queue as a keys boxes conveyor at QC. Inspector checks as much boxes as it can in its shift. Node operator uploads keys and go to the back of the line placing its box in the queue with as much keys in it as it has uploaded. Until the turn comes to the box, node operator is free to change or remove broken keys from it. But if the inspector checks the box and find broken keys, it gets the good ones and returns the rest to the node operator. Operator places the next batch at the back of the conveyor.

Operator

Every node operator has its own sequence of uploaded keys. CSM stores pointers to the keys:

struct Operator {
  	/* cursors */
    uint256 totalAddedKeys;
    uint256 totalVettedKeys;

    /* ... irrelevant fields ommited ... */

    /* counters */
    uint256 enqueuedCount;
    uint256 depositableValidatorsCount;
}

Queue definition

Queue is a continious array of items with a pointer to its head. New items are being added to the end of the array.

struct Queue {
    uint128 head;
    uint128 length;
    mapping(uint128 => Batch) queue; // essentially an array
}

Every item has the following structure:

struct Batch {
    uint64    noId;      // ID of the node operator
    uint64    keysCount; // count of places in the queue grabbed by the operator (see `enqueuedCount`)
    uint128   next;      // index of the next item in the queue
}

Any item except noId expected to MAY be mutated for needs of the module.

The queue is traversable from the head to the length-1 by incrementing the head value. While traversing, the batch's field next is taken into account to set the head to the value of the field.

Queue capacity isn't known in advance and can be figured out by traversing the queue.

Optimistic vetting

It's assumed there's no need for the explicit key vetting, and reporting of invalid keys by the key validation oracle is expected instead. With this approach the totalVettedKeys and totalAddedKeys pointers are equal until node operator's unvetting. In this case the totalVettedKeys pointer is set to the index of the last valid key in the node operator's keys sequence.
To restore the totalVettedKeys and totalAddedKeys pointers equality it's required for a node operator to remove a key. It's supposed that the key validation oracle will report again if the issue isn't resolved and the totalVettedKeys pointer will be brought down again.

Keys obtaining

The module traverses the queue to get items. Every item is being processed and checked for the count of keys it's possible to request from the node operator corresponding to the item. The depositableValidatorsCount acts as a counter of how much keys it's possible to get from the node operator in total. The depositableValidatorsCount is being recomputed by the business logic of the module, thus is out of scope for this paper. Obtaining keys from the node operator SHOULD decrease the depositableValidatorsCount counter.

The enqueuedCount counter of a node operators shows how much places in the queue is allocated to the node operator at the moment, thus after consuming a batch of the node operator (e.g. by obtaining keys for deposits), the counter should be decreased by the count of keys deposited or skipped.

If a deposit requests all the keys an item may return, the item should be dequeued from the queue.

If a deposit requests less keys the item may return, the item's keysCount field is decreased by the count of keys requested. The next iteration should be started from the same item.

It's possible to have multiple items which returns no keys. The algorithm assumes skipping such items, but in case there are too much empty items its assumed to have a permissionless method to clean the queue. The method advances the queue's head pointer over the empty items and optionally shortcuts multiple items using the next field.

Node operator's actions

Queue normalization

If there is some count of keys eligible to place in the queue, the normalizeQueue is being called.

function normalizeQueue(no) {
    if (no.enqueuedCount < no.depositableValidatorsCount) {
        enqueue(no.depositableValidatorsCount - no.enqueuedCount);
        no.enqueuedCount = no.depositableValidatorsCount;
    }
}

Every time the depositableValidatorsCount is being updated for a node operator by the module business logic, it makes sense to call the normalizeQueue for this node operator to make sure the node operator will receive deposits for the eligible keys.

Adding new key

When a node operator uploads a new key its being enqueued if there is no unused slots dedicated to the operator in the queue at the moment, which is indicated by the enqueuedCount field of the operator:

function addKeys(keys, count) {
    storeKeys(keys);
    // otherwise the operator was unvetted, do not move vettedKeys
    // pointer to avoid extra-report of the oracle
    if (no.totalVettedKeys == no.totalAddedKeys) {
    	no.totalVettedKeys += count;
    }
    no.totalAddedKeys += count;
    normalizeQueue(no); // checks the `enqueuedCount` under the hood
    moduleNonce++;
}

Removing a key

When a node operator removes a key, it keeps its dedicated slots in place, until the queue moves over unused operator's slots. In this case the enqueuedCount field is decremented by the count of skipped slots. Removing a key sets totalVettedKeys equal to totalAddedKeys optimistically:

function removeKey(key) {
    remove(key);
    no.totalAddedKeys--;
    no.totalVettedKeys = no.totalAddedKeys;
    normalizeQueue(no);
    moduleNonce++;
}