Module chain_step 

A Haraka lane specialised to exactly one DSig chain step.

The problem

A DSig key is 68 W-OTS+ chains (w = 4). Making a key walks every chain from its secret node three steps to its public end, and every step is one Haraka-512 hash of a 64-byte chain block. That is 204 chain steps per signature. The signer wants one chain step per clock per lane at 205 MHz, so the chain-step lane is replicated many times, and its size decides how many signers fit on the chip.

Most of a lane’s area is AES S-boxes. A plain Haraka-512 has 640 of them (10 AES rounds × 64 bytes). This module asks: how many of those 640 does a DSig chain step really need? The answer is 494, and this file is the hardware that uses only those.

The reasoning, step by step

1. The chain block is mostly fixed. Only the 16-byte salted nonce and the 18-byte node change; bytes 34..64 are always zero.
2. An S-box whose input is a known constant has a known constant output. It needs no hardware at all.
3. Haraka’s AES lanes do not talk to each other until the first word mix, after the second AES round. So the constants survive for two rounds.
4. DSig keeps only 18 of the 32 digest bytes. Any S-box that cannot reach those 18 bytes is wasted work.

The decision: compute, at compile time, which bytes are constant (going forwards) and which bytes are needed (going backwards), then build a pipeline in which the constant bytes are literal values. Synthesis does the rest: it deletes logic that drives nothing and folds logic whose inputs are constants.

How the constants fold away

  live = varies per chain step     · = compile-time constant

  AES lane:          0                 1                 2               3
  block bytes:     0..16            16..32            32..48          48..64
  round 0 in:   live×16           live×16        live×2 (32,33)    ·×16
                (salted nonce)    (node 0..16)   ·×14              (all zero)
                   │                 │                 │               │
  rounds 0-1:   all S-boxes       all S-boxes      only the S-boxes   every S-box
                live              live             fed by bytes 32,   constant:
                                                   33 and what they   32 boxes fold
                                                   spread to
                   └─────────────────┴─── word MIX after round 1 ──┴───────────────┘
  round 2:      the mix has moved lane 3's still-constant words into other
                lanes; S-boxes on those 16 bytes still fold
  rounds 3-6:   every byte varies and every byte is needed
  rounds 7-8:   working backwards from the output, one lane's worth of
                bytes (16) can no longer reach the 18 kept bytes
  round 9:      only the columns that feed the 18 kept bytes matter:
                5 of 16 columns × 4 bytes = 20 of 64 S-boxes
                   │
  output:       18 bytes = mid_haraka512(block)

  live S-boxes per AES round (constant ones folded, unobserved ones deleted):

    round:   0    1    2    3    4    5    6    7    8    9    total
    live:   34   40   48   64   64   64   64   48   48   20  =  494   (of 640)

The per-round detail is not written down by hand in the code: LIVE_SBOX records it, live_sbox_evaluations counts it, and a test pins the total of 494. The per-round row above is that same analysis re-run by hand for this explanation; only the total is checked by a test.

Why a second Haraka pipeline?

Haraka512Pipeline hashes any 64-byte block and returns the full 32-byte digest. DSig never asks for that. Every chain step hashes a block with a fixed shape (dsig_chain_block) and keeps only 18 bytes of the answer:

 byte  0      16        34                                   63
       ├──────┼─────────┼────────────────────────────────────┤
 block │nonce │ secret  │        thirty zero bytes           │
       └──────┴─────────┴────────────────────────────────────┘
        AES lane 0 = bytes 0..16      AES lane 2 = bytes 32..48
        AES lane 1 = bytes 16..32     AES lane 3 = bytes 48..64 (all zero)

Haraka runs four independent AES lanes and only mixes them after every second AES round. So for the first two rounds AES lane 3 sees nothing but zeros: its 32 S-box evaluations always produce the same bytes. Lane 2 only has two live bytes, so most of its first-round S-boxes are also constant. At the far end, the 18 kept output bytes depend on only five of the sixteen 32-bit columns, so most of the final round is never observed.

This module turns those facts into hardware savings:

1. A const fn (KNOWN) symbolically runs the pipeline over “known constant” / “live” bytes and records, for every stage, which state bytes are compile-time constants and what their values are.
2. The RHDL kernel pins those bytes to literals before each stage. Synthesis then folds their S-boxes into constants and deletes the registers that would have carried them.
3. The lane outputs only the 18 DSig bytes, so synthesis also deletes every S-box whose result can never reach an output.

