rhdl_dsig_scalable_core/

reference.rs

//! Complete byte-oriented reference for the explicitly versioned DSig profile.
//!
//! This is a software oracle and a trusted preload path, not synthesizable
//! hardware or sustained FPGA key-generation evidence. A [`PreparedKey`](crate::reference::PreparedKey) is
//! consumed by signing, is deliberately not `Clone`, and wipes its cached secret
//! nodes on drop. The caller must still persist epoch/batch allocation before
//! deriving seeds: reconstructing the same seed after reset defeats one-time
//! security. Do not expose precomputed chain caches outside a trusted boundary.
//!
//! # Why this module exists
//!
//! Hardware is hard to debug. When the engine writes a 1,642-byte signature to
//! HBM, how do you know that every byte is right? You need an answer key. This
//! module is that answer key: a plain, slow, easy-to-read Rust implementation
//! of the whole DSig profile, from seed to transferable signature. Every
//! hardware block is checked against it bit for bit (see
//! [`crate::slice_model`] and the tests in `tests/`), and the host tool
//! `dsig_engine_host` uses it to verify what the card produced.
//!
//! It is written for clarity, not speed. It uses byte arrays instead of RHDL
//! `Bits`, and the `blake3` and `ed25519-dalek` crates instead of hardware
//! lanes. Nothing here is synthesized.
//!
//! # The story of one signature, in software
//!
//! ```text
//!  master seed ─┐
//!  signer key  ─┼─ one_time_seed() ──▶ 32-byte seed per key (×128 per batch)
//!  epoch,batch ─┤        (BLAKE3 derive_key, SEED_DERIVATION_CONTEXT)
//!  key index   ─┘
//!                              │
//!                              ▼
//!                  PreparedKey::from_seed()
//!                    pk_nonce, nonce   (BLAKE3 XOF, prefixes 0x5eed / 0xc0ca)
//!                    nodes[0][0..68]   (BLAKE3 XOF of the seed: chain secrets)
//!                    nodes[1..=3]      (3 chain steps per chain: dsig_chain)
//!                    pk_hash           (endpoint_commitment of nodes[3])
//!                              │
//!            128 pk_hash ──▶ BatchTree::new() ──▶ root
//!                              │
//!                              ▼
//!            BatchCommitment { epoch, batch_id, root } ── Ed25519 ──▶ BatchCertificate
//!                              │
//!  message ──▶ message_digits() ──▶ 68 base-4 digits (64 message + 4 checksum)
//!                              │
//!                              ▼
//!            PreparedKey::sign(): reveal nodes[digit][chain] for each chain
//!                              │
//!                              ▼
//!            DsigSignature = WOTS part + key index + 7 siblings + certificate
//!                              │
//!                              ▼
//!            to_bytes(): 1,642 bytes on the wire
//! ```
//!
//! # Words you will meet
//!
//! * **W-OTS+** (Winternitz one-time signature): each of the 68 chains starts
//!   at a secret node and is hashed forward. Signing a base-4 digit `d`
//!   reveals the node at depth `d`; a verifier hashes it the remaining
//!   `3 − d` steps and must land on the public endpoint.
//! * **Checksum digits**: the last 4 digits encode the sum of `3 − digit`
//!   over the 64 message digits. An attacker can only hash *forward*, which
//!   raises digits; that lowers the checksum, which they cannot do. So no
//!   forgery comes for free from a seen signature.
//! * **Nonce** (salt): a 16-byte random value mixed into hashes so that two
//!   keys never share chain inputs.
//! * **Merkle tree**: a binary tree of hashes. Its 128 leaves are the keys'
//!   `pk_hash` values; its root stands for all 128 at once, so one Ed25519
//!   signature can vouch for all of them.
//!
//! # Wire layout of a signature
//!
//! | Bytes | Field |
//! |---|---|
//! | 0..64 | [`BatchCommitment`] (see [`crate::certificate`]) |
//! | 64..128 | Ed25519 signature `R ‖ S` |
//! | 128..130 | key index, little endian |
//! | 130..162 | `pk_hash` |
//! | 162..178 | `pk_nonce` |
//! | 178..194 | message `nonce` |
//! | 194..418 | 7 Merkle siblings × 32 bytes, bottom up |
//! | 418..1642 | 68 chain nodes × 18 bytes, in chain order |
//!
//! # Security rules this module enforces (and the ones it cannot)
//!
//! * A one-time key signs at most once. [`PreparedKey::sign`] takes `self` by
//!   value, so Rust's ownership rules stop a second call. [`PreparedBatch`]
//!   stores keys as `Option` and `take`s them, so a repeated index returns
//!   `None`.
//! * Secrets are wiped. Secret nodes, nonces, seeds and the master seed are
//!   zeroized as soon as they are no longer needed; the master seed is never
//!   stored in [`PreparedBatch`].
//! * What it cannot enforce: that `(epoch, batch_id)` was never used before.
//!   Rebuilding a batch from the same master seed and namespace recreates the
//!   same keys, which would let one key sign two messages. The host must
//!   durably allocate namespaces first; [`crate::lease`] does that.
//!
//! # Neighbours
//!
//! * [`crate::certificate`] defines the signed 64-byte batch envelope.
//! * [`crate::haraka`] provides [`dsig_chain`], one chain step in the
//!   compiled-in chain hash (Haraka-512 unless a `chain-*` feature says
//!   otherwise).
//! * [`crate::slice_model`] reuses [`message_digits`] and [`PreparedBatch`]
//!   to predict the hardware cycle by cycle.
//! * [`crate::lease`] wraps [`PreparedBatch`] with never-reused batch ranges.

