rhdl_dsig_scalable_core/verify/

certs.rs

//! The verifier's certificate cache, in front of the Ed25519 verify core.
//!
//! # The problem
//!
//! Every record carries its batch certificate: the 64-byte commitment and
//! the Ed25519 signature over it. Verifying that signature costs about a
//! thousand times more than the hash work, but all 128 records of a batch
//! carry the *same* certificate. So the verifier checks each certificate
//! once and remembers the answer, exactly as the reference
//! [`VerifiedBatch`](crate::reference::VerifiedBatch) does in software: a
//! record may reuse an answer only if its whole 128-byte certificate is
//! identical to the one that was checked.
//!
//! # The idea
//!
//! 64 entries, picked by the low 6 bits of the batch id (commitment byte
//! 24) mixed with the signer's key slot. So many because a certificate check takes 52,000–83,000 cycles
//! (Ed25519 project, native simulation of the `1,1,1,1` core): a unit
//! finishes a batch every ~4,500 cycles, so about 20 batches wait for their
//! checks at once. Each holds a certificate (two 64-byte rows in block RAM) and a
//! state:
//!
//! ```text
//!            miss: store, ask Ed25519
//!   FREE ───────────────────────────▶ PENDING ──ok──▶ VERIFIED
//!     ▲                                  │                │
//!     │                                  └──fail──▶ REJECTED
//!     └──── replaced by a different certificate (never while PENDING
//!           or while a waiting record still points at it)
//! ```
//!
//! A lookup compares the record's commitment and signature with the entry's
//! two rows. A hit on VERIFIED or REJECTED answers at once. A hit on PENDING,
//! or a miss that stores the certificate and asks the Ed25519 core, answers
//! "pending on entry `e`"; the record then waits at retirement until the
//! entry settles. An entry that waiting records point at (its `users` count)
//! is never replaced, so their answer cannot change under them.
//!
//! # Several signers
//!
//! The commitment does not name the signer's Ed25519 key, so one checked
//! certificate must not answer for a record that claims a different signer.
//! Each record arrives with its signer's key slot (0 when the verifier
//! trusts one key, as the HBM kernel does). The slot is part of the entry
//! choice (`batch id ^ slot << 2`), an entry remembers the slot it was
//! checked for, a hit needs the same slot, and the Ed25519 request carries
//! the slot so the cluster presents that slot's key.
//!
//! # Warm lookups
//!
//! A *warm* lookup brings a certificate in ahead of its records (the uBFT
//! service's certificate announce, [`crate::ubft`]): it is looked up like a
//! record's, and on a miss it is stored and checked, but it answers no
//! record and holds no `users` count, so it never delays a verdict. When
//! the entry it maps to is busy it is simply dropped; the first record of
//! the batch then checks the certificate as before.
//!
//! # Timing
//!
//! The loader presents the commitment (beat 0) and the signature (beat 1).
//! The answer comes a few cycles later, long before the record's 26 beats
//! are in; [`CertsOutput::busy`] holds the next record's beat 0 back in the
//! rare case a lookup must wait for an entry to free up.

use crate::verify::chains::CONTEXTS;
use rhdl::prelude::*;
use rhdl_fpga::core::{
    dff::DFF,
    ram::synchronous::{In as RamIn, SyncBRAM, Write as RamWrite},
};

/// Certificate entries.
pub const ENTRIES: usize = 64;

/// Entry state: no certificate.
pub const FREE: b2 = b2(0);
/// Entry state: asked the Ed25519 core, no answer yet.
pub const PENDING: b2 = b2(1);
/// Entry state: the certificate verified.
pub const VERIFIED: b2 = b2(2);
/// Entry state: the certificate failed.
pub const REJECTED: b2 = b2(3);

/// A certificate check for the Ed25519 core.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
pub struct CertRequest {
    /// A request is presented (held until taken).
    pub valid: bool,
    /// The entry that waits for the answer.
    pub entry: b6,
    /// The signer's key slot: the key the certificate must verify under.
    pub slot: b4,
    /// The 64-byte commitment, the signed message.
    pub commitment: [b8; 64],
    /// The Ed25519 signature `R ‖ S`.
    pub signature: [b8; 64],
}

