rhdl_dsig_scalable_core/

slice_schedule.rs

//! The fixed timetable that lets one BLAKE3 lane serve a whole slice.
//!
//! This module is pure compile-time arithmetic: no hardware. It answers one
//! question for [`crate::slice_factory`]: "in which cycle does each BLAKE3
//! compression of a key run?" The factory then turns the answer into small
//! constant tables ([`SLOTS`](crate::slice_factory::SLOTS),
//! [`WINDOW_LOADS`](crate::slice_factory::WINDOW_LOADS)) that a 0..=67
//! counter indexes.
//!
//! # The problem
//!
//! A [slice](crate::sustained) starts one key every [`KEY_PERIOD`] = 68 cycles,
//! because its chain engine accepts one of the key's 68 chains per cycle. Each
//! key needs 46 BLAKE3 compressions (seed, two nonces, 20 XOF blocks, a 21-block
//! endpoint commitment, a Merkle share and a message hash), and they all share
//! **one** pipelined BLAKE3 lane that accepts one compression per cycle.
//! Several keys are in flight at once, and some compressions depend on others,
//! up to 16 in a strict chain.
//!
//! (The "21-block endpoint commitment" counts its 20 data blocks plus the
//! parent that joins its two chunks: 3 + 20 + 21 + 2 = 46 slots, out of 68.)
//!
//! # The trick: a modulo schedule
//!
//! Give every compression of a key a fixed *offset* from the cycle `T` when that
//! key's chain 0 enters the chain engine. Key `k` starts at `T₀ + 68k`, so its
//! compression with offset `x` issues at `T₀ + 68k + x`. Two keys collide on the
//! lane only if two offsets are equal **mod 68**. So if every offset in the table
//! has a different residue mod 68, no two compressions ever collide, however
//! many keys overlap.
//!
//! ```text
//!   cycle mod 68:  0  1  2  3  4  5  …                              67
//!   op issued:     X7 C0 ·  P  X8 C1 …     one op (or idle) per residue
//!                   │  └ chunk-0 block of the key that started 1 period ago
//!                   └ XOF block 7 of the key that starts next period
//! ```
//!
//! The hardware is then a 68-entry table ([`Schedule::residue`]) and a counter,
//! with no arbiter. To stall, a slice simply does not start a key in some
//! period; every compression of that key becomes an idle slot.
//!
//! Words used below:
//!
//! | Term | Meaning |
//! |---|---|
//! | `T` | the cycle at which the key's chain 0 enters the chain engine |
//! | offset | an op's issue cycle minus `T`; negative = before chain 0 |
//! | residue | a cycle number mod 68; the hardware's counter value |
//! | period | 68 consecutive cycles, residue 0 to 67 |
//! | lag | `offset div 68`: in which period, relative to the key's own, the op runs |
//! | `D` | [`Schedule::use_delay`]: cycles from issue until a result can be used |
//!
//! # One key's life on the timeline
//!
//! ```text
//!   offset:  ≪0 ───────────────── 0 ────────── 67 ─────────────────────────▶
//!            Seed ─D─▶ PkNonce, Nonce
//!                 └D─▶ Xof(0..19), each D before the first chain that needs it
//!                                 chains 0..67 enter, one per cycle
//!                                           chain ends emerge (end_delay later)
//!                                              Chunk0(0) ─≥D─▶ Chunk0(1) … Chunk0(15)
//!                                                   Chunk1(0) ─≥D─▶ … Chunk1(3)
//!                                                                  ─D─▶ Parent → pk_hash
//! ```
//!
//! Preparation ops are placed **as late as possible** (so their results wait
//! in storage for the shortest time), and commitment ops **as early as
//! possible** (so the key finishes soon). Each op then lands on the nearest
//! residue no other op has taken.
//!
//! # Constraints the solver enforces
//!
//! A result is usable [`Schedule::use_delay`] cycles after its compression
//! issues: the BLAKE3 latency, one output register, then a write into and a
//! registered read from the slice's per-key context RAM (latency + 4).
//!
//! * **Seed first.** Nonces and XOF blocks hash the seed: each issues ≥ `D` after it.
//! * **XOF in time.** Chain `i` needs bytes `18i..18i+18` of the XOF stream when
//!   it issues at `T + i`, so each XOF block is ready before its first chain.
//! * **Salt in time.** `pk_nonce` salts every chain, so it is ready before `T`.
//! * **Commitment follows the chain ends.** The commitment hashes
//!   `pk_nonce ‖ end₀ ‖ … ‖ end₆₇` (1,240 bytes) as 20 blocks: chunk 0 is blocks
//!   0–15, chunk 1 is blocks 16–19. Block `j` needs every chain end that
//!   touches it, and each chunk's blocks chain through their chaining values,
//!   so consecutive blocks are ≥ `D` apart.
//! * **Parent last.** The `pk_hash` parent combines both chunks.
//!
//! The Merkle-share and message slots are reserved residues whose data comes
//! from elsewhere; their readiness is checked by the controllers that use them.
//! `tests/slice_schedule.rs` re-verifies every constraint independently.
//!
//! # How the solver works
//!
//! [`solve`] is a greedy, compile-time search. A table of 68 "used" flags
//! records which residues are taken.
//!
//! 1. Chunk 0 first: 16 blocks, each needing the previous one's chaining
//!    value, is the hardest fit. `solve_chunk` tries every start `base` and
//!    every spacing `gap ≥ D` (within one period of the earliest choice) and
//!    keeps the placement that finishes earliest without collisions.
//! 2. Chunk 1 the same way, around what chunk 0 took.
//! 3. The parent at the first free residue `D` after both chunks.
//! 4. XOF blocks, last to first, each at the latest free residue that is
//!    still `D` before its first chain.
//! 5. The two nonces at the latest free residue `D` before `T`.
//! 6. The seed at the latest free residue `D` before its earliest user.
//! 7. The Merkle and message slots at the first free residues from offset 0.
//!
//! If any step finds no room, `solve` fails at compile time, so a bad
//! timetable can never reach hardware.

