# Moxie Port Plan - gnarl-hamadryad

Source: ~7000 LOC non-test Go (excluding cayley, tests, benchmarks).
Target: WASM via Moxie. Single-threaded, no reflection, no `math/big`.

## Audit Summary

**Clean (zero issues):**
- No goroutines, no reflection, no empty interfaces (core), no `strings` package
- No string `+` concatenation, no `fallthrough`, no complex types, no `uintptr`
- All `errors.New()` calls use string literals
- All RNG-dependent functions already split into `Foo()` / `FooFrom(rng io.Reader)` pairs

**Mechanical transforms (search-and-replace + trivial rewrites):**
- 63 `make([]T, n)` -> `[]T{:n}` / `[]T{:n:c}` literal syntax
- 1 `make(map[...])` -> fixed array cache (only 3 known parameter sets)
- ~15 bare `int` in struct fields/params -> explicit `int32`
- `encoding/binary.LittleEndian.PutUint64(...)` etc -> inline byte ops
- `.s` file extension assembly -> drop (WASM target, use generic fallback)
- Build tags (`//go:build amd64`) -> remove, WASM only

**Requires rewrite:**
- `math/big` elimination (3 files, ~200 LOC affected)
- External deps: `chacha20`, `sha3` (reimplement or use moxie stdlib)
- Gaussian sampler float64 math (1 file, ~100 LOC)
- `fmt.Sprintf` elimination (5 calls)
- `crypto/sha256` -> native or moxie stdlib
- `crypto/subtle.ConstantTimeCompare` -> inline

## Port Order (dependency-driven)

### Phase 0: Foundation types (no deps)

Files: `ratio/ratio.go`, `epoch/epoch.go`

| File | LOC | Changes |
|------|-----|---------|
| ratio.go | 198 | Remove `fmt.Sprintf` in `String()`. Replace bare `int` with `int32`. `make([]T,n)` -> literal. |
| epoch.go | 207 | Remove `fmt.Sprintf` in `String()`. Replace bare `int` with `int32`. |

Trivial. These have zero crypto deps. Port first to validate the toolchain.

### Phase 1: Field arithmetic (pure math, no stdlib deps)

Files from `crypto/gnarl/`:

| File | LOC | Changes |
|------|-----|---------|
| field.go | 616 | Drop assembly stubs. Use `montMulGeneric`/`montSquareGeneric` only. `math/bits` -> inline (Moxie has `bits`?  verify; if not, manual `Add64`/`Mul64`/`Sub64`). Remove unused `fieldLen` const. |
| field_generic.go | 11 | Merge into field.go. |
| field_amd64.go | 9 | Drop. |
| field_amd64.s | asm | Drop. |
| scalar.go | 213 | **Eliminate `math/big`**: replace `scReduce` with native 4-limb mod (Barrett or repeated subtraction - Q is 213 bits, value is at most 256 bits, ~2 subtractions max). Replace `scMul` with 4-limb schoolbook multiply + Barrett reduce. ~80 LOC rewrite. |
| torus.go | 277 | **Eliminate `math/big`**: remove `bigToFe`, `feToBig`, `bigToScalar`, `scalarToBig`, `m4PowBig` (all unused per diagnostics). What remains is pure limb ops. |

Key insight: `scReduce` currently does `big.Int.Mod` on a 256-bit value mod 213-bit Q. Since the input is at most 256 bits and Q is 213 bits, this is at most a few conditional subtractions, or one Barrett reduction. `scMul` does 4-limb multiply -> 8-limb intermediate -> Barrett reduce mod Q. Both are ~40 LOC each to implement natively.

### Phase 2: NTT engines (pure math)

| File | LOC | Changes |
|------|-----|---------|
| ntt.go | 182 | Bare `int` -> `int32`. `make` -> literal. |
| ntt27.go | 370 | Same. |
| ring/ring.go | 284 | Bare `int` in `Params.N` -> `int32`. Propagate. `make` -> literal. |
| ring/ntt.go | 253 | Replace `map[[2]uint32]*nttTables` with fixed array of 3 entries (Falcon512, NewHope256, HE64). `make` -> literal. Bare `int` in nttTables fields -> `int32`. |
| ring/sample.go | 248 | `make` -> literal. `encoding/binary` -> inline. `io.ReadFull` -> read loop. |

