// Package crypto — Hamadryad: SWIFFT-derived lattice hash for kismet consensus.
//
// Hamadryad disperses an input through the NTT lattice into spectral components,
// then narrows the spectrum via per-coefficient modular projection. Two
// bandwidths of the same dispersal yield the full and local output modes.
//
// It is a fork of SWIFFT (Lyubashevsky, Micciancio, Peikert, Rosen 2008) —
// the only hash family with provable collision resistance reducible to
// worst-case ideal lattice problems (SVP).
//
// Two output modes share a single computation:
//
//	Hamadryad (448-bit / 56 bytes): canonical transaction identity.
//	  64 ring coefficients × 7 bits each = 448 bits.
//	  Obtained by reducing each Z_257 coefficient mod 128.
//	  Birthday bound: 2^224. Inversion bound: 2^448 (lattice).
//
//	Shard (48-bit / 6 bytes): epoch-scoped transaction address.
//	  Extracted from the Hamadryad hash. Collision-safe within any single
//	  epoch's transaction population (birthday bound 2^24 ≈ 16M).
//	  Domain-separated by the epoch parent hash in the preimage.
//
// Architecture (SWIFFT core):
//
//	Ring:       R = Z_p[x]/(x^n + 1), with n=64, p=257
//	Input:      m·n = 16·64 = 1024 bits
//	Fixed keys: a_1 … a_m ∈ R (random, public, pre-computed in NTT form)
//
//	Steps:
//	  1. Partition input into m=16 polynomials x_i with n=64 binary coefficients
//	  2. Forward NTT: X_i = NTT(x_i) over Z_257
//	  3. Pointwise multiply: Y_i = A_i · X_i (A_i pre-stored in NTT form)
//	  4. Sum: Y = Σ Y_i
//	  5. Inverse NTT: y = INTT(Y)
//	  6. Coefficient reduction: z_j = y_j mod 128 for j ∈ [0, 64)
//	  7. Output: 64 × 7 bits = 448-bit Hamadryad hash
//
// Reduction rationale (576 → 448):
//
//	Standard SWIFFT: 64 coefficients × ⌈log₂(257)⌉ = 64 × 9 = 576 bits
//	GCF(448, 576) = 64 = n (ring dimension)
//	448 / 64 = 7 bits per coefficient → project Z_257 → Z_128
//	576 / 64 = 9 bits per coefficient → full Z_257
//
//	This is a per-coefficient modular projection, not a bitstring truncation.
//	Collisions in the reduced ring imply near-collisions in the full ring,
//	whose hardness reduces to worst-case SVP in ideal lattices.
//
// Epoch binding:
//
//	Input = epoch_parent_hash ‖ transaction_bytes
//	The epoch parent hash (itself a 448-bit Hamadryad from the PoW leader)
//	acts as a domain separator. Two identical transactions in different
//	epochs produce different hashes. This is what makes the 48-bit Shard
//	safe: collision resistance only needs to hold within a single epoch's
//	population, not across the full history.
//
// Security:
//
//	Birthday (collision):  2^224 (Hamadryad), 2^24 (Shard)
//	Inversion (preimage):  2^448 (lattice hardness, Hamadryad)
//	Provability:           Collision resistance reduces to worst-case
//	                       SVP on ideal lattices over Z[x]/(x^64 + 1).
//	                       This is the distinguishing property of SWIFFT:
//	                       no other hash family offers this guarantee.
//
// Parameters:
//
//	n = 64    Ring dimension. Power of 2. Controls NTT size and output width.
//	m = 16    Input components. Controls compression ratio and lattice dimension.
//	p = 257   Ring modulus. Prime, p ≡ 1 (mod 128). Smallest such prime above 256.
//	r = 128   Reduction modulus. 2^7. Per-coefficient projection target.
//
// The 48/64 ratio: 48 bits = 6 bytes = 8 hexagrams of address space.
// 64 = 2^6 = the number of I Ching hexagrams = the ring dimension n.
// The Shard is one hexagram per byte, six lines deep.
package crypto

import (
	"crypto/rand"
	"encoding/binary"
	"fmt"
)

