# Gnarl Crypto Primitives

Lattice-based signature scheme and SWIFFT-derived hash functions for wire protocols.

Import paths:

    github.com/mlekudev/gnarl-hamadryad/crypto       // hash functions, wire format
    github.com/mlekudev/gnarl-hamadryad/crypto/gnarl  // signatures, key management


## Wire Sizes

| Primitive | Bytes | Description |
|-----------|------:|-------------|
| Private key | 27 | Scalar mod Q |
| Public key | 27 | Torus y-coordinate |
| Signature | 54 | 27 challenge + 27 response |
| GnarlHash | 31 | Full 243-bit hash |
| GnarlMid | 27 | Packet identity / auth tag |
| GnarlShard | 7 | Epoch-scoped address (54-bit) |
| Nonce | 10 | 8-byte counter + 2-byte epoch |
| Packet header | 64 | Nonce + Identity + AuthTag |

All sizes are fixed except ciphertext, which matches plaintext length.


## Performance

AMD Ryzen 5 7520U. Gnarl uses Go + hand-written AMD64 assembly (CIOS Montgomery
multiplication, AVX2 vectorized basis accumulation with BMI1 TZCNT/BLSR bit scanning).

### Gnarl Operations

| Operation | Time |
|-----------|-----:|
| GMid hash (128 B) | 2.3 µs |
| GHash (128 B) | 2.6 µs |
| KeyGen | 7.2 µs |
| Sign | 10.7 µs |
| Verify | 40.5 µs |
| Seal (128 B) | 14.8 µs |
| Open (128 B) | 14.8 µs |

### Comparison: Gnarl vs BIP-340 Schnorr

Three implementations compared: Gnarl (Go + asm), libsecp256k1 (C, the reference
implementation used by Bitcoin Core, linked via CGo), and btcec (pure Go secp256k1,
github.com/btcsuite/btcd/btcec/v2).

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

| Comparison | KeyGen | Sign | Verify |
|------------|-------:|-----:|-------:|
| Gnarl vs libsecp256k1 | 2.8x faster | 1.8x faster | ~parity |
| Gnarl vs btcec | 10.6x faster | 21.6x faster | 3.9x faster |

### Data Sizes

| | BIP-340 / secp256k1 | Gnarl |
|-----|--------------------:|------:|
| Secret key | 32 bytes | 27 bytes |
| Public key | 32 bytes (x-only) | 27 bytes |
| Signature | 64 bytes | 54 bytes |
| Pubkey + sig | 96 bytes | 81 bytes (-16%) |
| Hash | 32 bytes (SHA-256) | 27 bytes (GMid) / 31 bytes (GHash) |

### Hash Comparison

| Hash | Output | Birthday bound | Speed (128 B) |
|------|-------:|---------------:|--------------:|
| SHA-256 | 32 bytes | 2^128 | 142 ns |
| GnarlMid | 27 bytes | 2^108 | 2.3 µs |
| GnarlHash | 31 bytes | 2^121.5 | 2.6 µs |
| GnarlShard | 7 bytes | 2^27 | 2.3 µs |

SHA-256 is faster per byte. Gnarl hashes provide collision resistance reducible
to worst-case SVP in ideal lattices (quantum-relevant hardness assumption) and
algebraic structure (homomorphic addition, native ring arithmetic) that SHA-256
lacks. The hash cost is amortized in Sign/Verify where Gnarl's torus algebra
dominates and recovers the difference.


## Hash Functions

Three tiers of the same SWIFFT lattice hash, sharing a single computation.
Collision resistance reduces to worst-case SVP in ideal lattices.

```go
import "github.com/mlekudev/gnarl-hamadryad/crypto"

// Full hash (31 bytes, birthday bound 2^121.5)
h := crypto.GHash(msg)

// Packet identity (27 bytes, birthday bound 2^108)
mid := crypto.GMid(msg)

// Epoch address (7 bytes, birthday bound 2^27)
shard := crypto.GShard(msg)

// Downcast from full hash (no re-hashing)
mid2 := h.Mid()
shard2 := h.Shard()

// Homomorphic addition (coefficient-wise mod 271)
combined := h1.Sum(h2)

// Zero check
if h.IsZero() { ... }
```

Ring: Z_271[x]/(x^27 + 1). Input: 12 polynomials of 27 binary coefficients = 324 bits per block. Merkle-Damgard chaining for arbitrary-length messages with 0x80 padding and 64-bit LE length suffix.


## Signatures

Schnorr signatures over the non-split torus of SL(2, Z_P) for a 216-bit prime.
Security: ~107-bit Pollard-rho against discrete log in the torus subgroup.

```go
import (
    "github.com/mlekudev/gnarl-hamadryad/crypto"
    "github.com/mlekudev/gnarl-hamadryad/crypto/gnarl"
)

// Key generation
sk, pk, err := gnarl.GenerateKey()

// Serialization
skBytes := sk.Bytes()   // 27 bytes
pkBytes := pk.YBytes()  // 27 bytes (compressed, y-coordinate only)
pkFull  := pk.FullBytes() // 81 bytes (a, b, d torus components)

// Deserialization
sk2, err := gnarl.PrivateKeyFromBytes(skBytes)
pk2, err := gnarl.PublicKeyFromYBytes(pkBytes)
pk3 := gnarl.PublicKeyFromPrivate(sk)

// Sign (challenge hash = GMid)
sig, err := gnarl.Sign(sk, msg, func(data []byte) [27]byte {
    return crypto.GMid(data)
})

// Verify
ok := gnarl.Verify(pk, msg, sig, func(data []byte) [27]byte {
    return crypto.GMid(data)
})

// Signature serialization
sigBytes := sig.Bytes()  // 54 bytes
sig2, err := gnarl.SignatureFromBytes(sigBytes)
```

