math/SUBSTRATE.md at main

mirror of https://github.com/luxfi/math.git synced 2026-07-27 03:38:49 +00:00

Files

T

Hanzo AI e018a9c3d1 LP-107 Phase 2: math substrate — params, backend, codec, modarith,

ntt, poly, rns, sample

Eight pure-Go reference packages that own the canonical semantics of
every cryptographic-math primitive Lux protocols share. Backends
(AVX2 / NEON / cgo+C++ / CUDA / Metal / WGSL) plug in behind the
substrate; KATs gate byte-equality across them.

Packages added:

* params/    — ModulusID, NTTParamID, FHEParamID, PulsarParamID,
               HashSuiteID, BackendID; KATHeader required-fields
               schema. Stable string IDs; renaming is a breaking
               change.

* backend/   — Policy enum (PureGo / NativeCPU / GPUPreferred /
               GPURequired); Resolve(policy, registered) returns the
               BackendID per LP-107's fallback chain. GPURequired
               returns ErrUnavailable when no GPU backend is
               registered.

* codec/     — Bounded readers (closes lattice issues #2 + #4 DoS
               class permanently). Limits + LimitError + Reader.
               ReadUint{16,32,64}Slice all reject the 70T-element
               attack input before allocating; depth + frame-bytes
               caps; iterative (no recursion). Regression test
               TestReadUint64Slice_RejectsHugeLength encodes the
               original lattice issue #4 input.

* modarith/  — Modulus type with QInv, R2, Barrett constants
               (computed via math/big once per modulus). AddMod /
               SubMod / MulMod (Div64 reference path). MontMulMod /
               ToMontgomery / FromMontgomery cross-checked against
               MulMod across 100 random Pulsar-Q pairs.
               ReductionMode enum byte-equal to lattice/types.

* ntt/       — Service + Backend interface; pure-Go backend
               delegates to lattice/v7/ring.SubRing.NTT/INTT (the
               canonical Lattigo-derived Montgomery NTT body — no
               re-implementation, just dispatch). Round-trip +
               batch + determinism tests on Pulsar N=256.

* poly/      — Add / Sub / ScalarMul / PointwiseMul (NTT-domain) /
               negacyclic Mul (NTT round-trip). Composes modarith +
               ntt; no lower-level reach.

* rns/       — Basis(Moduli, Name) for FHE RNS chains. Single +
               two-prime construction validated; rejects even moduli.
               Phase 3 will add basis-extension and modulus-switching.

* sample/    — Uniform (rejection sampling, mask-and-retry); Ternary
               (density + sign byte); CenteredBinomial (popcount
               difference); DiscreteGaussianRejection (6-sigma cutoff).
               All take an io.Reader so callers can KAT-replay.

Architecture invariants enforced in package docs:

  - Go is the canonical semantic reference.
  - Backend selection MUST NOT alter transcript bytes (consensus
    paths default to PolicyPureGo / PolicyNativeCPU).
  - No unbounded codec readers anywhere near wire formats.
  - No re-implementation: where lattice/v7/ring already owns the
    canonical body, we delegate, not fork.
  - One ID space; renaming is a breaking change.

Test posture: 8/8 packages green via `GOWORK=off go test ./...`.

Phases 3-7 (queued):
  3. lattice consumes math
  4. pulsar consumes lattice + math
  5. fhe consumes math
  6. luxcpp/crypto/math native backend mirror
  7. cross-runtime KAT release gate

See SUBSTRATE.md for the full posture and migration plan; full LP at
~/work/lux/lps/LP-107-lux-math-substrate.md.

2026-05-04 09:28:23 -07:00

78 lines

4.7 KiB

Markdown

