rhdl_dsig_scalable_core/

slice_chain.rs

//! A slice's chain engine: one chain per cycle through three folded lanes.
//!
//! # Why this block exists
//!
//! A W-OTS+ chain (here with `w = 4`) is a short hash chain: secret →
//! hash → hash → hash. A one-time key has 68 of them, and the
//! [`slice_factory`](crate::slice_factory) makes one key every 68 cycles. So
//! the slice must finish **one chain per cycle**, which means three chain
//! hashes per cycle. Instead of one hash core used three times in a loop
//! (which would accept a new chain only every third pass), we build three
//! pipelined *lanes* and put them in series. A *lane* is a fully pipelined
//! hash: it accepts a new input every cycle (initiation interval, II = 1) and
//! returns each result a fixed number of cycles later.
//!
//! Every DSig chain starts from an 18-byte secret and is hashed three times,
//! at depths 0, 1 and 2. The slice keeps **all four** positions in its cache,
//! because the signer later reveals whichever position each message digit
//! selects ([`reference::PreparedKey::sign`](crate::reference::PreparedKey)).
//!
//! ```text
//!   secret ─▶ [lane depth 0] ─▶ node1 ─▶ [lane depth 1] ─▶ node2 ─▶ [lane depth 2] ─▶ node3
//!     │          20 cycles          │        20 cycles          │        20 cycles        │
//!     └────────── carried beside the hashes, so all four leave together ──────────────────┘
//! ```
//!
//! Each lane is a [`ChainLane`](crate::chain_lane::ChainLane), whose hash is
//! chosen at compile time by a `chain-*` feature (see [`crate::chain_lane`]).
//! With the default Haraka-512 hash it is a
//! [`TableChainStepLane`](crate::chain_step::TableChainStepLane) (the
//! T-table form of [`ChainStepLane`](crate::chain_step::ChainStepLane)),
//! shaped by the `TABLE_MASK` area knob. The diagram shows the Haraka lane
//! latency of 20 cycles; BLAKE3 lanes take 28 and SHA-512 lanes 82.
//!
//! Each depth salts the nonce differently: the low
//! 32 bits of `pk_nonce` gain `index + 68·depth`
//! ([`dsig_chain_block`](crate::haraka::dsig_chain_block)). The engine
//! computes the three salted nonces itself, so the caller supplies only the
//! raw `pk_nonce`.
//!
//! Timing contract: one chain may enter every cycle (II = 1), there is no
//! backpressure, and results appear exactly [`SLICE_CHAIN_LATENCY`] cycles
//! later in issue order with the tag unchanged. Reset discards every in-flight
//! chain. The caller must keep the index below 68; the slice controller does
//! this structurally by counting 0..=67.
//!
//! # How the earlier nodes keep up
//!
//! The cache wants all four positions of a chain at once, but each lane only
//! outputs the newest node. So a *carry* shift register, one stage per
//! pipeline cycle, runs beside the lanes. It holds the chain's earlier nodes,
//! its `pk_nonce` and its index. When a lane's result emerges, it is written
//! into the carry at that point, so the carry always holds every node
//! computed so far:
//!
//! ```text
//!   carry stage:   0 ……… L−1 │ L ……… 2L−1 │ 2L ……… 3L−1 │ output
//!   nodes[0]:      secret     │ secret      │ secret       │ position 0
//!   nodes[1]:      (secret)   │ node1 ◀─────┤ node1        │ position 1
//!   nodes[2]:      (secret)   │ (secret)    │ node2 ◀──────┤ position 2
//!   depth-2 lane output                                    │ position 3
//!   (L = LANE_LATENCY; "(secret)" = placeholder, overwritten later)
//! ```
//!
//! The carry also gives depth 1 and depth 2 the `pk_nonce` and chain index
//! they need for their salt, exactly when their input arrives.

use crate::chain_lane::{ChainLane, LANE_LATENCY as CHAIN_STEP_LATENCY};
use crate::chain_step::ChainStepInput;
use crate::{CHAINS, ELEMENT_BYTES};
use rhdl::prelude::*;
use rhdl_fpga::core::dff::DFF;

/// Cycles from a chain's issue until its four nodes are presented.
///
/// Three lanes in series: 3 × 20 = 60 with Haraka, 3 × 28 = 84 with BLAKE3,
/// 3 × 82 = 246 with SHA-512. The factory adds this to its
/// [`END_DELAY`](crate::slice_factory::END_DELAY).
pub const SLICE_CHAIN_LATENCY: usize = 3 * CHAIN_STEP_LATENCY;

