The five formulae worth drilling by hand, with their precise hamadryad equivalents pinned to the actual codebase.
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:
// 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 fA(x) = fA(x'), which means f_A(x - x') = 0 with ||(x - x')|| <= 2 (binary inputs).
Concrete instance: Rq = Z257[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:
// 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.
Standard: Why aggregation grows norms.
Hamadryad equivalent in crypto/ring/keyagg.go:59-62 and he.go:244-250:
// 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 Bi = a*si + 2e_i. After summing k keys, the aggregate error is e_agg = sum(e_i). By triangle inequality: ||e_agg||_inf <= k max(||ei||inf).
For HE operations, noise tracking is explicit in he.go:248:
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.
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.
Standard: The foundation everything stands on.
Hamadryad equivalent in crypto/ring/kem.go:91-108 (KEM keygen):
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:
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:
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
Standard: The NTT pipeline. The EVM bottleneck.
Hamadryad equivalent in crypto/ring/ntt.go:205-220:
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.
| 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 |
The NTT is O(n log n) multiplications mod q. For n=64 (hamadryad/HE64) that's 646 = 384 mulmod operations per transform. Three transforms per polynomial multiplication (NTT, NTT, INTT) plus n pointwise muls = 3384 + 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.
There are two layers in this system and they are not the same mathematical object, but they are not unrelated either. The ring Rq = Zq[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 ||eagg|| <= k * ||ei||. 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.
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.
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:
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.
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.