use ed25519_dalek::{SigningKey, VerifyingKey};
use zeroize::Zeroize;

use crate::{
    BATCH_KEYS, CHAINS, Digest, ELEMENT_BYTES, Element, MERKLE_HEIGHT, MESSAGE_DIGITS, Nonce,
    POSITIONS,
    certificate::{BatchCertificate, BatchCommitment},
    haraka::dsig_chain,
};

/// Four stored positions for every chain; the last row contains public nodes.
///
/// Indexed `[depth][chain]`: `depth` 0 is the secret start of a chain, 1 and
/// 2 are intermediate nodes, 3 is the public endpoint. Each entry is an
/// 18-byte [`Element`]. 4 × 68 × 18 = 4,896 bytes per key. Storing every
/// depth (instead of only the secret) is what lets signing be a table lookup
/// with no hashing; the hardware key cache ([`crate::cache_bank`]) stores the
/// same 4 × 68 nodes per key for the same reason.
pub type ChainCache = [[Element; CHAINS]; POSITIONS];
/// Self-standing signature wire length, with no transport padding.
///
/// 64 (commitment) + 64 (Ed25519) + 2 (index) + 32 + 16 + 16 (public key
/// hash, public salt, message salt) + 7 × 32 (Merkle path) + 68 × 18 (chain
/// nodes) = 1,642 bytes. The hardware pads each one to a 2 KiB frame slot in
/// HBM; this constant is the unpadded length.
pub const SIGNATURE_WIRE_BYTES: usize = 1642;

/// Public metadata for one cached one-time key.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct KeyPublic {
    /// Salt used in all of this key's Haraka chains (16 bytes).
    ///
    /// Public: a verifier needs it to recompute the chains.
    pub pk_nonce: Nonce,
    /// BLAKE3 commitment to public salt and 68 chain endpoints (32 bytes).
    ///
    /// This is the key's public identity and the Merkle leaf for its batch.
    pub pk_hash: Digest,
}

/// Single-use secret cache. Signing consumes this object before returning data.
///
/// It is not `Clone` on purpose: a copy would be a second chance to sign
/// with the same one-time key. Dropping it zeroizes the secret parts.
pub struct PreparedKey {
    /// Public salt and endpoint commitment; safe to share.
    public: KeyPublic,
    /// Secret 16-byte message salt, disclosed only inside the signature.
    nonce: Nonce,
    /// All four depths of all 68 chains. Rows 0 to 2 are secret.
    nodes: ChainCache,
}

impl Drop for PreparedKey {
    /// Wipe the secret chain nodes and the message salt so they do not
    /// linger in freed memory.
    fn drop(&mut self) {
        self.nodes.zeroize();
        self.nonce.zeroize();
    }
}