### Phase 3: Hash functions

| File | LOC | Changes |
|------|-----|---------|
| hamadryad.go | 356 | Remove `HashValue` (uses `any`). Remove `fmt`. `encoding/binary` -> inline. `crypto/rand.Read` -> moxie CSPRNG. `make` -> literal. |
| gnarl_hash.go | 379 | Same pattern. Remove `GnarlHashValue`. `crypto/rand` -> moxie CSPRNG. |
| gnarl_hash_amd64.go | 18 | Drop entirely. WASM target uses generic path. |
| hash.go | 15 | Drop entirely. `hashValue(any)` and `hashFingerprint` are dead code (`hashFingerprint` already flagged unused). |
| ring/sis.go | 376 | `encoding/binary` -> inline. `sha3.NewShake256` -> see Phase 3 deps below. `make` -> literal. |

**Dep: SHA3/SHAKE256.** Used by `ring/sis.go`, `ring/gpv.go`, `ring/kem.go`, `ring/he.go`, `ring/keyagg.go`, `ring/malleable.go`. Five files import `sha3`. Options:
1. Reimplement SHAKE256 from FIPS 202 spec (~300 LOC Keccak sponge)
2. Check if moxie stdlib has it
3. Use the Hamadryad hash as domain-separated PRF instead (architectural change)

**Dep: SHA256.** Used only in `gnarl/gnarl.go:47` for one-time prime seed derivation during `init()`. Can be replaced with a hardcoded seed constant (the prime is deterministic).

### Phase 4: Gnarl signatures

| File | LOC | Changes |
|------|-----|---------|
| gnarl/gnarl.go | 408 | **Eliminate `math/big` from `initPrime`**: the prime P and Q are deterministic constants derived from a fixed seed. Precompute them and embed as `pLimbs`/`qLimbs` constants (already done - `initPrime` just verifies). Replace `verifyConstants` with compile-time assertion or remove. Remove `Params()` function (returns `*big.Int`). Replace `crypto/sha256` call with hardcoded seed bytes. |
| gnarl/exp.go | 112 | Pure limb math. Remove unused `tmVarExp`. No changes needed. |

After Phase 1 scalar.go rewrite, gnarl.go's only remaining `big.Int` use is in `initPrime` (one-time verification) and `Params()` (export). Both removable.

### Phase 5: Wire protocol and stream cipher

| File | LOC | Changes |
|------|-----|---------|
| ctr.go | 101 | **Replace `chacha20` import.** Reimplement ChaCha20 quarter-round from RFC 8439 (~120 LOC). The file already wraps it minimally. `make` -> literal. |
| gnarl_wire.go | 200 | `encoding/binary` -> inline. `errors` OK. Depends on ctr.go for ChaCha20 and gnarl_hash.go for GMid. |

**Dep: ChaCha20.** Used in `ctr.go` only. One call: `chacha20.NewUnauthenticatedCipher(key, nonce)` + `.XORKeyStream()`. ChaCha20 is ~80 LOC from spec (8 quarter-rounds x 10 double-rounds + counter).

### Phase 6: Ring-LWE KEM

| File | LOC | Changes |
|------|-----|---------|
| ring/kem.go | 341 | `sha3` -> Phase 3 dep. `crypto/subtle.ConstantTimeCompare` -> inline loop. `make` -> literal. `io` -> keep (interface compat). |

### Phase 7: GPV signatures

| File | LOC | Changes |
|------|-----|---------|
| ring/gpv.go | 422 | `sha3` -> Phase 3 dep. `encoding/binary` -> inline. `make` -> literal. |
| ring/gaussian.go | 308 | **Float64 rewrite.** Uses `math.Exp`, `math.Pi`, `math.Ceil`, `math.Floor`, `math.Round`, `math.Abs`, `math.Log2`. Two options: (a) fixed-point CDT table precomputed at compile time, (b) check if Moxie has `math` float support for WASM. WASM has native f64 ops so float64 should work if the `math` package is available. |

### Phase 8: Homomorphic encryption + MPC