use crate::{CHAINS, ELEMENT_BYTES};

/// Cycles between consecutive key starts in a slice (one chain per cycle).
///
/// 68: the chain engine takes one chain per cycle and a key has 68 chains.
pub const KEY_PERIOD: usize = CHAINS;
/// XOF output blocks holding the 68 eighteen-byte chain secrets.
///
/// 68 × 18 = 1,224 bytes, rounded up to whole 64-byte blocks: 20.
pub const XOF_BLOCKS: usize = (CHAINS * ELEMENT_BYTES).div_ceil(64);
/// Endpoint-commitment blocks in the first 1,024-byte chunk.
///
/// BLAKE3 hashes input in chunks of 1,024 bytes = 16 blocks of 64 bytes.
pub const CHUNK0_BLOCKS: usize = 16;
/// Endpoint-commitment blocks in the 216-byte second chunk.
///
/// 216 = 3 × 64 + 24, so 4 blocks, the last one 24 bytes long.
pub const CHUNK1_BLOCKS: usize = 4;
/// Bytes hashed by the endpoint commitment: `pk_nonce` and 68 chain ends.
///
/// 16 + 68 × 18 = 1,240 bytes.
pub const COMMITMENT_BYTES: usize = 16 + CHAINS * ELEMENT_BYTES;

/// One kind of compression in the per-key timetable.
///
/// Software-side names. The factory maps each to a 4-bit hardware code
/// ([`crate::slice_factory::code`]).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Op {
    /// Derive the one-time seed (derive-key material block).
    Seed,
    /// `pk_nonce`: public salt for every chain of this key.
    PkNonce,
    /// Signer-private message nonce.
    Nonce,
    /// XOF block `n` of the chain-secret stream.
    Xof(u8),
    /// Endpoint-commitment chunk-0 block `n`.
    Chunk0(u8),
    /// Endpoint-commitment chunk-1 block `n`.
    Chunk1(u8),
    /// Combine both chunk chaining values into `pk_hash`.
    Parent,
    /// Reserved slot for one 16-leaf Merkle-subtree parent.
    Merkle,
    /// Reserved slot for one message-digit hash.
    Message,
    /// Profile 2 only: a second message slot for the digest's tail block.
    MessageTail,
}