impl PreparedKey {
    /// Prepare a fresh key from an exclusively allocated random 256-bit seed.
    ///
    /// The seed must never be reused, including across resets or processes.
    /// The four-byte salt prefixes retain the upstream x86 little-endian
    /// convention. The signature checksum and certificate format do not.
    ///
    /// Steps: derive two 16-byte salts from the seed, expand the seed into 68
    /// secret chain starts, hash each chain three steps forward, then commit
    /// to the public salt and the 68 endpoints.
    #[must_use]
    pub fn from_seed(mut seed: [u8; 32]) -> Self {
        // Helper: BLAKE3(prefix ‖ seed) read as a 16-byte XOF output. The
        // prefix separates the two salts so they are independent.
        let nonce_for = |prefix: u32| {
            let mut hasher = blake3::Hasher::new();
            hasher.update(&prefix.to_le_bytes());
            hasher.update(&seed);
            let mut nonce = [0; 16];
            let mut reader = hasher.finalize_xof();
            reader.fill(&mut nonce);
            reader.zeroize();
            hasher.zeroize();
            nonce
        };
        // Public chain salt (prefix 0x5eed) and secret message salt (prefix 0xc0ca).
        let pk_nonce = nonce_for(0x5eed);
        let nonce = nonce_for(0xc0ca);
        // nodes[depth][chain], filled row by row below.
        let mut nodes = [[[0; ELEMENT_BYTES]; CHAINS]; POSITIONS];
        // Row 0: the 68 secret chain starts, read in order from one BLAKE3
        // XOF stream of the seed (68 × 18 = 1,224 bytes).
        let mut expansion = blake3::Hasher::new();
        expansion.update(&seed);
        let mut reader = expansion.finalize_xof();
        for element in &mut nodes[0] {
            reader.fill(element);
        }
        // Wipe the XOF state: it could regenerate the secrets.
        reader.zeroize();
        expansion.zeroize();
        // Rows 1 to 3: each node is one chain step of the node above it. The
        // step is salted with pk_nonce and tweaked by (chain, depth), so no
        // two steps anywhere hash the same input.
        for depth in 0..POSITIONS - 1 {
            for chain in 0..CHAINS {
                nodes[depth + 1][chain] = dsig_chain(&nodes[depth][chain], &pk_nonce, chain, depth);
            }
        }
        // The seed is no longer needed; wipe this copy.
        seed.zeroize();
        // Row 3 holds the public endpoints; commit to them.
        let pk_hash = endpoint_commitment(&pk_nonce, &nodes[POSITIONS - 1]);
        Self {
            public: KeyPublic { pk_nonce, pk_hash },
            nonce,
            nodes,
        }
    }

    /// Public metadata to send through the authenticated key-admission plane.
    #[must_use]
    pub const fn public(&self) -> KeyPublic {
        self.public
    }

    /// Signer-private message nonce for the trusted hardware loader only.
    ///
    /// Do not distribute this with pre-certified public keys. It must remain
    /// unpredictable until the one-time key is irreversibly bound to a message;
    /// early disclosure weakens the 128-bit salted-digest chosen-message model.
    #[must_use]
    pub const fn signing_nonce_for_device(&self) -> Nonce {
        self.nonce
    }

    /// Borrow secret cache bytes for trusted device loading. Never log them.
    #[must_use]
    pub const fn cache_for_device(&self) -> &ChainCache {
        &self.nodes
    }

    /// Consume this key and reveal only message-selected nodes.
    ///
    /// Takes `self` by value, so this key cannot sign again. For chain `i`
    /// with digit `d`, the revealed node is `nodes[d][i]`.
    #[must_use]
    pub fn sign(self, message: &[u8]) -> WotsSignature {
        // 68 base-4 digits, each 0..=3, one per chain.
        let digits = message_digits(&self.public.pk_hash, &self.nonce, message);
        WotsSignature {
            public: self.public,
            nonce: self.nonce,
            elements: core::array::from_fn(|i| self.nodes[usize::from(digits[i])][i]),
        }
    }
}

/// Public salt plus endpoint commitment, exactly ordered as upstream DSig.
///
/// `BLAKE3(pk_nonce ‖ endpoint[0] ‖ … ‖ endpoint[67])`: 16 + 68 × 18 = 1,240
/// input bytes, which is why the summary in [`crate`] counts 21 BLAKE3
/// compressions for the endpoint commitment. Signer and verifier both call
/// this; a match proves the revealed nodes lead to this key's endpoints.
#[must_use]
pub fn endpoint_commitment(pk_nonce: &Nonce, endpoints: &[Element; CHAINS]) -> Digest {
    let mut hash = blake3::Hasher::new();
    hash.update(pk_nonce);
    for endpoint in endpoints {
        hash.update(endpoint);
    }
    *hash.finalize().as_bytes()
}

/// Extract low two bits from each XOF byte and append the complement checksum.
///
/// Input: 64 XOF bytes. Output: 68 digits in 0..=3. Digits 0..64 are the low
/// two bits of each byte. The checksum is `Σ (3 − digit)` (at most 64 × 3 =
/// 192, which fits in four base-4 digits) and is written little endian into
/// digits 64..68. The hardware signer ([`crate::slice_signer`]) does the same
/// split.
#[must_use]
pub fn digits_from_xof(xof: &[u8; 64]) -> [u8; CHAINS] {
    let mut digits = [0; CHAINS];
    // Sum of "steps left to the endpoint" over the 64 message digits.
    let mut checksum = 0_u16;
    for i in 0..MESSAGE_DIGITS {
        digits[i] = xof[i] & 3;
        checksum += u16::from(3 - digits[i]);
    }
    // Four base-4 checksum digits, least significant first.
    for i in 0..4 {
        digits[MESSAGE_DIGITS + i] = ((checksum >> (2 * i)) & 3) as u8;
    }
    digits
}