The `challengeFunc` parameter lets callers provide the hash binding without circular imports. Always use `crypto.GMid` for standard Gnarl signatures.


## Authenticated Encryption (Wire Format)

Packet-level authenticated encryption for UDP transport. 64-byte fixed header, variable ciphertext.

### Packet Layout

```
Offset  Size  Field
  0      10   Nonce (counter-based, 80-bit)
 10      27   Identity (GnarlMid of sender, cleartext)
 37      27   AuthTag (GnarlMid MAC)
 64      var  Ciphertext (CTR-mode, same length as plaintext)
```

Total overhead: 64 bytes. With standard 1500-byte MTU minus 28-byte IP+UDP header, usable payload is 1408 bytes.

### Usage

```go
import "github.com/mlekudev/gnarl-hamadryad/crypto"

// Both sides derive a shared secret (crypto.Hamadryad, 56 bytes)
// via key exchange (out of scope here).
var secret crypto.Hamadryad

// Sender identity: GMid of the sender's public fingerprint.
identity := crypto.GMid(myPubKey)

// Nonce: epoch + monotonic counter. Must never repeat for a given secret.
nonce := crypto.GnarlNonceFromCounter(epoch, counter)

// Seal: encrypt + authenticate
pkt := crypto.GnarlSeal(secret, identity, nonce, plaintext)

// Serialize for UDP send
wire := crypto.MarshalGnarlPacket(pkt)

// --- receiver side ---

// Deserialize
pkt, err := crypto.UnmarshalGnarlPacket(wire)
// pkt.Identity is cleartext -- use it to look up the shared secret
// for this sender before attempting decryption.

// Open: verify + decrypt
plaintext, err := crypto.GnarlOpen(secret, pkt)
if err != nil {
    // Authentication failed: tampered, wrong key, or replay.
}
```

### Security Properties

The auth tag binds nonce, identity, and ciphertext together under the shared secret:

    tag = GMid(secret || nonce || identity || GHash(ciphertext))

The keystream is CTR mode:

    block_i = GMid(secret || nonce || "ctr" || LE64(i))

Each keystream block produces 27 bytes. The identity field is not encrypted, allowing the receiver to do session lookup before any decryption work.

Nonce reuse with the same secret is fatal (keystream reuse). The 80-bit nonce space supports 2^64 packets per epoch with 2^16 epoch rotations.


## Nonce Management

```go
// Create nonce from epoch and counter
nonce := crypto.GnarlNonceFromCounter(epoch, counter)

// Layout: [8 bytes counter LE] [2 bytes epoch LE]
// Epoch: rotate on key renegotiation or time boundary.
// Counter: strictly monotonic per direction per epoch.
```

For a multiplexing UDP protocol, a reasonable approach:
- One epoch per session/connection.
- Counter increments per packet per direction.
- Receiver tracks highest seen counter per sender to detect replay.


## Integration Pattern for Multiplexed UDP

A multiplexed protocol carrying multiple logical streams over one UDP socket:

```go
// Packet with stream multiplexing
type MuxPacket struct {
    StreamID uint16
    Seq      uint32
    Payload  []byte
}

func sendMuxPacket(conn *net.UDPConn, addr *net.UDPAddr,
    secret crypto.Hamadryad, identity crypto.GnarlMid,
    epoch uint16, counter *uint64,
    streamID uint16, seq uint32, payload []byte) error {

    // Frame the mux header + payload
    var buf bytes.Buffer
    binary.Write(&buf, binary.LittleEndian, streamID)
    binary.Write(&buf, binary.LittleEndian, seq)
    buf.Write(payload)

    // Encrypt the entire mux frame
    nonce := crypto.GnarlNonceFromCounter(epoch, atomic.AddUint64(counter, 1))
    pkt := crypto.GnarlSeal(secret, identity, nonce, buf.Bytes())
    wire := crypto.MarshalGnarlPacket(pkt)

    _, err := conn.WriteToUDP(wire, addr)
    return err
}

func recvMuxPacket(wire []byte, secret crypto.Hamadryad) (
    streamID uint16, seq uint32, payload []byte, err error) {

    pkt, err := crypto.UnmarshalGnarlPacket(wire)
    if err != nil {
        return 0, 0, nil, err
    }

    plain, err := crypto.GnarlOpen(secret, pkt)
    if err != nil {
        return 0, 0, nil, err
    }

    // Demux
    r := bytes.NewReader(plain)
    binary.Read(r, binary.LittleEndian, &streamID)
    binary.Read(r, binary.LittleEndian, &seq)
    payload, _ = io.ReadAll(r)
    return streamID, seq, payload, nil
}
```

Key exchange to derive the shared `Hamadryad` secret is out of scope for this document. The `pkt.Identity` field (27 bytes, cleartext) serves as session/peer lookup key on the receive path, so the receiver can maintain a map of `GnarlMid -> shared secret` without trial decryption.


## Constants Reference

```go
// Hash sizes
crypto.GnarlHashBytes  = 31  // full hash
crypto.GnarlMidBytes   = 27  // packet identity / auth tag
crypto.GnarlShardBytes = 7   // epoch address

// Ring parameters
crypto.GnarlP = 271  // ring modulus
crypto.GnarlN = 27   // ring dimension

// Wire format
crypto.GnarlNonceLen  = 10  // nonce size
crypto.GnarlHeaderLen = 64  // fixed packet header
```