/// Number of scheduled compressions or reserved slots per key.
///
/// 3 (seed, two nonces) + 20 XOF + 16 + 4 commitment + 1 parent + 2 reserved
/// = 46, plus profile 2's message-tail slot (47). The rest of the 68
/// residues are idle.
pub const OPS: usize = BASE_OPS + TAIL_OPS;
/// The ops of every profile.
const BASE_OPS: usize = 3 + XOF_BLOCKS + CHUNK0_BLOCKS + CHUNK1_BLOCKS + 1 + 2;
/// Profile 2 (`DSIG_MESSAGE_BYTES=64`) hashes the message in two blocks.
const TAIL_OPS: usize = if crate::MESSAGE_BYTES == 64 { 1 } else { 0 };
/// Cycles between a message result leaving the lane and its tail request
/// being ready (result register, signer latch, request register, margin).
pub const TAIL_SLACK: i32 = 6;

/// The op stored at position `index` of [`Schedule::offsets`].
///
/// The layout is: seed, pk_nonce, nonce, XOF 0..20, chunk-0 0..16,
/// chunk-1 0..4, parent, Merkle, message.
#[must_use]
pub const fn op_at(index: usize) -> Op {
    match index {
        0 => Op::Seed,
        1 => Op::PkNonce,
        2 => Op::Nonce,
        i if i < 3 + XOF_BLOCKS => Op::Xof((i - 3) as u8),
        i if i < 3 + XOF_BLOCKS + CHUNK0_BLOCKS => Op::Chunk0((i - 3 - XOF_BLOCKS) as u8),
        i if i < 3 + XOF_BLOCKS + CHUNK0_BLOCKS + CHUNK1_BLOCKS => {
            Op::Chunk1((i - 3 - XOF_BLOCKS - CHUNK0_BLOCKS) as u8)
        }
        i if i == BASE_OPS - 3 => Op::Parent,
        i if i == BASE_OPS - 2 => Op::Merkle,
        i if i == BASE_OPS - 1 => Op::Message,
        _ => Op::MessageTail,
    }
}

/// Index of an op in [`Schedule::offsets`]; the inverse of [`op_at`].
#[must_use]
pub const fn op_index(op: Op) -> usize {
    match op {
        Op::Seed => 0,
        Op::PkNonce => 1,
        Op::Nonce => 2,
        Op::Xof(n) => 3 + n as usize,
        Op::Chunk0(n) => 3 + XOF_BLOCKS + n as usize,
        Op::Chunk1(n) => 3 + XOF_BLOCKS + CHUNK0_BLOCKS + n as usize,
        Op::Parent => BASE_OPS - 3,
        Op::Merkle => BASE_OPS - 2,
        Op::Message => BASE_OPS - 1,
        Op::MessageTail => BASE_OPS,
    }
}

/// A complete, collision-free timetable for one slice.
///
/// `offsets` and `residue` are two views of the same placement: per op ("when
/// does op `i` run?") and per residue ("which op runs at residue `r`?").
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Schedule {
    /// Issue cycle of each op relative to the key's chain-0 cycle `T`.
    ///
    /// Indexed by [`op_index`]. In cycles; may be negative.
    pub offsets: [i32; OPS],
    /// For each residue mod 68, the op index issued there (`None` = idle).
    ///
    /// The hardware's lookup table. Distinct residues per op are what make
    /// the schedule collision-free.
    pub residue: [Option<u8>; KEY_PERIOD],
    /// Cycles from issuing a compression until its result is usable (latency + 4).
    ///
    /// The `+ 4` covers the lane's output register and the round trip through
    /// the factory's context RAM (a write, then a registered read) before the
    /// consuming op issues. With the 28-stage BLAKE3 lane this is 32.
    pub use_delay: i32,
    /// Cycles from a chain's issue until its end is stored for the commitment.
    ///
    /// Supplied by the caller ([`END_DELAY`](crate::slice_factory::END_DELAY));
    /// depends on the compiled-in chain hash.
    pub end_delay: i32,
}