impl Default for CertRequest {
    /// No request.
    fn default() -> Self {
        Self {
            valid: false,
            entry: b6(0),
            slot: b4(0),
            commitment: [b8(0); 64],
            signature: [b8(0); 64],
        }
    }
}

/// The Ed25519 core's answer for an entry.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct CertResult {
    /// An answer this cycle.
    pub valid: bool,
    /// The entry it belongs to.
    pub entry: b6,
    /// The certificate verified.
    pub ok: bool,
}

/// What a record learns from its lookup.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct CertAnswer {
    /// The answer is presented this cycle.
    pub valid: bool,
    /// The record's context.
    pub ctx: b6,
    /// The answer is not known yet: wait for `entry` to settle.
    pub pending: bool,
    /// The entry (meaningful when `pending`).
    pub entry: b6,
    /// The certificate is valid (meaningful when not `pending`).
    pub ok: bool,
}

/// Inputs of the cache.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
pub struct CertsInput {
    /// Beat 0 of a record (its commitment) is presented.
    pub commitment_valid: bool,
    /// Beat 1 (its signature) is presented.
    pub signature_valid: bool,
    /// The beat.
    pub beat: [b8; 64],
    /// The record's context (with beat 0).
    pub ctx: b6,
    /// The record's signer key slot (with beat 0).
    pub slot: b4,
    /// The lookup is a warm one (with beat 0): no answer, no user.
    pub warm: bool,
    /// The Ed25519 core took the presented request this cycle.
    pub taken: bool,
    /// An answer from the Ed25519 core.
    pub result: CertResult,
    /// A record that waited on an entry retires (its `users` count drops).
    pub release_valid: bool,
    /// That entry.
    pub release_entry: b6,
}

/// Outputs of the cache.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
pub struct CertsOutput {
    /// Do not present a new commitment this cycle.
    pub busy: bool,
    /// The answer to a lookup.
    pub answer: CertAnswer,
    /// The request for the Ed25519 core.
    pub request: CertRequest,
    /// Each entry's state.
    pub state: [b2; ENTRIES],
    /// Requests issued so far.
    pub checks: b32,
    /// Answers that failed so far.
    pub fails: b32,
}

/// Lookup phases.
const IDLE: b3 = b3(0);
/// Commitment stored; waiting for the signature.
const HAVE_COMMITMENT: b3 = b3(1);
/// Row 0 is here: compare it, ask for row 1.
const COMPARE0: b3 = b3(2);
/// Row 1 is here: decide (or wait for the entry, keeping row 1 addressed).
const DECIDE: b3 = b3(3);
/// Writing the signature row of a replaced entry.
const WRITE_ROW1: b3 = b3(4);

/// Resettable state.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct CertsControl {
    /// Lookup phase.
    phase: b3,
    /// The looked-up entry.
    entry: b6,
    /// The record's context.
    ctx: b6,
    /// The record's signer key slot.
    slot: b4,
    /// The lookup is warm.
    warm: bool,
    /// Row 0 matched.
    match0: bool,
    /// Entry states.
    state: [b2; ENTRIES],
    /// Records waiting on each entry.
    users: [b12; ENTRIES],
    /// The key slot each entry was checked (or is being checked) for.
    slots: [b4; ENTRIES],
    /// A request is presented to the Ed25519 core.
    request: bool,
    /// Its entry.
    request_entry: b6,
    /// Its key slot.
    request_slot: b4,
    /// The answer register holds an answer.
    answer: CertAnswer,
    /// Requests issued.
    checks: b32,
    /// Failed answers.
    fails: b32,
}

impl Default for CertsControl {
    /// Every entry free, nothing in flight.
    fn default() -> Self {
        Self {
            phase: IDLE,
            entry: b6(0),
            ctx: b6(0),
            slot: b4(0),
            warm: false,
            match0: false,
            state: [FREE; ENTRIES],
            users: [b12(0); ENTRIES],
            slots: [b4(0); ENTRIES],
            request: false,
            request_entry: b6(0),
            request_slot: b4(0),
            answer: CertAnswer::default(),
            checks: b32(0),
            fails: b32(0),
        }
    }
}