// Hamadryad ring parameters.
const (
	// HamN is the ring dimension: degree of the cyclotomic polynomial x^n + 1.
	// Must be a power of 2 for NTT and for x^n + 1 to be irreducible over Z.
	HamN = 64

	// HamM is the number of input polynomial components.
	// Input size = HamM × HamN = 1024 bits.
	// Lattice dimension for security proof = HamM × HamN = 1024.
	HamM = 16

	// HamP is the ring modulus. Prime, with HamP ≡ 1 (mod 2·HamN).
	// This ensures primitive 2n-th roots of unity exist in Z_p for the NTT.
	// 257 = 2^8 + 1, a Fermat prime. Arithmetic mod 257 is efficient.
	HamP = 257

	// HamR is the reduction modulus for the 448-bit output.
	// Each coefficient is reduced: z_j = y_j mod HamR.
	// 128 = 2^7, giving 7 bits per coefficient, 64 × 7 = 448 bits total.
	HamR = 128

	// HamInputBits is the total input size in bits.
	HamInputBits = HamM * HamN // 1024

	// HamFullBits is the full (unreduced) SWIFFT output size.
	HamFullBits = HamN * 9 // 576

	// HamBits is the reduced output size (canonical hash).
	HamBits = HamN * 7 // 448

	// HamBytes is the reduced output in bytes.
	HamBytes = HamBits / 8 // 56

	// ShardBits is the epoch-local address size.
	ShardBits = 48

	// ShardBytes is the epoch-local address in bytes.
	ShardBytes = ShardBits / 8 // 6
)

// Hamadryad is a 448-bit (56-byte) canonical transaction identity.
// 64 ring coefficients reduced mod 128, packed at 7 bits each.
// Named for the tree nymph bonded to her tree — the signature
// is bonded to the Bethe lattice's constraint topology.
type Hamadryad [HamBytes]byte

// Shard is a 48-bit (6-byte) epoch-scoped transaction address.
// Extracted from a Hamadryad hash. Only unique within a single epoch.
// A leaf separated from the tree.
type Shard [ShardBytes]byte

// Disperse extracts the 48-bit Shard from a full 448-bit Hamadryad.
// Takes the first 6 bytes — the first 6 reduced ring coefficients
// packed into bytes, corresponding to the lowest-index evaluation
// points of the NTT.
func (p Hamadryad) Disperse() Shard {
	var s Shard
	copy(s[:], p[:ShardBytes])
	return s
}

// hamKeys holds the m=16 fixed random polynomials a_1..a_m in NTT form.
// These are the public parameters of the hash family. Generated
// deterministically from a fixed seed for reproducibility.
var hamKeys [HamM][HamN]uint16

func init() {
	// Ensure NTT lookup tables are ready before generating key polynomials.
	// Go runs init functions in source file alphabetical order within a
	// package, and "hamadryad.go" sorts before "ntt.go".
	initNTTTables()

	// Deterministic PRNG seeded with "hamadryad-swifft-v1" to generate
	// the fixed key polynomials. The specific values don't matter for
	// security — SWIFFT's proof holds for any random keys — but they
	// must be consistent across all implementations.
	//
	// We use a simple xorshift64 seeded from the string bytes.
	seed := uint64(0)
	seedStr := []byte("hamadryad-swifft-v1-dendrite-kismet")
	for i, b := range seedStr {
		seed ^= uint64(b) << ((uint(i) * 7) % 64)
	}

	xorshift := func() uint64 {
		seed ^= seed << 13
		seed ^= seed >> 7
		seed ^= seed << 17
		return seed
	}

	for i := range HamM {
		// Generate random polynomial in coefficient form.
		var poly [HamN]uint16
		for j := range HamN {
			poly[j] = uint16(xorshift() % uint64(HamP))
		}
		// Store in NTT form for fast multiplication.
		ntt64(&poly)
		hamKeys[i] = poly
	}
}

// hamInputBytes is the input block size in bytes (1024 bits = 128 bytes).
const hamInputBytes = HamInputBits / 8

// hamCompress computes one SWIFFT compression: 128 bytes → 64 coefficients in Z_257.
//
// The input block is split into m=16 polynomials of n=64 binary coefficients.
// Each polynomial is NTT-transformed, pointwise-multiplied with its fixed key,
// and the results are summed. The output is 64 coefficients in Z_257.
func hamCompress(block *[hamInputBytes]byte) [HamN]uint16 {
	var acc [HamN]uint16 // accumulator in NTT domain

	for i := range HamM {
		// Extract 64-bit (8-byte) chunk → 64 binary coefficients.
		var poly [HamN]uint16
		base := i * (HamN / 8) // 8 bytes per polynomial
		for j := range HamN {
			byteIdx := base + j/8
			bitIdx := uint(j % 8)
			if block[byteIdx]&(1<<bitIdx) != 0 {
				poly[j] = 1
			}
		}

		// Forward NTT.
		ntt64(&poly)

		// Pointwise multiply with fixed key and accumulate.
		for j := range HamN {
			product := mod257(int(poly[j]) * int(hamKeys[i][j]))
			acc[j] = mod257(int(acc[j]) + int(product))
		}
	}

	// Inverse NTT to get coefficients.
	intt64(&acc)

	return acc
}