/// First cycle (relative to `T`) at which commitment block `block` is complete.
///
/// Chain end `i` occupies commitment bytes `16 + 18i .. 34 + 18i` and is
/// available `end_delay` cycles after its chain issues at `T + i`. The packer
/// that assembles 64-byte blocks adds one register.
#[must_use]
pub const fn block_ready(block: usize, end_delay: i32) -> i32 {
    // One past the block's last byte (the final block is short).
    let block_end = if 64 * (block + 1) < COMMITMENT_BYTES {
        64 * (block + 1)
    } else {
        COMMITMENT_BYTES
    };
    // Last chain end with a byte inside this block.
    let last = (block_end - 16 - 1) / ELEMENT_BYTES;
    // Chain `last` issues at T + last, its end is stored end_delay later,
    // and the packer's register adds one cycle.
    last as i32 + end_delay + 1
}

/// First chain that reads XOF block `block`.
///
/// Chain `c` reads XOF bytes `18c..18c+18`. The answer is the smallest `c`
/// whose last byte falls in or after block `block`, that is
/// `18c + 18 > 64 · block`. Chain `c` issues at `T + c`, so this is also the
/// offset by which the block must be in the window.
#[must_use]
pub const fn first_chain_of_xof(block: usize) -> i32 {
    // Walk forward while chain `chain` still ends before the block starts.
    let mut chain = 0;
    while ELEMENT_BYTES * chain + ELEMENT_BYTES <= 64 * block {
        chain += 1;
    }
    chain as i32
}

/// Residue (0..68) of an offset; correct for negative offsets too, because
/// `rem_euclid` never returns a negative value.
const fn residue_of(offset: i32) -> usize {
    offset.rem_euclid(KEY_PERIOD as i32) as usize
}

/// Claims the residue of `offset` if it is free.
///
/// Returns `true` (and marks the residue used) on success, `false` if
/// another op already sits on that residue.
const fn take(used: &mut [bool; KEY_PERIOD], offset: i32) -> bool {
    let r = residue_of(offset);
    if used[r] {
        // Taken: this offset would collide with another op.
        false
    } else {
        used[r] = true;
        true
    }
}

/// Latest offset `<= limit` with a free residue (claims it).
///
/// Used for preparation ops: `limit` is the last cycle at which the op can
/// still issue and deliver on time; we step earlier until a residue is free.
/// Terminates while fewer than 68 residues are used.
const fn latest_free(used: &mut [bool; KEY_PERIOD], limit: i32) -> i32 {
    // Try the deadline itself first, then one cycle earlier each time.
    let mut offset = limit;
    while !take(used, offset) {
        offset -= 1;
    }
    offset
}

/// Earliest offset `>= limit` with a free residue (claims it).
///
/// Used for ops that should run as soon as their inputs are ready: `limit`
/// is the first cycle their inputs exist; we step later until a residue is
/// free.
const fn earliest_free(used: &mut [bool; KEY_PERIOD], limit: i32) -> i32 {
    // Try the earliest allowed cycle first, then one cycle later each time.
    let mut offset = limit;
    while !take(used, offset) {
        offset += 1;
    }
    offset
}