Raw Permalink Blame History

 # Lux Math — High-Performance Cryptographic Substrate
 LP-107 reference implementation. The `luxfi/math` Go module owns the
 canonical Go reference for every cryptographic-math primitive that
 Lux protocols share, with a backend interface that lets native CPU
 (AVX2 / NEON / cgo+C++) and GPU (CUDA / Metal / WGSL) realizations
 drop in behind it.
 ## Substrate packages (LP-107 Phase 2)
 | Package | Owns | Status |
 |---|---|---|
 | [`params`](./params/) | ModulusID, NTTParamID, FHEParamID, PulsarParamID, HashSuiteID, BackendID; KAT header schema | ✅ pure-Go reference, validated |
 | [`backend`](./backend/) | Policy enum (PureGo / NativeCPU / GPUPreferred / GPURequired), Resolve() dispatch | ✅ pure-Go reference, validated |
 | [`codec`](./codec/) | Bounded readers (closes lattice issues #2 + #4 DoS class) | ✅ pure-Go reference, validated |
 | [`modarith`](./modarith/) | Barrett, Montgomery, AddMod / SubMod / MulMod, ReductionMode | ✅ pure-Go reference, validated |
 | [`ntt`](./ntt/) | NTT Service + Backend interface; pure-Go backend delegates to `lattice/v7/ring.SubRing.NTT/INTT` | ✅ pure-Go reference, validated |
 | [`poly`](./poly/) | Polynomial Add / Sub / ScalarMul / PointwiseMul / negacyclic Mul (via NTT round-trip) | ✅ pure-Go reference, validated |
 | [`rns`](./rns/) | RNS Basis primitives (single + multi-prime towers) | ✅ pure-Go reference, validated |
 | [`sample`](./sample/) | Uniform / Ternary / CenteredBinomial / DiscreteGaussianRejection samplers | ✅ pure-Go reference, validated |
 ## Architecture invariants
 * **Go is the canonical semantic reference.** C++ / GPU backends
   realize the same contract; KATs prove byte-equality.
 * **Backend selection MUST NOT alter transcript bytes** for consensus
   paths. Default policy is `PolicyPureGo` or `PolicyNativeCPU`.
 * **No unbounded codec readers.** Every wire-format decode goes
   through `codec.Reader`; the `ReadUint64Slice` recursion + OOM bug
   classes are fixed centrally.
 * **No re-implementation.** Where the canonical impl already lives
   in `luxfi/lattice` (Lattigo-derived NTT/Montgomery), the substrate
   delegates rather than fork. LP-107 Phase 3 inverts the dependency.
 * **One ID space.** `params.ModulusID` / `NTTParamID` / etc. are
   stable strings; renaming is a breaking change. KATs key off them.
 ## Test posture
 ```bash
 GOWORK=off go test ./...
 ```
 | Package | Tests |
 |---|---|
 | `params` | ModulusID/NTTParamID/FHEParamID/PulsarParamID/HashSuiteID/BackendID validation; KATHeader required-fields |
 | `backend` | Policy String + Validate; Resolve fallback chain (PureGo / NativeCPU / GPUPreferred / GPURequired); GPU-required-no-GPU returns ErrUnavailable |
 | `codec` | Limits validation; Uvarint round-trip; happy-path uint16/32/64 slice reads; **regression test for lattice issue #4 (70T-element attack input rejected with LimitError)**; depth + frame-bytes caps |
 | `modarith` | NewModulus rejects zero/even; QInv satisfies q\*QInv ≡ -1 mod 2^64; AddMod / SubMod / MulMod cross-checked vs math/big across 1000 random pairs; Montgomery round-trip + 100 randomized MontMul-vs-MulMod cross-checks; LazyModeFits |
 | `ntt` | Params validation; PureGo round-trip on Pulsar N=256; batch round-trip; **determinism across two Service instances** |
 | `poly` | Add+Sub round-trip; ScalarMul; **negacyclic Mul** via NTT (a=2 \* b=3 → coefficient 0 = 6, others = 0) |
 | `rns` | Basis construction (single-prime + two-prime); rejection of empty + even moduli |
 | `sample` | Uniform determinism (same seed → byte-equal output); Ternary distribution + balance; CenteredBinomial range-bounded; DiscreteGaussianRejection 1000-sample range |
 ## Migration plan (LP-107 Phases 3-7)
 * **Phase 3 — `lattice` consumes `math`.** `lattice/ring/SubRing.NTT`
   rewires to delegate to `math/ntt`. Pulsar / Lens / FHE see no
   source change at first; v0.2.0 deprecates direct `lattice/ring`
   imports for new code.
 * **Phase 4 — `pulsar` consumes `lattice` + `math`.** Drop ad-hoc
   Montgomery code; consume `math/modarith`.
 * **Phase 5 — `fhe` consumes `math`.** Share NTT/RNS primitives with
   Pulsar where parameter-compatible.
 * **Phase 6 — `luxcpp/crypto/math`** mirrors the Go module structure
   and becomes the native backend for `math/ntt`, `math/poly`,
   `math/sample`. KATs gate every byte across runtimes.
 * **Phase 7 — Cross-runtime KAT release gate.** Go math KAT → C++
   verifies; C++ math KAT → Go verifies; GPU math KAT → CPU verifies.
 ## Design references
 * [`LP-107`](../lps/LP-107-lux-math-substrate.md) — full spec.
 * [`lattice/v7/ring`](https://github.com/luxfi/lattice/tree/main/ring)
   — canonical Lattigo-derived NTT/Montgomery body that this module
   delegates to.
 * [`luxcpp/crypto/corona`](https://github.com/luxcpp/crypto/tree/main/corona)
   — native C++ Montgomery NTT that Phase 6 mirrors as `math` C++.

78 lines 4.7 KiB Markdown Raw Permalink Blame History

78 lines

4.7 KiB

Markdown

Raw Permalink Blame History