/// Resetless data.
#[derive(Clone, Copy, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct CertsData {
    /// The record's commitment.
    commitment: [b8; 64],
    /// The record's signature.
    signature: [b8; 64],
    /// The presented request's commitment (kept while the next lookup runs).
    request_commitment: [b8; 64],
    /// The presented request's signature.
    request_signature: [b8; 64],
}

/// The certificate cache.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct VerifyCerts {
    /// Entry `e`'s commitment at row `2e`, signature at row `2e + 1`.
    rows: SyncBRAM<[b8; 64], 7>,
    /// Phases, states and counters.
    control: DFF<CertsControl>,
    /// The looked-up certificate.
    data: DFF<CertsData>,
}

impl Default for VerifyCerts {
    /// An empty cache.
    fn default() -> Self {
        Self {
            rows: SyncBRAM::default(),
            control: DFF::new(CertsControl::default()),
            data: DFF::resetless(),
        }
    }
}

impl SynchronousIO for VerifyCerts {
    type I = CertsInput;
    type O = CertsOutput;
    type Kernel = verify_certs_kernel;
}

/// Whether two 64-byte rows are equal (a 512-bit compare as a tree of bytes).
#[allow(clippy::needless_range_loop)]
#[kernel]
pub fn rows_equal_kernel(a: [b8; 64], b: [b8; 64]) -> bool {
    let mut same = [false; 64];
    for i in 0..64 {
        same[i] = a[i] == b[i];
    }
    let mut eights = [false; 8];
    for g in 0..8 {
        eights[g] = same[8 * g]
            && same[8 * g + 1]
            && same[8 * g + 2]
            && same[8 * g + 3]
            && same[8 * g + 4]
            && same[8 * g + 5]
            && same[8 * g + 6]
            && same[8 * g + 7];
    }
    eights[0] && eights[1] && eights[2] && eights[3] && eights[4] && eights[5] && eights[6] && eights[7]
}