/// Try to place a chunk's dependent chain starting at `base` with `gap`.
///
/// Block `n` of the chunk (overall commitment block `first_block + n`) goes
/// at offset `base + gap · n`. The trial succeeds if every block is at or
/// after its [`block_ready`] cycle and on a free residue. It works on a copy
/// of `used`, so a failed trial changes nothing; the caller claims the
/// residues afterwards.
const fn place_chunk(
    used: &[bool; KEY_PERIOD],
    first_block: usize,
    blocks: usize,
    base: i32,
    gap: i32,
    end_delay: i32,
) -> bool {
    // Scratch copy: claims made here are thrown away.
    let mut trial = *used;
    let mut n = 0;
    while n < blocks {
        // Offset of block n of this chunk.
        let offset = base + gap * n as i32;
        // Too early (its chain ends are not packed yet) or a collision.
        if offset < block_ready(first_block + n, end_delay) || !take(&mut trial, offset) {
            return false;
        }
        n += 1;
    }
    true
}

/// Earliest feasible `(base, gap)` for a chunk, minimising its finish time.
///
/// Searches `gap` from `delay` (blocks of one chunk depend on each other, so
/// they must be at least one use-delay apart) up to `delay + 67`, and `base`
/// from the first block's ready cycle up to 67 cycles later: one period of
/// each, since shifting by a whole period lands on the same residues.
/// Panics at compile time if nothing fits.
const fn solve_chunk(
    used: &[bool; KEY_PERIOD],
    first_block: usize,
    blocks: usize,
    delay: i32,
    end_delay: i32,
) -> (i32, i32) {
    // The first block cannot start before its chain ends are packed.
    let earliest = block_ready(first_block, end_delay);
    // Best placement so far, and the offset of its last block.
    let mut best = (0, 0);
    let mut best_finish = i32::MAX;
    let mut gap = delay;
    while gap < delay + KEY_PERIOD as i32 {
        let mut base = earliest;
        while base < earliest + KEY_PERIOD as i32 {
            // Offset of the chunk's last block under this (base, gap).
            let finish = base + gap * (blocks as i32 - 1);
            // Keep it only if it finishes earlier and actually fits.
            if finish < best_finish && place_chunk(used, first_block, blocks, base, gap, end_delay)
            {
                best = (base, gap);
                best_finish = finish;
            }
            base += 1;
        }
        gap += 1;
    }
    assert!(best_finish != i32::MAX, "no collision-free chunk placement");
    best
}