// packCoeffs packs 64 Z_128 coefficients (7 bits each) into 56 bytes (448 bits).
// Bit packing is little-endian: coefficient 0 occupies bits 0-6, coefficient 1
// occupies bits 7-13, etc.
func packCoeffs(coeffs [HamN]uint16) Hamadryad {
	var out Hamadryad
	bitPos := 0
	for _, c := range coeffs {
		v := c % HamR // reduce mod 128 → 7 bits
		for b := range 7 {
			if v&(1<<uint(b)) != 0 {
				byteIdx := bitPos / 8
				bitIdx := uint(bitPos % 8)
				out[byteIdx] |= 1 << bitIdx
			}
			bitPos++
		}
	}
	return out
}

// unpackCoeffs unpacks a Hamadryad back into 64 Z_128 coefficients.
func unpackCoeffs(p Hamadryad) [HamN]uint16 {
	var coeffs [HamN]uint16
	bitPos := 0
	for i := range HamN {
		var v uint16
		for b := range 7 {
			byteIdx := bitPos / 8
			bitIdx := uint(bitPos % 8)
			if p[byteIdx]&(1<<bitIdx) != 0 {
				v |= 1 << uint(b)
			}
			bitPos++
		}
		coeffs[i] = v
	}
	return coeffs
}

// Hash computes the Hamadryad hash of an arbitrary-length message.
//
// For messages longer than 128 bytes (the SWIFFT block size), we use
// a Merkle-Damgård construction: each block is compressed with the
// previous block's output fed into the next block's input as chaining.
//
// The final block is padded with the message length (8 bytes, LE) to
// prevent length-extension and ensure distinct inputs produce distinct hashes.
func Hash(msg []byte) Hamadryad {
	// Chaining value starts at zero.
	var chain [HamN]uint16

	// Process full blocks. Each block: 128 bytes input.
	// We reserve space in each block for chaining: the first HamBytes (56)
	// bytes carry the chaining value, leaving 72 bytes for message data.
	// But this reduces throughput. Instead, XOR the chain into the output.
	//
	// Simpler Merkle-Damgård: process 128-byte blocks, XOR chain into
	// each block's output coefficients.

	// Pad message: append 0x80, then zeros, then 8-byte LE length.
	// Ensure at least one full block after padding.
	padded := make([]byte, len(msg))
	copy(padded, msg)
	padded = append(padded, 0x80)

	// Pad to next multiple of hamInputBytes, leaving 8 bytes for length.
	for (len(padded)+8)%hamInputBytes != 0 {
		padded = append(padded, 0)
	}

	// Append message length in bits as 8-byte LE.
	var lenBuf [8]byte
	binary.LittleEndian.PutUint64(lenBuf[:], uint64(len(msg))*8)
	padded = append(padded, lenBuf[:]...)

	// Process each 128-byte block.
	for off := 0; off < len(padded); off += hamInputBytes {
		var block [hamInputBytes]byte
		copy(block[:], padded[off:off+hamInputBytes])

		result := hamCompress(&block)

		// XOR-combine with chain (coefficient-wise addition mod 257).
		for j := range HamN {
			chain[j] = mod257(int(chain[j]) + int(result[j]))
		}
	}

	// Reduce each coefficient mod 128 and pack.
	return packCoeffs(chain)
}

// HashValue computes the Hamadryad hash of an arbitrary Go value.
// Replaces the old SHA-256 based hashValue function.
func HashValue(v any) Hamadryad {
	data := []byte(fmt.Sprintf("%v", v))
	return Hash(data)
}

// Sum returns a new Hamadryad that is the coefficient-wise sum (mod 128)
// of two Hamadryad hashes. Useful for domain separation and chaining.
func (p Hamadryad) Sum(other Hamadryad) Hamadryad {
	a := unpackCoeffs(p)
	b := unpackCoeffs(other)
	var result [HamN]uint16
	for i := range HamN {
		result[i] = (a[i] + b[i]) % HamR
	}
	return packCoeffs(result)
}

// IsZero reports whether the Hamadryad hash is all zeros.
func (p Hamadryad) IsZero() bool {
	for _, b := range p {
		if b != 0 {
			return false
		}
	}
	return true
}

// RandomHamadryad generates a cryptographically random Hamadryad value.
// Used for testing and key generation.
func RandomHamadryad() Hamadryad {
	var p Hamadryad
	if _, err := rand.Read(p[:]); err != nil {
		panic(fmt.Sprintf("crypto/rand: %v", err))
	}
	return p
}