mirror of
https://github.com/luxfi/math.git
synced 2026-09-24 00:25:16 +00:00
zeekay
c9bc60da0e
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.
128 lines
3.0 KiB
Go
128 lines
3.0 KiB
Go
// Copyright (c) 2026 Lux Industries Inc.
|
|
// SPDX-License-Identifier: BSD-3-Clause
|
|
|
|
package ntt
|
|
|
|
import (
|
|
"math/rand/v2"
|
|
"testing"
|
|
|
|
"github.com/luxfi/math/backend"
|
|
"github.com/luxfi/math/params"
|
|
)
|
|
|
|
// PulsarN256 — Pulsar/LP-073 NTT instance.
|
|
var PulsarN256 = &Params{
|
|
N: 256,
|
|
Q: 0x1000000004A01,
|
|
ID: params.NTTPulsarN256,
|
|
}
|
|
|
|
func TestParams_Validate(t *testing.T) {
|
|
if err := PulsarN256.Validate(); err != nil {
|
|
t.Errorf("Pulsar N=256: %v", err)
|
|
}
|
|
bad := &Params{N: 0, Q: 7, ID: params.NTTPulsarN256}
|
|
if err := bad.Validate(); err == nil {
|
|
t.Error("N=0: no error")
|
|
}
|
|
bad2 := &Params{N: 257, Q: 7, ID: params.NTTPulsarN256}
|
|
if err := bad2.Validate(); err == nil {
|
|
t.Error("N=257 (not pow2): no error")
|
|
}
|
|
notNTT := &Params{N: 256, Q: 13, ID: params.NTTPulsarN256}
|
|
if err := notNTT.Validate(); err == nil {
|
|
t.Error("not NTT-friendly: no error")
|
|
}
|
|
}
|
|
|
|
func TestService_PureGo_RoundTrip(t *testing.T) {
|
|
s, err := NewService(PulsarN256, backend.PolicyPureGo)
|
|
if err != nil {
|
|
t.Fatalf("NewService: %v", err)
|
|
}
|
|
if s.Backend() != params.BackendPureGo {
|
|
t.Errorf("Backend = %s, want %s", s.Backend(), params.BackendPureGo)
|
|
}
|
|
|
|
r := rand.New(rand.NewPCG(0xdeadbeef, 0x12345678))
|
|
N := int(PulsarN256.N)
|
|
a := make([]uint64, N)
|
|
for i := range a {
|
|
a[i] = r.Uint64() % PulsarN256.Q
|
|
}
|
|
saved := make([]uint64, N)
|
|
copy(saved, a)
|
|
|
|
if err := s.Forward(a, 1); err != nil {
|
|
t.Fatalf("Forward: %v", err)
|
|
}
|
|
if err := s.Inverse(a, 1); err != nil {
|
|
t.Fatalf("Inverse: %v", err)
|
|
}
|
|
for i := range a {
|
|
if a[i] != saved[i] {
|
|
t.Fatalf("round-trip [%d]: %d != %d", i, a[i], saved[i])
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestService_BatchRoundTrip(t *testing.T) {
|
|
s, err := NewService(PulsarN256, backend.PolicyPureGo)
|
|
if err != nil {
|
|
t.Fatalf("NewService: %v", err)
|
|
}
|
|
N := int(PulsarN256.N)
|
|
const batch = 8
|
|
a := make([]uint64, batch*N)
|
|
r := rand.New(rand.NewPCG(0xfeedface, 1))
|
|
for i := range a {
|
|
a[i] = r.Uint64() % PulsarN256.Q
|
|
}
|
|
saved := make([]uint64, batch*N)
|
|
copy(saved, a)
|
|
|
|
if err := s.Forward(a, batch); err != nil {
|
|
t.Fatalf("Forward: %v", err)
|
|
}
|
|
if err := s.Inverse(a, batch); err != nil {
|
|
t.Fatalf("Inverse: %v", err)
|
|
}
|
|
for i := range a {
|
|
if a[i] != saved[i] {
|
|
t.Fatalf("batch round-trip [%d]: %d != %d", i, a[i], saved[i])
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestPureGo_Determinism_AcrossInvocations(t *testing.T) {
|
|
// Same input -> identical output across two Service instances.
|
|
a := make([]uint64, PulsarN256.N)
|
|
r := rand.New(rand.NewPCG(0xa5a5a5a5, 0))
|
|
for i := range a {
|
|
a[i] = r.Uint64() % PulsarN256.Q
|
|
}
|
|
b := make([]uint64, len(a))
|
|
copy(b, a)
|
|
|
|
s1, err := NewService(PulsarN256, backend.PolicyPureGo)
|
|
if err != nil {
|
|
t.Fatalf("NewService 1: %v", err)
|
|
}
|
|
s2, err := NewService(PulsarN256, backend.PolicyPureGo)
|
|
if err != nil {
|
|
t.Fatalf("NewService 2: %v", err)
|
|
}
|
|
if err := s1.Forward(a, 1); err != nil {
|
|
t.Fatalf("Forward 1: %v", err)
|
|
}
|
|
if err := s2.Forward(b, 1); err != nil {
|
|
t.Fatalf("Forward 2: %v", err)
|
|
}
|
|
for i := range a {
|
|
if a[i] != b[i] {
|
|
t.Fatalf("non-deterministic [%d]: %d != %d", i, a[i], b[i])
|
|
}
|
|
}
|
|
}
|