/// Salted BLAKE3-XOF message mapping; 64 low-bit digits encode 128 digest bits.
///
/// `BLAKE3-XOF(pk_hash ‖ nonce ‖ message)`, 64 bytes, then
/// [`digits_from_xof`]. Binding `pk_hash` ties the digest to one key; the
/// secret `nonce` keeps the digits unpredictable until the signature is out.
#[must_use]
pub fn message_digits(pk_hash: &Digest, nonce: &Nonce, message: &[u8]) -> [u8; CHAINS] {
    let mut hash = blake3::Hasher::new();
    hash.update(pk_hash);
    hash.update(nonce);
    hash.update(message);
    // Only the low 2 bits of each of these 64 bytes are used.
    let mut xof = [0; 64];
    hash.finalize_xof().fill(&mut xof);
    digits_from_xof(&xof)
}

/// WOTS component only; its public-key hash is not itself a trusted identity.
///
/// Anyone can make a key and a matching WOTS signature. Trust comes from the
/// Merkle path and the Ed25519 certificate in [`DsigSignature`].
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct WotsSignature {
    /// Salts and claimed public commitment.
    pub public: KeyPublic,
    /// Message salt disclosed only after the key is bound to this message.
    pub nonce: Nonce,
    /// The 68 selected 18-byte nodes, in chain order.
    pub elements: [Element; CHAINS],
}

impl WotsSignature {
    /// Verify the hash-chain component, without authenticating the claimed key.
    ///
    /// Recompute the digits, hash each revealed node forward to depth 3, and
    /// compare the commitment with the claimed `pk_hash`.
    #[must_use]
    pub fn verify_hash_component(&self, message: &[u8]) -> bool {
        let digits = message_digits(&self.public.pk_hash, &self.nonce, message);
        // Start from the revealed nodes; after the loop these are endpoints.
        let mut endpoints = self.elements;
        for chain in 0..CHAINS {
            for depth in usize::from(digits[chain])..POSITIONS - 1 {
                endpoints[chain] =
                    dsig_chain(&endpoints[chain], &self.public.pk_nonce, chain, depth);
            }
        }
        endpoint_commitment(&self.public.pk_nonce, &endpoints) == self.public.pk_hash
    }
}

/// Fixed 128-leaf BLAKE3 tree authenticating public-key commitments.
///
/// Stored as a flat array in heap order: node 0 is the root, node `i` has
/// children `2i + 1` and `2i + 2`, and the 128 leaves sit at 127..255.
///
/// ```text
///               0  (root)
///            /     \
///           1       2
///          / \     / \
///        ...  ...  ...  ...        7 levels
///   127 128 ...        254         leaves = pk_hash of keys 0..127
/// ```
#[derive(Clone)]
pub struct BatchTree {
    /// 255 digests: 127 inner nodes followed by 128 leaves.
    nodes: [Digest; BATCH_KEYS * 2 - 1],
}

/// One Merkle parent: `BLAKE3(left ‖ right)`, 64 input bytes, one BLAKE3
/// compression. The order matters: swapping children gives a different root.
fn parent_hash(left: &Digest, right: &Digest) -> Digest {
    let mut hash = blake3::Hasher::new();
    hash.update(left);
    hash.update(right);
    *hash.finalize().as_bytes()
}

impl BatchTree {
    /// Construct a tree of exactly one complete certificate batch.
    #[must_use]
    pub fn new(leaves: &[Digest; BATCH_KEYS]) -> Self {
        let mut nodes = [[0; 32]; BATCH_KEYS * 2 - 1];
        // Leaves go at the end of the heap array.
        nodes[BATCH_KEYS - 1..].copy_from_slice(leaves);
        // Walk inner nodes from the last to the root, so both children of
        // each node are already computed.
        for i in (0..BATCH_KEYS - 1).rev() {
            nodes[i] = parent_hash(&nodes[i * 2 + 1], &nodes[i * 2 + 2]);
        }
        Self { nodes }
    }

    /// Batch commitment presented to the Ed25519 background service.
    #[must_use]
    pub const fn root(&self) -> Digest {
        self.nodes[0]
    }