/// The cache's logic.
#[allow(clippy::needless_range_loop, clippy::too_many_lines)]
#[kernel]
pub fn verify_certs_kernel(clock_reset: ClockReset, input: CertsInput, q: VerifyCertsQ) -> (CertsOutput, VerifyCertsD) {
    // No reset gating here: every register this logic feeds resets itself,
    // and keeping the reset out of the logic cones keeps it off the routed
    // kernel's failing paths (verifier build v1).
    let resetting = clock_reset.reset.any();
    let _ = resetting;
    let mut c = q.control;
    let mut data = q.data;
    let mut read_addr: b7 = q.control.entry.resize::<7>() << 1;
    let mut write = RamWrite::<[b8; 64], 7> {
        addr: q.control.entry.resize::<7>() << 1,
        value: q.data.commitment,
        enable: false,
    };
    c.answer.valid = false;
    let mut state = q.control.state;
    let mut users = q.control.users;
    // Ed25519 answers settle their entry.
    if input.result.valid {
        for e in 0..ENTRIES {
            if input.result.entry == b6(e as u128) {
                state[e] = if input.result.ok { VERIFIED } else { REJECTED };
            }
        }
        if !input.result.ok {
            c.fails = q.control.fails + b32(1);
        }
    }
    if input.taken {
        c.request = false;
    }
    // Entry state and users of the looked-up entry.
    let mut entry_state = FREE;
    let mut entry_users = b12(0);
    let mut entry_slot = b4(0);
    for e in 0..ENTRIES {
        if q.control.entry == b6(e as u128) {
            entry_state = q.control.state[e];
            entry_users = q.control.users[e];
            entry_slot = q.control.slots[e];
        }
    }
    let mut slots = q.control.slots;
    let mut add_user = false;
    if q.control.phase == IDLE {
        if input.commitment_valid {
            data.commitment = input.beat;
            // Batch id bits 0..6, mixed with the key slot, pick the entry.
            c.entry = (input.beat[24] ^ (input.slot.resize::<8>() << 2)).resize();
            c.ctx = input.ctx;
            c.slot = input.slot;
            c.warm = input.warm;
            c.phase = HAVE_COMMITMENT;
        }
    } else if q.control.phase == HAVE_COMMITMENT {
        if input.signature_valid {
            data.signature = input.beat;
            read_addr = q.control.entry.resize::<7>() << 1;
            c.phase = COMPARE0;
        }
    } else if q.control.phase == COMPARE0 {
        // Row 0 is here; ask for row 1 and keep asking while deciding.
        c.match0 = rows_equal_kernel(q.rows, q.data.commitment);
        read_addr = (q.control.entry.resize::<7>() << 1) | b7(1);
        c.phase = DECIDE;
    } else if q.control.phase == DECIDE {
        read_addr = (q.control.entry.resize::<7>() << 1) | b7(1);
        let hit = q.control.match0
            && rows_equal_kernel(q.rows, q.data.signature)
            && entry_state != FREE
            && entry_slot == q.control.slot;
        let warm = q.control.warm;
        if hit {
            if !warm {
                c.answer = CertAnswer {
                    valid: true,
                    ctx: q.control.ctx,
                    pending: entry_state == PENDING,
                    entry: q.control.entry,
                    ok: entry_state == VERIFIED,
                };
                add_user = entry_state == PENDING;
            }
            c.phase = IDLE;
        } else if warm && (entry_state == PENDING || entry_users != b12(0) || q.control.request) {
            // A warm lookup never waits: the entry is busy, drop it.
            c.phase = IDLE;
        } else if entry_state != PENDING && entry_users == b12(0) && !q.control.request {
            // Replace the entry: commitment row now, signature row next.
            write.enable = true;
            c.phase = WRITE_ROW1;
            for e in 0..ENTRIES {
                if q.control.entry == b6(e as u128) {
                    state[e] = PENDING;
                    slots[e] = q.control.slot;
                }
            }
            c.request = true;
            c.request_entry = q.control.entry;
            c.request_slot = q.control.slot;
            data.request_commitment = q.data.commitment;
            data.request_signature = q.data.signature;
            c.checks = q.control.checks + b32(1);
            if !warm {
                c.answer = CertAnswer {
                    valid: true,
                    ctx: q.control.ctx,
                    pending: true,
                    entry: q.control.entry,
                    ok: false,
                };
                add_user = true;
            }
        }
        // Otherwise wait here until the entry is free to replace.
    } else {
        // WRITE_ROW1
        write = RamWrite::<[b8; 64], 7> {
            addr: (q.control.entry.resize::<7>() << 1) | b7(1),
            value: q.data.signature,
            enable: true,
        };
        c.phase = IDLE;
    }
    // Users: one more for a pending answer, one fewer for a release.
    for e in 0..ENTRIES {
        let mut u = users[e];
        if add_user && q.control.entry == b6(e as u128) {
            u = u + b12(1);
        }
        if input.release_valid && input.release_entry == b6(e as u128) {
            u = u - b12(1);
        }
        users[e] = u;
    }
    c.state = state;
    c.users = users;
    c.slots = slots;
    let d = VerifyCertsD {
        rows: RamIn::<[b8; 64], 7> { read_addr, write },
        control: c,
        data,
    };
    (
        CertsOutput {
            busy: q.control.phase != IDLE,
            answer: CertAnswer {
                valid: q.control.answer.valid,
                ctx: q.control.answer.ctx,
                pending: q.control.answer.pending,
                entry: q.control.answer.entry,
                ok: q.control.answer.ok,
            },
            request: CertRequest {
                valid: q.control.request,
                entry: q.control.request_entry,
                slot: q.control.request_slot,
                commitment: q.data.request_commitment,
                signature: q.data.request_signature,
            },
            state: q.control.state,
            checks: q.control.checks,
            fails: q.control.fails,
        },
        d,
    )
}

const _: () = assert!(CONTEXTS <= 4095, "users counts are 12 bits");