rhdl_ed25519_scalable_core/

lib.rs

//! An all-RHDL Ed25519 signer and known-key verifier whose throughput scales
//! with its LUT and DSP budget.
//!
//! # Building for Wolverine's U280
//!
//! Generate the card bundle from Rust/RHDL, then package and link it with Vitis.
//! The `card` feature enables the exporter; `export_scalable` alone exports a
//! core rather than the complete card kernel.
//!
//! Run commands from the workspace root. Before compilation or RTL generation,
//! record ownership in `PROJECT_COORDINATION.md` and
//! `/home/sahasta/Development/FPGA_COORDINATION.md`, and use the applicable
//! nonblocking `local-heavy.lock`; `crates/ed25519/tools/bounded.sh` wraps local
//! Cargo commands with that lock and resource limits. Reserve Wolverine builds
//! in both ledgers too, then use `crates/dsig/tools/with-u280-lock.sh` to hold
//! `u280.lock`. Do not bypass a busy lock.
//!
//! Inside the reserved, locked build session:
//!
//! ```sh
//! export CARGO_TARGET_DIR="$PWD/target"
//! cargo build --locked --profile sim -p rhdl_ed25519_scalable_core \
//!   --features card --bin export_card
//! "$CARGO_TARGET_DIR/sim/export_card" /absolute/path/new-bundle
//! ```
//!
//! Select `ED25519_SCALABLE_PROFILE` before compilation if changing the signer
//! configuration, and retain the resulting profile in `BUNDLE.txt`.
//!
//! The card build uses Vivado/Vitis 2023.2, the installed U280 `.xpfm`
//! platform and XRT. Replace the absolute example paths below with real paths
//! on Wolverine; the bundle must be copied there with its `BUNDLE.txt` intact,
//! and the output directory must be new. Keep the repository checkout available
//! on Wolverine because the scripts use its Tcl and host sources. Building an
//! image does not program the card or establish measured performance.
//!
//! The Ed25519 link script requires at least 40 GiB free disk. After recording
//! Wolverine ownership in both ledgers, run there:
//!
//! ```sh
//! export HASHSIGS_U280_COORDINATION_ACK=both-ledgers-recorded
//! crates/dsig/tools/with-u280-lock.sh \
//!   "$PWD/crates/ed25519/fpga/u280/card/wolverine-card.sh" build \
//!   /absolute/path/new-bundle /absolute/path/new-build-output \
//!   /absolute/path/U280-platform.xpfm \
//!   /home/Xilinx/Vitis/2023.2/settings64.sh
//! ```
//!
//! This produces `ed25519_card.xclbin`, `xclbin.sha256` and `STEPS.txt`.
//! The script packages and links only; review routed timing/utilization and
//! complete the host verification flow before claiming hardware success or a
//! rate. See `docs/ed25519-card-evidence-journey.md` in the repository for the
//! card evidence requirements. Card programming is a separate operation.
//!
//! **In numbers.** Each row below is one build. LUT, DSP and WNS come from
//! Vivado 2023.2 out of context, routed at 4.878 ns (205 MHz). Rates come
//! from native simulation, where every signature equals `ed25519-dalek`.
//!
//! | Build | Rate at 205 MHz | Cycles/op | CLB LUT | DSP | WNS (ns) |
//! |---|---:|---:|---:|---:|---:|
//! | small signer [`Ed25519SignCoreSmall`] (1/1/1/0) | 229k sign/s | 895 | 29,055 | 248 | +0.306 |
//! | signer 8/0/2/1 (the 100 % plan of 2026-10-17) | 4.41M sign/s | 46.46 | 148,691 | 2,071 | +0.218 |
//! | signer 12/0/3/1 (planned for 200 %) | 6.42M sign/s | 31.95 (before the timing fixes) | 254,817 | 2,994 | **+0.050** |
//! | known-key verifier 6/0/1/1 | 1.52M verify/s | 134.81 | 150,200 | 1,823 | +0.043 |
//! | known-key verifier 1/1/1/1 (DSig's certificate misses) | 0.279M verify/s, 257 µs alone | 735 | 82,184 | 698 | +0.094 |
//! | signer 15/11/3/1 (largest simulated) | 7.76M sign/s | 26.43 | ~264k (synthesis only) | 3,669 | not routed |
//!
//! The 0 in a profile means the core hashes on the shared SHA-512 line.
//! [Chapter 10](#chapter-10-meeting-205-mhz) tells how these builds met
//! timing. `measure/results.tsv` and `measure/native-results.tsv` in the
//! repository hold every number.
//!
//! Verification is [`KnownKeyVerifyCore`]: strict Ed25519 verification for
//! up to eight public keys loaded in advance, equal to `ed25519-dalek`'s
//! `verify_strict` on every case we test.
//!
//! **The story in one breath.** A signature is about 391 multiplications of
//! 255-bit numbers. So we built a multiplier that starts one every clock, gave
//! it 32 signatures to take turns on so it never waits, and wrote the
//! algorithms as Rust programs that compile into the machine. Then we cut the
//! multiplications per signature, kept more signatures in flight, and put one
//! register at a time into the paths that missed 205 MHz. Every step was
//! measured before we believed it, and each chapter below is one of those
//! steps. The last chapter is the one you can write.
//!
//! This page tells the story of how the design came to be, one problem at a
//! time: what we were trying to do, what stood in the way, how we reasoned
//! about it, and what we built. Each chapter ends in the module that holds
//! the details. Read it in order once; afterwards the
//! [validation](#chapter-11-proving-it) table and the
//! [open problems](#epilogue-your-turn) are the parts you will come back to.
//!
//! # Contents
//!
//! 1. [The question: what does a signature cost?](#chapter-1-the-question-what-does-a-signature-cost)
//! 2. [A multiplier made of DSPs](#chapter-2-a-multiplier-made-of-dsps)
//! 3. [Keeping the multiplier busy](#chapter-3-keeping-the-multiplier-busy)
//! 4. [Telling the machine what to do](#chapter-4-telling-the-machine-what-to-do)
//! 5. [Doing less work](#chapter-5-doing-less-work)
//! 6. [More hardware did not help](#chapter-6-more-hardware-did-not-help)
//! 7. [Measuring honestly](#chapter-7-measuring-honestly)
//! 8. [Verification](#chapter-8-verification)
//! 9. [Living on a shared chip](#chapter-9-living-on-a-shared-chip)
//! 10. [Meeting 205 MHz](#chapter-10-meeting-205-mhz)
//! 11. [Proving it](#chapter-11-proving-it)
//! 12. [Beside a consensus protocol](#chapter-12-beside-a-consensus-protocol)
//! 13. [Epilogue: your turn](#epilogue-your-turn)
//! 14. [Where to go next](#where-to-go-next)
//! 15. [Glossary](#glossary)
//!
//! # Chapter 1: The question: what does a signature cost?
//!
//! The goal was blunt: as many Ed25519 signatures per second as one FPGA can
//! produce at 205 MHz, scaling smoothly with however many LUTs and DSPs we
//! are given. Before designing anything we counted the work, because
//! *throughput = hardware / work per signature*, and we can attack both.
//!
//! ```text
//! r = SHA-512(prefix || M) mod l      1 SHA-512 block, 1 scalar job
//! R = [r]B, encoded                   fixed-base multiplication + inversion
//! k = SHA-512(R || A || M)            2 SHA-512 blocks
//! S = k * a + r mod l                 1 scalar job          signature = R || S
//! ```
//!
//! `[r]B` "multiplies" the fixed curve point `B` by the secret `r`. It is
//! almost all of the arithmetic: 378 field multiplications (modulo
//! `2^255 - 19`), plus about 13 more to encode `R` when 32 points share one
//! inversion. The hashing and the small `mod l` jobs are cheap by
//! comparison and run on their own small hardware.
//!
#![doc = concat!("<div style=\"overflow-x:auto\">", include_str!("../docs/images/signature-cost.svg"), "</div>")]
//!
//! **The conclusion that shaped everything:** signatures per second ≈ field
//! multiplications per second ÷ 391. So the design is, at heart, a way to
//! deliver as many field multiplications per clock as the chip allows and
//! to waste none of them. Every later chapter is one of those two halves:
//! *more multiplications per clock*, or *fewer multiplications per
//! signature*.
//!
//! # Chapter 2: A multiplier made of DSPs
//!
//! **Problem.** A 255-bit multiplication in LUTs is enormous and slow. The
//! FPGA has thousands of DSP48E2 blocks, each a hardened 27 × 18 multiplier
//! with a 48-bit accumulator and a dedicated cascade to its neighbor.
//!
//! **Reasoning.** If the multiplication can be phrased as exactly the shape
//! a DSP cascade computes, `P = PCIN + A × B`, the fabric does almost
//! nothing: no LUT adders, short wires, timing closed by construction.
//!
//! **Decision.** Split a field element into fifteen 17-bit digits. Because
//! `2^255 ≡ 19 (mod p)`, the high half of the product folds back onto the
//! low half, so each of the fifteen result columns is a 15-deep chain of
//! `17 × 22`-bit products: one DSP cascade per column, 225 DSPs per
//! multiplier, a new product every clock, 23 clocks of latency. → [`fe17`]
//!
//! # Chapter 3: Keeping the multiplier busy
//!
//! **Problem.** A multiplier that starts a product every clock is useless if
//! the next product needs the previous result: the scalar-multiplication
//! formulas are long dependency chains, and the result takes 23 clocks to
//! arrive.
//!
//! **Reasoning.** One signature cannot keep the multiplier busy, but many
//! signatures can, and signatures never depend on each other. If 32 of them
//! take turns, one instruction each per clock in rotation, every result is
//! back before its signature's next turn.
//!
//! **Decision.** *Barrel threading.* A field machine holds 32 contexts and
//! issues one bundle per clock from each in turn. There is no stall logic
//! and no hazard detection, because hazards cannot happen; all per-signature
//! state lives in block RAM indexed by context instead of in LUTs. →
//! [`machine`]
//!
#![doc = concat!("<div style=\"overflow-x:auto\">", include_str!("../docs/images/barrel-machine.svg"), "</div>")]
//!
//! # Chapter 4: Telling the machine what to do
//!
//! **Problem.** The curve algorithms change often while we optimize them,
//! and a hand-written state machine for each would take days and hide bugs.
//!
//! **Reasoning.** Treat the field machine as a tiny VLIW processor and the
//! algorithms as software: if a program can be written in ordinary Rust,
//! checked against `ed25519-dalek` on the host in seconds, and then compiled
//! into the machine's instruction ROM, changing an algorithm costs minutes.
//!
//! **Decision.** Programs are Rust ([`programs`]) built on a small
//! microcode compiler ([`microcode`]) that list-schedules them into bundles
//! of one multiply, one add/sub/output and one table step. Interleaving two
//! independent addition chains lifted multiplier use from 88 % to 98.8 %.
//! The host interpreter runs the same bundles, so hardware is compared with
//! the interpreter bit for bit.
//!
//! # Chapter 5: Doing less work
//!
//! **Problem.** With the multiplier busy, the only way left to go faster per
//! machine is fewer multiplications per signature.
//!
//! **Reasoning and decisions.**
//!
//! - **Encoding `R` needs `1/Z`**, 265 multiplications on its own. Inversions
//!   can be shared: Montgomery's trick inverts 32 values with one inversion
//!   and three multiplications each. A separate compress machine collects 32
//!   points and inverts them together: 13.2 multiplications per point. →
//!   [`programs::batch_compress`], [`compress_stage`]
//! - **`[r]B` with precomputed tables.** `B` never changes, so its multiples
//!   live in ROM. One table per digit removes every doubling; a mixed
//!   radix-32/16 recoding balances table scans against multiplications; two
//!   lookup slots and a searched lookup order finish the job. 492 → 392
//!   bundles. → [`programs`]
//!
//! # Chapter 6: More hardware did not help
//!
//! **Problem.** The first full runs, 12/6/2/1 at 45.7 cycles per signature
//! and 13/8/2/1 at 44.1, barely improved when we added machines. Every unit
//! looked idle some of the time, and nothing looked saturated.
//!
//! **Reasoning.** When adding units does nothing, the limit is not a unit but
//! the *system*. Little's law says in flight = throughput × time in system.
//! A request held one of 1,024 admission credits for about 45k cycles, so at
//! most 1,024 ÷ 45k ≈ one request every 44 clocks could enter: exactly the
//! measured rate. The machines were starving behind a queue we had sized.
//!
//! **Decision.** 2,048 credits (13/8/2/1 then measured 37.97 with machines at
//! 99.7 %), and a compress machine of 64 contexts × 32 points so a credit is
//! held for 27k instead of 44k cycles. Credits also make the design
//! deadlock-free: a request is admitted only when every resource it will
//! need later is reserved, so nothing ever waits on something that waits on
//! it. → [`sign_core`]
//!
#![doc = concat!("<div style=\"overflow-x:auto\">", include_str!("../docs/images/dataflow.svg"), "</div>")]
//!
//! # Chapter 7: Measuring honestly
//!
//! **Problem.** A 700-signature run said 32.6 cycles per signature; a
//! 6,000-signature run of the same design said 26.43.
//!
//! **Reasoning.** A run shorter than the credit pool (2,048 requests) only
//! measures the start-up transient: the pipeline is still filling. Steady
//! state needs several times the pool.
//!
//! **Decision.** Throughput is always measured over 6,000 signatures, every
//! one compared with `ed25519-dalek`: **26.43 cycles = 7.76M signatures/s at
//! 205 MHz**. → [`simulation`]
//!
#![doc = concat!("<div style=\"overflow-x:auto\">", include_str!("../docs/images/road-to-7m.svg"), "</div>")]
//!
//! # Chapter 8: Verification
//!
//! **Problem.** Verifying `[S]B = R + [k]A` costs about four times a
//! signature, because `[k]A` multiplies a point we have never seen: no
//! precomputed tables, ~3,050 bundles instead of 392.
//!
//! **Reasoning.** In the workloads we serve (and in DSig in particular),
//! verifiers know the signers' public keys long before the signatures
//! arrive. A key known in advance can get its own tables, built once, and
//! then `[k]A` is just another fixed-base walk.
//!
//! **Decision.** [`KnownKeyVerifyCore`] loads up to eight keys (about 100k
//! cycles each, on an auxiliary machine that decodes `A` and builds its
//! tables) and verifies with two fixed-base walks: 775 bundles. Strictness is
//! not negotiable: canonical `S`, `A` and `R`, no low-order points, and the
//! equation without the cofactor, with the same error codes as the reference.
//! The common case is cheap (encode `[S]B − [k]A` and compare bytes with
//! `R`); only a mismatch pays for decoding `R` to tell a malformed `R` from a
//! failed equation. → [`verify_core`]
//!
//! # Chapter 9: Living on a shared chip
//!
//! **Problem.** The chip is shared: with Ed25519 verification, with DSig,
//! with a SHA-512 line on its own allowance. Two things changed.
//!
//! - **Hashing.** Each module used to carry its own SHA-512 rings (~4.6k
//!   LUTs each, eleven of them in the large signer). A shared, fully
//!   pipelined SHA-512 line does one block per clock for everyone. A module
//!   talks to it through a client that looks exactly like a ring, holds a
//!   credit per block in flight (the line cannot stall), and resubmits the
//!   constant padding block of a two-block message itself. → [`sha_client`]
//! - **Memory.** On a full chip, block RAM ran out before LUTs or DSPs. A
//!   fixed-base machine used 72 BRAM36, mostly register banks and constants.
//!   Banks written at run time move to UltraRAM (barely used elsewhere);
//!   constants move to a small LUT ROM; the compress machine's input bank,
//!   once its identity defaults are written at reset instead of preloaded,
//!   moves to UltraRAM too. → [`machine::MachineMemory`]
//!
//! The planner ([`frontier`], `planner`) turns all of this into numbers for
//! any LUT and DSP budget.
//!
//! # Chapter 10: Meeting 205 MHz
//!
//! **Problem.** Every block met 205 MHz on its own, and no whole core did.
//! The first routed whole cores missed by 0.6 to 2.6 ns
//! (2026-10-17). A whole core is where long paths meet: a 255-bit carry, a
//! signal that fans out to every machine, or a decision that waits on
//! another decision.
//!
//! **Approach.** Route a core, read its worst path, and break that path with
//! one register in the architecture, not a Vivado option. Then simulate
//! again, because a register can change behavior. Each step below is one
//! such path, with its slack before and after.
//!
//! 1. **The 255-bit add.** *Path:* the field adder's final reduction
//!    (−0.592 ns in signer 8/0/2/1). *Idea:* add one limb per cycle, five
//!    cycles in all. *Result:* the adder alone routes at +2.036.
//!    The verifier's point-decode negations took the same treatment
//!    (−2.165 and −2.577 before). → `e62418a`, [`fe17`]
//! 2. **The multiplier's normalizer**, made limb-serial too
//!    (`MUL_LATENCY` 23). *Result:* the multiplier routes at +1.832.
//!    → `9934e35`
//! 3. **SHA ring ready from registers.** *Path:* the ring's combinational
//!    ready. *Result:* the SHA ring routes at +1.995. → `f9c1900`, [`sha_ring`]
//! 4. **Register the machine's write-only inputs.** *Path:* dispatch to
//!    every machine's clock enable. → `70295a5`, [`machine`]
//! 5. **Take scalar results only when the stage is empty.** *Path:*
//!    `fb_stage_free` into the scalar-result UltraRAM write (−0.37).
//!    → `e9fe5cd`, [`sign_core`]
//! 6. **Pick the scan digit a cycle earlier.** *Path:* inside a machine,
//!    from the 128:1 digit pick, through the compare, to the 765-bit
//!    accumulator select (−0.627 / −0.581). → `e9c1e2a`
//! 7. **Registered credit spend.** *Path:* the controller's credits, then
//!    the compress flush decision, then back to the credits (verifier
//!    −0.641). → `3c67f00`, [`compress_stage`]
//! 8. **A three-operand add in the scalar ring.** *Path:* a 272-bit carry
//!    into the `t·c` DSP product (−0.373). → `e50dfa8`, [`scalar_ring`]
//! 9. **Read the ROM two slots ahead.** *Path:* the program ROM into the
//!    table digit, then the digit pick (verifier −0.370). *Result:* the
//!    whole cores for 100 % of the chip meet timing: signer 8/0/2/1 at
//!    +0.218 and verifier 6/0/1/1 at +0.043. → `e0c9caa`
//! 10. **Carry-select in scalar-ring stage 8.** *Path:* at 12 machines the
//!     four-limb add's carry chains are placed far apart (−0.358). *Idea:*
//!     stage 7 computes both high halves, and stage 8 only finishes the low
//!     half and picks one. *Result:* signer 12/0/3/1 at **+0.050**, the
//!     largest core to meet timing. → `06bd8d3`
//! 11. **A registered verify-output arbiter.** *Path:* 24 machines'
//!     offers, chained through a priority chain into the compress loader
//!     (−5.763). *Idea:* pick from registered offers into a registered
//!     point. *Result:* placement −1.236.
//!     - *What simulation caught:* the first version lost a point's `X`. A
//!       flush could close the batch between the pick and the offer, and
//!       verification 585 of 3,000 failed with code 6.
//!     - The fix: a machine is accepted only when the compress stage takes
//!       its point (`200f4e8`).
//!     → [`verify_core`]
//! 12. **Take an encoded point only when the compare register is empty.**
//!     *Path:* the admission key match, then the result register, then the
//!     compare's retire, then the compress stage's `out_ready`, which fans
//!     out over its output stage (verifier 6/0/1/1 −0.190). *Result:*
//!     +0.019, at 151,645 LUT (job 007zzh). → `dcb2e6e`
//! 13. **Register what grows with the machine count.** *Path:* the
//!     first-free-machine pick over 24 × 32 free bits, and paths that meet
//!     at 6 machines and miss at 24 because a die crossing eats the cycle
//!     (24/0/2/1 −2.225, −1.047 with the hard route directives). *Idea:* a
//!     registered free-machine flag, a two-step decode root, an admission
//!     register, and chained key-table writes. *Result:* the 24-machine
//!     verifier meets 205 MHz at **+0.008** ns, 827,202 LUT (job 007zzq,
//!     hard route directives). → `74fdc93`
//!
//! **Each fix is cheap in throughput.** All of them were re-simulated:
//! signer 8/0/2/1 went from 46.37 to 46.46 cycles, and verifier 6/0/1/1
//! from 134.81 to 134.93.
//!
//! **Each fix costs LUTs.** The verify controller grew from 17,540 to
//! 30,657 LUT. The planner's costs were refit to the RTL that meets timing,
//! and checked on cores routed later (+0.2 %, −0.4 %, −1.0 % and +2.3 %
//! LUT).
//!
//! **Met, with no room to spare:** the 24-machine verifier (planned for
//! 200 %). Steps 11–13 took it from −5.763 ns to +0.008 ns. Step 12 left it
//! at −2.225 ns (842,345 LUT, job 007zzg), with 207,219 endpoints failing
//! and 82 % of the worst path's delay in wire. Step 13 registered the
//! paths that grow with the machine count. Three caveats: the +0.008 needs
//! the hard route directives, it is on fix13, and fix14's constant ROM adds
//! LUTs (the 1,1,1,1 verifier lost 0.022 ns of slack to it). A fix14 route
//! of this core is the next check.
//!
//! # Chapter 11: Proving it
//!
//! Every claim climbs the same ladder: the host model equals the reference,
//! the RHDL equals the host model, Vivado maps it, the planner is
//! recalibrated. The table says which rung each claim is on.
//!
//! | Claim | Evidence |
//! |---|---|
//! | Programs equal ed25519-dalek (incl. `0`, `1`, `l − 1`) | host interpreter, `programs` tests |
//! | Machines equal the interpreter bit for bit; rings equal `sha2` / big integers | native RHDL simulation |
//! | Whole signers equal ed25519-dalek (1/1/1/1, 2/1/1/0, `Ed25519SignCoreSmall` on 64 envelopes) | native RHDL simulation |
//! | 15/11/3/1: 26.43 cycles/signature | native simulation, 6,000 signatures |
//! | Known-key verifier equals strict verification and `verify_strict` (valid; wrong message; `S + l`; `R` non-canonical, off-curve, low order; unknown key) | native RHDL simulation, `tests::verifier::known_key_verifier_matches_reference` |
//! | Shared SHA-512 port: clients, arbiter, credits and pad-block resubmission give correct digests with a stalling consumer | native RHDL simulation against an 82-cycle pipeline model, `sha_client` tests |
//! | Sign and verify through one shared SHA-512: signatures equal ed25519-dalek, verifier accepts them and rejects a tampered one | same, `tests::shared_sha::sign_and_verify_share_one_sha_pipeline` |
//! | Exports to Verilog (37.0 MB) and lints clean | `export_scalable`, Verilator 5.040 |
//! | Small core: 29,055 CLB LUT, 248 DSP, 40 BRAM36, 32 URAM, WNS +0.306 ns | Vivado 2023.2 out of context, routed at 4.878 ns (`measure/results.tsv`, job 007zd) |
//! | Every block meets 205 MHz on the fix9 RTL: fixed-base machine +0.848 (UltraRAM banks), +0.544 (block RAM), +0.450 (LUT RAM); verify machine +0.609; compress machine +0.679; key loader +0.863; SHA ring +1.995 ns | same, one routed run per block (jobs 007zq–007zzb) |
//! | Whole cores meet 205 MHz: signers 4/0/1/1 +0.024, 8/0/2/0 +0.397, 8/0/2/1 +0.218 (150-DSP multiplier +0.103), 8/0/3/1 +0.159, 9/0/2/1 +0.114, 12/0/3/1 +0.050; verifiers 1/1/1/1 +0.094 (82,184 LUT; +0.072 and 84,435 on fix14), 6/0/1/1 +0.019, 12/0/1/1 +0.031 (233,052 LUT), 24/0/2/1 +0.008 (827,202 LUT, hard route directives) | same, whole cores routed ([Chapter 10](#chapter-10-meeting-205-mhz)) |
//! | 24-machine verifier: 827,202 LUT, **+0.008 ns** (fix13, hard route directives; fix12 −2.225, −1.047 hard; fix9 −5.763); planner LUT +1.5 % | routed, meets (job 007zzq; misses: 007zzg, 007zzj); **not routed on fix14** |
//! | Planned builds' throughput: 8/0/2/1 46.46, 12/0/3/1 31.95 cycles/signature; verifier 6/0/1/1 134.93 cycles/verification | native simulation, 3,000–6,000 operations, every result checked |
//! | Large core 15/11/3/1: 263,810 LUT, 3,669 DSP | Vivado synthesis only; **not routed** |
//! | Specialized memory layout (UltraRAM banks, LUT-ROM constants) and its block-RAM and LUT-RAM fallbacks | routed (above) and simulated in every whole core |
//! | Exported Verilog behaves like the model | Icarus replay of RHDL vectors (DSig, fix12): matches |
//! | Synthesized netlist behaves like the model (1/1/1/1 key load, 20,000 cycles) | post-synthesis xsim replay, `measure/gate/`: fix14 0 mismatches; fix12 fails at cycle 8,871, as the card did |
//! | On-card rate | **not yet measured** |
//!
//! **What the card caught.** DSig's verifier v3, the first card build with
//! our key loader, rejected a valid key. Every simulation we had passed:
//! RHDL, Icarus on the exported Verilog, the whole kernel. DSig replayed
//! our RHDL vectors against the routed netlist and found it at cycle 65
//! of the aux machine: the constant `d` read back with 16 wrong bits.
//! Vivado 2023.2 had mapped the write-disabled constant bank to LUT RAM,
//! dropped the bit columns that are zero in every entry, and kept the INIT
//! strings in the old layout. The fix is in RHDL: the constant bank is now
//! a literal and a mux ([`machine::ConstRom`], fix14), which leaves Vivado
//! no RAM to infer. It costs +1,658 CLB LUT on the 1/1/1/1 verifier after
//! synthesis. The lesson is the new rung on the ladder: replay the vectors
//! after synthesis (`measure/gate/`), before a link.
//!
//! # Chapter 12: Beside a consensus protocol
//!
//! **Problem.** uBFT ([YiJiang0908/ubft_new]) runs Byzantine consensus as
//! an HLS kernel on the same U280. On its slow path, each replica signs a
//! certificate share for every slot. It then checks its peers' shares until
//! it holds a quorum of `2f + 1`. Today it calls the Vitis Security
//! library's Ed25519 inline. One signature takes 3.07M cycles and one
//! verification 10.4M (HLS C/RTL cosimulation, measured by DSig). The
//! state machine waits for each one, and that signer is the kernel's worst
//! timing path: it pulled uBFT's clock from 300 MHz down to 161.3 MHz.
//! uBFT tolerates `f = (n − 1) / 2` faults, so a quorum is nearly every
//! replica. At three replicas a slot spends about 148 ms on crypto, and
//! at seven about 406 ms. The library call
//! also hashes only the first byte of the 8-byte slot summary.
//!
//! **Idea.** Don't call crypto inside the state machine; give it a service
//! beside it. `ubft::UbftEd25519` (feature `ubft`) takes requests on four AXI streams:
//! a message in and a signature out, a share in and a verdict out. Up to 16
//! requests per direction stay in flight, each with a tag that uBFT
//! chooses. uBFT keeps its loop. It sends a request and goes on with
//! other work, then picks up the answer by tag. The service is the small
//! signer of [chapter 6](#chapter-6-more-hardware-did-not-help) and one
//! known-key verifier of [chapter 8](#chapter-8-verification), and needs
//! nothing new beyond tag tables and two FIFOs. Peers' keys are loaded once
//! per session into key slots. uBFT allows up to 12 replicas, more than the
//! verifier's 8 slots, so the feature `key-slots-16` widens the slot
//! number to 4 bits ([`machine::KEY_SLOTS`]). It is a feature, not the
//! default, because 16 slots double every verify machine's key tables.
//! That is cheap for this one-machine service and costly for the
//! 24-machine verifier of chapter 10. DSig offers the same four streams
//! with the same header layout, so uBFT can be built with either scheme by
//! changing only sizes.
//!
//! **Result.** In the planner's uBFT mode (`Mode::UbftEd25519`), the
//! replica takes its routed footprint off the device (346k LUTs, an upper
//! bound because it includes the shell). The service needs about 120k more.
//! A slot's crypto then takes about 367 µs at three replicas and 397 µs at
//! eleven, against 148 ms and 665 ms inline: 400 to 1,700 times less.
//!
//! **What is proven, what is not.** The signer's cost and its 22,240-cycle
//! latency are measured. The 1,1,1,1 verifier is routed at 205 MHz (fix14,
//! +0.072 ns). The simulation `ubft::tests::ubft_service_signs_and_verifies`
//! drives the whole service through its streams. It checks three
//! signatures against ed25519-dalek, and four verdicts: valid, tampered,
//! wrong slot and empty slot. It passes: 26 minutes of native
//! simulation, about 290k cycles, most of them the two key loads. Not yet measured: the service logic (the
//! planner estimates 6k LUTs), the 16-slot key tables (+57 BRAM36 per
//! machine, a model), the verifier's latency inside the service, and
//! anything on the card. The slot model also ignores network time and
//! assumes peers' shares arrive together.
//!
//! [YiJiang0908/ubft_new]: https://github.com/YiJiang0908/ubft_new
//!
//! # Epilogue: your turn
//!
//! ## Using the cores
//!
//! Both signers and the verifier are ordinary RHDL
//! [`Synchronous`](rhdl::prelude::Synchronous) components; embed them as
//! child fields.
//!
//! ```rust,ignore
//! use rhdl_ed25519_scalable_core::{Ed25519SignCoreSmall, KnownKeyVerifyCore, ScalableSignCore, sign_core::CTX_BITS};
//!
//! let small = Ed25519SignCoreSmall::default();                          // 1/1/1/0, 128 contexts
//! let large = ScalableSignCore::<15, 11, 3, 1, CTX_BITS, 0>::default(); // own SHA rings
//! let verify = KnownKeyVerifyCore::<2, 1, 1, 0>::default();             // 2 verify machines
//! ```
//!
//! The last const parameter `SH` picks own SHA rings (0) or the shared line
//! (1). Single requests are slow (~22k cycles on the small core) and many
//! requests are fast, so keep many in flight. [`ed25519_sign_core`] documents
//! the small core's ports; [`sign_core`] and [`verify_core`] the large ones.
//!
//! ## How to work
//!
//! Prove each change at the cheapest level that covers it, then climb:
//!
//! | Level | Command | Time |
//! |---|---|---|
//! | Host model: programs and planner | `cd tools/hostmodel && nice cargo test --offline -j2` | ~20 s |
//! | RHDL units, signers, verifier | `cargo test --profile sim --lib` | ~4 min (+ two ~18 min verify tests) |
//! | Throughput | `SCALABLE_BENCH_COUNT=6000 cargo test --profile sim --lib tests::signer::sustained_throughput_15_11_3_1 -- --ignored --nocapture` | ~40 min |
//! | Verilog export | `cargo run --profile sim --bin export_scalable [-- --small \| --block NAME]` | 1–2 min |
//! | Vivado out of context | `tools/vivado_ooc.tcl` (on the U280 host) | hours |
//!
//! On the shared host, run heavy commands through `tools/bounded.sh` (memory
//! and CPU caps, one heavy job at a time) and record each run in the
//! coordination ledger.
//!
//! RHDL has sharp edges that compile under rustc and fail only when
//! lowering: no `/` or `%` in kernels (even on loop constants), literal or
//! const-generic loop bounds, `Bits` of at most 128 bits, at most ~11
//! synchronous children per struct, and a component's generated `Q`/`D`
//! types carry its name as a prefix when a module holds several
//! components. [`export`] describes the lowering-memory patch.
//!
//! ## Open problems
//!
//! 1. **Keep the 24-machine verifier at 205 MHz.** Fix13 meets it by
//!    0.008 ns with the hard route directives (Chapter 10, step 13). Route
//!    it on fix14 (constant ROM, more LUTs) and with default directives,
//!    and win back some margin.
//! 2. **Wire the shared SHA-512 line for real** (`rhdl_sha512_pipelined`) in
//!    one chip and route it.
//! 3. **A reduce-only scalar ring** for verification. (The 150-DSP
//!    Karatsuba multiplier is built and meets 205 MHz on the timing-fixed
//!    RTL: signer 8/0/2/1 at +0.103, 188,537 LUT.)
//! 4. **Latency**: the compress machine's batch wait dominates; a smaller
//!    batch or an early flush trades throughput for latency.
//! 5. **Gate every core after synthesis.** The gate covers the 1/1/1/1
//!    verifier's key load. Record vectors for a signer and for a
//!    verification, and run them on every core before it ships.
//! 6. Strict verification for arbitrary keys (variable-base), if needed.
//!
//! Smaller items found while documenting every kernel (none is a known bug):
//!
//! - **Admission is capped at one request per three cycles** by the free-context
//!   FIFO's refill latency (the credit limit is ~23 cycles, so it is not binding
//!   today).
//! - **Fixed-priority arbitration.** Verify-machine outputs and ring results are
//!   taken lowest index first, not round-robin; a starvation bound would need
//!   checking if a module ever runs saturated for long.
//! - **Combinational `ready` with `SH = 1`.** A core's `ready` depends on the
//!   shared port's `ready` in the same cycle. This is safe because
//!   [`sha_client::SharedShaPort`] drives that from registers, but it is a
//!   contract for any other port. The verifier's `ready` also depends on
//!   `load_key_valid` in the same cycle (a key load goes first).
//! - **Caller contracts.** Nothing guards these:
//!   - a field machine must not be started on a running context;
//!   - the compress stage expects each point's `X` before its `Y` and `Z`.
//! - **`Ed25519SignCore` builds only small sizes.** With `CB = 7` it is limited
//!   to `NFB <= 4` and fused mode; larger sizes use [`ScalableSignCore`].
//! - **`interpret` runs one program at a time.** It ignores intermediate `end`
//!   flags, so it cannot start a [`microcode::concat`] ROM at a later entry.
//! - **Duplicate encoding helpers.** `compress_stage::encode_y` repeats
//!   `sign_core`'s point encoding.
//! - **Fitted model constants.** `config::CREDIT_OVERHEAD` was fitted to older
//!   programs and not refitted. The verify utilization is assumed equal to
//!   signing's, not measured.
//!
//! # Where to go next
//!
//! Pick the row that matches what you want to do. Each row lists the pages to
//! read, in order, and the first command to run.
//!
//! | You want to... | Read, in order | Then run |
//! |---|---|---|
//! | **understand how a signature is computed** | [`programs`] (the algorithm as Rust), [`microcode`] (how it becomes bundles), [`host`] (the reference model) | `cd tools/hostmodel && nice cargo test --offline -j2` |
//! | **make signing faster per machine** | [Chapter 5](#chapter-5-doing-less-work), [`programs::fixed_base`], [`microcode`] | the host model; count bundles before touching hardware |
//! | **make signing faster per chip** | [Chapter 6](#chapter-6-more-hardware-did-not-help), [`sign_core`] (credits, contexts), [`config`] (cycle model) | `tests::signer::sustained_throughput_15_11_3_1` (40 min) |
//! | **understand the hardware datapath** | [`fe17`] (multiplier), [`machine`] (barrel machine, memories), [`sign_core`] (controller) | `cargo test --profile sim --lib tests::machines::fixed_base_machine_matches_interpreter` |
//! | **work on verification** | [Chapter 8](#chapter-8-verification), [`verify_core`], [`programs::verify_known_key`], the key-load programs in [`programs`] | `tests::verifier::known_key_verifier_matches_reference` (~18 min) |
//! | **save BRAM, LUTs or DSPs** | [`machine`] ("Where the memories live"), [`frontier`] (costs, marked measured or projected), `mapping/vivado-20261014` (per-block reports) | `cargo run --profile sim --bin export_scalable -- --block NAME`, then Vivado |
//! | **connect to the shared SHA-512 line** | [Chapter 9](#chapter-9-living-on-a-shared-chip), [`sha_client`], the `SH` parameter of [`sign_core`] and [`verify_core`] | `tests::shared_sha::sign_and_verify_share_one_sha_pipeline` |
//! | **change the planner or its numbers** | [`frontier`], `planner` (feature `tuner`), and the repository guide's "How a plan is made" | `cargo test --features tuner --lib planner` |
//! | **serve uBFT (or another protocol) over streams** | [Chapter 12](#chapter-12-beside-a-consensus-protocol), `ubft` (feature `ubft`: streams, register map, session), `planner::ubft` (feature `tuner`) | `cargo test --profile sim --features ubft --lib ubft -- --ignored` |
//! | **embed a core in your own design** | [Using the cores](#using-the-cores), [`ed25519_sign_core`] (ports and handshake), [`wire`] (port types) | `tests::signer::small_core_signs_dsig_envelopes` |
//! | **get Verilog for Vivado** | [`export`] (what is generated and why it fits in memory) | `cargo run --profile sim --bin export_scalable -- --small` |
//! | **pick something to work on** | [Open problems](#open-problems), and the repository guide's "Good first contributions" (sized tasks with a clear finish line) | write down its work count and binding resource first |
//!
//! # Glossary
//!
//! | Term | Meaning |
//! |---|---|
//! | Barrel threading | many jobs share one pipeline, one per clock in rotation |
//! | Bundle | one VLIW instruction: a multiply, an add/sub/output, a table step |
//! | Context | one job resident in a machine (32 per fixed-base machine) |
//! | Credit | permission to admit a request; reserves every later resource it needs |
//! | Fused mode | no compress machine; each program inverts its own point |
//! | Known-key verification | verification for public keys whose tables were built in advance |
//! | Little's law | in flight = throughput × time in system |
//! | MACC chain | DSP cascade `P = PCIN + A × B` |
//! | Mixed radix | 39 five-bit and 15 four-bit signed digits |
//! | Profile `fb/sha/sc/cp` | build size: fixed-base machines, SHA rings, scalar rings, compress machine (1) or fused (0) |
//! | Ring | a small pipeline with several jobs circulating |
#![warn(missing_docs)]
// RHDL lowers fixed-bound range loops directly into hardware. Rewriting them
// as host iterators, as Clippy suggests, would leave the synthesizable subset.
#![allow(clippy::needless_range_loop)]
// Explicit hardware expressions are kept uniform inside `#[kernel]` code.
#![allow(clippy::assign_op_pattern, clippy::unnecessary_cast)]

// ---- Host model (no hardware): the reference everything is checked against.
pub mod host;
pub mod microcode;
pub mod programs;

// ---- Hardware (RHDL components).
pub mod compress_stage;
pub mod digest;
pub mod ed25519_sign_core;
pub mod fe17;
pub mod fe17_kara;
pub mod machine;
pub mod scalar_ring;
pub mod sha_client;
pub mod sha_ring;
pub mod sign_core;
#[cfg(feature = "ubft")]
pub mod ubft;
#[cfg(feature = "card")]
pub mod card;
pub mod verify_core;
pub mod wire;

// ---- Sizing, export and simulation tools.
pub mod config;
pub mod export;
pub mod frontier;
#[cfg(feature = "tuner")]
pub mod planner;
pub mod simulation;

#[cfg(test)]
mod tests;

pub use ed25519_sign_core::{Ed25519SignCore, Ed25519SignCoreSmall};
pub use sign_core::{ScalableSignCore, ScalableSignIn, ScalableSignOut};
pub use verify_core::{KnownKeyVerifyCore, VerifyIn, VerifyOut};
pub use wire::{CachedSignIn, CachedSignOut, ScalarWords, SignRequest, VerifyRequest, Words512};