/// One chain to expand.
///
/// The factory presents one of these per cycle (or `valid = false`).
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
pub struct SliceChainInput {
    /// Position-0 secret for this chain (bytes `18i..18i+18` of the key's XOF).
    pub secret: [b8; ELEMENT_BYTES],
    /// The key's public 16-byte nonce, unsalted.
    pub pk_nonce: [b8; 16],
    /// Chain number `0..68` within the key.
    pub index: b7,
    /// Opaque routing tag (key slot and chain), returned unchanged.
    pub tag: b32,
    /// A chain enters this cycle.
    pub valid: bool,
}

/// An idle input: zeros and `valid = false`.
impl Default for SliceChainInput {
    /// Returns the idle input.
    fn default() -> Self {
        Self {
            secret: [b8(0); ELEMENT_BYTES],
            pk_nonce: [b8(0); 16],
            index: b7(0),
            tag: b32(0),
            valid: false,
        }
    }
}

/// All four positions of one finished chain.
///
/// Appears [`SLICE_CHAIN_LATENCY`] cycles after the matching input.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
pub struct SliceChainOutput {
    /// Positions 0 (secret) through 3 (public chain end).
    pub nodes: [[b8; ELEMENT_BYTES]; 4],
    /// The input tag.
    pub tag: b32,
    /// Four valid nodes are presented this cycle.
    pub valid: bool,
    /// All three lanes have loaded their UltraRAM S-boxes.
    pub ready: bool,
}

/// One stage of the carry shift register: what travels beside the lanes.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
#[doc(hidden)] // Public only for the derived Synchronous associated state.
pub struct ChainCarry {
    /// Positions 0, 1 and 2 of the chain so far (18 bytes each). Positions
    /// not computed yet hold a copy of the secret as a placeholder.
    nodes: [[b8; ELEMENT_BYTES]; 3],
    /// The key's unsalted `pk_nonce`, for the salts of depths 1 and 2.
    pk_nonce: [b8; 16],
    /// Chain number 0..68, also for the salts.
    index: b7,
}

/// Three lanes in series plus the metadata that travels beside them.
///
/// `TABLE_MASK` is passed to each lane unchanged (see
/// [`crate::chain_lane::ChainLane`]).
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct SliceChainEngine<const TABLE_MASK: usize> {
    /// First hash: secret (position 0) → position 1.
    depth0: ChainLane<TABLE_MASK>,
    /// Second hash: position 1 → position 2.
    depth1: ChainLane<TABLE_MASK>,
    /// Third hash: position 2 → position 3 (the public chain end).
    depth2: ChainLane<TABLE_MASK>,
    /// The carry shift register, [`SLICE_CHAIN_LATENCY`] stages long. Not
    /// reset: its contents matter only where `valid` says so.
    carry: [DFF<ChainCarry>; SLICE_CHAIN_LATENCY],
    /// A valid bit per carry stage, cleared by reset.
    valid: [DFF<bool>; SLICE_CHAIN_LATENCY],
}

/// An empty engine: no chains in flight.
impl<const TABLE_MASK: usize> Default for SliceChainEngine<TABLE_MASK> {
    /// Builds the three lanes, a don't-care carry and all-false valid bits.
    fn default() -> Self {
        Self {
            depth0: ChainLane::default(),
            depth1: ChainLane::default(),
            depth2: ChainLane::default(),
            carry: core::array::from_fn(|_| DFF::resetless()),
            valid: core::array::from_fn(|_| DFF::new(false)),
        }
    }
}

/// Connects [`SliceChainEngine`] to its port types and wiring kernel.
impl<const TABLE_MASK: usize> SynchronousIO for SliceChainEngine<TABLE_MASK> {
    /// One chain per cycle.
    type I = SliceChainInput;
    /// One finished chain per cycle.
    type O = SliceChainOutput;
    /// The wiring, [`slice_chain_kernel`].
    type Kernel = slice_chain_kernel<TABLE_MASK>;
}

/// Add `index + 68·depth` to the nonce's low 32 bits (no carry into byte 4).
///
/// Why salt: every hash call in the scheme gets a distinct input, so an
/// attacker cannot attack all chains at once. The value `index + 68·depth`
/// is unique for each of the 68 × 3 hash calls of a key.
///
/// Inputs: the 16-byte `pk_nonce`, the chain index (7 bits) and the depth
/// (2 bits, 0..=2). Output: the salted nonce. Combinational (a 32-bit adder).
#[kernel]
pub fn salt_kernel(pk_nonce: [b8; 16], index: b7, depth: b2) -> [b8; 16] {
    // Bytes 4..16 pass through unchanged.
    let mut salted = pk_nonce;
    // Bytes 0..4 as a little-endian 32-bit number.
    let low: b32 = pk_nonce[0].resize()
        | (pk_nonce[1].resize::<32>() << 8)
        | (pk_nonce[2].resize::<32>() << 16)
        | (pk_nonce[3].resize::<32>() << 24);
    let offset: b32 = index.resize::<32>() + b32(CHAINS as u128) * depth.resize::<32>();
    // Wraps modulo 2^32: the carry never reaches byte 4.
    let sum = low + offset;
    salted[0] = sum.resize();
    salted[1] = (sum >> 8).resize();
    salted[2] = (sum >> 16).resize();
    salted[3] = (sum >> 24).resize();
    salted
}