/// Build the timetable for a BLAKE3 latency and a chain-end delay.
///
/// `blake3_latency` is the compression pipeline's registered latency
/// ([`PIPELINE_STAGES`](crate::blake3_core::PIPELINE_STAGES) for the LUT
/// lane). `end_delay` is the cycles from a chain's issue until its end reaches
/// the commitment packer (the chain engine's latency plus wiring registers).
///
/// # Panics
///
/// At compile time, if no collision-free placement exists (more than 68 ops).
///
/// See the module doc ("How the solver works") for the order of placement
/// and the reasoning behind it.
#[must_use]
pub const fn solve(blake3_latency: i32, end_delay: i32) -> Schedule {
    // D: issue-to-usable delay of every BLAKE3 result.
    let delay = blake3_latency + 4;
    // Which residues are already claimed.
    let mut used = [false; KEY_PERIOD];
    // Result: offset of every op, filled in below.
    let mut offsets = [0; OPS];
    // The 16-block chunk-0 chain is the hardest constraint: place it first.
    let (base0, gap0) = solve_chunk(&used, 0, CHUNK0_BLOCKS, delay, end_delay);
    let mut n = 0;
    while n < CHUNK0_BLOCKS {
        offsets[op_index(Op::Chunk0(n as u8))] = base0 + gap0 * n as i32;
        take(&mut used, offsets[op_index(Op::Chunk0(n as u8))]);
        n += 1;
    }
    // Chunk 1 (commitment blocks 16..20) fits around chunk 0's residues.
    let (base1, gap1) = solve_chunk(&used, CHUNK0_BLOCKS, CHUNK1_BLOCKS, delay, end_delay);
    n = 0;
    while n < CHUNK1_BLOCKS {
        offsets[op_index(Op::Chunk1(n as u8))] = base1 + gap1 * n as i32;
        take(&mut used, offsets[op_index(Op::Chunk1(n as u8))]);
        n += 1;
    }
    // The parent needs both chunks' final chaining values.
    let last0 = offsets[op_index(Op::Chunk0(CHUNK0_BLOCKS as u8 - 1))];
    let last1 = offsets[op_index(Op::Chunk1(CHUNK1_BLOCKS as u8 - 1))];
    let after = if last0 > last1 { last0 } else { last1 };
    offsets[op_index(Op::Parent)] = earliest_free(&mut used, after + delay);
    // XOF blocks: as late as possible so the secret buffer stays small.
    // Tracks the earliest op that reads the seed, so the seed can be placed
    // D before it. Starts at the nonces' deadline.
    let mut earliest_seed_use = -1 - delay;
    n = XOF_BLOCKS;
    while n > 0 {
        n -= 1;
        // Deadline: D before the cycle the window load needs block n
        // (one cycle before its first chain).
        let offset = latest_free(&mut used, first_chain_of_xof(n) - 1 - delay);
        offsets[op_index(Op::Xof(n as u8))] = offset;
        if offset < earliest_seed_use {
            earliest_seed_use = offset;
        }
    }
    // pk_nonce salts chain 0 at T; the signer's nonce is needed much later.
    offsets[op_index(Op::PkNonce)] = latest_free(&mut used, -1 - delay);
    offsets[op_index(Op::Nonce)] = latest_free(&mut used, -1 - delay);
    // The seed must be usable before its earliest reader (XOF or nonce).
    let mut seed_limit = earliest_seed_use;
    if offsets[op_index(Op::PkNonce)] < seed_limit {
        seed_limit = offsets[op_index(Op::PkNonce)];
    }
    if offsets[op_index(Op::Nonce)] < seed_limit {
        seed_limit = offsets[op_index(Op::Nonce)];
    }
    offsets[op_index(Op::Seed)] = latest_free(&mut used, seed_limit - delay);
    // The reserved slots carry outside work; any free residue will do.
    offsets[op_index(Op::Merkle)] = earliest_free(&mut used, 0);
    offsets[op_index(Op::Message)] = earliest_free(&mut used, 0);
    if TAIL_OPS == 1 {
        // The tail needs the first block's chaining value: one lane latency
        // plus the result register, the signer's latch and its request
        // register after the message slot. Placed within the same period,
        // a signature's two blocks still take one key period.
        let after = offsets[op_index(Op::Message)] + delay + TAIL_SLACK;
        offsets[op_index(Op::MessageTail)] = earliest_free(&mut used, after);
    }
    // Invert the placement: for each residue, which op (if any) runs there.
    let mut residue = [None; KEY_PERIOD];
    let mut index = 0;
    while index < OPS {
        residue[residue_of(offsets[index])] = Some(index as u8);
        index += 1;
    }
    Schedule {
        offsets,
        residue,
        use_delay: delay,
        end_delay,
    }
}

/// Convenience queries used by the factory, the tests and the documentation.
impl Schedule {
    /// Issue offset of `op` relative to its key's chain-0 cycle.
    #[must_use]
    pub const fn offset(&self, op: Op) -> i32 {
        self.offsets[op_index(op)]
    }

    /// Cycles from the seed compression to a usable `pk_hash` for one key.
    ///
    /// How long one key is "in flight". Throughput does not depend on it
    /// (keys overlap); it decides how many contexts the factory needs.
    #[must_use]
    pub const fn key_latency(&self) -> i32 {
        self.offset(Op::Parent) + self.use_delay - self.offset(Op::Seed)
    }

    /// Idle residues per period: spare BLAKE3 capacity in the slice.
    ///
    /// 68 − [`OPS`] = 22 for the current op list.
    #[must_use]
    pub const fn idle_slots(&self) -> usize {
        // Count residues with no op.
        let mut idle = 0;
        let mut r = 0;
        while r < KEY_PERIOD {
            if self.residue[r].is_none() {
                idle += 1;
            }
            r += 1;
        }
        idle
    }
}