sfinx

sphincs+ inspired signing utility
git clone git://git.finwo.net/app/sfinx
Log | Files | Refs | README | LICENSE

commit 197594041e9a41011987c1024aa11982ffb45b3f
parent b7806545d6ae2f3ec111c15f0b7e02de328f8736
Author: finwo <finwo@pm.me>
Date:   Sat, 10 Oct 2026 21:53:21 +0200

Organize docs

Diffstat:
MREADME.md | 299++++++++++++-------------------------------------------------------------------
Adocs/cli.md | 62++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adocs/idea.md | 158+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adocs/scheme.md | 259+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 524 insertions(+), 254 deletions(-)

diff --git a/README.md b/README.md @@ -1,274 +1,65 @@ # sfinx -<small>sphincs+ inspired data signing library</small> +<small>a small, stateless, hash-based signing library and CLI in C</small> -## Rough idea +sfinx signs data with a SPHINCS+-inspired scheme built from hash chains and a +tree you never build. The secret is one seed. The public key is a single hash. +Nothing is stored between signatures, and one keypair verifies any tree depth. -- Glossary: - - `L`: hash output size in bytes, one of `28`, `32`, `48`, `64` (SHA3-224, SHA3-256, SHA3-384, SHA3-512). Every example here uses `32`. - - `H`: the hash function, `SHA3-8*L`. - - `seed`: the secret, any byte string up to 64 MiB. Random bytes are recommended, a passphrase is allowed. - - `w`: Winternitz chain length (256, so one chain digit is one byte). - - `len1`: message chains (`= L`). - - `len2`: checksum chains (`= 2`). - - `c`: chains per WOTS (`= len1 + len2 = L + 2`). - - `b`: bits per subtree (8, one path byte, so 256 leaves). - - `N`: path length in bytes, E4M4-representable. `N` subtrees and `N` WOTS keys for `N >= 1`. - - `bitlen`, `mask`: the sub-byte part of a node's position. `bitlen` is the bit count (0..8), `mask` one byte holding those bits in its top `bitlen` positions with the low `8 - bitlen` bits zeroed. - - `layer`: which WOTS key in the stack, `1..N`. A layer-`k` key is named by the first `k` path bytes. - - `org`: what the bottom WOTS signs, `= H(path | message)`, so the same message on a different path signs a different value. With no path, `org = H(message)`. - - `E4M4`: the log-ish length byte, 4-bit exponent then 4-bit mantissa. Exponent `0` is the mantissa (0..15); for exponent `E >= 1` the value is `(16 + mantissa) << (E-1)`, so `0x10` is 16, `0x20` is 32, `0x30` is 64, and each exponent step doubles. +- No state, no counters, no state file. +- The seed is any byte string, up to 64 MiB. Random bytes are recommended, a passphrase is allowed. +- `L` and the tree depth are runtime values, so the same seed works with any hash size. +- Hashing is SHA3/SHAKE from `finwo/keccak-fast`, runtime-dispatched and batched. +- The library is C99 with POSIX calls and depends only on libc plus the hash core. -- Tree: - - Binary, built as `N` stacked subtrees of height `b = 8`. - - Every subtree leaf is a WOTS public key. - - Every subtree root is a hash, never a signature. - - The public key is the top subtree root, with no WOTS above it. This matches SPHINCS+, whose key is `(PK.seed, PK.root)`. - - The WOTS at layer `k` signs the root of subtree `k`. The bottom WOTS (layer `N`) has no subtree below it and signs `org`. - - The top subtree root is the same for every `N >= 1`, so one keypair verifies any tree depth. - - `N = 0` is the single-key mode: no subtrees, and the public key is the layer-0 WOTS pubkey itself. +## Quick start -- Merkle hash: - - Keyed by the parent's position, `H(bitlen | mask | prefix | left | right)`. - - `bitlen` is one byte, 0..8, the number of sub-byte bits in the position. `mask` holds those bits in its top `bitlen` positions, low bits zeroed, so `bitlen = 4` gives `0xff` and `0xfc` the same `0xf0`. - - `prefix` is the byte-aligned path prefix above the parent. - - `left` and `right` are ordered by the path bit, not by value. - - Keying moves the tree from collision resistance to second-preimage resistance, so an `L`-byte hash is not silently halved. + make + BIN=build/$(uname -s | tr '[:upper:]' '[:lower:]')-$(uname -m)/sfinx -- Path: - - The signer picks a random path of `N` bytes. It is the randomizer, so it never derives from the message. - - `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). - - One path byte selects a leaf in one subtree. The most significant bit (bit 7) is the decision nearest the subtree root, the least significant bit (bit 0) the decision at the leaf. - - `N` must be E4M4-representable, because the signature carries it as an E4M4 byte. + $BIN generate -o demo.key + $BIN sign -k demo.key -p 32 -m "hello sfinx" -o demo.sig + $BIN verify -k demo.key -S demo.sig -m "hello sfinx" -- WOTS: - - Pre-image: `SHAKE256(seed | path[0..k-1])` for a layer-`k` key, `c * L` bytes, split into `c` chains of `L` bytes. The path is truncated, not masked, and there is no layer byte, because SHA3 has no length extension. - - Chain `i` signs digit `i` by hashing its pre-image `digit[i]` times. - - Digits `0..L-1`: the `L` bytes of the signed value (a subtree root, or `org` at the bottom). - - Digits `L..c-1`: the checksum `C = sum(255 - digit[i])`, big-endian in 2 bytes. - - Proof: `c` values, `c * L` bytes. - - Pubkey: `H(chain_end[0] | ... | chain_end[c-1])`, chain end = pre-image hashed `w = 256` times. - -- Signing: - - Output `E4M4(N)`, the random path, then `E4M4(L)`, then the proof data. - - `N = 0`: no path, just the single WOTS proof for `org = H(message)`. - - `N >= 1`: walk bottom up. At each subtree, output the WOTS proof for the path key, then the `b = 8` Merkle neighbours in verification order: LSB (deepest) first, up to MSB (subtree root) last. - -- Signature layout: - - `E4M4(N)` (1 byte) `|` `path` (`N` bytes) `|` `E4M4(L)` (1 byte) `|` data. - - `N = 0`: data is one WOTS proof, `c * L` bytes. - - `N >= 1`: data is `N` rounds of `c * L` bytes WOTS proof followed by `b * L` bytes Merkle neighbours (LSB first). - -- Verifying: - - Read `N`, then the path, then `L`, and check `L` against the public key length. - - When `N = 0`, `org = H(message)`, otherwise recompute `org = H(path | message)`. - - Advance each of the `c` proof values to `w = 256`, hash the chain ends into the WOTS pubkey, and check the checksum chains. - - `N = 0`: compare the WOTS pubkey directly to the public key. - - `N >= 1`: hash up to the subtree root one level at a time, consuming one neighbour and the matching path bit per step, LSB first. Repeat with the next WOTS up, until the top subtree root is compared to the public key. - -- Wire order: - - Numbers are MSB first, matching human notation: `E4M4(N)`, `E4M4(L)`, the path bytes (most significant, near the root, first), the `bitlen` and `mask` bytes, and the checksum (high byte first). - - The Merkle neighbour list is a sequence, not a number, so it follows the verification algorithm: LSB (deepest) first, MSB (top) last. - -- Size and cost: - - `size(0) = 2 + c * L`, `size(N) = 2 + N + N*(c*L) + N*(b*L) = 2 + N + N*(L + 10)*L` for `N >= 1`. - - `keygen(N)`: `c * w` hashes for `N = 0`, `2^b * c * w` hashes for `N >= 1`. - - `sign(N)`: `c * w` hashes for `N = 0`, `N * 2^b * c * w` hashes for `N >= 1`. - -| N | WOTS | subtrees | size | keygen | sign hashes | -|---:|-----:|---------:|---------:|-------:|------------:| -| 0 | 1 | 0 | 1,090 B | 8.7k | 8.7k | -| 1 | 1 | 1 | 1,347 B | 2.2M | 2.2M | -| 16 | 16 | 16 | 21,522 B | 2.2M | 35.7M | -| 32 | 32 | 32 | 43,042 B | 2.2M | 71.3M | - -- Why the checksum: - - Any increased digit decreases `C`. - - An attacker can only hash chains forward, so increasing a message digit forces a checksum chain backward, which needs a preimage. - - `len2 = 2` because `L * 255` fits in 2 base-256 bytes for every supported `L` (7,140 at `L = 28`, 16,320 at `L = 64`). - -- Parallelism: - - Hash chains are independent, so the library is designed to run them in parallel when compiled with pthread support, and sequentially when it is not. Not implemented yet. - - Work is spread over a small worker pool sized to the machine's CPU count, and the switch is compile-time only. The output is identical either way, so it is invisible in the signature. +`generate` writes one file with the seed and its public key. `sign` picks a +random path of 32 bytes, so the same message signs differently every time. +`verify` prints `OK`. Run `$BIN help` or `$BIN <command> --help` for every +option. ## How it works -Think of sfinx as a tree you never build. The public key is a hash, and below -it sit subtrees whose leaves are one-time signature keys. Nothing is stored: -every key is derived from the seed plus the path that reaches it, so the whole -keyspace is a function rather than a pile of bytes on disk. - -### The shape - -The tree is binary, stacked as `N` subtrees of height `b = 8`. - -- Each subtree has 256 leaves, and each leaf is a WOTS public key. -- Each subtree root is only a hash of its children. -- The WOTS at layer `k` signs the root of the subtree below it. -- The public key is the top subtree root, with nothing above it. That is the SPHINCS+ shape. - -Because the top subtree is fixed, its root is the same for every `N >= 1`, so -one keypair covers every tree depth. The bottom WOTS has no subtree below it, so -it signs `org = H(path | message)`. - -`N = 0` collapses the whole thing: no subtrees, no path, and the public key is a -single WOTS key over `org = H(message)`. - -### The path - -The signer picks a random path of `N` bytes. It is the randomizer, so it never -derives from the message, and signing the same message twice lands on different -keys. - -- `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). -- One path byte selects a leaf in one subtree, most significant bit first. -- A one-time key is named by the truncated path that reaches it, `path[0..k-1]` for a layer-`k` key. No mask and no layer byte, because the path is already split into bytes and SHA3 resists length extension. - -### WOTS - -Each key is a Winternitz one-time signature over an `L`-byte value. - -- Pre-image: `SHAKE256(seed | path[0..k-1])` for a layer-`k` key, `c * L` bytes, split into `c = L + 2` chains of `L` bytes. -- Chain `i` signs digit `i` by hashing its pre-image `digit[i]` times. -- The first `L` digits are the signed value. The last `len2 = 2` digits are the checksum `C = sum(255 - digit[i])`. -- The pubkey is `H(chain_end[0] | ... | chain_end[c-1])`, where a chain end is the pre-image hashed `w = 256` times. - -The checksum is what stops a chain from being reversed. Increasing any digit -decreases `C`, and the attacker can only hash forward, so a checksum chain would -have to run backward, which needs a preimage. - -### The Merkle tree - -Each subtree is a plain binary hash tree, but the hash is keyed by position: - -``` -H(bitlen | mask | prefix | left | right) -``` - -`prefix` is the byte-aligned path prefix above the node. `bitlen` (0..8) and -`mask` carry the sub-byte remainder, so a node at depth `8k + d` is named by -`k` path bytes plus `d` bits. `mask` keeps the top `bitlen` bits and zeroes the -rest, so `0xff` and `0xfc` are the same prefix at `bitlen = 4`. No node hash can -be replayed at another depth or in another subtree, so the tree rests on -second-preimage resistance instead of collision resistance. An `L`-byte hash is -not silently cut in half. - -### Reading the path - -The path is read one byte at a time, and a node is named by a prefix of it. The -prefix is truncated at a byte boundary, and the leftover bits travel as `bitlen` -and `mask`. Only the uncovered bits of the `mask` byte are zeroed, so the prefix -itself is never padded. SHA3 has no length extension, so `seed | prefix` cannot -be stretched into another prefix. - -### Verifying - -Verification walks from the bottom up. - -- Read `N`, then the path, then `L`, and check `L` against the public key length. -- Recompute `org = H(path | message)`. -- Advance each of the `c` proof values to `w = 256`, hash the chain ends into the WOTS pubkey, and check the checksum digits. -- Hash up the `b = 8` Merkle neighbours to this subtree root, one level at a time, LSB first. -- Repeat with the next WOTS up, each one signing the subtree root below it. -- The last subtree root is the public key. - -When `N = 0` there is nothing to climb, so the WOTS pubkey over `org = H(message)` -is compared to the public key directly. - -### Why reuse is fine - -The path is random, so every signature lands on a fresh set of one-time keys. -The upper keys only ever sign a fixed subtree root, and the bottom key signs -`org`, which changes with the path. No key is ever asked to sign two different -values. - -### No state - -sfinx is stateless. There is no counter and no state file. A signature is a -proof that you can produce the path to a given root, and the virtual tree gives -a universal keyspace. - -## Command line - -`sfinx` is one binary that dispatches on its first argument. - -- `sfinx seed [length] [-o file] [--force]`: write `length` random seed bytes, default 32, to stdout or a file. -- `sfinx generate [length] [-L hash] [--out-fmt fmt] [--single] [-o file] [-F]`: generate a seed and derive its public key. `--out-fmt hdr` writes one combined file, `raw` and `hex` write a seed file and a `.pub` file beside it. Stdout carries the seed alone. -- `sfinx printkey -k file [-L hash] [--in-fmt fmt] [--out-fmt fmt] [--single] [-o file] [--public-only] [--force]`: read a key file, derive the public key from the seed, and re-encode it. `--in-fmt` defaults to auto-detect, `--out-fmt` to `hdr`. `--public-only` drops the seed. -- `sfinx sign -k keyfile [-L hash] [--single | -p path-len | -P path] [-m message | -M message-file] [--key-fmt fmt] [--sig-fmt fmt] [-o file] [-F]`: sign a message and write the signature. `--key-fmt` defaults to auto-detect with a `raw` seed fallback, `--sig-fmt` to `hex` on stdout and `raw` to a file. -- `sfinx verify -k keyfile [-L hash] [-s signature | -S signature-file] [-m message | -M message-file] [--key-fmt fmt] [--sig-fmt fmt]`: verify a signature and print `OK` or `FAIL`. `--key-fmt` defaults to auto-detect with a `rawpub` fallback, `--sig-fmt` to auto-detect with a `raw` fallback. -- `sfinx help` and `sfinx version`. -- `--single` selects single-key mode (`N = 0`), one WOTS key signing `H(message)` for a seed. It is one-time: signing two different messages with the same seed destroys unforgeability, so use a fresh seed per message. `verify` takes no flag and reads the mode from the signature. - -A key file carries a seed, a public key, or both. `hdr` is the text form (`hash:`, `seed:`, `public-key:`, `signature:`), and `raw`, `hex`, `rawpub`, and `hexpub` are the bare forms. The encode and decode code lives in the library, so any program using sfinx reads and writes the same files. - -## Pseudocode - -A sketch, not reference code. - -```c -// A one-time key is named by the truncated path that reaches it. -pre_image(seed, prefix) = SHAKE256(seed | prefix, c * L) // c = L + 2 - -// L message digits, then the 2 checksum digits. -digits(value) = value[0..L-1] ++ be16(sum(255 - value[i])) - -// Keyed subtree parent: byte prefix plus the sub-byte remainder. -// mask keeps the top bitlen bits of the byte, low bits zeroed. -parent(bitlen, mask, prefix, left, right) = - H(bitlen | mask | prefix | left | right) - -// WOTS -single_sign(seed, prefix, value): - pre = pre_image(seed, prefix) - d = digits(value) - return [ pre[i] hashed d[i] times, for i in 0..c-1 ] - -single_pubkey(proof, value): - d = digits(value) - ends = [ proof[i] hashed (w - d[i]) times, for i in 0..c-1 ] - return H(ends[0] | ... | ends[c-1]) -``` - -Signing, with `value` starting at `org` and climbing one subtree per round: - -```c -tree_sign(seed, message, N): - path = random(N bytes) - value = (N == 0) ? H(message) : H(path | message) - - out = E4M4(N) | path | E4M4(L) +Think of sfinx as a tree you never build. The public key is a hash, and below it +sit subtrees whose leaves are one-time signature keys. Nothing is stored: every +key is derived from the seed plus the path that reaches it. - if N == 0: - out += single_sign(seed, "", value) - return out +- The signer picks a random path. It is the randomizer, so signing the same message twice lands on different one-time keys. +- The bottom key signs `H(path | message)`. Each key above it signs the root of the subtree below, and the top subtree root is the public key. +- Each one-time key is a Winternitz chain set with a checksum, so no chain can be run backward. +- Each subtree parent is hashed together with its position, so a node cannot be replayed at another depth or in another subtree. - for k = N down to 1: - out += single_sign(seed, path[0..k-1], value) // the value from below - out += auth(subtree = k-1, path) // 8 neighbours, LSB first - value = root(subtree = k-1, path) // what the next round signs +A signature is a proof that you can produce the path to a given root, with no +secret kept between signatures. The idea is in `docs/idea.md`, and the formulas +are in `docs/scheme.md`. - return out -``` +## Single-key mode -Verifying: +`--single` collapses the tree to one one-time key (`N = 0`). It is small and +fast, but one-time: signing two different messages with the same seed destroys +unforgeability, so use a fresh seed per message. `verify` reads the mode from +the signature and needs no flag. -```c -verify(pubkey, message, sig): - N = E4M4_decode(sig) - path = read_path(N) - L = E4M4_decode(sig) +## Embedding - if N == 0: - return single_pubkey(read_proof(), H(message)) == pubkey +The library is `src/sfinx.c`, `src/keypair.c`, and `src/fmt/*.c`, listed in +`export.mk`. Compile those plus the `finwo/keccak-fast` sources and include +`<finwo/sfinx.h>`. No CLI, argparse, or util code is reachable from the library; +`test/test_embed.sh` builds exactly that set. - value = H(path | message) +pthread is optional. The bundled CLI links it and runs the subtree build on a +worker pool. The library manifest does not, so a consumer opts in. - for k = N down to 1: - pub = single_pubkey(read_proof(), value) // proof for layer k - if k == 1: - return hash_up(pub, read_auth()) == pubkey // root of subtree 0 - value = hash_up(pub, read_auth()) // root of subtree k-1 +## Docs - return false -``` +- `docs/idea.md`: the rough idea, the glossary, and how the pieces fit. +- `docs/scheme.md`: the precise scheme, the formulas, and pseudocode. +- `docs/cli.md`: the command reference and the key and signature file formats. diff --git a/docs/cli.md b/docs/cli.md @@ -0,0 +1,62 @@ +# sfinx command line + +`sfinx` is one binary that dispatches on its first argument. Build it with +`make`; the binary lands at `build/$(uname -s | tr '[:upper:]' '[:lower:]')-$(uname -m)/sfinx`. + +## Quick start + +``` +$ sfinx generate -o demo.key +$ sfinx sign -k demo.key -p 32 -m "hello sfinx" -o demo.sig +$ sfinx verify -k demo.key -S demo.sig -m "hello sfinx" +OK +``` + +`generate` writes one file holding the seed and its public key. `sign` picks a +random path of 32 bytes, so the same message signs differently every time. +`verify` prints `OK` or `FAIL`. + +## Commands + +- `sfinx seed [length] [-o file] [--force]`: write `length` random seed bytes, default 32, to stdout or a file. +- `sfinx generate [length] [-L hash] [--out-fmt fmt] [--single] [-o file] [-F]`: generate a seed and derive its public key. `--out-fmt hdr` writes one combined file, `raw` and `hex` write a key file and a `.pub` file beside it. Stdout carries the seed alone. +- `sfinx printkey -k file [-L hash] [--in-fmt fmt] [--out-fmt fmt] [--single] [-o file] [--public-only] [--force]`: read a key file, derive the public key from the seed, and re-encode it. `--in-fmt` defaults to auto-detect, `--out-fmt` to `hdr`. `--public-only` drops the seed. +- `sfinx sign -k keyfile [-L hash] [--single | -p path-len | -P path] [-m message | -M message-file] [--key-fmt fmt] [--sig-fmt fmt] [-o file] [-F]`: sign a message and write the signature. `--key-fmt` defaults to auto-detect with a `raw` seed fallback, `--sig-fmt` to `hex` on stdout and `raw` to a file. +- `sfinx verify -k keyfile [-L hash] [-s signature | -S signature-file] [-m message | -M message-file] [--key-fmt fmt] [--sig-fmt fmt]`: verify a signature and print `OK` or `FAIL`. `--key-fmt` defaults to auto-detect with a `rawpub` fallback, `--sig-fmt` to auto-detect with a `raw` fallback. +- `sfinx help` and `sfinx version`. + +`-h/--help` on any command prints its options. + +## Hashing and paths + +- `-L hash`: hash size, one of `224`, `256`, `384`, `512`. Default `256`. +- `-p path-len`: draw a random path of that many bytes. +- `-P path`: use an explicit path, as hex. +- `--single`: single-key mode (`N = 0`), one WOTS key signing `H(message)` for a seed. +- `-F`, `--force`: overwrite existing output files. + +`--single` is mutually exclusive with `-p` and `-P`. It is small and fast, but +one-time: signing two different messages with the same seed destroys +unforgeability, so use a fresh seed per message. `verify` takes no flag and +reads the mode from the signature. + +## File formats + +A key file carries a seed, a public key, or both. A signature file carries a +signature. The encode and decode code lives in the library, so any program using +sfinx reads and writes the same files. + +Key and signature formats (`--key-fmt`, `--sig-fmt`, `--in-fmt`, `--out-fmt`): + +- `hdr`: text, self-detecting. Lines are `hash:`, `seed:`, `public-key:`, and `signature:`, with hex values. +- `raw`: bare bytes. A key seed is bare seed bytes, a signature is bare signature bytes. +- `hex`: lowercase hex, one line. +- `rawpub`: a bare public key, `L` bytes. Explicit only. +- `hexpub`: a public key as lowercase hex. Explicit only. + +Auto-detect (a null or omitted format) recognises `hdr` and `hex` by looking at +the content. `raw`, `rawpub`, and `hexpub` are never guessed; name them +explicitly. + +The wire layout of the signature itself, including `E4M4(N)` and the path, is in +`scheme.md`. diff --git a/docs/idea.md b/docs/idea.md @@ -0,0 +1,158 @@ +# sfinx, the idea + +`sfinx` is a stateless, SPHINCS+-inspired hash-based signature. Think of it as a +tree you never build. The public key is a hash, and below it sit subtrees whose +leaves are one-time signature keys. Nothing is stored: every key is derived from +the seed plus the path that reaches it, so the whole keyspace is a function +rather than a pile of bytes on disk. + +This document is the intuition and the vocabulary. The precise formulas are in +`scheme.md`. + +## Glossary + +- `L`: hash output size in bytes, one of `28`, `32`, `48`, `64` (SHA3-224, SHA3-256, SHA3-384, SHA3-512). Every example uses `32`. +- `H`: the hash function, `SHA3-8*L`. +- `seed`: the secret, any byte string up to 64 MiB. Random bytes are recommended, a passphrase is allowed. +- `w`: Winternitz chain length (256, so one chain digit is one byte). +- `len1`: message chains (`= L`). +- `len2`: checksum chains (`= 2`). +- `c`: chains per WOTS (`= len1 + len2 = L + 2`). +- `b`: bits per subtree (8, one path byte, so 256 leaves). +- `N`: path length in bytes, E4M4-representable. `N` subtrees and `N` WOTS keys for `N >= 1`. +- `bitlen`, `mask`: the sub-byte part of a node's position. `bitlen` is the bit count (0..8), `mask` one byte holding those bits in its top `bitlen` positions with the low `8 - bitlen` bits zeroed. +- `layer`: which WOTS key in the stack, `1..N`. A layer-`k` key is named by the first `k` path bytes. +- `org`: what the bottom WOTS signs, `= H(path | message)`, so the same message on a different path signs a different value. With no path, `org = H(message)`. +- `E4M4`: the log-ish length byte, 4-bit exponent then 4-bit mantissa. Exponent `0` is the mantissa (0..15); for exponent `E >= 1` the value is `(16 + mantissa) << (E-1)`, so `0x10` is 16, `0x20` is 32, `0x30` is 64, and each exponent step doubles. + +## The shape + +The tree is binary, stacked as `N` subtrees of height `b = 8`. + +- Each subtree has 256 leaves, and each leaf is a WOTS public key. +- Each subtree root is only a hash of its children. +- The WOTS at layer `k` signs the root of the subtree below it. +- The public key is the top subtree root, with nothing above it. + +Because the top subtree is fixed, its root is the same for every `N >= 1`, so +one keypair covers every tree depth. The bottom WOTS has no subtree below it, so +it signs `org = H(path | message)`. + +`N = 0` collapses the whole thing: no subtrees, no path, and the public key is a +single WOTS key over `org = H(message)`. + +## The path + +The signer picks a random path of `N` bytes. It is the randomizer, so it never +derives from the message, and signing the same message twice lands on different +keys. + +- `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). +- One path byte selects a leaf in one subtree, most significant bit first. +- A one-time key is named by the truncated path that reaches it, `path[0..k-1]` for a layer-`k` key. No mask and no layer byte, because the path is already split into bytes and SHA3 resists length extension. +- `N` must be E4M4-representable, because the signature carries it as an E4M4 byte. + +## WOTS + +Each key is a Winternitz one-time signature over an `L`-byte value. + +- Pre-image: `SHAKE256(seed | path[0..k-1])` for a layer-`k` key, `c * L` bytes, split into `c = L + 2` chains of `L` bytes. +- Chain `i` signs digit `i` by hashing its pre-image `digit[i]` times. +- The first `L` digits are the signed value. The last `len2 = 2` digits are the checksum `C = sum(255 - digit[i])`. +- The pubkey is `H(chain_end[0] | ... | chain_end[c-1])`, where a chain end is the pre-image hashed `w = 256` times. + +The checksum is what stops a chain from being reversed. Increasing any digit +decreases `C`, and an attacker can only hash forward, so a checksum chain would +have to run backward, which needs a preimage. `len2 = 2` because `L * 255` fits +in two base-256 bytes for every supported `L` (7,140 at `L = 28`, 16,320 at +`L = 64`). + +## The Merkle tree + +Each subtree is a plain binary hash tree, but the hash is keyed by position: + +``` +H(bitlen | mask | prefix | left | right) +``` + +`prefix` is the byte-aligned path prefix above the node. `bitlen` (0..8) and +`mask` carry the sub-byte remainder, so a node at depth `8k + d` is named by +`k` path bytes plus `d` bits. `mask` keeps the top `bitlen` bits and zeroes the +rest, so `0xff` and `0xfc` are the same prefix at `bitlen = 4`. No node hash can +be replayed at another depth or in another subtree, so the tree rests on +second-preimage resistance instead of collision resistance. An `L`-byte hash is +not silently cut in half. + +## Reading the path + +The path is read one byte at a time, and a node is named by a prefix of it. The +prefix is truncated at a byte boundary, and the leftover bits travel as `bitlen` +and `mask`. Only the uncovered bits of the `mask` byte are zeroed, so the prefix +itself is never padded. SHA3 has no length extension, so `seed | prefix` cannot +be stretched into another prefix. + +## Signing + +- Output `E4M4(N)`, the random path, then `E4M4(L)`, then the proof data. +- `N = 0`: no path, just the single WOTS proof for `org = H(message)`. +- `N >= 1`: walk bottom up. At each subtree, output the WOTS proof for the path key, then the `b = 8` Merkle neighbours in verification order: LSB (deepest) first, up to MSB (subtree root) last. + +## Verifying + +Verification walks from the bottom up. + +- Read `N`, then the path, then `L`, and check `L` against the public key length. +- Recompute `org = H(path | message)`. +- Advance each of the `c` proof values to `w = 256`, hash the chain ends into the WOTS pubkey, and check the checksum digits. +- Hash up the `b = 8` Merkle neighbours to this subtree root, one level at a time, LSB first. +- Repeat with the next WOTS up, each one signing the subtree root below it. +- The last subtree root is the public key. + +When `N = 0` there is nothing to climb, so the WOTS pubkey over `org = H(message)` +is compared to the public key directly. + +## Wire order + +- Numbers are MSB first, matching human notation: `E4M4(N)`, `E4M4(L)`, the path bytes (most significant, near the root, first), the `bitlen` and `mask` bytes, and the checksum (high byte first). +- The Merkle neighbour list is a sequence, not a number, so it follows the verification algorithm: LSB (deepest) first, MSB (top) last. + +## Why reuse is fine + +The path is random, so every signature normally lands on a fresh set of one-time +keys. The upper keys only ever sign a fixed subtree root, and the bottom key +signs `org`, which changes with the path. As long as the path does not repeat, no +key is ever asked to sign two different values. + +## How many times can a seed sign? + +What eventually breaks is a path collision: two signatures reaching the same +bottom key with different messages. The bottom key is named by the full `N`-byte +path, so for the default `N = 32` the collision space is 256 bits. + +- Random path, which is what the library does: the birthday bound puts a 50 percent chance of one collision at about `2^128` signatures. The scheme is many-time up to roughly `2^128`, even though each individual key is one-time. +- Tracked paths, where the caller never repeats one: the limit is the path space, `2^256` signatures, on one machine for one purpose. The library tracks nothing, so this is for the caller to build. +- Single-key mode (`N = 0`): one key signs `H(message)` every time, so two different messages break it. That mode really is one-time. + +## No state + +sfinx is stateless. There is no counter and no state file. A signature is a +proof that you can produce the path to a given root, and the virtual tree gives +a universal keyspace. + +## Cost and parallelism + +- `size(0) = 2 + c * L`, `size(N) = 2 + N + N*(c*L) + N*(b*L) = 2 + N + N*(L + 10)*L` for `N >= 1`. +- `keygen(N)`: `c * w` hashes for `N = 0`, `2^b * c * w` hashes for `N >= 1`. +- `sign(N)`: `c * w` hashes for `N = 0`, `N * 2^b * c * w` hashes for `N >= 1`. + +| N | WOTS | subtrees | size | keygen | sign hashes | +|---:|-----:|---------:|---------:|-------:|------------:| +| 0 | 1 | 0 | 1,090 B | 8.7k | 8.7k | +| 1 | 1 | 1 | 1,347 B | 2.2M | 2.2M | +| 16 | 16 | 16 | 21,522 B | 2.2M | 35.7M | +| 32 | 32 | 32 | 43,042 B | 2.2M | 71.3M | + +Hash chains are independent, so the library runs the 256-leaf subtree build on +a worker pool when compiled with pthread support, and sequentially when it is +not. The switch is compile-time only, and the output is identical either way, so +it is invisible in the signature. The detailed formulas live in `scheme.md`. diff --git a/docs/scheme.md b/docs/scheme.md @@ -0,0 +1,259 @@ +# sfinx scheme spec + +This is the implementable specification. A compatible signer and verifier can be +written from this document alone. For the intuition, read `idea.md`; for the +command line and file formats, read `cli.md`. + +`sfinx` is a stateless, SPHINCS+-inspired hash-based signature. The tree is +binary, stacked as `N` subtrees of height `b = 8`, with a Winternitz one-time +key (WOTS) at each subtree leaf. Every key is derived from the seed and the path +that reaches it, so the tree is never built or stored. + +## Constants + +| name | value | meaning | +| :------ | ----------: | :--------------------------------------------------------------------------------- | +| `L` | 28/32/48/64 | hash output size in bytes, from `sfinx_hash` (SHA3-224/256/384/512). Default `32`. | +| `len1` | `L` | message chains, one per byte of the signed value | +| `len2` | 2 | checksum chains | +| `c` | `L + 2` | chains per WOTS key (`= len1 + len2`) | +| `w` | 256 | chain length, `1 << 8`, so one digit is one byte | +| `b` | 8 | subtree height in bits, so `1 << b = 256` leaves per subtree | +| `N` | 32 | path length in bytes, E4M4-representable. Default `32`. | +| `layer` | `1..N` | which WOTS key in the stack; a layer-`k` key is named by the first `k` path bytes | + +- `H` is `SHA3-8*L`, so SHA3-224/256/384/512, and returns `L` bytes. +- `SHAKE256(x)` is the XOF; the WOTS pre-image asks for `c * L = (L + 2) * L` bytes. +- The seed is any byte string up to `SFINX_SEED_LEN_MAX` (64 MiB), not a fixed length. +- `N` is bounded only by E4M4: any representable value up to `SFINX_PATH_LEN_MAX` (507904) is accepted. + +## E4M4 length byte + +`N` and `L` each travel as one byte called E4M4: high nibble is the exponent +`E`, low nibble is the mantissa `M`. + +- `E == 0`: value = `M`, so `0x00..0x0F` = 0..15. +- `E >= 1`: value = `(16 + M) << (E - 1)`. +- Rows: `0x00..0x0F` = 0..15, `0x10..0x1F` = 16..31, `0x20..0x2F` = 32..62, `0x30..0x3F` = 64..124, doubling each exponent step. +- `N = 0` encodes as `0x00`, `N = 32` as `0x20`. `L` encodes as `0x1C` (28), `0x20` (32), `0x28` (48), `0x30` (64). + +## Node position + +A node is named by a path prefix, not a mask. WOTS keys sit at byte-aligned +depths, so their prefix is a whole number of path bytes. Merkle internals can +sit at any depth, so their position is `prefix` bytes plus a sub-byte remainder +carried as `bitlen` (0..8) and `mask` (the partial byte, top `bitlen` bits kept +and the rest zeroed). Nothing else is zero-padded, because SHA3 has no length +extension, so `seed | prefix` cannot be confused with another prefix. + +## Path + +- The signer draws `N` bytes from a CSPRNG. This is the randomizer and it is carried in the signature. +- `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). +- Each path byte navigates one subtree of height `b = 8`, most significant bit first: bit 7 is the decision nearest the subtree root, bit 0 the decision at the leaf. +- A WOTS key is named by the truncated path that reaches it: a layer-`k` key uses `path[0..k-1]`. +- `N` must be E4M4-representable, because `E4M4(N)` leads the signature. +- The library never draws the path. `sfinx_tree_sign` takes `path` as an argument, and `sfinx_random_bytes` is a helper the caller uses. + +## WOTS + +One WOTS key signs one `L`-byte value. It is derived from the seed and the +truncated path that reaches it. + +Pre-image, `c * L = (L + 2) * L` bytes: + +``` +stream = SHAKE256(seed | path[0..k-1]) for a layer-k key +pre[i] = stream[i*L .. i*L + L-1] for i in 0..c-1 +``` + +The layer-0 key (the `N = 0` case) has an empty prefix, so its stream is +`SHAKE256(seed)`. There is no layer byte, because the truncation length already +encodes the depth. + +Digits, from the `L`-byte `value`: + +``` +d[i] = value[i] for i in 0..L-1 +d[L] = (C >> 8) & 0xff where C = sum(255 - value[i]) +d[L+1] = C & 0xff +``` + +`C` max is `L * 255`, which fits in two bytes for every supported `L` (7,140 at +`L = 28`, 16,320 at `L = 64`), so `len2 = 2`. + +Chain and keys: + +``` +chain_i(x, 0) = x +chain_i(x, k) = H(chain_i(x, k-1)) + +proof[i] = chain_i(pre[i], d[i]) sign +end[i] = chain_i(pre[i], w) pubkey build +pubkey = H(end[0] | end[1] | ... | end[c-1]) +``` + +Verify a proof against a value: recompute the digits from the value, then +`end[i] = chain_i(proof[i], w - d[i])`, then the pubkey hash. An attacker can +only hash forward, so raising any `d[i]` lowers `C`, which forces a checksum +chain backward, which needs a preimage. + +## Merkle subtree + +Each subtree is binary with height `b = 8`, so 256 leaves, each leaf a WOTS +public key. The parent hash is keyed by the parent's position: + +``` +parent = H(bitlen (1) | mask (1) | prefix (k) | left (L) | right (L)) +``` + +- `prefix` is the byte-aligned path prefix above the parent. +- `bitlen` is 0..8, the number of sub-byte bits in the position. `mask` holds those bits in its top `bitlen` positions with the low `8 - bitlen` bits zeroed, so a prefix has one encoding. +- For a node at depth `8k + d`, `prefix` is `path[0..k-1]` and `bitlen` is `d`. +- `left` is the child reached by a 0 bit, `right` the child reached by a 1 bit. +- Keying by position is what moves the tree from collision resistance to second-preimage resistance. +- A leaf is `H(ends)` over the `c` chain ends, and a parent is keyed by position. The two input shapes differ, so a leaf hash cannot pass as a parent hash. + +## Tree structure + +- `N` subtrees, `0` top to `N-1` bottom, and `N` WOTS keys at layers `1..N`. +- `R_k` is the root of subtree `k`. `R_0` is the public key. `R_N := org`. +- WOTS at layer `k` signs `R_k`, so `k = N` signs `org` and `1 <= k <= N-1` signs `R_k`. +- `R_{k-1}` is the WOTS pubkey at layer `k` hashed up subtree `k-1` with its `b` neighbours. At `k = 1` that is the public key. +- `N >= 1`: the public key is `R_0`, the top subtree root, with no WOTS above it. This matches SPHINCS+. `R_0` depends only on the seed and `L`, never on `N`, so one keypair verifies any `N >= 1`. +- `N = 0`: no subtrees and no path. The public key is the layer-0 WOTS pubkey over `SHAKE256(seed)`, and that key signs `org = H(message)`. + +## org + +- `N >= 1`: `org = H(path | message)`, so the same message on a different path signs a different value. +- `N = 0`: `org = H(message)`. + +## Signature layout + +``` +offset field size +0 N 1 (E4M4) +1 PATH N +1 + N L 1 (E4M4) +2 + N DATA see below +``` + +- `N` is the path length, E4M4-encoded. +- `PATH` is `N` bytes, `path[0]` first. +- `L` is the hash size in bytes, E4M4-encoded, and must match the public key length. +- `N = 0`: `DATA` is one WOTS proof, `c * L` bytes. +- `N >= 1`: `DATA` is `N` rounds. Round `k` counts `N` down to `1` and holds the WOTS proof for layer `k` (`c * L` bytes), then the `b` neighbours of subtree `k-1` (`b * L` bytes), LSB (deepest) first. + +Sizes: + +- `size(0) = 2 + c * L = 2 + (L + 2) * L` +- `size(N) = 2 + N + N * (c + b) * L = 2 + N + N * (L + 10) * L` +- At `L = 32`: `size(0) = 1,090` and `size(N) = 2 + 1345 * N`. + +## Signing + +1. Draw `path`, `N` random bytes. +2. `org = H(path | message)` for `N >= 1`, else `H(message)`. +3. Emit `E4M4(N)`, then `path`, then `E4M4(L)`. +4. `N = 0`: emit the WOTS proof for layer 0 over `org`. Done. +5. `N >= 1`: for `k = N` down to `1`: emit the WOTS proof for layer `k` over `R_k` (`R_N = org`), then the `b` neighbours of subtree `k-1` along the path, LSB first. + +## Verifying + +1. Read `E4M4(N)` and decode `N`. +2. Read the `N`-byte `path`, then read `E4M4(L)` and check it against the public key length. +3. `N = 0`: read one WOTS proof, rebuild its pubkey over `H(message)`, compare to the public key. +4. `N >= 1`: compute `org = H(path | message)`. +5. Set `value = org`. For `k = N` down to `1`: + - read a WOTS proof and rebuild its pubkey over `value`; + - read `b` neighbours and hash the pubkey up subtree `k-1` to its root, LSB first; + - if `k == 1`, that root is the public key, so compare and finish; + - else set `value` to that root. + +## Sizes and hash counts + +With `c = L + 2`, at the default `L = 32` (`c = 34`): + +- keygen `N = 0`: `c * w = 8,704` hashes. +- keygen `N >= 1`: `(1 << b) * c * w = 2,228,224` hashes, because the top subtree needs its 256 WOTS pubkeys. +- sign `N = 0`: `c * w = 8,704` hashes. +- sign `N >= 1`: `N * (1 << b) * c * w`, which is `71,303,168` at `N = 32`. +- verify `N >= 1`: about `N * c * w` chain hashes plus `N * b` parent hashes. + +## Number formats + +- All multi-byte integers are MSB first (big-endian). +- `E4M4(N)`, `E4M4(L)`, and the checksum are MSB first. +- The Merkle neighbour list is a sequence, not a number, so it follows verification order: LSB (deepest) first, MSB (subtree root) last. +- Path bytes run most significant (near the root, `path[0]`) to least significant (near the message, `path[N-1]`). Within a byte, the most significant bit is nearest the subtree root and the least significant bit is at the leaf. + +## Pseudocode + +A sketch, not reference code. + +```c +// A one-time key is named by the truncated path that reaches it. +pre_image(seed, prefix) = SHAKE256(seed | prefix, c * L) // c = L + 2 + +// L message digits, then the 2 checksum digits. +digits(value) = value[0..L-1] ++ be16(sum(255 - value[i])) + +// Keyed subtree parent: byte prefix plus the sub-byte remainder. +// mask keeps the top bitlen bits of the byte, low bits zeroed. +parent(bitlen, mask, prefix, left, right) = + H(bitlen | mask | prefix | left | right) + +// WOTS +single_sign(seed, prefix, value): + pre = pre_image(seed, prefix) + d = digits(value) + return [ pre[i] hashed d[i] times, for i in 0..c-1 ] + +single_pubkey(proof, value): + d = digits(value) + ends = [ proof[i] hashed (w - d[i]) times, for i in 0..c-1 ] + return H(ends[0] | ... | ends[c-1]) +``` + +Signing, with `value` starting at `org` and climbing one subtree per round: + +```c +tree_sign(seed, message, N): + path = random(N bytes) + value = (N == 0) ? H(message) : H(path | message) + + out = E4M4(N) | path | E4M4(L) + + if N == 0: + out += single_sign(seed, "", value) + return out + + for k = N down to 1: + out += single_sign(seed, path[0..k-1], value) // the value from below + out += auth(subtree = k-1, path) // 8 neighbours, LSB first + value = root(subtree = k-1, path) // what the next round signs + + return out +``` + +Verifying: + +```c +verify(pubkey, message, sig): + N = E4M4_decode(sig) + path = read_path(N) + L = E4M4_decode(sig) + + if N == 0: + return single_pubkey(read_proof(), H(message)) == pubkey + + value = H(path | message) + + for k = N down to 1: + pub = single_pubkey(read_proof(), value) // proof for layer k + if k == 1: + return hash_up(pub, read_auth()) == pubkey // root of subtree 0 + value = hash_up(pub, read_auth()) // root of subtree k-1 + + return false +```