    /// Bottom-up sibling path; invalid indices are rejected instead of masked.
    ///
    /// Returns the 7 sibling digests a verifier needs to rebuild the root from
    /// leaf `index` (0..128).
    #[must_use]
    pub fn proof(&self, index: usize) -> Option<[Digest; MERKLE_HEIGHT]> {
        if index >= BATCH_KEYS {
            return None;
        }
        // Heap position of the leaf.
        let mut node = BATCH_KEYS - 1 + index;
        let mut proof = [[0; 32]; MERKLE_HEIGHT];
        for sibling in &mut proof {
            // In heap order a left child is odd and a right child is even;
            // the sibling is the neighbour on the other side.
            *sibling = self.nodes[if node % 2 == 0 { node - 1 } else { node + 1 }];
            // Move up to the parent.
            node = (node - 1) / 2;
        }
        Some(proof)
    }
}

/// Recover a root from a public-key commitment and checked leaf index.
///
/// Bit `level` of `index` says whether the running hash is a left (0) or
/// right (1) child at that level. Returns `None` for an index of 128 or more.
#[must_use]
pub fn root_from_proof(
    leaf: Digest,
    index: usize,
    proof: &[Digest; MERKLE_HEIGHT],
) -> Option<Digest> {
    if index >= BATCH_KEYS {
        return None;
    }
    // The running hash, from the leaf up to the root.
    let mut root = leaf;
    for (level, sibling) in proof.iter().enumerate() {
        root = if (index >> level) & 1 == 0 {
            parent_hash(&root, sibling)
        } else {
            parent_hash(sibling, &root)
        };
    }
    Some(root)
}

/// Transferable signature: hash-based component, inclusion proof, certificate.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct DsigSignature {
    /// One-time hash-based message signature.
    pub wots: WotsSignature,
    /// Leaf position within the fixed-size authenticated batch (0..128).
    pub key_index: u16,
    /// Seven bottom-up siblings linking this one-time key to the batch root.
    pub proof: [Digest; MERKLE_HEIGHT],
    /// Background Ed25519 certificate, retained for uncached verifiers.
    pub certificate: BatchCertificate,
}

impl DsigSignature {
    /// Full cold-path verification, bound to a caller's trusted Ed25519 identity.
    ///
    /// "Cold" means nothing is cached: this does one Ed25519 verification
    /// plus the hash work. [`VerifiedBatch::verify`] is the warm path.
    #[must_use]
    pub fn verify(&self, message: &[u8], trusted_signer: &VerifyingKey) -> bool {
        self.certificate.verify_strict(trusted_signer)
            && self.verify_authenticated_hash_component(message)
    }

    /// The hash-only part of verification: the Merkle path must lead from
    /// `pk_hash` to the certified root, and the WOTS part must check out.
    /// Private because it is only safe after the certificate is trusted.
    fn verify_authenticated_hash_component(&self, message: &[u8]) -> bool {
        root_from_proof(
            self.wots.public.pk_hash,
            usize::from(self.key_index),
            &self.proof,
        ) == Some(self.certificate.commitment.root)
            && self.wots.verify_hash_component(message)
    }

    /// Stable wire layout, independent of Rust/C++ padding or native word size.
    #[must_use]
    ///
    /// The byte offsets are listed in the module docs' wire layout table.
    pub fn to_bytes(&self) -> [u8; SIGNATURE_WIRE_BYTES] {
        let mut bytes = [0; SIGNATURE_WIRE_BYTES];
        // Write cursor into `bytes`.
        let mut position = 0;
        // Append one field and advance the cursor.
        let mut put = |part: &[u8]| {
            bytes[position..position + part.len()].copy_from_slice(part);
            position += part.len();
        };
        put(&self.certificate.commitment.to_bytes());
        put(&self.certificate.signature);
        put(&self.key_index.to_le_bytes());
        put(&self.wots.public.pk_hash);
        put(&self.wots.public.pk_nonce);
        put(&self.wots.nonce);
        for sibling in &self.proof {
            put(sibling);
        }
        for element in &self.wots.elements {
            put(element);
        }
        debug_assert_eq!(position, SIGNATURE_WIRE_BYTES);
        bytes
    }

