Expand description
Fixed-base lookup, recoding, and signed multi-comb multiplication.
§Fixed-Base Scalar Multiplication
The current backend computes [s]B with a signed 4x8x8 multi-comb table. It
uses one 16-context scheduler, four field multipliers, two modular add/subtract
lanes, and a constant-pattern table scanner. The same engine computes [a]B
during key loading and [r]B for each signature.
§multicomb_mul_stream
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/multicomb_mul_stream.sv.
§Parameters
| Parameter | Default | Active value | Meaning |
|---|---|---|---|
TAG_BITS | 16 | CONTEXT_BITS+1 at the signer | Width of opaque result metadata; the extra bit distinguishes a key point |
CONTEXTS | 8 | 16 | Number of scalar multiplications retained and interleaved |
CONTEXT_BITS | 3 | 4 | Bits used to index CONTEXTS; active settings require 2^CONTEXT_BITS = CONTEXTS |
FIELD_LATENCY | 17 | 17 | Tag-pipeline length expected from radix51_field_mul_pipe |
Local constant SCALAR_L is the Ed25519 group order. The engine turns an even
input scalar into an odd representative by adding l, then forms
signed_scalar_in = {1, adjusted_scalar[255:1]} for the signed comb
decomposition. This transformation preserves the represented multiple under
the table construction.
§Ports
| Port | Direction | Meaning |
|---|---|---|
clk, rst | input | Clock and synchronous reset |
valid_in | input | Qualifies scalar_in and tag_in |
ready_in | output | At least one context is free and the registered allocation slot is empty |
scalar_in | input, 256 bits | Canonical or bounded scalar to multiply by the Ed25519 basepoint |
tag_in | input, TAG_BITS | Metadata returned unchanged |
valid_out | output | One-cycle projective-point completion pulse |
tag_out | output, TAG_BITS | Tag associated with the completed point |
x_out, y_out, z_out, t_out | output, 255 bits each | Extended/projective Edwards coordinates of [scalar_in]B |
§Per-context state
Each context stores the signed scalar, caller tag, comb_round, comb_block,
the current (X,Y,Z,T) point, cached Y+X and Y-X, selected Projective Niels
coordinates, formula temporaries, and four completed values. Arithmetic workers
return only a context index; that index selects the retained state to update.
§State constants
| State | Purpose |
|---|---|
ST_FREE | Context may be allocated |
ST_LOOKUP | Context is eligible for a table request |
ST_LOOKUP_WAIT | Constant-scan lookup is in flight |
ST_ISSUE_A | First formula product phase is eligible |
ST_WAIT_A | First product phase is in flight |
ST_BUILD_PENDING | First pair of add/sub formula values must be built |
ST_BUILD_WAIT | First add/sub task is in flight |
ST_TWICE_PENDING | A doubling path requires a dedicated modular doubling |
ST_TWICE_WAIT | The doubling add/sub task is in flight |
ST_BUILD2_PENDING | Second pair of formula values must be built |
ST_BUILD2_WAIT | Second add/sub task is in flight |
ST_ISSUE_B | Four final coordinate products are eligible |
ST_WAIT_B | Final product phase is in flight |
ST_POST_PENDING | Recompute cached Y+X and Y-X after coordinate update |
ST_POST_WAIT | Post-update add/sub task is in flight |
Builder task codes select the two-lane add/sub operands:
| Task | Function |
|---|---|
TASK_BUILD1 | Form the first sum and difference after product phase A |
TASK_TWICE | Form 2*C or 2*Z needed by a doubling formula |
TASK_BUILD2 | Form the four completed-coordinate factors |
TASK_POST | Recompute current point Y+X and Y-X |
§Comb schedule
For each of eight comb_round values, blocks 0 through 3 select and mixed-add
four table points. Between rounds, synthetic block 4 performs one point
doubling. There are therefore 32 constant scans/mixed additions and seven
doublings per scalar.
The lookup bit index is
block*64 + tooth*8 + (7-round) for teeth 0 through 7. The high bit becomes
the sign and the lower seven bits, conditionally complemented, form the table
candidate. Candidate bits do not become ROM addresses.
§Arithmetic issue
Product phase A launches four field multipliers together. A mixed addition
computes (Y+X)*Niels(Y+X), (Y-X)*Niels(Y-X), T*Niels(XY2D), and 2*Z.
A doubling computes X^2, Y^2, Z^2, and (Y+X)^2. Product phase B launches
the four coordinate products together. The fourth mixed-add multiplier is used
for 2Z, removing a separate add/sub operation on the common path.
The two radix17_field_addsub_pipe instances execute builder tasks. Four
metadata slots named task_valid_pipe, task_kind_pipe, and
task_context_pipe retain task ownership while the add/sub lanes run; actual
state updates are gated by both lane-valid outputs. The multiplier return tags
have FIELD_LATENCY=17 slots. Registered builder and multiplier inputs prevent
wide context-selection logic from feeding arithmetic in the same cycle.
Round-robin pointers advance allocation, lookup, multiplier, and builder selection. Some selectors inspect only the current and next context, relying on 16 interleaved contexts to keep arithmetic occupied without a 16-way global priority tree.
Current matching-source OOC synthesis attributes 82,095 LUTs, 84,605 registers, 352 RAMB36s, and 2,116 DSP48E2s to this direct hierarchy. Its DSPs are four 523-DSP field multipliers plus two 12-DSP add/subtract lanes. The 352 RAMB36s are the replicated constant-scan table, not message storage.
§multicomb_lookup_rom
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/multicomb_lookup_rom.sv.
This module scans all 128 candidates in four groups of 32 candidates while reading eight public groups per cycle. Selection occurs after the reads.
§Parameter
| Parameter | Default | Meaning |
|---|---|---|
TAG_BITS | 8 | Width of metadata retained for the four-cycle scan |
Its local constant P is the field modulus, used to negate xy2d for a
negative table digit.
§Ports
| Port | Direction | Meaning |
|---|---|---|
clk, rst | input | Clock and synchronous control reset |
valid_in | input | Qualifies one lookup request |
ready_in | output | High when no scan is active |
block | input, 2 bits | Public multi-comb block, selecting one 32-group region in each file |
candidate | input, 7 bits | Secret absolute candidate encoded as group bits 6:2 and bank bits 1:0 |
sign | input | Negates the selected Projective Niels point after the scan |
tag_in | input, TAG_BITS | Metadata returned with the point |
valid_out | output | One-cycle completion pulse after every group has been examined |
tag_out | output, TAG_BITS | Delayed request tag |
y_plus_x, y_minus_x, xy2d | output, 255 bits each | Selected signed Projective Niels coordinates |
read_address contains {block, group} only. The four low candidate bits select
one of four returned physical banks, while candidate_group is compared with
every group observed during the scan. A negative point swaps y_plus_x and
y_minus_x and replaces nonzero xy2d with P-xy2d.
§Memory images
The module names comb_scan_bank00.mem, comb_scan_bank01.mem,
comb_scan_bank02.mem, and comb_scan_bank03.mem. They live in
assets/multicomb_t8_n4_s8. Packaging scripts add them as sources; the OOC
script changes to that directory before reading RTL so relative simulation and
synthesis initialization resolve consistently.
§multicomb_scan_bank
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/multicomb_lookup_rom.sv.
This leaf provides two independent read ports over one 128x765-bit logical ROM. It duplicates a single-port memory rather than inferring one secret-indexed multiport structure.
§Parameter
MEMORY_FILE defaults to "none" and names the hexadecimal initialization
file. Each instantiation overrides it with an active comb-scan image.
§Ports
clk clocks both reads. enable qualifies them. address_a and address_b
are independent 7-bit public addresses; data_a and data_b are corresponding
765-bit {xy2d,y_minus_x,y_plus_x} records. rst is present for interface
uniformity but is not connected to XPM reset in synthesis and does not clear the
simulation array.
Under SYNTHESIS, two AMD xpm_memory_sprom instances use block memory,
one-cycle read latency, MEMORY_SIZE=97920, and READ_DATA_WIDTH_A=765.
Outside synthesis, one initialized register array supplies two registered reads.
§multicomb_scan_bank8
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/multicomb_lookup_rom.sv.
This structural adapter has the same MEMORY_FILE parameter. Shared ports are
clk, rst, and enable; inputs address0 through address7 and outputs
data0 through data7 form eight logical read ports. It instantiates four
multicomb_scan_bank copies for port pairs 0/1, 2/3, 4/5, and 6/7.
§Legacy radix16_recode_stream
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/radix16_recode_stream.sv.
§Parameter and ports
TAG_BITS defaults to 16 and controls tag_in/tag_out. Other ports are
clk, rst, valid_in, ready_in, 256-bit scalar, valid_out, and 512-bit
digits_out.
The module consumes one 4-bit nibble per cycle for 64 cycles, propagates a
carry, and writes each balanced signed digit into one 8-bit slot. For all but
the top digit it computes next_carry=(value+8)>>4 and
balanced=value-16*next_carry, giving the usual [-8,7] range. It is not
instantiated by the active multi-comb engine.
§Legacy basepoint_lookup_rom
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/basepoint_lookup_rom.sv.
This parameterless radix-16 lookup reads the same public five-bit window from
all eight magnitude banks and applies secret digit selection only after the
registered reads. Inputs are clk, rst, valid_in, window, and signed
8-bit digit; outputs are valid_out, y_plus_x, y_minus_x, and xy2d.
Local constants P and IDENTITY support sign negation and zero-digit
selection. The eight ROMs are initialized from radix17_bank0.mem through
radix17_bank7.mem. Magnitudes 1 through 8 select a bank; every other magnitude
selects the identity. This module is not part of the active cached hierarchy.
§Legacy fixed_base_mul_stream
Source: crates/rhdl_ed25519_fast_fixed_base/rtl/fixed_base_mul_stream.sv.
This predecessor expects 64 already balanced radix-16 digits and shares one field multiplier among multiple contexts.
§Parameters
| Parameter | Default | Meaning |
|---|---|---|
TAG_BITS | 16 | Request metadata width |
CONTEXTS | 16 | Number of retained point contexts |
CONTEXT_BITS | 4 | Context index width |
FIELD_LATENCY | 16 | Return-tag pipeline length for the field multiplier |
Ports are clk, rst, valid_in, ready_in, 512-bit digits_in, tag_in,
valid_out, tag_out, and projective outputs x_out, y_out, z_out,
t_out.
Its local states are ST_FREE, ST_LOOKUP, ST_ISSUE_A, ST_WAIT_A,
ST_ISSUE_B, and ST_WAIT_B; FIELD_P is the field modulus. Point indices
0-31 process odd radix-16 digits, indices 32-35 perform four doublings, and
indices 36-67 process even digits.
§Helper functions
| Function | Inputs | Purpose |
|---|---|---|
field_reduce | Bounded 257-bit value | Fold bits above 254 by 19 twice, then conditionally subtract FIELD_P |
field_add | Packed field values a, b | Add and call field_reduce |
field_sub | Packed field values a, b | Add a fixed 2*FIELD_P bias, subtract b, and call field_reduce |
These functions are combinational copies at use sites. The predecessor is not used in current resource or throughput figures.