# Hamadryad Math: Standard Notation to Codebase Mapping

The five formulae worth drilling by hand, with their precise hamadryad equivalents pinned to the actual codebase.

---

## 1. Ax = 0 (mod q), ||x|| <= beta --- SIS

**Standard form:** Given random A in R_q, find short x with A*x = 0. The whole game.

**Hamadryad equivalent** in `crypto/ring/sis.go:174-204`:

```go
// Compress computes f_A(x) = sum( a_i * x_i ) mod q
// x_i have binary (0/1) coefficients --- bounded norm by construction
for i := range sp.M {
    NTT(poly)
    MulAdd(acc, poly, h.keys[i])   // acc += a_i * x_i
}
INTT(acc)
```

The hash IS the SIS compression function. Collision = finding two short x, x' with f_A(x) = f_A(x'), which means f_A(x - x') = 0 with ||(x - x')|| <= 2 (binary inputs).

Concrete instance: R_q = Z_257[x]/(x^64+1), m=16 key polynomials, 1024-bit input, 448-bit output. The SIS norm bound beta = 1 (binary coefficients).

The GPV signature scheme in `crypto/ring/gpv.go:220-228` uses the dual SIS structure directly:

```go
// b = -a*r (mod q)
// [a | b] * [r; 1] = 0  --- r is a short kernel vector of the SIS instance
ar := MulPointwise(a, rNTT)
b := Neg(ar)
```

The trapdoor r has ||r||_inf <= 1 (ternary). The signing key is literally a short SIS solution.

---

## 2. ||x1 + x2|| <= ||x1|| + ||x2|| --- Triangle Inequality

**Standard:** Why aggregation grows norms.

**Hamadryad equivalent** in `crypto/ring/keyagg.go:59-62` and `he.go:244-250`:

```go
// Aggregate: B_agg = sum(B_i)
bAgg := ref.B.Clone()
for i := 1; i < len(pks); i++ {
    bAgg = Add(bAgg, pks[i].B)   // polynomial Add is coefficient-wise mod q
}
```

Each B_i = a*s_i + 2*e_i. After summing k keys, the aggregate error is e_agg = sum(e_i). By triangle inequality: ||e_agg||_inf <= k * max(||e_i||_inf).

For HE operations, noise tracking is explicit in `he.go:248`:

```go
NoiseEstimate: a.NoiseEstimate + b.NoiseEstimate,      // linear growth for add
// ...
NoiseEstimate: a.NoiseEstimate * b.NoiseEstimate * 4,   // quadratic for multiply
```

The decryption threshold is q/4. When ||noise|| exceeds q/4, the bit flips. The `NoiseEstimate` field tracks this throughout the computation.

---

## 3. beta_d = beta * (sqrt(k))^d --- Tree Norm Growth

**Standard:** Depth-d circuit over k participants, how the norm compounds. The proposal in one line.

**Hamadryad equivalent** -- the noise budget arithmetic is spread across `he.go` and `ring.go:84-108`:

```
HE64: n=64, q=10000769, eta=1

Fresh noise:          ~2 * n * eta = 128
After addition:       128 + 128 = 256            (linear, triangle inequality)
After multiplication: 4 * n * 128^2 = 4,194,304  (quadratic, tensor product)
Decryption threshold: q/2 = 5,000,384
```

For k-party aggregation at depth d=1 (from `keyagg.go:21-22`):

```
k=10 participants, aggregate noise ~ k * eta * sqrt(n) ~ 10 * 1 * 8 = 80
Threshold: q/4 ~ 2,500,192
Headroom: 2,500,192 / 80 ~ 31,000x
```

The tree structure maps to the circuit depth. Depth-0 = just aggregation (linear sum). Depth-1 = one AND gate (one multiplication). The HE64 ring was specifically parameterized for exactly one level of multiplication (`ring.go:95-98` spells this out explicitly). The (sqrt(k))^d growth factor is why deeper circuits need either larger q (more noise budget) or modulus switching.

---

## 4. b = As + e (mod q) --- LWE

**Standard:** The foundation everything stands on.

**Hamadryad equivalent** in `crypto/ring/kem.go:91-108` (KEM keygen):

