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.

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.

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

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

// 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:

// 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

// 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

gnarl-crypto-api.md raw