| File | LOC | Changes |
|------|-----|---------|
| ring/he.go | 381 | `sha3` dep. `float64` in `NoiseEstimate` field (can be `int32` noise bound instead). `make` -> literal. |
| ring/keyagg.go | 163 | `sha3` dep. `make` -> literal. |
| ring/mpc.go | 114 | Thin wrapper. `errors` OK. |
| ring/malleable.go | 234 | `sha3` dep. `float64` in noise est. `make` -> literal. |
| ring/recognizer.go | 362 | `make` -> literal. Depends on he.go. |

### Phase 9: Params

| File | LOC | Changes |
|------|-----|---------|
| params.go | 111 | Uses `ratio.Ratio`. Bare `int` -> `int32`. |

## Critical Dependencies to Resolve Before Starting

1. **Does Moxie stdlib have `math/bits`?** (`Add64`, `Mul64`, `Sub64` used in Montgomery multiply.) If not, inline the ~10 functions needed. These are just `(hi, lo) = a * b` and `(sum, carry) = a + b + c` patterns.

2. **Does Moxie stdlib have `math` (float64 ops)?** WASM has native f64. If `math.Exp`/`math.Pi` are unavailable, precompute the Gaussian CDT table as integer constants.

3. **Does Moxie stdlib have `crypto/rand`?** WASM needs `crypto.getRandomValues()` or equivalent. If not, the `io.Reader` pattern lets us inject any RNG source.

4. **SHAKE256 availability.** If absent, implement Keccak-f[1600] sponge (~300 LOC). Used pervasively in ring/ for domain-separated hashing.

5. **`crypto/subtle` availability.** If absent, one function: `ConstantTimeCompare` (~10 LOC).

## Estimated Effort

| Phase | LOC to port | Difficulty | New code needed |
|-------|-------------|------------|-----------------|
| 0 | 405 | trivial | 0 |
| 1 | 1117 | moderate | ~120 (native scalar arith) |
| 2 | 1337 | easy | ~20 (cache array) |
| 3 | 1144 | moderate | ~300 (SHAKE256 if needed) |
| 4 | 520 | easy | 0 (big.Int removal) |
| 5 | 301 | moderate | ~120 (ChaCha20 if needed) |
| 6 | 341 | easy | ~10 (subtle inline) |
| 7 | 730 | moderate | ~50 (float path) |
| 8 | 1254 | easy | 0 |
| 9 | 111 | trivial | 0 |
| **Total** | **~7260** | | **~620 new LOC** |

The port is dominated by mechanical transforms. The only algorithmically interesting work is:
- 4-limb Barrett reduction for scalar mod Q (~40 LOC)
- 4-limb schoolbook multiply for scalar mul (~40 LOC)
- ChaCha20 quarter-round (~120 LOC, if not in stdlib)
- Keccak sponge for SHAKE256 (~300 LOC, if not in stdlib)

None of these are research problems - they're well-specified algorithms with test vectors.

## File Mapping

```
moxie/
  ratio/ratio.mx
  epoch/epoch.mx
  crypto/
    hamadryad.mx        <- hamadryad.go (no hash.go, no amd64)
    gnarl_hash.mx       <- gnarl_hash.go (no amd64)
    gnarl_wire.mx       <- gnarl_wire.go
    ctr.mx              <- ctr.go (+ inline chacha20)
    ntt.mx              <- ntt.go
    ntt27.mx            <- ntt27.go
    params.mx           <- params.go
    gnarl/
      field.mx          <- field.go + field_generic.go (merged)
      scalar.mx         <- scalar.go (native 4-limb arith)
      torus.mx          <- torus.go (pruned)
      exp.mx            <- exp.go
      gnarl.mx          <- gnarl.go (no big.Int)
    ring/
      ring.mx           <- ring.go
      ntt.mx            <- ntt.go (array cache)
      sample.mx         <- sample.go
      kem.mx             <- kem.go
      gpv.mx            <- gpv.go
      gaussian.mx       <- gaussian.go
      he.mx             <- he.go
      keyagg.mx         <- keyagg.go
      mpc.mx            <- mpc.go
      malleable.mx      <- malleable.go
      recognizer.mx     <- recognizer.go
      sis.mx            <- sis.go
    shake256.mx         <- new (if needed): Keccak sponge
    chacha20.mx         <- new (if needed): RFC 8439 ChaCha20
```