```go
a := UniformPolyFrom(p, rng)           // a <- uniform in R_q
NTT(a)
s := CBDPolyFrom(p, kp.Eta1, rng)      // s <- CBD_eta (secret, short)
NTT(s)
e := CBDPolyFrom(p, kp.Eta1, rng)      // e <- CBD_eta (error, short)
NTT(e)
b := MulPointwise(a, s)                 // b = a*s
b = Add(b, e)                           //     + e  (mod q, in NTT domain)
```

The BGV variant in `he.go:84-102` scales the error by 2 for the plaintext modulus t=2:

```go
e := CBDPolyFrom(p, kp.Eta1, rng)
e = ScalarMul(e, 2)        // e <- 2*e  (BGV structure: noise is even)
NTT(e)
b := MulPointwise(a, s)    // b = a*s + 2*e
b = Add(b, e)
```

Same equation -- b = a*s + e -- but the factor of 2 is what makes BGV work: all noise terms are even, so the plaintext bit sits in the LSB and can be recovered by taking the result mod 2.

The CCA2 KEM encryption in `kem.go:121-154` is the dual:

```go
u = a*r + e1             // "re-encryption" with fresh randomness r
v = b*r + e2 + encode(m)
// Decrypt: v - s*u = e2 + r*e - s*e1 + encode(m) = noise + message
```

---

## 5. f * g = INTT(NTT(f) @ NTT(g)) --- NTT Pipeline

**Standard:** The NTT pipeline. The EVM bottleneck.

**Hamadryad equivalent** in `crypto/ring/ntt.go:205-220`:

```go
func Mul(a, b *Poly) *Poly {
    if a.isNTT && b.isNTT {
        return MulPointwise(a, b)   // already in NTT form, just pointwise
    }
    aNTT := a.Clone()
    bNTT := b.Clone()
    NTT(aNTT)                       // forward NTT
    NTT(bNTT)                       // forward NTT
    c := MulPointwise(aNTT, bNTT)   // pointwise multiplication (@ operator)
    INTT(c)                          // inverse NTT
    return c
}
```

The NTT itself (`ntt.go:119-158`) is a negacyclic Cooley-Tukey butterfly with precomputed twiddle factors (psi^i for i in [0, 2n), where psi is a primitive 2n-th root of unity). The inverse (`ntt.go:163-203`) is Gentleman-Sande. Both are zero-allocation on the hot path.

### Concrete Rings

| Ring | n | q | psi | Used for |
|------|---|---|-----|----------|
| Hamadryad | 64 | 257 | 9 | SWIFFT hash (SIS) |
| HE64 | 64 | 10,000,769 | 6,028,202 | BGV homomorphic encryption |
| Falcon-512 | 512 | 12,289 | 49 | GPV signatures, KEM |
| Falcon-1024 | 1,024 | 12,289 | 1,945 | GPV signatures (256-bit) |
| NewHope-256 | 256 | 7,681 | 4,055 | KEM alternative |

### EVM Gas Cost Estimation

The NTT is O(n log n) multiplications mod q. For n=64 (hamadryad/HE64) that's 64*6 = 384 mulmod operations per transform. Three transforms per polynomial multiplication (NTT, NTT, INTT) plus n pointwise muls = 3*384 + 64 = 1,216 mulmod operations total.

Each BGV multiplication (`HEMul`) does ~6 polynomial multiplications plus relinearization, so roughly 7,000-10,000 mulmod operations per homomorphic AND gate. That's the number that matters for EVM gas cost estimation.

---

## The Bethe Lattice Connection

There are two layers in this system and they are not the same mathematical object, but they are not unrelated either. The ring R_q = Z_q[x]/(x^n+1) is the local algebra -- the arithmetic each participant performs. The Bethe lattice is the global topology -- the shape of how participants compose their local operations into aggregate results.

The interface between them is the norm budget.