    /// Parse exactly one corrected-profile signature. Parsing never authenticates.
    ///
    /// Returns `None` for a wrong length, a foreign domain/profile/batch size
    /// or a key index of 128 or more. Call [`DsigSignature::verify`] after.
    #[must_use]
    pub fn from_bytes(bytes: &[u8]) -> Option<Self> {
        if bytes.len() != SIGNATURE_WIRE_BYTES {
            return None;
        }
        // Bytes 0..64: rejects any other domain, profile or batch size.
        let commitment = BatchCommitment::from_bytes(bytes[..64].try_into().ok()?)?;
        let certificate = BatchCertificate {
            commitment,
            signature: bytes[64..128].try_into().ok()?,
        };
        // Bytes 128..130: must name one of the 128 leaves.
        let key_index = u16::from_le_bytes(bytes[128..130].try_into().ok()?);
        if usize::from(key_index) >= BATCH_KEYS {
            return None;
        }
        let public = KeyPublic {
            pk_hash: bytes[130..162].try_into().ok()?,
            pk_nonce: bytes[162..178].try_into().ok()?,
        };
        // Bytes 178..194: the message salt.
        let nonce = bytes[178..194].try_into().ok()?;
        // Bytes 194..418: seven 32-byte siblings.
        let mut proof = [[0; 32]; MERKLE_HEIGHT];
        for (i, sibling) in proof.iter_mut().enumerate() {
            sibling.copy_from_slice(&bytes[194 + i * 32..194 + (i + 1) * 32]);
        }
        // Bytes 418..1642: sixty-eight 18-byte chain nodes.
        let mut elements = [[0; ELEMENT_BYTES]; CHAINS];
        for (i, element) in elements.iter_mut().enumerate() {
            element.copy_from_slice(&bytes[418 + i * ELEMENT_BYTES..418 + (i + 1) * ELEMENT_BYTES]);
        }
        Some(Self {
            wots: WotsSignature {
                public,
                nonce,
                elements,
            },
            key_index,
            proof,
            certificate,
        })
    }
}

/// Authenticated background cache entry; no unchecked public constructor.
///
/// Why: Ed25519 verification is the expensive part of checking a signature.
/// All 128 signatures of a batch share one certificate, so a verifier checks
/// it once, keeps a `VerifiedBatch`, and then checks each signature with hash
/// work only. The only way to build one is [`VerifiedBatch::authenticate`].
pub struct VerifiedBatch {
    /// The trusted Ed25519 public key (32 bytes) the certificate verified under.
    signer: [u8; 32],
    /// The exact certificate that verified.
    certificate: BatchCertificate,
}

impl VerifiedBatch {
    /// Cache a certificate only after strict Ed25519 verification succeeds.
    #[must_use]
    pub fn authenticate(
        certificate: &BatchCertificate,
        trusted_signer: &VerifyingKey,
    ) -> Option<Self> {
        certificate.verify_strict(trusted_signer).then(|| Self {
            signer: trusted_signer.to_bytes(),
            certificate: certificate.clone(),
        })
    }

    /// Fast-path eligibility binds the full certificate and trusted identity.
    #[must_use]
    pub fn can_verify_fast(
        &self,
        signature: &DsigSignature,
        trusted_signer: &VerifyingKey,
    ) -> bool {
        self.signer == trusted_signer.to_bytes() && self.certificate == signature.certificate
    }

    /// Verify without a repeated Ed25519 operation; cache misses fail closed.
    #[must_use]
    pub fn verify(
        &self,
        signature: &DsigSignature,
        message: &[u8],
        trusted_signer: &VerifyingKey,
    ) -> bool {
        self.can_verify_fast(signature, trusted_signer)
            && signature.verify_authenticated_hash_component(message)
    }
}

/// Prepare and certify a reference batch; repeated namespace allocation is unsafe.
///
/// One batch = 128 one-time keys, their Merkle tree and one Ed25519
/// certificate. It holds no master seed. Use it through [`crate::lease`],
/// which makes sure each `(epoch, batch_id)` is used once.
pub struct PreparedBatch {
    /// The 128 keys; `None` once a key has signed or gone to a device.
    keys: [Option<PreparedKey>; BATCH_KEYS],
    /// Merkle tree over the keys' `pk_hash` values.
    tree: BatchTree,
    /// Ed25519 certificate over the tree root and namespace.
    certificate: BatchCertificate,
}

/// Derive the 32-byte seed of one one-time key.
///
/// `BLAKE3 derive_key(SEED_DERIVATION_CONTEXT, master ‖ signer ‖ epoch ‖
/// batch_id ‖ index)` over 32 + 32 + 8 + 8 + 4 = 84 bytes, little endian.
/// Every input that names the key goes in, so two signers, two namespaces or
/// two indices never share a seed. The derivation context string,
/// [`crate::SEED_DERIVATION_CONTEXT`], is frozen and shared with the hardware
/// builders.
fn one_time_seed(
    master: &[u8; 32],
    signer: &[u8; 32],
    epoch: u64,
    batch_id: u64,
    index: u32,
) -> [u8; 32] {
    // The 84-byte input, wiped right after hashing because it holds the master seed.
    let mut material = [0; 84];
    material[..32].copy_from_slice(master);
    material[32..64].copy_from_slice(signer);
    material[64..72].copy_from_slice(&epoch.to_le_bytes());
    material[72..80].copy_from_slice(&batch_id.to_le_bytes());
    material[80..].copy_from_slice(&index.to_le_bytes());
    let mut hasher = blake3::Hasher::new_derive_key(crate::SEED_DERIVATION_CONTEXT);
    hasher.update(&material);
    material.zeroize();
    let mut seed = [0; 32];
    let mut reader = hasher.finalize_xof();
    reader.fill(&mut seed);
    reader.zeroize();
    hasher.zeroize();
    seed
}

