1 // Package crypto — Hamadryad: SWIFFT-derived lattice hash for kismet consensus.
2 //
3 // Hamadryad disperses an input through the NTT lattice into spectral components,
4 // then narrows the spectrum via per-coefficient modular projection. Two
5 // bandwidths of the same dispersal yield the full and local output modes.
6 //
7 // It is a fork of SWIFFT (Lyubashevsky, Micciancio, Peikert, Rosen 2008) —
8 // the only hash family with provable collision resistance reducible to
9 // worst-case ideal lattice problems (SVP).
10 //
11 // Two output modes share a single computation:
12 //
13 // Hamadryad (448-bit / 56 bytes): canonical transaction identity.
14 // 64 ring coefficients × 7 bits each = 448 bits.
15 // Obtained by reducing each Z_257 coefficient mod 128.
16 // Birthday bound: 2^224. Inversion bound: 2^448 (lattice).
17 //
18 // Shard (48-bit / 6 bytes): epoch-scoped transaction address.
19 // Extracted from the Hamadryad hash. Collision-safe within any single
20 // epoch's transaction population (birthday bound 2^24 ≈ 16M).
21 // Domain-separated by the epoch parent hash in the preimage.
22 //
23 // Architecture (SWIFFT core):
24 //
25 // Ring: R = Z_p[x]/(x^n + 1), with n=64, p=257
26 // Input: m·n = 16·64 = 1024 bits
27 // Fixed keys: a_1 … a_m ∈ R (random, public, pre-computed in NTT form)
28 //
29 // Steps:
30 // 1. Partition input into m=16 polynomials x_i with n=64 binary coefficients
31 // 2. Forward NTT: X_i = NTT(x_i) over Z_257
32 // 3. Pointwise multiply: Y_i = A_i · X_i (A_i pre-stored in NTT form)
33 // 4. Sum: Y = Σ Y_i
34 // 5. Inverse NTT: y = INTT(Y)
35 // 6. Coefficient reduction: z_j = y_j mod 128 for j ∈ [0, 64)
36 // 7. Output: 64 × 7 bits = 448-bit Hamadryad hash
37 //
38 // Reduction rationale (576 → 448):
39 //
40 // Standard SWIFFT: 64 coefficients × ⌈log₂(257)⌉ = 64 × 9 = 576 bits
41 // GCF(448, 576) = 64 = n (ring dimension)
42 // 448 / 64 = 7 bits per coefficient → project Z_257 → Z_128
43 // 576 / 64 = 9 bits per coefficient → full Z_257
44 //
45 // This is a per-coefficient modular projection, not a bitstring truncation.
46 // Collisions in the reduced ring imply near-collisions in the full ring,
47 // whose hardness reduces to worst-case SVP in ideal lattices.
48 //
49 // Epoch binding:
50 //
51 // Input = epoch_parent_hash ‖ transaction_bytes
52 // The epoch parent hash (itself a 448-bit Hamadryad from the PoW leader)
53 // acts as a domain separator. Two identical transactions in different
54 // epochs produce different hashes. This is what makes the 48-bit Shard
55 // safe: collision resistance only needs to hold within a single epoch's
56 // population, not across the full history.
57 //
58 // Security:
59 //
60 // Birthday (collision): 2^224 (Hamadryad), 2^24 (Shard)
61 // Inversion (preimage): 2^448 (lattice hardness, Hamadryad)
62 // Provability: Collision resistance reduces to worst-case
63 // SVP on ideal lattices over Z[x]/(x^64 + 1).
64 // This is the distinguishing property of SWIFFT:
65 // no other hash family offers this guarantee.
66 //
67 // Parameters:
68 //
69 // n = 64 Ring dimension. Power of 2. Controls NTT size and output width.
70 // m = 16 Input components. Controls compression ratio and lattice dimension.
71 // p = 257 Ring modulus. Prime, p ≡ 1 (mod 128). Smallest such prime above 256.
72 // r = 128 Reduction modulus. 2^7. Per-coefficient projection target.
73 //
74 // The 48/64 ratio: 48 bits = 6 bytes = 8 hexagrams of address space.
75 // 64 = 2^6 = the number of I Ching hexagrams = the ring dimension n.
76 // The Shard is one hexagram per byte, six lines deep.
77 package crypto
78 79 import (
80 "crypto/rand"
81 "encoding/binary"
82 "fmt"
83 )
84 85 // Hamadryad ring parameters.
86 const (
87 // HamN is the ring dimension: degree of the cyclotomic polynomial x^n + 1.
88 // Must be a power of 2 for NTT and for x^n + 1 to be irreducible over Z.
89 HamN = 64
90 91 // HamM is the number of input polynomial components.
92 // Input size = HamM × HamN = 1024 bits.
93 // Lattice dimension for security proof = HamM × HamN = 1024.
94 HamM = 16
95 96 // HamP is the ring modulus. Prime, with HamP ≡ 1 (mod 2·HamN).
97 // This ensures primitive 2n-th roots of unity exist in Z_p for the NTT.
98 // 257 = 2^8 + 1, a Fermat prime. Arithmetic mod 257 is efficient.
99 HamP = 257
100 101 // HamR is the reduction modulus for the 448-bit output.
102 // Each coefficient is reduced: z_j = y_j mod HamR.
103 // 128 = 2^7, giving 7 bits per coefficient, 64 × 7 = 448 bits total.
104 HamR = 128
105 106 // HamInputBits is the total input size in bits.
107 HamInputBits = HamM * HamN // 1024
108 109 // HamFullBits is the full (unreduced) SWIFFT output size.
110 HamFullBits = HamN * 9 // 576
111 112 // HamBits is the reduced output size (canonical hash).
113 HamBits = HamN * 7 // 448
114 115 // HamBytes is the reduced output in bytes.
116 HamBytes = HamBits / 8 // 56
117 118 // ShardBits is the epoch-local address size.
119 ShardBits = 48
120 121 // ShardBytes is the epoch-local address in bytes.
122 ShardBytes = ShardBits / 8 // 6
123 )
124 125 // Hamadryad is a 448-bit (56-byte) canonical transaction identity.
126 // 64 ring coefficients reduced mod 128, packed at 7 bits each.
127 // Named for the tree nymph bonded to her tree — the signature
128 // is bonded to the Bethe lattice's constraint topology.
129 type Hamadryad [HamBytes]byte
130 131 // Shard is a 48-bit (6-byte) epoch-scoped transaction address.
132 // Extracted from a Hamadryad hash. Only unique within a single epoch.
133 // A leaf separated from the tree.
134 type Shard [ShardBytes]byte
135 136 // Disperse extracts the 48-bit Shard from a full 448-bit Hamadryad.
137 // Takes the first 6 bytes — the first 6 reduced ring coefficients
138 // packed into bytes, corresponding to the lowest-index evaluation
139 // points of the NTT.
140 func (p Hamadryad) Disperse() Shard {
141 var s Shard
142 copy(s[:], p[:ShardBytes])
143 return s
144 }
145 146 // hamKeys holds the m=16 fixed random polynomials a_1..a_m in NTT form.
147 // These are the public parameters of the hash family. Generated
148 // deterministically from a fixed seed for reproducibility.
149 var hamKeys [HamM][HamN]uint16
150 151 func init() {
152 // Ensure NTT lookup tables are ready before generating key polynomials.
153 // Go runs init functions in source file alphabetical order within a
154 // package, and "hamadryad.go" sorts before "ntt.go".
155 initNTTTables()
156 157 // Deterministic PRNG seeded with "hamadryad-swifft-v1" to generate
158 // the fixed key polynomials. The specific values don't matter for
159 // security — SWIFFT's proof holds for any random keys — but they
160 // must be consistent across all implementations.
161 //
162 // We use a simple xorshift64 seeded from the string bytes.
163 seed := uint64(0)
164 seedStr := []byte("hamadryad-swifft-v1-dendrite-kismet")
165 for i, b := range seedStr {
166 seed ^= uint64(b) << ((uint(i) * 7) % 64)
167 }
168 169 xorshift := func() uint64 {
170 seed ^= seed << 13
171 seed ^= seed >> 7
172 seed ^= seed << 17
173 return seed
174 }
175 176 for i := range HamM {
177 // Generate random polynomial in coefficient form.
178 var poly [HamN]uint16
179 for j := range HamN {
180 poly[j] = uint16(xorshift() % uint64(HamP))
181 }
182 // Store in NTT form for fast multiplication.
183 ntt64(&poly)
184 hamKeys[i] = poly
185 }
186 }
187 188 // hamInputBytes is the input block size in bytes (1024 bits = 128 bytes).
189 const hamInputBytes = HamInputBits / 8
190 191 // hamCompress computes one SWIFFT compression: 128 bytes → 64 coefficients in Z_257.
192 //
193 // The input block is split into m=16 polynomials of n=64 binary coefficients.
194 // Each polynomial is NTT-transformed, pointwise-multiplied with its fixed key,
195 // and the results are summed. The output is 64 coefficients in Z_257.
196 func hamCompress(block *[hamInputBytes]byte) [HamN]uint16 {
197 var acc [HamN]uint16 // accumulator in NTT domain
198 199 for i := range HamM {
200 // Extract 64-bit (8-byte) chunk → 64 binary coefficients.
201 var poly [HamN]uint16
202 base := i * (HamN / 8) // 8 bytes per polynomial
203 for j := range HamN {
204 byteIdx := base + j/8
205 bitIdx := uint(j % 8)
206 if block[byteIdx]&(1<<bitIdx) != 0 {
207 poly[j] = 1
208 }
209 }
210 211 // Forward NTT.
212 ntt64(&poly)
213 214 // Pointwise multiply with fixed key and accumulate.
215 for j := range HamN {
216 product := mod257(int(poly[j]) * int(hamKeys[i][j]))
217 acc[j] = mod257(int(acc[j]) + int(product))
218 }
219 }
220 221 // Inverse NTT to get coefficients.
222 intt64(&acc)
223 224 return acc
225 }
226 227 // packCoeffs packs 64 Z_128 coefficients (7 bits each) into 56 bytes (448 bits).
228 // Bit packing is little-endian: coefficient 0 occupies bits 0-6, coefficient 1
229 // occupies bits 7-13, etc.
230 func packCoeffs(coeffs [HamN]uint16) Hamadryad {
231 var out Hamadryad
232 bitPos := 0
233 for _, c := range coeffs {
234 v := c % HamR // reduce mod 128 → 7 bits
235 for b := range 7 {
236 if v&(1<<uint(b)) != 0 {
237 byteIdx := bitPos / 8
238 bitIdx := uint(bitPos % 8)
239 out[byteIdx] |= 1 << bitIdx
240 }
241 bitPos++
242 }
243 }
244 return out
245 }
246 247 // unpackCoeffs unpacks a Hamadryad back into 64 Z_128 coefficients.
248 func unpackCoeffs(p Hamadryad) [HamN]uint16 {
249 var coeffs [HamN]uint16
250 bitPos := 0
251 for i := range HamN {
252 var v uint16
253 for b := range 7 {
254 byteIdx := bitPos / 8
255 bitIdx := uint(bitPos % 8)
256 if p[byteIdx]&(1<<bitIdx) != 0 {
257 v |= 1 << uint(b)
258 }
259 bitPos++
260 }
261 coeffs[i] = v
262 }
263 return coeffs
264 }
265 266 // Hash computes the Hamadryad hash of an arbitrary-length message.
267 //
268 // For messages longer than 128 bytes (the SWIFFT block size), we use
269 // a Merkle-Damgård construction: each block is compressed with the
270 // previous block's output fed into the next block's input as chaining.
271 //
272 // The final block is padded with the message length (8 bytes, LE) to
273 // prevent length-extension and ensure distinct inputs produce distinct hashes.
274 func Hash(msg []byte) Hamadryad {
275 // Chaining value starts at zero.
276 var chain [HamN]uint16
277 278 // Process full blocks. Each block: 128 bytes input.
279 // We reserve space in each block for chaining: the first HamBytes (56)
280 // bytes carry the chaining value, leaving 72 bytes for message data.
281 // But this reduces throughput. Instead, XOR the chain into the output.
282 //
283 // Simpler Merkle-Damgård: process 128-byte blocks, XOR chain into
284 // each block's output coefficients.
285 286 // Pad message: append 0x80, then zeros, then 8-byte LE length.
287 // Ensure at least one full block after padding.
288 padded := make([]byte, len(msg))
289 copy(padded, msg)
290 padded = append(padded, 0x80)
291 292 // Pad to next multiple of hamInputBytes, leaving 8 bytes for length.
293 for (len(padded)+8)%hamInputBytes != 0 {
294 padded = append(padded, 0)
295 }
296 297 // Append message length in bits as 8-byte LE.
298 var lenBuf [8]byte
299 binary.LittleEndian.PutUint64(lenBuf[:], uint64(len(msg))*8)
300 padded = append(padded, lenBuf[:]...)
301 302 // Process each 128-byte block.
303 for off := 0; off < len(padded); off += hamInputBytes {
304 var block [hamInputBytes]byte
305 copy(block[:], padded[off:off+hamInputBytes])
306 307 result := hamCompress(&block)
308 309 // XOR-combine with chain (coefficient-wise addition mod 257).
310 for j := range HamN {
311 chain[j] = mod257(int(chain[j]) + int(result[j]))
312 }
313 }
314 315 // Reduce each coefficient mod 128 and pack.
316 return packCoeffs(chain)
317 }
318 319 // HashValue computes the Hamadryad hash of an arbitrary Go value.
320 // Replaces the old SHA-256 based hashValue function.
321 func HashValue(v any) Hamadryad {
322 data := []byte(fmt.Sprintf("%v", v))
323 return Hash(data)
324 }
325 326 // Sum returns a new Hamadryad that is the coefficient-wise sum (mod 128)
327 // of two Hamadryad hashes. Useful for domain separation and chaining.
328 func (p Hamadryad) Sum(other Hamadryad) Hamadryad {
329 a := unpackCoeffs(p)
330 b := unpackCoeffs(other)
331 var result [HamN]uint16
332 for i := range HamN {
333 result[i] = (a[i] + b[i]) % HamR
334 }
335 return packCoeffs(result)
336 }
337 338 // IsZero reports whether the Hamadryad hash is all zeros.
339 func (p Hamadryad) IsZero() bool {
340 for _, b := range p {
341 if b != 0 {
342 return false
343 }
344 }
345 return true
346 }
347 348 // RandomHamadryad generates a cryptographically random Hamadryad value.
349 // Used for testing and key generation.
350 func RandomHamadryad() Hamadryad {
351 var p Hamadryad
352 if _, err := rand.Read(p[:]); err != nil {
353 panic(fmt.Sprintf("crypto/rand: %v", err))
354 }
355 return p
356 }
357