gnarl_hash.go raw
1 package crypto
2
3 // Trinary Hamadryad hash — SWIFFT-derived lattice hash for the Gnarl scheme.
4 //
5 // Ring: Z_271[x]/(x^27 + 1), with n=27 = 3^3, p=271, m=12 input polynomials.
6 //
7 // Three output tiers share a single computation:
8 //
9 // GnarlHash (243 bits / 31 bytes): canonical transaction identity.
10 // 27 ring coefficients × 9 bits each = 243 bits.
11 // Obtained by keeping each Z_271 coefficient in full (0..270, 9 bits).
12 // Birthday bound: 2^121.5. Inversion bound: 2^243 (lattice).
13 //
14 // GnarlMid (216 bits / 27 bytes): packet-field identity.
15 // 27 coefficients × 8 bits each = 216 bits.
16 // Obtained by reducing each Z_271 coefficient mod 243 (= 3^5).
17 // Byte-aligned. Birthday bound: 2^108.
18 //
19 // GnarlShard (54 bits / 7 bytes): epoch-scoped transaction address.
20 // 27 coefficients × 2 bits each = 54 bits (27 trits).
21 // Obtained by reducing each Z_271 coefficient mod 3.
22 // Birthday bound: 2^27.
23 //
24 // Architecture (SWIFFT core, trinary variant):
25 //
26 // Ring: R = Z_p[x]/(x^n + 1), with n=27, p=271
27 // Input: m·n = 12·27 = 324 bits = 41 bytes (last byte partial)
28 // Fixed keys: a_1 … a_m ∈ R (random, public, pre-computed in NTT form)
29 //
30 // Steps:
31 // 1. Partition input into m=12 polynomials x_i with n=27 binary coefficients
32 // 2. Forward NTT: X_i = NTT(x_i) over Z_271
33 // 3. Pointwise multiply: Y_i = A_i · X_i (A_i pre-stored in NTT form)
34 // 4. Sum: Y = Σ Y_i
35 // 5. Inverse NTT: y = INTT(Y)
36 // 6. Coefficient reduction to desired tier
37 // 7. Output: pack into bytes
38
39 import (
40 "crypto/rand"
41 "encoding/binary"
42 "fmt"
43 )
44
45 // Trinary Hamadryad constants.
46 const (
47 // GnarlM is the number of input polynomial components.
48 GnarlM = 12
49
50 // GnarlInputBits is the total input size in bits per block.
51 GnarlInputBits = GnarlM * GnarlN // 324
52
53 // gnarlInputBytes is the input block size in bytes (324 bits = 41 bytes, last byte partial).
54 gnarlInputBytes = (GnarlInputBits + 7) / 8 // 41
55
56 // GnarlHashBits is the full output size (27 × 9 = 243 bits).
57 GnarlHashBits = GnarlN * 9 // 243
58
59 // GnarlHashBytes is the full output in bytes (ceil(243/8) = 31).
60 GnarlHashBytes = (GnarlHashBits + 7) / 8 // 31
61
62 // GnarlMidBits is the mid-tier output (27 × 8 = 216 bits = 27 bytes).
63 GnarlMidBits = GnarlN * 8 // 216
64
65 // GnarlMidBytes = 27.
66 GnarlMidBytes = GnarlMidBits / 8 // 27
67
68 // GnarlShardBits is the shard output (27 × 2 = 54 bits).
69 GnarlShardBits = GnarlN * 2 // 54
70
71 // GnarlShardBytes = ceil(54/8) = 7.
72 GnarlShardBytes = (GnarlShardBits + 7) / 8 // 7
73
74 // GnarlMidR is the reduction modulus for the mid tier: 243 = 3^5.
75 GnarlMidR = 243
76
77 // GnarlShardR is the reduction modulus for the shard tier: 3.
78 GnarlShardR = 3
79 )
80
81 // GnarlHash is a 243-bit (31-byte) canonical transaction identity.
82 // 27 ring coefficients in full Z_271, packed at 9 bits each.
83 // 5 spare bits in the last byte are zeroed.
84 type GnarlHash [GnarlHashBytes]byte
85
86 // GnarlMid is a 216-bit (27-byte) packet-field identity.
87 // 27 coefficients reduced mod 243, packed at 8 bits each. Byte-aligned.
88 type GnarlMid [GnarlMidBytes]byte
89
90 // GnarlShard is a 54-bit (7-byte) epoch-scoped transaction address.
91 // 27 coefficients reduced mod 3, packed at 2 bits each (27 trits).
92 // 2 spare bits in the last byte are zeroed.
93 type GnarlShard [GnarlShardBytes]byte
94
95 // gnarlKeys holds the m=12 fixed random polynomials a_1..a_m in NTT form.
96 var gnarlKeys [GnarlM][GnarlN]uint16
97
98 // gnarlKeyBasis[i][k][j] = gnarlKeys[i][j] * NTT(e_k)[j] mod 271
99 // where e_k is the k-th standard basis vector (1 at position k, 0 elsewhere).
100 // This allows computing the full NTT-domain multiply-accumulate for a binary
101 // input polynomial by just summing the rows for set bits — no forward NTT needed.
102 //
103 // Padded to 32 elements per row (from 27) for AVX2 alignment: 32 uint16 = 64 bytes
104 // = 2 YMM registers. Extra 5 elements are always zero.
105 const gnarlBasisPad = 32
106
107 var gnarlKeyBasis [GnarlM][GnarlN][gnarlBasisPad]uint16
108
109 func init() {
110 // Ensure NTT tables are ready.
111 initNTT27Tables()
112
113 // Deterministic PRNG seeded with "gnarl-hamadryad-v1" to generate
114 // the fixed key polynomials.
115 seed := uint64(0)
116 seedStr := []byte("gnarl-hamadryad-v1-dendrite-trinary")
117 for i, b := range seedStr {
118 seed ^= uint64(b) << ((uint(i) * 7) % 64)
119 }
120
121 xorshift := func() uint64 {
122 seed ^= seed << 13
123 seed ^= seed >> 7
124 seed ^= seed << 17
125 return seed
126 }
127
128 for i := range GnarlM {
129 var poly [GnarlN]uint16
130 for j := range GnarlN {
131 poly[j] = uint16(xorshift() % uint64(GnarlP))
132 }
133 ntt27(&poly)
134 gnarlKeys[i] = poly
135 }
136
137 // Precompute basis tables: for each key i and basis vector k,
138 // compute gnarlKeys[i] * NTT(e_k) pointwise.
139 for i := range GnarlM {
140 for k := range GnarlN {
141 var ek [GnarlN]uint16
142 ek[k] = 1
143 ntt27(&ek) // NTT of the k-th basis vector
144 for j := range GnarlN {
145 gnarlKeyBasis[i][k][j] = mod271(uint32(gnarlKeys[i][j]) * uint32(ek[j]))
146 }
147 }
148 }
149 }
150
151 // gnarlCompress computes one SWIFFT compression: 41 bytes → 27 coefficients in Z_271.
152 //
153 // Uses precomputed basis tables to avoid all forward NTTs. Since input polynomials
154 // are binary (coefficients 0 or 1), NTT(x_i) = sum of NTT(e_k) for each set bit k.
155 // The pointwise multiply with the key is precomputed in gnarlKeyBasis[i][k][j].
156 func gnarlCompress(block *[gnarlInputBytes]byte) [GnarlN]uint16 {
157 // Accumulator in NTT domain (uint32, padded to 32 for AVX2 alignment).
158 var acc [gnarlBasisPad]uint32
159
160 gnarlAccumulate(&acc, &gnarlKeyBasis, block)
161
162 // Reduce accumulated values mod 271 and convert to uint16.
163 var result [GnarlN]uint16
164 for j := range GnarlN {
165 result[j] = mod271(acc[j])
166 }
167
168 // Inverse NTT to get coefficients.
169 intt27(&result)
170
171 return result
172 }
173
174 // gnarlAccumulateGeneric scans bits in block and accumulates basis table rows.
175 func gnarlAccumulateGeneric(acc *[gnarlBasisPad]uint32, basis *[GnarlM][GnarlN][gnarlBasisPad]uint16, block *[gnarlInputBytes]byte) {
176 for i := range GnarlM {
177 bitBase := i * GnarlN
178 for k := range GnarlN {
179 bitIdx := bitBase + k
180 byteIdx := bitIdx / 8
181 bitOff := uint(bitIdx % 8)
182 if byteIdx < gnarlInputBytes && block[byteIdx]&(1<<bitOff) != 0 {
183 row := &basis[i][k]
184 for j := range gnarlBasisPad {
185 acc[j] += uint32(row[j])
186 }
187 }
188 }
189 }
190 }
191
192 // packCoeffs243 packs 27 Z_271 coefficients (9 bits each) into 31 bytes (243 bits).
193 func packCoeffs243(coeffs [GnarlN]uint16) GnarlHash {
194 var out GnarlHash
195 bitPos := 0
196 for _, c := range coeffs {
197 v := c % GnarlP // ensure in [0, 270]
198 for b := range 9 {
199 if v&(1<<uint(b)) != 0 {
200 byteIdx := bitPos / 8
201 bitIdx := uint(bitPos % 8)
202 out[byteIdx] |= 1 << bitIdx
203 }
204 bitPos++
205 }
206 }
207 return out
208 }
209
210 // unpackCoeffs243 unpacks a GnarlHash back into 27 Z_271 coefficients.
211 func unpackCoeffs243(h GnarlHash) [GnarlN]uint16 {
212 var coeffs [GnarlN]uint16
213 bitPos := 0
214 for i := range GnarlN {
215 var v uint16
216 for b := range 9 {
217 byteIdx := bitPos / 8
218 bitIdx := uint(bitPos % 8)
219 if h[byteIdx]&(1<<bitIdx) != 0 {
220 v |= 1 << uint(b)
221 }
222 bitPos++
223 }
224 coeffs[i] = v
225 }
226 return coeffs
227 }
228
229 // packCoeffs216 packs 27 coefficients reduced mod 243 (8 bits each) into 27 bytes.
230 func packCoeffs216(coeffs [GnarlN]uint16) GnarlMid {
231 var out GnarlMid
232 for i, c := range coeffs {
233 out[i] = byte(c % GnarlMidR)
234 }
235 return out
236 }
237
238 // packCoeffs54 packs 27 coefficients reduced mod 3 (2 bits each) into 7 bytes.
239 func packCoeffs54(coeffs [GnarlN]uint16) GnarlShard {
240 var out GnarlShard
241 bitPos := 0
242 for _, c := range coeffs {
243 v := c % GnarlShardR // 0, 1, or 2
244 for b := range 2 {
245 if v&(1<<uint(b)) != 0 {
246 byteIdx := bitPos / 8
247 bitIdx := uint(bitPos % 8)
248 out[byteIdx] |= 1 << bitIdx
249 }
250 bitPos++
251 }
252 }
253 return out
254 }
255
256 // gnarlHashCore computes the trinary Hamadryad hash of an arbitrary-length message,
257 // returning the raw Z_271 coefficients. All output tiers derive from this.
258 func gnarlHashCore(msg []byte) [GnarlN]uint16 {
259 var chain [GnarlN]uint16
260
261 // Pad message: append 0x80, then zeros, then 8-byte LE length.
262 padded := make([]byte, len(msg))
263 copy(padded, msg)
264 padded = append(padded, 0x80)
265
266 // Pad to next multiple of gnarlInputBytes, leaving 8 bytes for length.
267 for (len(padded)+8)%gnarlInputBytes != 0 {
268 padded = append(padded, 0)
269 }
270
271 // Append message length in bits as 8-byte LE.
272 var lenBuf [8]byte
273 binary.LittleEndian.PutUint64(lenBuf[:], uint64(len(msg))*8)
274 padded = append(padded, lenBuf[:]...)
275
276 // Process each block.
277 for off := 0; off < len(padded); off += gnarlInputBytes {
278 var block [gnarlInputBytes]byte
279 copy(block[:], padded[off:off+gnarlInputBytes])
280
281 result := gnarlCompress(&block)
282
283 // Chain: coefficient-wise addition mod 271.
284 for j := range GnarlN {
285 chain[j] = mod271(uint32(chain[j]) + uint32(result[j]))
286 }
287 }
288
289 return chain
290 }
291
292 // GHash computes the 243-bit GnarlHash of an arbitrary-length message.
293 func GHash(msg []byte) GnarlHash {
294 coeffs := gnarlHashCore(msg)
295 return packCoeffs243(coeffs)
296 }
297
298 // GMid computes the 216-bit (27-byte) GnarlMid of an arbitrary-length message.
299 func GMid(msg []byte) GnarlMid {
300 coeffs := gnarlHashCore(msg)
301 return packCoeffs216(coeffs)
302 }
303
304 // GShard computes the 54-bit GnarlShard of an arbitrary-length message.
305 func GShard(msg []byte) GnarlShard {
306 coeffs := gnarlHashCore(msg)
307 return packCoeffs54(coeffs)
308 }
309
310 // Mid extracts the GnarlMid tier from a full GnarlHash.
311 func (h GnarlHash) Mid() GnarlMid {
312 coeffs := unpackCoeffs243(h)
313 return packCoeffs216(coeffs)
314 }
315
316 // Shard extracts the GnarlShard tier from a full GnarlHash.
317 func (h GnarlHash) Shard() GnarlShard {
318 coeffs := unpackCoeffs243(h)
319 return packCoeffs54(coeffs)
320 }
321
322 // IsZero reports whether the GnarlHash is all zeros.
323 func (h GnarlHash) IsZero() bool {
324 for _, b := range h {
325 if b != 0 {
326 return false
327 }
328 }
329 return true
330 }
331
332 // IsZero reports whether the GnarlMid is all zeros.
333 func (m GnarlMid) IsZero() bool {
334 for _, b := range m {
335 if b != 0 {
336 return false
337 }
338 }
339 return true
340 }
341
342 // IsZero reports whether the GnarlShard is all zeros.
343 func (s GnarlShard) IsZero() bool {
344 for _, b := range s {
345 if b != 0 {
346 return false
347 }
348 }
349 return true
350 }
351
352 // Sum returns a new GnarlHash that is the coefficient-wise sum (mod 271)
353 // of two GnarlHash values.
354 func (h GnarlHash) Sum(other GnarlHash) GnarlHash {
355 a := unpackCoeffs243(h)
356 b := unpackCoeffs243(other)
357 var result [GnarlN]uint16
358 for i := range GnarlN {
359 result[i] = mod271(uint32(a[i]) + uint32(b[i]))
360 }
361 return packCoeffs243(result)
362 }
363
364 // GnarlHashValue computes the GnarlHash of an arbitrary Go value.
365 func GnarlHashValue(v any) GnarlHash {
366 data := []byte(fmt.Sprintf("%v", v))
367 return GHash(data)
368 }
369
370 // RandomGnarlHash generates a cryptographically random GnarlHash value.
371 func RandomGnarlHash() GnarlHash {
372 var h GnarlHash
373 if _, err := rand.Read(h[:]); err != nil {
374 panic(fmt.Sprintf("crypto/rand: %v", err))
375 }
376 // Zero the 5 spare bits in the last byte.
377 h[GnarlHashBytes-1] &= 0x07
378 return h
379 }
380