impl PreparedBatch {
    /// Software bootstrap/oracle. Persist a fresh `(epoch, batch_id)` first.
    ///
    /// Derives 128 seeds, prepares 128 keys, builds the tree and signs the
    /// commitment with `signer`. The master seed is zeroized before return.
    #[must_use]
    pub fn new(mut master_seed: [u8; 32], epoch: u64, batch_id: u64, signer: &SigningKey) -> Self {
        // The Ed25519 public key is mixed into every seed.
        let signer_identity = signer.verifying_key().to_bytes();
        let keys: [Option<PreparedKey>; BATCH_KEYS] = core::array::from_fn(|index| {
            let mut seed = one_time_seed(
                &master_seed,
                &signer_identity,
                epoch,
                batch_id,
                index as u32,
            );
            let prepared = PreparedKey::from_seed(seed);
            seed.zeroize();
            Some(prepared)
        });
        master_seed.zeroize();
        // Leaf i is key i's public commitment.
        let leaves = core::array::from_fn(|i| keys[i].as_ref().expect("new key").public.pk_hash);
        let tree = BatchTree::new(&leaves);
        let certificate = BatchCertificate::sign_reference(
            BatchCommitment {
                epoch,
                batch_id,
                root: tree.root(),
            },
            signer,
        );
        Self {
            keys,
            tree,
            certificate,
        }
    }

    /// Certificate to pre-verify at expected recipients before online traffic.
    #[must_use]
    pub const fn certificate(&self) -> &BatchCertificate {
        &self.certificate
    }

    /// Burn ownership before returning a key to a hardware loader.
    ///
    /// The slot becomes `None`, so this batch can never sign with that key
    /// again, even if the device later fails.
    pub fn take_key_for_device(&mut self, index: usize) -> Option<PreparedKey> {
        self.keys.get_mut(index)?.take()
    }

    /// Finish a hardware-produced WOTS signature without recreating a secret key.
    ///
    /// The full signature must still be independently verified before use.
    #[must_use]
    ///
    /// Returns `None` if `index` is out of range or `wots` is not the key at
    /// that leaf.
    pub fn attach_certificate(&self, index: usize, wots: WotsSignature) -> Option<DsigSignature> {
        let proof = self.tree.proof(index)?;
        // Refuse a WOTS part whose key is not leaf `index` of this tree.
        if root_from_proof(wots.public.pk_hash, index, &proof) != Some(self.tree.root()) {
            return None;
        }
        Some(DsigSignature {
            wots,
            key_index: index as u16,
            proof,
            certificate: self.certificate.clone(),
        })
    }

