rhdl_dsig_scalable_core/verify/
chains.rs

1//! The verifier's chain block: three recirculating chain lanes.
2//!
3//! # The problem
4//!
5//! To check a W-OTS+ signature, chain `i` must be hashed from its revealed
6//! node to the end of the chain: `3 − digit_i` steps, where the digit comes
7//! from the message digest. Over a signature's 68 chains that is 105 steps on
8//! average, but anything from 0 to 3 per chain, and only known once the
9//! digest is back. The signer's chain engine ([`crate::slice_chain`]) cannot
10//! be reused as it is: it pushes every chain through all three steps in a
11//! fixed pipeline, which here would waste half of every lane.
12//!
13//! # The idea: lanes that recirculate
14//!
15//! Each lane is the signer's chain lane ([`ChainLane`], 20 cycles, one step
16//! per clock), closed into a ring. What leaves the lane either goes round
17//! again (it needs another step) or is finished (it is a chain end). A slot
18//! that comes back empty, or carries a finished chain, takes the next new
19//! chain. So every clock does a useful step whenever there is work:
20//!
21//! ```text
22//!              ┌───────────────────── recirculate (depth < 3) ─────────────────┐
23//!              │                                                               │
24//!   nodes ─▶ fetch ─▶ skid ─▶ ┌mux┐ ─▶ [ chain lane, 20 cycles ] ─▶ ─ R ─▶ ───┘
25//!   (bank)     │      FIFO    └───┘          ▲ salt(depth)                │
26//!              │                                                          │ depth = 3
27//!              └── digit = 3: already an end ─▶ end queue ─┐              ▼
28//!                                                          └──▶ end banks ─▶ row assembler
29//!
30//! Chains whose digit is 3 need no step: they wait in their own small queue
31//! for a cycle when the end port is free, so they never take a lane slot.
32//! (Sharing one queue cost a lane slot per such chain, about six per record
33//! and lane: 41.7 instead of about 35 cycles per record, measured in native
34//! simulation.)
35//! ```
36//!
37//! Chain `c` always uses lane `c mod 3`, so each lane owns its chains' node
38//! and end storage and no two lanes ever write the same RAM.
39//!
40//! # Storage
41//!
42//! All RAMs are indexed by *context* (the slot of a record in flight, 0..64)
43//! and by `k = c / 3`, the chain's number within its lane (0..23):
44//!
45//! | RAM | Per lane | Address | Written by | Read by |
46//! |---|---|---|---|---|
47//! | node banks | 2 (`k` even, odd) | `ctx·16 + k/2` | the loader | this lane's fetch |
48//! | end banks | 5 (`k mod 5`) | `ctx·8 + k/5` | this lane | the row assembler |
49//! | digits | 1 | `ctx` | the hasher (digest result) | fetch, once per context |
50//! | `pk_nonce` | 1 (+1 for the row assembler) | `ctx` | the loader | fetch, once per context |
51//!
52//! Two node banks let the loader write up to four nodes per beat (four
53//! consecutive chains fall in four different banks, `c mod 6`). Five end
54//! banks per lane, fifteen in all (`c mod 15`), let the row assembler read
55//! any five consecutive chain ends at once: a 64-byte commitment block
56//! touches at most five chains.
57//!
58//! # The row assembler
59//!
60//! The endpoint commitment hashes `pk_nonce ‖ end₀ ‖ … ‖ end₆₇` (1,240
61//! bytes) as 20 BLAKE3 blocks. The hasher asks for block `j` of a context;
62//! two cycles later this block delivers it, built by a fixed byte map
63//! ([`ROW_SOURCE`]) from the fifteen end banks and the context's `pk_nonce`.
64//! No block is ever stored: each is assembled when the BLAKE3 lane is about
65//! to use it.
66//!
67//! # Contract
68//!
69//! * A context's nodes and `pk_nonce` are written before its digits arrive.
70//! * Digits arrive at most once per context between retirements.
71//! * [`ChainsOutput::done`]`[ctx]` rises once all 68 chain ends of `ctx` are
72//!   stored, and stays high until [`ChainsInput::retire`] names `ctx`.
73//! * A row request for `ctx` is made only while `done[ctx]` is high.
74
75use crate::chain_lane::{ChainLane, LANE_LATENCY};
76use crate::chain_step::{ChainStepInput, ChainStepOutput};
77use crate::slice_chain::salt_kernel;
78use crate::{CHAINS, ELEMENT_BYTES};
79use rhdl::prelude::*;
80use rhdl_fpga::core::{
81    dff::DFF,
82    ram::synchronous::{In as RamIn, SyncBRAM, Write as RamWrite},
83};
84
85/// Records in flight per unit; a record's context is its number mod 64.
86pub const CONTEXTS: usize = 64;
87/// Chain lanes per unit. Chain `c` runs on lane `c mod LANES`.
88pub const LANES: usize = 3;
89/// Most chains one lane serves per record: lanes 0 and 1 get 23, lane 2 gets 22.
90pub const LANE_CHAINS: usize = CHAINS.div_ceil(LANES);
91/// 64-byte blocks of the endpoint commitment (16 + 68 × 18 = 1,240 bytes).
92pub const ROWS: usize = (16 + CHAINS * ELEMENT_BYTES).div_ceil(64);
93/// End banks per lane (`k mod 5`).
94pub const END_BANKS: usize = 5;
95/// Node banks per lane (`k mod 2`).
96pub const NODE_BANKS: usize = 2;
97/// Cycles from a row request to its row on the output.
98pub const ROW_LATENCY: usize = 2;
99/// `k` of a lane's 23rd chain (only lanes 0 and 1 have one).
100const LAST_LANE_CHAIN: usize = LANE_CHAINS - 1;
101/// Chain 66, lane 0's last.
102const CHAIN_66: usize = CHAINS - 2;
103/// Chain 67, lane 1's last.
104const CHAIN_67: usize = CHAINS - 1;
105/// Last stage of the nonce delay beside a lane.
106const LANE_LAST: usize = LANE_LATENCY - 1;
107/// Entries of the fetch skid FIFO in front of each lane.
108const SKID: usize = 4;
109
110const _: () = assert!(LANES == 3, "the bank maps below assume three lanes");
111const _: () = assert!(ROWS == 20);
112const _: () = assert!(CONTEXTS == 64, "contexts are 6-bit numbers");
113
114/// One node write into a lane's node bank.
115#[derive(Clone, Copy, Debug, PartialEq, Digital)]
116pub struct NodeWrite {
117    /// Write this cycle.
118    pub enable: bool,
119    /// `ctx·16 + k/2`.
120    pub addr: b10,
121    /// The 18-byte revealed node.
122    pub value: [b8; ELEMENT_BYTES],
123}
124
125impl Default for NodeWrite {
126    /// No write.
127    fn default() -> Self {
128        Self {
129            enable: false,
130            addr: b10(0),
131            value: [b8(0); ELEMENT_BYTES],
132        }
133    }
134}
135
136/// A context's `pk_nonce`, written once per record by the loader.
137#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
138pub struct NonceWrite {
139    /// Write this cycle.
140    pub valid: bool,
141    /// The record's context.
142    pub ctx: b6,
143    /// The unsalted 16-byte `pk_nonce`.
144    pub value: [b8; 16],
145}
146
147/// A context leaves the unit: its counters restart from zero.
148#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
149pub struct Retire {
150    /// Retire this cycle.
151    pub valid: bool,
152    /// The context.
153    pub ctx: b6,
154}
155
156/// One lane's share of a record's digits: digit `k` belongs to chain `lane + 3k`.
157#[derive(Clone, Copy, Debug, PartialEq, Digital)]
158pub struct LaneDigits {
159    /// The digits are presented this cycle.
160    pub valid: bool,
161    /// The record's context.
162    pub ctx: b6,
163    /// Digit of chain `lane + 3k` (0..=3) at index `k`; lane 2 ignores `k = 22`.
164    pub digits: [b2; LANE_CHAINS],
165}
166
167impl Default for LaneDigits {
168    /// No digits.
169    fn default() -> Self {
170        Self {
171            valid: false,
172            ctx: b6(0),
173            digits: [b2(0); LANE_CHAINS],
174        }
175    }
176}
177
178/// The digits of one record, from the hasher's digest result.
179#[derive(Clone, Copy, Debug, PartialEq, Digital)]
180pub struct DigitsEvent {
181    /// The digits are presented this cycle (one cycle per record).
182    pub valid: bool,
183    /// The record's context.
184    pub ctx: b6,
185    /// Digit `i` of chain `i` (64 message digits, then 4 checksum digits).
186    pub digits: [b2; CHAINS],
187}
188
189impl Default for DigitsEvent {
190    /// No digits.
191    fn default() -> Self {
192        Self {
193            valid: false,
194            ctx: b6(0),
195            digits: [b2(0); CHAINS],
196        }
197    }
198}
199
200// ------------------------------------------------------------------- lane ring
201
202/// Inputs of one lane ring.
203#[derive(Clone, Copy, Debug, PartialEq, Digital)]
204pub struct RingInput {
205    /// Which lane this ring is (0..=2): its chains are `lane + 3k`. A
206    /// constant from the parent, so one ring module serves all three.
207    pub lane: b2,
208    /// Writes into node banks 0 (`k` even) and 1 (`k` odd).
209    pub nodes: [NodeWrite; NODE_BANKS],
210    /// This lane's digits of a record.
211    pub digits: LaneDigits,
212    /// A record's `pk_nonce`.
213    pub nonce: NonceWrite,
214    /// A context leaves the unit.
215    pub retire: Retire,
216    /// Read address of each end bank (`ctx·8 + k/5`); data one cycle later.
217    pub end_read: [b9; END_BANKS],
218}
219
220/// Outputs of one lane ring.
221#[derive(Clone, Copy, Debug, PartialEq, Digital)]
222pub struct RingOutput {
223    /// Each end bank's data for the address presented last cycle.
224    pub ends: [[b8; ELEMENT_BYTES]; END_BANKS],
225    /// All of this lane's chains of the context are ends.
226    pub done: [bool; CONTEXTS],
227    /// The lane's S-boxes are loaded.
228    pub ready: bool,
229    /// A chain step enters the lane this cycle (activity counter).
230    pub stepped: bool,
231}
232
233/// A chain in flight (in the skid FIFO or the recirculation register).
234#[derive(Clone, Copy, Debug, PartialEq, Digital)]
235#[doc(hidden)]
236pub struct RingItem {
237    /// The node at `depth`.
238    node: [b8; ELEMENT_BYTES],
239    /// The record's unsalted `pk_nonce`.
240    nonce: [b8; 16],
241    /// `nonce` salted for the step from `depth` (low 32 bits + `chain + 68·depth`).
242    salted: [b8; 16],
243    /// Routing tag: context, chain, depth and end-bank position.
244    tag: b32,
245}
246
247/// Resettable state of a ring.
248#[derive(Clone, Copy, Debug, PartialEq, Digital)]
249#[doc(hidden)]
250pub struct RingControl {
251    /// Contexts queued (digits written), and taken, as 7-bit counters.
252    queue_tail: b7,
253    /// Contexts taken from the queue.
254    queue_head: b7,
255    /// Context start: 0 idle, 1 queue read, 2 digits and nonce read.
256    phase: b2,
257    /// A context is being fetched.
258    active: bool,
259    /// That context.
260    ctx: b6,
261    /// Next chain to fetch, `k`, with `k mod 5` and `k / 5`.
262    k: b5,
263    /// `k mod 5`.
264    k_mod5: b3,
265    /// `k / 5`.
266    k_div5: b3,
267    /// A node read is in flight; its data arrives next cycle.
268    fetching: bool,
269    /// Items in the skid FIFO.
270    count: b3,
271    /// Oldest skid entry.
272    head: b2,
273    /// Chains in the end queue (digit 3: already ends, waiting for the end port).
274    ends_count: b3,
275    /// Oldest end-queue entry.
276    ends_head: b2,
277    /// The recirculation register holds a chain.
278    recirculate: bool,
279    /// Chain ends stored per context.
280    ends: [b5; CONTEXTS],
281}
282
283impl Default for RingControl {
284    /// Empty queue, idle fetch, no chains, zero counts.
285    fn default() -> Self {
286        Self {
287            queue_tail: b7(0),
288            queue_head: b7(0),
289            phase: b2(0),
290            active: false,
291            ctx: b6(0),
292            k: b5(0),
293            k_mod5: b3(0),
294            k_div5: b3(0),
295            fetching: false,
296            count: b3(0),
297            head: b2(0),
298            ends_count: b3(0),
299            ends_head: b2(0),
300            recirculate: false,
301            ends: [b5(0); CONTEXTS],
302        }
303    }
304}
305
306/// Resetless data of a ring.
307#[derive(Clone, Copy, Debug, PartialEq, Digital)]
308#[doc(hidden)]
309pub struct RingData {
310    /// The active context's digits.
311    digits: [b2; LANE_CHAINS],
312    /// The active context's `pk_nonce`.
313    nonce: [b8; 16],
314    /// The node read in flight, minus its node (which the bank delivers).
315    fetch: RingItem,
316    /// Which node bank the read went to.
317    fetch_bank: bool,
318    /// The skid FIFO: chains that need steps.
319    skid: [RingItem; SKID],
320    /// The end queue: chains whose revealed node is already the end.
321    end_queue: [RingItem; SKID],
322    /// The recirculation register.
323    recirculate: RingItem,
324}
325
326/// One chain lane closed into a ring, with its node, end, digit and nonce RAMs.
327#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
328pub struct VerifyRing<const TABLE_MASK: usize> {
329    /// The chain-step lane (20 cycles with Haraka).
330    lane: ChainLane<TABLE_MASK>,
331    /// Each chain's unsalted `pk_nonce`, travelling beside the lane.
332    nonces_in_lane: [DFF<[b8; 16]>; LANE_LATENCY],
333    /// Revealed nodes: bank 0 holds even `k`, bank 1 odd `k`.
334    nodes: [SyncBRAM<[b8; ELEMENT_BYTES], 10>; NODE_BANKS],
335    /// Chain ends: bank `k mod 5`.
336    ends: [SyncBRAM<[b8; ELEMENT_BYTES], 9>; END_BANKS],
337    /// Contexts whose digits have arrived, in arrival order.
338    queue: SyncBRAM<b6, 6>,
339    /// Digits per context.
340    digits: SyncBRAM<[b2; LANE_CHAINS], 6>,
341    /// `pk_nonce` per context.
342    nonce_ram: SyncBRAM<[b8; 16], 6>,
343    /// Counters and flags.
344    control: DFF<RingControl>,
345    /// Wide resetless registers.
346    data: DFF<RingData>,
347}
348
349impl<const TABLE_MASK: usize> Default for VerifyRing<TABLE_MASK> {
350    /// An idle ring: empty RAMs, zero counters.
351    fn default() -> Self {
352        Self {
353            lane: ChainLane::default(),
354            nonces_in_lane: core::array::from_fn(|_| DFF::resetless()),
355            nodes: core::array::from_fn(|_| SyncBRAM::default()),
356            ends: core::array::from_fn(|_| SyncBRAM::default()),
357            queue: SyncBRAM::default(),
358            digits: SyncBRAM::default(),
359            nonce_ram: SyncBRAM::default(),
360            control: DFF::new(RingControl::default()),
361            data: DFF::resetless(),
362        }
363    }
364}
365
366impl<const TABLE_MASK: usize> SynchronousIO for VerifyRing<TABLE_MASK> {
367    type I = RingInput;
368    type O = RingOutput;
369    type Kernel = verify_ring_kernel<TABLE_MASK>;
370}
371
372/// Packs a ring tag: context (6 bits), chain (7), depth (2), `k mod 5` (3), `k / 5` (3).
373#[kernel]
374pub fn ring_tag_kernel(ctx: b6, chain: b7, depth: b2, k_mod5: b3, k_div5: b3) -> b32 {
375    ctx.resize::<32>()
376        | (chain.resize::<32>() << 6)
377        | (depth.resize::<32>() << 13)
378        | (k_mod5.resize::<32>() << 15)
379        | (k_div5.resize::<32>() << 18)
380}
381
382/// A ring tag with its depth field (bits 13..15) cleared.
383const DEPTH_CLEAR: b32 = b32(0xffff_ffff ^ (0b11 << 13));
384/// An idle 18-byte node (zeros), for default ports.
385const ZERO_NODE: [b8; ELEMENT_BYTES] = [b8(0); ELEMENT_BYTES];
386
387/// One ring's logic, once per clock.
388///
389/// Order of business: start the next queued context, fetch its nodes into
390/// the skid FIFO, feed the lane (recirculating chains first), store chain
391/// ends, count them per context.
392#[allow(clippy::needless_range_loop, clippy::too_many_lines)]
393#[kernel]
394pub fn verify_ring_kernel<const TABLE_MASK: usize>(
395    clock_reset: ClockReset,
396    input: RingInput,
397    q: VerifyRingQ<TABLE_MASK>,
398) -> (RingOutput, VerifyRingD<TABLE_MASK>) {
399    // No reset gating here: every register this logic feeds resets itself,
400    // and keeping the reset out of the logic cones keeps it off the routed
401    // kernel's failing paths (verifier build v1).
402    let resetting = clock_reset.reset.any();
403    let _ = resetting;
404    let mut c = q.control;
405    let mut data = q.data;
406    // Chains of this lane: 23, or 22 for lane 2.
407    let chains: b5 = if input.lane == b2(2) { b5(22) } else { b5(23) };
408
409    // ------------------------------------------------ queue of contexts
410    // A digits event stores the digits and queues the context.
411    if input.digits.valid {
412        c.queue_tail = q.control.queue_tail + b7(1);
413    }
414    let queue_write = RamWrite::<b6, 6> {
415        addr: q.control.queue_tail.resize(),
416        value: input.digits.ctx,
417        enable: input.digits.valid,
418    };
419    let digits_write = RamWrite::<[b2; LANE_CHAINS], 6> {
420        addr: input.digits.ctx,
421        value: input.digits.digits,
422        enable: input.digits.valid,
423    };
424    let nonce_write = RamWrite::<[b8; 16], 6> {
425        addr: input.nonce.ctx,
426        value: input.nonce.value,
427        enable: input.nonce.valid,
428    };
429
430    // ------------------------------------------------ start a context
431    // Phase 1 sees the queued context; phase 2 sees its digits and nonce.
432    let mut queue_read: b6 = q.control.queue_head.resize();
433    let mut context_read: b6 = q.control.ctx;
434    if q.control.phase == b2(1) {
435        context_read = q.queue;
436        c.ctx = q.queue;
437        c.queue_head = q.control.queue_head + b7(1);
438        c.phase = b2(2);
439    } else if q.control.phase == b2(2) {
440        data.digits = q.digits;
441        data.nonce = q.nonce_ram;
442        c.active = true;
443        c.k = b5(0);
444        c.k_mod5 = b3(0);
445        c.k_div5 = b3(0);
446        c.phase = b2(0);
447    } else if !q.control.active && q.control.queue_head != q.control.queue_tail {
448        queue_read = q.control.queue_head.resize();
449        c.phase = b2(1);
450    }
451
452    // ------------------------------------------------ fetch nodes
453    // The read issued last cycle lands now: chains that need steps go to
454    // the skid FIFO, chains already at their end (digit 3) to the end
455    // queue, so they never hold up the lane.
456    let mut count = q.control.count;
457    let mut skid = q.data.skid;
458    let mut ends_count = q.control.ends_count;
459    let mut end_queue = q.data.end_queue;
460    if q.control.fetching {
461        let mut item = q.data.fetch;
462        item.node = if q.data.fetch_bank { q.nodes[1] } else { q.nodes[0] };
463        let landed_depth: b2 = (item.tag >> 13).resize();
464        if landed_depth == b2(3) {
465            let slot: b2 = q.control.ends_head + ends_count.resize::<2>();
466            for s in 0..SKID {
467                if slot == b2(s as u128) {
468                    end_queue[s] = item;
469                }
470            }
471            ends_count = ends_count + b3(1);
472        } else {
473            let slot: b2 = q.control.head + count.resize::<2>();
474            for s in 0..SKID {
475                if slot == b2(s as u128) {
476                    skid[s] = item;
477                }
478            }
479            count = count + b3(1);
480        }
481    }
482    // Issue the next read while both queues have room for it.
483    let in_flight = if q.control.fetching { b4(1) } else { b4(0) };
484    let fetch = q.control.active
485        && q.control.phase == b2(0)
486        && q.control.k < chains
487        && (q.control.count.resize::<4>() + in_flight) < b4(SKID as u128)
488        && (q.control.ends_count.resize::<4>() + in_flight) < b4(SKID as u128);
489    c.fetching = fetch;
490    let node_read: b10 = (q.control.ctx.resize::<10>() << 4) | (q.control.k >> 1).resize::<10>();
491    if fetch {
492        // This chain's digit and number.
493        let mut digit = b2(0);
494        for k in 0..LANE_CHAINS {
495            if q.control.k == b5(k as u128) {
496                digit = q.data.digits[k];
497            }
498        }
499        let k7: b7 = q.control.k.resize();
500        let chain: b7 = input.lane.resize::<7>() + (k7 << 1) + k7;
501        data.fetch = RingItem {
502            node: ZERO_NODE,
503            nonce: q.data.nonce,
504            salted: salt_kernel(q.data.nonce, chain, digit),
505            tag: ring_tag_kernel(q.control.ctx, chain, digit, q.control.k_mod5, q.control.k_div5),
506        };
507        data.fetch_bank = (q.control.k & b5(1)) == b5(1);
508        c.k = q.control.k + b5(1);
509        if q.control.k_mod5 == b3(4) {
510            c.k_mod5 = b3(0);
511            c.k_div5 = q.control.k_div5 + b3(1);
512        } else {
513            c.k_mod5 = q.control.k_mod5 + b3(1);
514        }
515        // The context is fully fetched after its last chain.
516        if q.control.k + b5(1) == chains {
517            c.active = false;
518        }
519    }
520
521    // ------------------------------------------------ lane output
522    let out: ChainStepOutput = q.lane;
523    let out_depth: b2 = (out.tag >> 13).resize();
524    let out_chain: b7 = (out.tag >> 6).resize();
525    // A finished chain: the step just done was from depth 2.
526    let completes = out.valid && out_depth == b2(2);
527    // Not finished: back into the lane next cycle, one depth further.
528    c.recirculate = out.valid && out_depth != b2(2);
529    let next_depth = out_depth + b2(1);
530    let lane_nonce = q.nonces_in_lane[LANE_LAST];
531    data.recirculate = RingItem {
532        node: out.node,
533        nonce: lane_nonce,
534        salted: salt_kernel(lane_nonce, out_chain, next_depth),
535        tag: (out.tag & DEPTH_CLEAR) | (next_depth.resize::<32>() << 13),
536    };
537
538    // ------------------------------------------------ feed the lane
539    let mut head_item = q.data.skid[0];
540    for s in 0..SKID {
541        if q.control.head == b2(s as u128) {
542            head_item = q.data.skid[s];
543        }
544    }
545    let have_head = q.control.count != b3(0);
546    let mut lane_in = ChainStepInput {
547        salted_nonce: q.data.recirculate.salted,
548        secret: q.data.recirculate.node,
549        tag: q.data.recirculate.tag,
550        valid: q.control.recirculate,
551    };
552    let mut lane_nonce_in = q.data.recirculate.nonce;
553    // Recirculating chains first; otherwise the next new chain.
554    if !q.control.recirculate && have_head {
555        lane_in = ChainStepInput {
556            salted_nonce: head_item.salted,
557            secret: head_item.node,
558            tag: head_item.tag,
559            valid: true,
560        };
561        lane_nonce_in = head_item.nonce;
562        c.head = q.control.head + b2(1);
563        count = count - b3(1);
564    }
565    c.count = count;
566    data.skid = skid;
567    // A chain already at its end is stored when the end port is free
568    // (completions have priority).
569    let mut end_item = q.data.end_queue[0];
570    for s in 0..SKID {
571        if q.control.ends_head == b2(s as u128) {
572            end_item = q.data.end_queue[s];
573        }
574    }
575    let skip = q.control.ends_count != b3(0) && !completes;
576    if skip {
577        c.ends_head = q.control.ends_head + b2(1);
578        ends_count = ends_count - b3(1);
579    }
580    c.ends_count = ends_count;
581    data.end_queue = end_queue;
582
583    // ------------------------------------------------ store chain ends
584    let write_tag = if completes { out.tag } else { end_item.tag };
585    let write_node = if completes { out.node } else { end_item.node };
586    let write = completes || skip;
587    let write_ctx: b6 = write_tag.resize();
588    let write_bank: b3 = (write_tag >> 15).resize();
589    let write_addr: b9 = (write_ctx.resize::<9>() << 3) | (write_tag >> 18).resize::<9>();
590    let mut end_ports = [RamIn::<[b8; ELEMENT_BYTES], 9> {
591        read_addr: b9(0),
592        write: RamWrite::<[b8; ELEMENT_BYTES], 9> {
593            addr: write_addr,
594            value: write_node,
595            enable: false,
596        },
597    }; END_BANKS];
598    for b in 0..END_BANKS {
599        end_ports[b].read_addr = input.end_read[b];
600        end_ports[b].write.enable = write && write_bank == b3(b as u128);
601    }
602
603    // ------------------------------------------------ count ends per context
604    let mut ends = q.control.ends;
605    let mut done = [false; CONTEXTS];
606    for x in 0..CONTEXTS {
607        if input.retire.valid && input.retire.ctx == b6(x as u128) {
608            ends[x] = b5(0);
609        } else if write && write_ctx == b6(x as u128) {
610            ends[x] = q.control.ends[x] + b5(1);
611        }
612        done[x] = q.control.ends[x] == chains;
613    }
614    c.ends = ends;
615
616    // ------------------------------------------------ next state
617    let mut nonces_in_lane = q.nonces_in_lane;
618    nonces_in_lane[0] = lane_nonce_in;
619    for s in 1..LANE_LATENCY {
620        nonces_in_lane[s] = q.nonces_in_lane[s - 1];
621    }
622    let d = VerifyRingD::<TABLE_MASK> {
623        lane: lane_in,
624        nonces_in_lane,
625        nodes: [
626            RamIn::<[b8; ELEMENT_BYTES], 10> {
627                read_addr: node_read,
628                write: RamWrite::<[b8; ELEMENT_BYTES], 10> {
629                    addr: input.nodes[0].addr,
630                    value: input.nodes[0].value,
631                    enable: input.nodes[0].enable,
632                },
633            },
634            RamIn::<[b8; ELEMENT_BYTES], 10> {
635                read_addr: node_read,
636                write: RamWrite::<[b8; ELEMENT_BYTES], 10> {
637                    addr: input.nodes[1].addr,
638                    value: input.nodes[1].value,
639                    enable: input.nodes[1].enable,
640                },
641            },
642        ],
643        ends: end_ports,
644        queue: RamIn::<b6, 6> {
645            read_addr: queue_read,
646            write: queue_write,
647        },
648        digits: RamIn::<[b2; LANE_CHAINS], 6> {
649            read_addr: context_read,
650            write: digits_write,
651        },
652        nonce_ram: RamIn::<[b8; 16], 6> {
653            read_addr: context_read,
654            write: nonce_write,
655        },
656        control: c,
657        data,
658    };
659    (
660        RingOutput {
661            ends: q.ends,
662            done,
663            ready: out.ready,
664            stepped: lane_in.valid,
665        },
666        d,
667    )
668}
669
670// ------------------------------------------------------------------ the block
671
672/// Row request from the hasher: commitment block `row` of context `ctx`.
673#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
674pub struct RowRequest {
675    /// Request this cycle.
676    pub valid: bool,
677    /// The context.
678    pub ctx: b6,
679    /// The block number, 0..20.
680    pub row: b5,
681}
682
683/// Inputs of the chain block.
684#[derive(Clone, Copy, Debug, PartialEq, Digital)]
685pub struct ChainsInput {
686    /// Node writes per node bank `c mod 6`.
687    pub nodes: [NodeWrite; 2 * LANES],
688    /// A record's digits.
689    pub digits: DigitsEvent,
690    /// A record's `pk_nonce`.
691    pub nonce: NonceWrite,
692    /// A context leaves the unit.
693    pub retire: Retire,
694    /// A commitment-block request.
695    pub row: RowRequest,
696}
697
698/// Outputs of the chain block.
699#[derive(Clone, Copy, Debug, PartialEq, Digital)]
700pub struct ChainsOutput {
701    /// The block requested [`ROW_LATENCY`] cycles ago.
702    pub row: [b8; 64],
703    /// `row` holds a requested block this cycle.
704    pub row_valid: bool,
705    /// All 68 chain ends of the context are stored.
706    pub done: [bool; CONTEXTS],
707    /// All lanes are loaded.
708    pub ready: bool,
709    /// Per lane: a chain step entered the lane this cycle (activity counter).
710    pub stepped: [bool; LANES],
711}
712
713/// The row pipeline's registers.
714#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
715#[doc(hidden)]
716pub struct RowStage {
717    /// Stage 1 holds a request.
718    pending: bool,
719    /// Its block number.
720    row: b5,
721    /// Stage 2 (the output register) holds a block.
722    out_valid: bool,
723}
724
725/// The three rings, the row assembler and its `pk_nonce` copy.
726#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
727pub struct VerifyChains<const TABLE_MASK: usize> {
728    /// The three lane rings (one module, three instances).
729    rings: rhdl::core::ReplicatedSynchronous<VerifyRing<TABLE_MASK>, LANES>,
730    /// `pk_nonce` per context, for commitment block 0.
731    nonces: SyncBRAM<[b8; 16], 6>,
732    /// Row pipeline flags.
733    stage: DFF<RowStage>,
734    /// The assembled block.
735    out: DFF<[b8; 64]>,
736}
737
738impl<const TABLE_MASK: usize> Default for VerifyChains<TABLE_MASK> {
739    /// Three idle rings and an empty row pipeline.
740    fn default() -> Self {
741        Self {
742            rings: rhdl::core::ReplicatedSynchronous::new(VerifyRing::default()),
743            nonces: SyncBRAM::default(),
744            stage: DFF::new(RowStage::default()),
745            out: DFF::resetless(),
746        }
747    }
748}
749
750impl<const TABLE_MASK: usize> SynchronousIO for VerifyChains<TABLE_MASK> {
751    type I = ChainsInput;
752    type O = ChainsOutput;
753    type Kernel = verify_chains_kernel<TABLE_MASK>;
754}
755
756/// End-bank sources of the row assembler: index `5·lane + (k mod 5)` for the
757/// fifteen end banks, then [`NONCE_SOURCE`] and [`ZERO_SOURCE`].
758const SOURCES: usize = LANES * END_BANKS + 2;
759/// Source index of the context's `pk_nonce` (padded to 18 bytes).
760pub const NONCE_SOURCE: usize = LANES * END_BANKS;
761/// Source index of an all-zero node (bytes past the 1,240-byte message).
762pub const ZERO_SOURCE: usize = LANES * END_BANKS + 1;
763
764/// Where byte `p` of commitment block `j` comes from: `(source, byte)`.
765///
766/// Message byte `m = 64j + p`: `m < 16` is `pk_nonce[m]`; then chain
767/// `c = (m − 16) / 18`, byte `(m − 16) mod 18`, held in end bank
768/// `5·(c mod 3) + (c/3 mod 5)`; past 1,240 bytes, zero.
769pub const ROW_SOURCE: [[(usize, usize); 64]; ROWS] = row_sources();
770/// The source half of [`ROW_SOURCE`] (kernels index plain `usize` tables).
771pub const ROW_SOURCE_BANK: [[usize; 64]; ROWS] = split_sources().0;
772/// The byte half of [`ROW_SOURCE`].
773pub const ROW_SOURCE_BYTE: [[usize; 64]; ROWS] = split_sources().1;
774/// For block `j` and end bank `e`, the `k / 5` of the chain the block needs
775/// from that bank (0 if it needs none).
776pub const ROW_SLOT: [[b3; LANES * END_BANKS]; ROWS] = row_slots();
777
778/// Computes [`ROW_SOURCE`].
779const fn row_sources() -> [[(usize, usize); 64]; ROWS] {
780    let mut table = [[(ZERO_SOURCE, 0); 64]; ROWS];
781    let mut j = 0;
782    while j < ROWS {
783        let mut p = 0;
784        while p < 64 {
785            let m = 64 * j + p;
786            table[j][p] = if m < 16 {
787                (NONCE_SOURCE, m)
788            } else if m < 16 + CHAINS * ELEMENT_BYTES {
789                let chain = (m - 16) / ELEMENT_BYTES;
790                (END_BANKS * (chain % LANES) + (chain / LANES) % END_BANKS, (m - 16) % ELEMENT_BYTES)
791            } else {
792                (ZERO_SOURCE, 0)
793            };
794            p += 1;
795        }
796        j += 1;
797    }
798    table
799}
800
801/// Splits [`ROW_SOURCE`] into its two columns.
802const fn split_sources() -> ([[usize; 64]; ROWS], [[usize; 64]; ROWS]) {
803    let mut banks = [[0; 64]; ROWS];
804    let mut bytes = [[0; 64]; ROWS];
805    let mut j = 0;
806    while j < ROWS {
807        let mut p = 0;
808        while p < 64 {
809            banks[j][p] = ROW_SOURCE[j][p].0;
810            bytes[j][p] = ROW_SOURCE[j][p].1;
811            p += 1;
812        }
813        j += 1;
814    }
815    (banks, bytes)
816}
817
818/// Computes [`ROW_SLOT`], checking that no block needs two chains of one bank.
819const fn row_slots() -> [[b3; LANES * END_BANKS]; ROWS] {
820    let mut table = [[b3(0); LANES * END_BANKS]; ROWS];
821    let mut used = [[false; LANES * END_BANKS]; ROWS];
822    let mut chain = 0;
823    while chain < CHAINS {
824        let first = (16 + chain * ELEMENT_BYTES) / 64;
825        let last = (16 + chain * ELEMENT_BYTES + ELEMENT_BYTES - 1) / 64;
826        let bank = END_BANKS * (chain % LANES) + (chain / LANES) % END_BANKS;
827        let mut j = first;
828        while j <= last {
829            assert!(!used[j][bank], "two chains of one block share an end bank");
830            used[j][bank] = true;
831            table[j][bank] = b3(((chain / LANES) / END_BANKS) as u128);
832            j += 1;
833        }
834        chain += 1;
835    }
836    table
837}
838
839/// The chain block's logic: route writes to the rings, assemble rows.
840#[allow(clippy::needless_range_loop)]
841#[kernel]
842pub fn verify_chains_kernel<const TABLE_MASK: usize>(
843    clock_reset: ClockReset,
844    input: ChainsInput,
845    q: VerifyChainsQ<TABLE_MASK>,
846) -> (ChainsOutput, VerifyChainsD<TABLE_MASK>) {
847    // No reset gating here: every register this logic feeds resets itself,
848    // and keeping the reset out of the logic cones keeps it off the routed
849    // kernel's failing paths (verifier build v1).
850    let resetting = clock_reset.reset.any();
851    let _ = resetting;
852    // One-hot block number of this cycle's request.
853    let mut onehot = [false; ROWS];
854    for j in 0..ROWS {
855        onehot[j] = input.row.row == b5(j as u128);
856    }
857    // End-bank read addresses: ctx·8 + the needed chain's k/5.
858    let mut end_read = [[b9(0); END_BANKS]; LANES];
859    for l in 0..LANES {
860        for b in 0..END_BANKS {
861            let mut slot = b3(0);
862            for j in 0..ROWS {
863                if onehot[j] {
864                    slot = slot | ROW_SLOT[j][END_BANKS * l + b];
865                }
866            }
867            end_read[l][b] = (input.row.ctx.resize::<9>() << 3) | slot.resize::<9>();
868        }
869    }
870    // This lane's digits: chain l + 3k.
871    let mut lane_digits = [[b2(0); LANE_CHAINS]; LANES];
872    for l in 0..LANES {
873        for k in 0..LAST_LANE_CHAIN {
874            lane_digits[l][k] = input.digits.digits[l + LANES * k];
875        }
876    }
877    lane_digits[0][LAST_LANE_CHAIN] = input.digits.digits[CHAIN_66];
878    lane_digits[1][LAST_LANE_CHAIN] = input.digits.digits[CHAIN_67];
879    // Ring inputs.
880    let mut rings = [RingInput {
881        lane: b2(0),
882        nodes: [NodeWrite::default(); NODE_BANKS],
883        digits: LaneDigits::default(),
884        nonce: input.nonce,
885        retire: input.retire,
886        end_read: [b9(0); END_BANKS],
887    }; LANES];
888    for l in 0..LANES {
889        rings[l].lane = b2(l as u128);
890        rings[l].nodes = [input.nodes[l], input.nodes[l + LANES]];
891        rings[l].digits = LaneDigits {
892            valid: input.digits.valid,
893            ctx: input.digits.ctx,
894            digits: lane_digits[l],
895        };
896        rings[l].end_read = end_read[l];
897    }
898
899    // Stage 1: the banks answer; assemble the block from the fixed map.
900    let r0 = q.rings[0].ends;
901    let r1 = q.rings[1].ends;
902    let r2 = q.rings[2].ends;
903    let mut nonce18 = [b8(0); ELEMENT_BYTES];
904    for b in 0..16 {
905        nonce18[b] = q.nonces[b];
906    }
907    let sources: [[b8; ELEMENT_BYTES]; SOURCES] = [
908        r0[0], r0[1], r0[2], r0[3], r0[4], r1[0], r1[1], r1[2], r1[3], r1[4], r2[0], r2[1], r2[2], r2[3], r2[4],
909        nonce18, ZERO_NODE,
910    ];
911    let mut block_onehot = [false; ROWS];
912    for j in 0..ROWS {
913        block_onehot[j] = q.stage.row == b5(j as u128);
914    }
915    let mut row = [b8(0); 64];
916    for p in 0..64 {
917        let mut value = b8(0);
918        for j in 0..ROWS {
919            if block_onehot[j] {
920                value = value | sources[ROW_SOURCE_BANK[j][p]][ROW_SOURCE_BYTE[j][p]];
921            }
922        }
923        row[p] = value;
924    }
925    let mut done = [false; CONTEXTS];
926    for x in 0..CONTEXTS {
927        done[x] = q.rings[0].done[x] && q.rings[1].done[x] && q.rings[2].done[x];
928    }
929    let d = VerifyChainsD::<TABLE_MASK> {
930        rings,
931        nonces: RamIn::<[b8; 16], 6> {
932            read_addr: input.row.ctx,
933            write: RamWrite::<[b8; 16], 6> {
934                addr: input.nonce.ctx,
935                value: input.nonce.value,
936                enable: input.nonce.valid,
937            },
938        },
939        stage: RowStage {
940            pending: input.row.valid,
941            row: input.row.row,
942            out_valid: q.stage.pending,
943        },
944        out: row,
945    };
946    (
947        ChainsOutput {
948            row: q.out,
949            row_valid: q.stage.out_valid,
950            done,
951            ready: q.rings[0].ready && q.rings[1].ready && q.rings[2].ready,
952            stepped: [q.rings[0].stepped, q.rings[1].stepped, q.rings[2].stepped],
953        },
954        d,
955    )
956}
957
958/// Software check of the bank maps; the cycle test lives in `tests/`.
959#[cfg(test)]
960mod tests {
961    use super::*;
962
963    /// Every message byte appears exactly once in the row map, in order.
964    #[test]
965    fn row_map_covers_the_commitment_message() {
966        let mut seen = 0;
967        for j in 0..ROWS {
968            for p in 0..64 {
969                let m = 64 * j + p;
970                let (source, byte) = ROW_SOURCE[j][p];
971                if m < 16 {
972                    assert_eq!((source, byte), (NONCE_SOURCE, m));
973                    seen += 1;
974                } else if m < 1240 {
975                    let chain = (m - 16) / 18;
976                    assert_eq!(source, 5 * (chain % 3) + (chain / 3) % 5);
977                    assert_eq!(byte, (m - 16) % 18);
978                    assert_eq!(ROW_SLOT[j][source], b3(((chain / 3) / 5) as u128));
979                    seen += 1;
980                } else {
981                    assert_eq!(source, ZERO_SOURCE);
982                }
983            }
984        }
985        assert_eq!(seen, 1240);
986    }
987}
rhdl_dsig_scalable_core/verify/chains.rs

rhdl_dsig_scalable_core/verify/
chains.rs