/// Wiring for [`SliceChainEngine`]: salt, cascade, and carry earlier nodes.
///
/// Timing, for a chain presented at cycle `t` (L = lane latency):
///
/// | Cycle | Event |
/// |---|---|
/// | `t` | enters depth 0 with salt `index`; carry stage 0 loaded |
/// | `t + L` | depth 0 result enters depth 1 (salt `index + 68`) and carry stage L |
/// | `t + 2L` | depth 1 result enters depth 2 (salt `index + 136`) and carry stage 2L |
/// | `t + 3L` | depth 2 result and the carried nodes 0..2 leave together |
///
/// Output `valid` is forced low during reset; `ready` is the AND of the
/// three lanes' ready flags (UltraRAM S-boxes loaded).
#[allow(clippy::needless_range_loop)] // Compile-time pipeline elaboration.
#[kernel]
pub fn slice_chain_kernel<const TABLE_MASK: usize>(
    clock_reset: ClockReset,
    input: SliceChainInput,
    q: SliceChainEngineQ<TABLE_MASK>,
) -> (SliceChainOutput, SliceChainEngineD<TABLE_MASK>) {
    let resetting = clock_reset.reset.any();
    // Metadata leaving each lane boundary, aligned with that lane's output.
    let at1 = q.carry[CHAIN_STEP_LATENCY - 1];
    let at2 = q.carry[2 * CHAIN_STEP_LATENCY - 1];
    let at3 = q.carry[SLICE_CHAIN_LATENCY - 1];
    // Next inputs of the three lanes and the shift registers.
    let mut d = SliceChainEngineD::<TABLE_MASK> {
        // Depth 0 takes the new chain straight from the input.
        depth0: ChainStepInput {
            salted_nonce: salt_kernel(input.pk_nonce, input.index, b2(0)),
            secret: input.secret,
            tag: input.tag,
            valid: input.valid,
        },
        // Depth 1 takes depth 0's output, with metadata from the carry.
        depth1: ChainStepInput {
            salted_nonce: salt_kernel(at1.pk_nonce, at1.index, b2(1)),
            secret: q.depth0.node,
            tag: q.depth0.tag,
            valid: q.depth0.valid,
        },
        // Depth 2 takes depth 1's output, likewise.
        depth2: ChainStepInput {
            salted_nonce: salt_kernel(at2.pk_nonce, at2.index, b2(2)),
            secret: q.depth1.node,
            tag: q.depth1.tag,
            valid: q.depth1.valid,
        },
        // Placeholders; every stage is overwritten just below.
        carry: q.carry,
        valid: q.valid,
    };
    // The new chain enters the carry. Nodes 1 and 2 hold the secret only
    // as filler until their lanes produce them.
    d.carry[0] = ChainCarry {
        nodes: [input.secret, input.secret, input.secret],
        pk_nonce: input.pk_nonce,
        index: input.index,
    };
    // Shift every carry stage forward by one.
    for stage in 1..SLICE_CHAIN_LATENCY {
        d.carry[stage] = q.carry[stage - 1];
    }
    // Capture each lane's result into the carried node list as it emerges.
    d.carry[CHAIN_STEP_LATENCY].nodes[1] = q.depth0.node;
    d.carry[2 * CHAIN_STEP_LATENCY].nodes[2] = q.depth1.node;
    // The valid bits shift in step with the carry.
    d.valid[0] = input.valid;
    for stage in 1..SLICE_CHAIN_LATENCY {
        d.valid[stage] = q.valid[stage - 1];
    }
    // Output: carried positions 0..2 plus depth 2's result as position 3.
    (
        SliceChainOutput {
            nodes: [at3.nodes[0], at3.nodes[1], at3.nodes[2], q.depth2.node],
            tag: q.depth2.tag,
            valid: q.valid[SLICE_CHAIN_LATENCY - 1] && !resetting,
            ready: q.depth0.ready && q.depth1.ready && q.depth2.ready,
        },
        d,
    )
}