    /// Consume exactly one unused key; a repeated index returns `None`.
    pub fn sign(&mut self, index: usize, message: &[u8]) -> Option<DsigSignature> {
        let key = self.keys.get_mut(index)?.take()?;
        self.attach_certificate(index, key.sign(message))
    }
}

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

    /// Same master seed, different signer, epoch, batch or index: different seeds; and the input layout is exactly the documented 84 bytes.
    #[test]
    fn identical_master_material_is_separated_by_signer_and_namespace() {
        let master = [0x37; 32];
        let a = SigningKey::from_bytes(&[0x31; 32])
            .verifying_key()
            .to_bytes();
        let b = SigningKey::from_bytes(&[0x32; 32])
            .verifying_key()
            .to_bytes();
        let seed = one_time_seed(&master, &a, 11, 29, 17);
        assert_ne!(seed, one_time_seed(&master, &b, 11, 29, 17));
        assert_ne!(seed, one_time_seed(&master, &a, 12, 29, 17));
        assert_ne!(seed, one_time_seed(&master, &a, 11, 30, 17));
        assert_ne!(seed, one_time_seed(&master, &a, 11, 29, 18));
        let mut material = [0; 84];
        material[..32].copy_from_slice(&master);
        material[32..64].copy_from_slice(&a);
        material[64..72].copy_from_slice(&11u64.to_le_bytes());
        material[72..80].copy_from_slice(&29u64.to_le_bytes());
        material[80..].copy_from_slice(&17u32.to_le_bytes());
        assert_eq!(
            seed,
            blake3::derive_key(crate::SEED_DERIVATION_CONTEXT, &material)
        );
    }

    /// The complement checksum falls when a digit rises, so forward-only hashing cannot forge; a raw-sum checksum would not.
    #[test]
    fn complement_checksum_blocks_the_upstream_monotone_counterexample() {
        let a = [1; 64];
        let mut b = a;
        b[0] = 2;
        let da = digits_from_xof(&a);
        let db = digits_from_xof(&b);
        assert_eq!(&da[64..], &[0, 0, 0, 2]);
        assert_eq!(&db[64..], &[3, 3, 3, 1]);
        assert!(da.iter().zip(db).any(|(before, after)| after < *before));
        // Structural fixture only: raw-sum upstream digits would permit this
        // forward-only transformation. No message preimage attack is claimed.
        let upstream_a = [0_u8, 0, 0, 1];
        let upstream_b = [1_u8, 0, 0, 1];
        assert!(upstream_a.iter().zip(upstream_b).all(|(x, y)| y >= *x));
        assert_eq!(&digits_from_xof(&[0; 64])[64..], &[0, 0, 0, 3]);
        assert_eq!(&digits_from_xof(&[255; 64])[64..], &[0, 0, 0, 0]);
    }

    /// A WOTS signature verifies for its message and fails for another message or a flipped node bit.
    #[test]
    fn one_time_chain_signature_round_trip_and_tamper_rejection() {
        let signature = PreparedKey::from_seed([0x45; 32]).sign(b"sixteen byte msg");
        assert!(signature.verify_hash_component(b"sixteen byte msg"));
        assert!(!signature.verify_hash_component(b"different message"));
        for index in [0, 32, 64, 67] {
            let mut bad = signature.clone();
            bad.elements[index][0] ^= 1;
            assert!(!bad.verify_hash_component(b"sixteen byte msg"));
        }
    }

    /// All 128 keys sign once, verify cold and warm, round-trip the wire format, refuse reuse and reject tampering.
    #[test]
    fn complete_batch_is_transferable_cached_and_single_use() {
        let signer = SigningKey::from_bytes(&[0x29; 32]);
        let trusted = signer.verifying_key();
        let wrong = SigningKey::from_bytes(&[0x28; 32]).verifying_key();
        let mut batch = PreparedBatch::new([0x61; 32], 17, 40, &signer);
        let cached =
            VerifiedBatch::authenticate(batch.certificate(), &trusted).expect("certificate");
        assert!(VerifiedBatch::authenticate(batch.certificate(), &wrong).is_none());
        for index in 0..BATCH_KEYS {
            let message = (index as u128).to_le_bytes();
            let signature = batch.sign(index, &message).expect("unused key");
            assert!(signature.verify(&message, &trusted));
            assert!(cached.verify(&signature, &message, &trusted));
            assert!(!cached.can_verify_fast(&signature, &wrong));
            assert!(batch.sign(index, &message).is_none());
            assert_eq!(
                DsigSignature::from_bytes(&signature.to_bytes()),
                Some(signature.clone())
            );
            let mut bad = signature.clone();
            bad.proof[0][0] ^= 1;
            assert!(!bad.verify(&message, &trusted));
            let mut bad = signature.clone();
            bad.certificate.commitment.batch_id += 1;
            assert!(!cached.can_verify_fast(&bad, &trusted));
            assert!(!bad.verify(&message, &trusted));
            let mut bad = signature.clone();
            bad.key_index = 128;
            assert!(!bad.verify(&message, &trusted));
            assert!(DsigSignature::from_bytes(&bad.to_bytes()).is_none());
        }
        assert!(batch.sign(128, b"bad index").is_none());
    }

    /// Every leaf's proof rebuilds the root; a wrong index or index 128 is rejected.
    #[test]
    fn merkle_all_positions_and_invalid_indices() {
        let leaves = core::array::from_fn(|i| *blake3::hash(&(i as u64).to_le_bytes()).as_bytes());
        let tree = BatchTree::new(&leaves);
        for (i, leaf) in leaves.iter().enumerate() {
            let proof = tree.proof(i).expect("in range");
            assert_eq!(root_from_proof(*leaf, i, &proof), Some(tree.root()));
            assert_ne!(root_from_proof(*leaf, i ^ 1, &proof), Some(tree.root()));
        }
        assert!(tree.proof(128).is_none());
        assert!(root_from_proof(leaves[0], 128, &[[0; 32]; 7]).is_none());
    }
}