Module slice_merkle 

A slice’s share of the batch Merkle tree: one subtree per batch.

The problem

DSig pays for one expensive Ed25519 signature per batch of 128 one-time keys, not per key. To make that one signature cover 128 keys, the keys’ public commitments (pk_hash, one 32-byte hash per key) become the leaves of a Merkle tree: a binary tree where every parent is the hash of its two children. Ed25519 signs only the root. A signature then proves that its key belongs to the batch by carrying the 7 siblings on the path from its leaf to the root (the inclusion proof); a verifier rehashes up the path and compares with the signed root.

The 128 keys of a batch are not made in one place. Each slice makes its own share, so each slice can build the part of the tree that sits above its own keys, without talking to any other slice. Only the last few levels need everyone’s results; they are built by the shared cert unit.

  one batch, 8-slice build (128 keys, 7 levels)

  level 7                          batch root ──▶ Ed25519 (cert unit)
  levels 5..7          ┌──── Merkle top: 4 + 2 + 1 hashes (cert unit) ────┐
  level 4             r0     r1     r2     r3     r4     r5     r6     r7   subtree roots
  levels 1..4        [s0]   [s1]   [s2]   [s3]   [s4]   [s5]   [s6]   [s7]  15 parents each
  level 0 (leaves)   0..15 16..31 32..47  ...                        112..127  keys
                     └─ this module, one copy per slice ─┘

What this module does

A batch of 128 keys has a 7-level Merkle tree. Slice s owns keys K·s .. K·s + K with K = KEYS_PER_SLICE (16, 32 or 64 for 8, 4 or 2 slices), which form exactly one subtree of height SUBTREE_LEVELS. For the 8-slice build:

  level 4                         root ──▶ shared Merkle top (3 more levels)
  level 3               ┌─────────┴─────────┐
  level 2          ┌────┴────┐         ┌────┴────┐
  level 1        ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐
  level 0 (leaf) j=0 1     2   3  …                 15     pk_hash of each key

With 4 slices the subtree is one level taller and the certificate unit’s top one level shorter; the inclusion proof is always 7 siblings.

SubtreeBuilder receives each finished key’s pk_hash from the slice_factory, stores it, and as soon as both children of a node exist it queues that parent. Queued parents go into the factory’s Merkle slot one at a time (one per 68-cycle period, enough for K − 1 parents per K keys). A finished top-level node leaves as the slice’s subtree root.

Why there is no BLAKE3 core here

A parent is one BLAKE3 compression of left ‖ right. The factory’s timetable already reserves one free “Merkle slot” on its BLAKE3 lane every 68-cycle key period. A subtree of K keys needs only K − 1 parents per K keys, so that one slot is enough, and the slice saves a whole hash core. This module only decides what to hash and stores the results.

When a parent is ready

Keys finish in order j = 0, 1, 2, …. When an odd leaf j arrives, its even sibling j − 1 is already stored, so parent j / 2 at level 1 can be queued at once. The same rule repeats one level up: a parent result with an odd index means its even sibling finished earlier (jobs are served in order), so the grandparent is queued. When the level-SUBTREE_LEVELS result arrives, it is the subtree root.

  leaf j=0 ─ store
  leaf j=1 ─ store, queue (level 1, index 0)
  leaf j=2 ─ store
  leaf j=3 ─ store, queue (level 1, index 1)
  result (1,0) ─ store
  result (1,1) ─ store, queue (level 2, index 0)   … and so on up to the root

For each queued job the builder reads the two children from its node RAM (one cycle each), then offers left ‖ right to the factory until the factory takes it. The 16-bit request tag carries (ring, level, index) so the result can be stored where it belongs when it comes back.

Storage

Every node is kept, because a signature’s inclusion proof needs one sibling per level. The signer reads siblings through the separate proof port. Nodes live in a ring of NODE_RING_BATCHES batches, the same number of batches the key cache holds. The slice’s admission limit keeps one whole batch of slack, so a batch’s nodes are never overwritten while one of its keys can still sign (see slice).

Node address = ring · 2K + NODE_BASE[level] + index, with NODE_BASE[level] = 2K − 2K / 2^level (for 16 keys: 0, 16, 24, 28, 30). All 2K − 1 nodes of a batch fit in its 2K slots, and ring entries × slots is always 1,024, a 10-bit address.

  one ring entry, 16 keys (32 slots of 32 bytes)
  slot:  0 ............ 15 | 16 ...... 23 | 24 .. 27 | 28 29 | 30 | 31
         level 0 (leaves)  | level 1      | level 2  | lvl 3 | root | spare

The node RAM exists twice (SubtreeBuilder’s job_nodes and proof_nodes) with identical writes. A synchronous RAM has one read port; the builder and the signer read at unrelated times, so each gets its own copy instead of arbitrating for one port.

Structs

Job

One queued parent: ring entry, level (1..=SUBTREE_LEVELS) and index within the level.

SubtreeBuilder

The subtree builder.

SubtreeControl

Resettable control.

SubtreeData

Resetless datapath: the two children of the job being offered.

SubtreeInput

Inputs from the factory and the signer.

SubtreeOutput

Outputs to the factory, the shared Merkle top and the signer.

SubtreeRoot

A finished subtree root.

Constants

JOB_QUEUE

Pending-parent queue depth.

NODES_PER_ENTRY

Node slots per ring entry: 2·KEYS_PER_SLICE (2K − 1 nodes, one spare).

NODE_BASE

First node slot of each level inside a ring entry: 2K − 2K / 2^level. For 16 keys: 0, 16, 24, 28, 30.

NODE_RING_BATCHES

Batches whose subtree nodes are kept (ring size): one per cache batch.

RING_MASK

Mask turning a batch number into its ring entry.

ROOT_LEVEL

Level of the subtree root (log2 KEYS_PER_SLICE).

Functions

job_tag_kernel

Pack a job into the 16-bit slot tag and back.

node_address_kernel

Node address of (level, index) in ring entry ring: ring · NODES_PER_ENTRY + NODE_BASE[level] + index.

pair_block_kernel

Words of left ‖ right, little-endian.

ring_of_kernel

The ring entry holding batch batch’s nodes.

subtree_kernel

The builder’s wiring.

Type Aliases

NodeSlot

A node slot within one ring entry (NODE_SLOT_BITS wide).