Counted by live_sbox_evaluations, one chain step needs 494 S-box evaluations instead of Haraka’s 640, about 23% less of the dominant area. The count is a structural planning number. Only an implemented-design report measures LUTs (see the validation ladder in the crate documentation).

Where this sits

 ChainEngine ── three steps in series (depth 0 → 1 → 2) ──▶ four cache nodes
      │
      └── each step is one ChainStepLane: 20 registered stages, II = 1

“ChainEngine” is SliceChainEngine in crate::slice_chain. “II = 1” (initiation interval of one) means a new token can enter every clock. Which chain hash is compiled in, and so whether this lane is used at all, is decided in crate::chain_lane.

The neighbours this file leans on:

Module	What it gives this file
crate::haraka	round keys, word mix, truncation, mix_key512_kernel, the dsig_chain oracle
crate::aes_table	the S-box stages (SboxStages), the UltraRAM loader, the T-table ROMs
crate::sbox_placement	which of the 494 live S-boxes (LIVE_SBOX) go to UltraRAM or block RAM

Reading order

1. KnownBytes, KNOWN: the forward constant analysis.
2. live_sbox_evaluations, LIVE_SBOX: the backward “is it needed” analysis.
3. ChainStepInput, ChainStepOutput: the lane’s ports.
4. ChainStepLane, chain_step_kernel: the all-S-box lane.
5. TableChainStepLane, table_chain_step_kernel: the same lane with some rounds done by T-table lookups instead.

The lane has the same timing contract as the general pipeline: it accepts a token every cycle, has no backpressure, and returns it after exactly CHAIN_STEP_LATENCY registered transfers with its tag unchanged. Reset clears only the valid bits, so all in-flight tokens are discarded. Compare it bit-for-bit with dsig_chain using tests/chain_step.rs.

Structs

ChainStepInput

One chain-step request; an asserted valid is always accepted.

ChainStepLane

Twenty-stage, II = 1 DSig chain step with compile-time constant folding.

ChainStepOutput

The next chain node; all fields except valid are meaningless when invalid.

KnownBytes

Compile-time knowledge about the state entering one stage.

TableChainStepLane

ChainStepLane with selected AES rounds moved from LUTs into T-table ROMs.

Constants

CHAIN_STEP_LATENCY

Registered stages per chain step (two per AES round, as in Haraka).

KNOWN

KNOWN[s] describes the state entering stage s; KNOWN[20] is the final state before feed-forward. Index 0 is the DSig chain block itself.

KNOWN_MASK

RHDL-typed copy of the masks in KNOWN, indexed [stage][byte].

KNOWN_VALUE

RHDL-typed copy of the constant values in KNOWN.

LIVE_SBOX

Per-position live S-boxes (computed by the private live_sboxes).

ROMS_PER_TABLE_ROUND

Dual-port ROMs per table round: 64 S-boxes, two per ROM.

STEP_OUTPUT_BYTES

DSig keeps this many leading bytes of the standard 32-byte digest.

TABLE_ROUND_FIRST

AES rounds that may use block-RAM T-tables: every byte is live and used.

TABLE_ROUND_SLOTS

Number of table-capable rounds (rounds 3 through 8).

ZERO_TAIL_START

First block byte that is always zero in a DSig chain block.

Functions

chain_step_block_kernel

Builds the zero-tailed DSig chain block from its two live fields.

chain_step_digest_kernel

Final feed-forward: the 18 kept digest bytes of a finished state.

chain_step_feed_kernel

The 18 input bytes that the feed-forward XORs back into the digest.

chain_step_kernel

Stage wiring for ChainStepLane.

live_sbox_evaluations

Count the S-box evaluations that are neither constant nor unobserved.

pin_known_kernel

Replace the bytes mask marks as compile-time constants by value.

table_addresses_kernel

Present ShiftRows-ordered state bytes to a round’s 32 dual-port ROMs.

table_chain_step_kernel

Stage wiring for TableChainStepLane.

table_combine_kernel

Combine one round’s 64 table words: rotated XOR per column plus the key.

valid_table_mask

Whether mask is a legal TableChainStepLane table selection.