When k parties aggregate keys (formula #2), the noise grows as ||e_agg|| <= k * ||e_i||. When a depth-d circuit chains homomorphic gates (formula #3), the norm compounds as beta_d = beta * (sqrt(k))^d. These are statements about propagation through a tree -- how local bounded operations compose into a global result without the norms exploding. That IS the Bethe lattice coordination constraint: every node has bounded degree k, information propagates through the tree, and the system only works if the accumulated quantity (noise, in crypto; state, in dendrite) stays within threshold at every level.

The Bethe lattice doesn't live in the polynomial ring. It lives in the protocol topology -- the multi-party computation graph, the aggregation tree, the circuit structure. The ring is what each node computes. The tree is how they compose. The norm budget is the contract between the two: each node promises its output is short, the tree structure guarantees the aggregate stays below the decryption threshold.

This is the path nobody else has taken. Standard lattice cryptography treats the aggregation topology as an afterthought -- pick your ring, prove your reduction, bolt on a threshold protocol. The dendrite design came at it backwards: the tree coordination structure was primary (crystal growth, bounded propagation), and the ring arithmetic was chosen to fit inside it. The result is that the norm budget isn't an external constraint bolted onto the scheme -- it's the design parameter the whole system was built around.

### Why Trinary Matters

The Gnarl signature scheme operates over Z_271[x]/(x^27+1) with balanced ternary coefficients {-1, 0, 1}. This is not a cosmetic choice. Ternary encoding collapses the representation:

| | BIP-340 / secp256k1 | Gnarl |
|-----|----:|-----:|
| Secret key | 32 bytes | 27 bytes |
| Public key | 32 bytes | 27 bytes |
| Signature | 64 bytes | 54 bytes |
| Pubkey + sig | 96 bytes | 81 bytes (-16%) |

And the speed advantage is not marginal:

| Operation | Gnarl | libsecp256k1 (C) | btcec (Go) |
|-----------|------:|------------------:|-----------:|
| KeyGen | 7.2 us | 20 us | 76 us |
| Sign | 10.7 us | 20 us | 231 us |
| Verify | 40.5 us | 40 us | 158 us |

Gnarl keygen is 2.8x faster than the C reference implementation of secp256k1 used by Bitcoin Core. Signing is 1.8x faster. Verification is at parity. Against the pure-Go secp256k1 (btcec), it's 10x-21x faster. This is a Go implementation with hand-written AMD64 assembly for the Montgomery multiplication hot path -- not a C library with decades of optimization behind it.

The KEM (key encapsulation / key exchange) uses the larger Falcon-512 ring (n=512, q=12289) and is slower -- that's standard Ring-LWE, comparable to Kyber/ML-KEM. But key exchange happens once per session. Signing and verification happen per transaction. The operations that dominate on-chain cost are the ones where Gnarl is fastest.

### The EVM Path

If aggregation works over the Gnarl signature scheme -- composing k signatures into one via the Bethe lattice coordination structure -- then the on-chain verification story becomes:

1. **Generate proofs off-chain.** Aggregation, partial decryption, homomorphic evaluation all happen outside the VM. The norm budget math (formulas #2 and #3) guarantees correctness as long as participants stay within their coordination bound.

2. **Verify on-chain.** A single aggregate signature verification: one NTT multiply (27 coefficients, q=271), one hash comparison. The 27-byte public key and 54-byte signature are the smallest in any post-quantum scheme. The verification is a handful of multiplications in a tiny ring -- orders of magnitude less computation than pairing-based or elliptic curve verification.

3. **The encoding advantage compounds.** Every byte saved in signature size is a byte saved in calldata. Every mulmod saved in verification is gas saved. At n=27, q=271, the NTT is 27 * log2(27) ~ 135 mulmod operations per transform. Compare to BN254 pairing verification at ~500,000 gas. The ratio is not close.

The Bethe lattice is the aggregation topology. The trinary ring is the local algebra. The norm budget is the bridge. Off-chain composition, on-chain verification, smallest possible encoding. That's the proposal.

---

## The Endgame

Veni, vidi, vici, izcheznih.

Show up with a working post-quantum aggregation scheme that nobody else has. Demonstrate it runs faster than the thing it replaces. Show the code, show the math, show the benchmarks. Collect enough stablecoin to disappear back into the forest. The mysterious shadow cryptographer who walked in from the trees, dropped a lattice on the table, and vanished.