# Form B — `cuda-bignum-cgbn` implementation plan

You wrap NVlabs CGBN (Cooperative Groups Big Numbers) as a BSHK-speaking
daemon under our existing bend-form pattern. Output: a single CUDA
binary `cgbn-batch-worker`, a Scheme handler in `gpu-worker.lsp`, a
Makefile target, & a validation harness. Cross-cite: catalog entry
`cuda-bignum-cgbn` in `CATALOG.md` (form B, build order step 3), source
NVlabs/CGBN at https://github.com/NVlabs/CGBN, midsize-int benchmark at
https://arxiv.org/pdf/2405.14642.

## 1. CGBN model → wire model

CGBN groups 4/8/16/32 threads into one **instance**; each instance owns
one bignum (32-bit to 32 K-bit). The library handles cooperative-group
dispatch (https://github.com/NVlabs/CGBN/blob/master/samples/sample_01_add/add.cu);
you write a kernel templated on `cgbn_env_t<context_t, BITS>` & call
`cgbn_load / cgbn_mul / cgbn_modular_inverse / cgbn_store`.

For our 256-bit secp256k1 case: `TPI=8` (threads per instance) at 256 bits
is the published sweet spot per CGBN README. One warp (32 threads) =
4 instances. A 3090 SM holds 1024 threads = 128 instances per SM × 82 SMs
= **10,496 in-flight 256-bit ops per kernel wave**. Map: one BSHK
request = one launch = N instances. We never expose CGBN's cooperative-
group primitive across our wire; we expose **op-coded batches**.

## 2. Operation dispatcher — `cgbn-batch-worker`

Single binary, op-coded. Op table (one byte each, room to grow):

| op_id | mnemonic       | inputs | output | kernel                                |
|------:|----------------|--------|--------|---------------------------------------|
| 0x01  | mod-add        | a, b   | a+b mod m | `cgbn_add` + `cgbn_rem`            |
| 0x02  | mod-sub        | a, b   | a-b mod m | `cgbn_sub` + conditional `cgbn_add` |
| 0x03  | mod-mul        | a, b   | a*b mod m | `cgbn_mont_mul` (precomputed `m`)   |
| 0x04  | mod-sqr        | a      | a^2 mod m | `cgbn_mont_sqr`                     |
| 0x05  | mod-inv        | a      | a^-1 mod m | `cgbn_modular_inverse`             |
| 0x06  | mod-exp        | a, b   | a^b mod m | `cgbn_modular_power` (binary ladder) |
| 0x07  | mod-reduce     | a      | a mod m  | `cgbn_rem` standalone                |
| 0x08  | add-no-mod     | a, b   | a+b      | `cgbn_add` straight                  |
| 0x09  | mul-no-mod     | a, b   | a*b (lift to 2 × width) | `cgbn_mul_wide`     |

Kernel dispatch via single `__global__` switch on op_id. CGBN environment
template is bit-width parameterized; you compile one specialization per
expected bit-width (256, 384, 521) & route via a runtime `switch
(bitwidth)` over the templated launchers. Default bit-widths to ship:
256, 384. Wider widths land on demand.

## 3. Wire protocol — BSHK / BSHR for CGBN

Request (little-endian throughout, matching `bench_tiers.py`
`make_payload_binary` in this dir):

```
"BSHK"  (4 bytes magic)
u32 op_id
u32 bitwidth        ; one of {256, 384}
u32 n_instances
u8[bitwidth/8]      modulus m       (omitted for op 0x08, 0x09)
u8[n * bitwidth/8]  operand_a
u8[n * bitwidth/8]  operand_b       (omitted for 0x04, 0x05, 0x07)
```

Response:

```
"BSHR"  (4 bytes magic — matches handle-binary-shake in gpu-worker.lsp)
u32 status          ; 0 = ok; nonzero = error code
u32 n_instances
u8[n * width_out/8] result          ; width_out = bitwidth or 2*bitwidth
```

For 256-bit secp256k1 case @ N=1M instances: input ~64 MB
(modulus + 2 operand arrays), output ~32 MB. CGBN documents 32K-bit max
per instance (see `cgbn.h` `BITS` template parameter
https://github.com/NVlabs/CGBN/blob/master/include/cgbn/cgbn.h); 256-bit
fits trivially. TPI=8 at 256 bits leaves no SM under-utilization on
3090/4090 because each SM still hosts 128 in-flight instances.

## 4. `gpu-worker.lsp` handler

You add `handle-cuda-bignum-cgbn` modeled on `handle-cuda-shake-fanout`
plus the binary path in `handle-binary-shake` already in this dir's
`gpu-worker.lsp`. Two surfaces:

S-expression (small N, dev convenience):

```scheme
(cgbn-batch
  (op . mod-mul)
  (bitwidth . 256)
  (modulus . "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f")
  (a . ("..." "..."))
  (b . ("..." "...")))
```

Binary (production): client sends `BSHK | u32 op_id | …` blob exactly as
above. Worker writes blob to `/tmp/bend-cgbn-in-<ts>.bin`, calls daemon
`process-bin <in> <out>`, reads `/tmp/bend-cgbn-out-<ts>.bin`, prepends
`"BSHR"`, sends back via `wire-send-raw`. Register the daemon at startup
next to `register-daemon!` for `'cuda-shake-fanout`:

```scheme
(define *binary-cgbn-batch*
  (or (get-environment-variable "CGBN_BATCH_WORKER")
      "./cgbn-batch-worker"))
(register-daemon! 'cuda-bignum-cgbn *binary-cgbn-batch*)
```

Dispatch in `handle-request`: `((eq? op 'cgbn-batch) (handle-cuda-bignum-cgbn args))`.

## 5. Daemon protocol

Inherited verbatim from `shake256-fanout.cu --daemon` (this dir): stdin
line-protocol `process-bin <in> <out>` / `quit`, stdout `ready` once
CUDA context warms, `done <out>` / `error <reason>` per command, `bye`
on quit. CUDA context init pays once per worker startup, never per BSHK
request — same architectural point the SHAKE form already proved.

## 6. Build recipe

```makefile
CGBN_DIR := vendor/CGBN
NVCC_ARCH_3090 := -arch=sm_86
NVCC_ARCH_4090 := -arch=sm_89
NVCC_FLAGS := -O3 -I$(CGBN_DIR)/include --extended-lambda

cgbn-batch-worker: cgbn-batch-worker.cu $(CGBN_DIR)/include/cgbn/cgbn.h
	nvcc $(NVCC_FLAGS) $(NVCC_ARCH_3090) -gencode=arch=compute_89,code=sm_89 \
	     -o $@ cgbn-batch-worker.cu -lgmp

vendor/CGBN/include/cgbn/cgbn.h:
	git submodule add https://github.com/NVlabs/CGBN vendor/CGBN

cgbn-bench: cgbn-batch-worker
	python3 bench_cgbn.py --small 1000 --medium 100000 --huge 1000000

cgbn-test: cgbn-batch-worker
	python3 test_cgbn_known_answers.py
```

CGBN ships as header-only inside `include/cgbn/` — no separate
`libcgbn.so` build. Vendor the headers; do not pull the full repo into
our build graph. License: BSD 3-Clause per https://github.com/NVlabs/CGBN/blob/master/LICENSE
— compatible with our AGPLv3 binary distribution (CGBN headers ship
permissively, our wrapper binary stays AGPLv3).

## 7. Validation plan

Three layers, cheapest first:

1. **openssl bignum CLI** for op 0x03 mod-mul on tiny operands. Drive
   from `test_cgbn_known_answers.py`: pass N=32 hand-picked triples
   (a, b, m, expected = a*b mod m). Sanity, not throughput.
2. **python gmpy2** for batches at N ∈ {1k, 10k, 100k}. Generate
   random a, b ∈ [0, m); compute reference on host (`gmpy2.f_mod(a*b, m)`),
   compare byte-for-byte against GPU result. Cover ops 0x01, 0x03, 0x04,
   0x05, 0x06. gmpy2 docs: https://gmpy2.readthedocs.io.
3. **secp256k1 round-trip**: m = secp256k1 field prime
   `0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f`,
   load N random 256-bit a, b; compute a*b mod m through CGBN; verify
   against Python `coincurve` reference (https://github.com/ofek/coincurve).
   Halt promotion if any byte mismatches.

Cross-tier portal validation: identical BSHK input bytes to Python,
C tree-walker, asm-gc workers via our `bench_tiers.py` shape (already
binary-wire-aware) must produce byte-identical BSHR responses. Mismatch
on any tier halts promotion per `ecdsa/CLAUDE.md` cross-tier rule.

## 8. Performance projection

Sources: midsize-int benchmark https://arxiv.org/pdf/2405.14642 (Table 3
reports ~100×+ on 256-bit dense mul vs Xeon-20c GMP+OpenMP on V100);
NVlabs CGBN README claims 5-10× over GMP per-op on Volta. A 3090 is
~3× V100 throughput on dense integer work (per
https://www.nvidia.com/en-us/data-center/a100/ comparison & 3090
whitepaper).

Rough numbers, to be confirmed on hardware:

- **mod-mul 256-bit**: ~3-5 Gops/s on a 3090 (TPI=8 at warp-saturated
  occupancy, kernel-only). 4090 ~1.6× that. Reference: midsize-int paper
  Fig 7, scaled by 3090/V100 fp32 ratio.
- **mod-inv 256-bit** (CGBN's binary GCD path): ~50-100 Mops/s on 3090.
  Bernstein-Yang batched variant (form E in catalog) wins ~3-5× over
  this once we add it.
- **mod-exp 256-bit** (256-bit ladder): ~10-30 Mops/s on 3090.
- **wire-overhead crossover**: BSHK round-trip pays ~3 ms median per call
  per `bench_tiers.py` binary-mode at small N (this dir's existing
  measurements). At 3 Gops/s kernel rate, you break even with CPU GMP
  (~5 Mops/s single-thread) around **N ≈ 15,000 instances per BSHK
  call**. Stay above N=100k for clean 100×.

## 9. Risks & open questions

- **CGBN maintenance.** Last public commit on https://github.com/NVlabs/CGBN
  is 2021-era. NVlabs has not formally archived it. You must verify
  it compiles under CUDA 12.x on Ampere & Ada (sm_86, sm_89). If not,
  patch `cgbn.h` toolchain checks ourselves & vendor the patched copy.
- **License.** BSD 3-Clause per https://github.com/NVlabs/CGBN/blob/master/LICENSE.
  No AGPL incompatibility for our binary distribution.
- **sm_86 / sm_89 support.** CGBN documents Volta + Turing as primary
  targets. Ampere (sm_86) cooperative-groups API is a superset, so the
  cooperative-thread-array primitives CGBN calls remain valid. Open
  risk: warp-shuffle reductions in `cgbn_add` may need width
  adjustment for newer warp-scheduler behavior. Mitigation: ship
  validation suite first; any divergence shows up against gmpy2 ref.
- **Under-utilization at 256-bit / TPI=8.** Each warp owns 4
  independent instances. At N=1M & 82 SMs × 128 in-flight, you get
  ~95 kernel waves on a 3090. Each wave is ~µs; total kernel ~100 µs.
  Memory bandwidth (32 MB input, 32 MB output → 64 MB at 936 GB/s =
  ~70 µs) becomes the floor. Kernel & PCIe transfer are co-dominant.
- **PCIe transfer budget.** 64 MB host→device + 32 MB back via PCIe
  Gen4 x16 (32 GB/s) = ~3 ms. Already comparable to wire overhead;
  pinned-host memory & overlap with kernel via streams cuts this in
  half.

## 10. Effort estimate

You should land this in **3-5 days** end-to-end as an experienced CUDA
developer. Breakdown:

- Day 1: vendor CGBN, build sample_01_add unmodified on 3090 host,
  confirm sm_86 compatibility, build baseline `cgbn-batch-worker.cu`
  with op 0x03 mod-mul only.
- Day 2: daemon mode (clone shake256-fanout `--daemon` skeleton), add
  ops 0x01, 0x04, 0x05, wire validation against gmpy2 at N=1k, 10k.
- Day 3: gpu-worker.lsp handler, BSHK dispatch, cross-tier validation
  (Python + C + asm via `bench_tiers.py`-style harness), portal test
  for secp256k1 mod-mul.
- Day 4: remaining ops (0x02, 0x06, 0x07, 0x08, 0x09), bench_cgbn.py
  driver covering all ops at N ∈ {1k, 100k, 1M}, telemetry lines in
  Scheme handler (wall-ms / cpu-ms / gpu-ms / gpu/cpu ratio).
- Day 5 (buffer): polish, README, CATALOG.md row promotion to `live`,
  Makefile install/test targets, runs/lumbda-cgbn-001/ baseline
  artifacts.

Lower than form A (`cuda-secp256k1-batched-mul`) since CGBN is a
**direct API consumption** — no extraction effort from a research
codebase, no curve-specific Montgomery tuning to port. Form A risks 7-10
days; form B caps at 5.
