commit 6a542c743eea11968d653194bde7808eb633e455
parent 281803cc9430967245621910a4eea86efcf752db
Author: finwo <finwo@pm.me>
Date: Tue, 13 Oct 2026 12:07:10 +0200
Wording
Diffstat:
4 files changed, 30 insertions(+), 39 deletions(-)
diff --git a/README.md b/README.md
@@ -3,17 +3,16 @@ sfinx
> Stateless hash-based signatures
-Signing uses a SPHINCS+-inspired scheme built on hash chains over a merkle tree
-that is never stored. Every key is derived from the seed and the path that
-reaches it, so there is no counter and no state file to keep in sync. The secret
-is a seed, and the public key is a single hash.
+A SPHINCS+-inspired signature scheme. Its only assumption is SHA3, so there is
+no curve or factoring problem for a quantum computer to solve.
-The hash size and the tree depth (`-p`) are arguments rather than build options.
-The depth defaults to 32 and sets the signature size. The docs cover changing
-either.
+| at the defaults | |
+| --------------- | ------------ |
+| Secret | a seed |
+| Public key | 32 bytes |
+| Signature | 43,042 bytes |
-This project makes use of [dep](https://git.finwo.net/app/dep) to manage its
-dependencies and exports.
+Dependencies and exports are managed with [dep](https://git.finwo.net/app/dep).
Features
--------
diff --git a/docs/cli.md b/docs/cli.md
@@ -7,7 +7,7 @@
```
$ sfinx generate -o demo.key
-$ sfinx sign -k demo.key -p 32 -m "hello sfinx" -o demo.sig
+$ sfinx sign -k demo.key -m "hello sfinx" -o demo.sig
$ sfinx verify -k demo.key -S demo.sig -m "hello sfinx"
OK
```
diff --git a/docs/idea.md b/docs/idea.md
@@ -21,7 +21,7 @@ This document is the intuition and the vocabulary. The precise formulas are in
- `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.
+- `layer`: which WOTS key in the stack, `1..N`. A layer-`k` key is named by `E4M4(N)` and 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.
@@ -73,21 +73,13 @@ 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.
+`prefix` is `E4M4(N)` plus 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`. The
+prefix itself is never padded. 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.
## Signing
@@ -130,9 +122,8 @@ collision space is 256 bits.
## 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.
+A signature is a proof that you can produce the path to a given root, not a
+record that you did.
## Cost and parallelism
@@ -150,4 +141,4 @@ a universal keyspace.
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`.
+it is invisible in the signature.
diff --git a/docs/scheme.md b/docs/scheme.md
@@ -20,7 +20,7 @@ that reaches it, so the tree is never built or stored.
| `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 |
+| `layer` | `1..N` | which WOTS key in the stack; layer-`k` is named by `E4M4(N)` and `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.
@@ -40,11 +40,12 @@ that reaches it, so the tree is never built or stored.
## 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.
+depths, so their prefix is `E4M4(N)` plus 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
@@ -103,14 +104,14 @@ 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))
+parent = H(bitlen (1) | mask (1) | prefix (p) | left (L) | right (L))
```
-- For a node at depth `8k + d`, `prefix` is `E4M4(N) | path[0..k-1]` and `bitlen` is `d`.
+- For a node at depth `8k + d`, `prefix` is `E4M4(N) | path[0..k-1]`, so `p = k + 1`, and `bitlen` is `d`.
- `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.
- `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 input is `c * L` bytes and a parent input `2 + k + 2L`, so the two coincide at `L*L + 2L` bytes, where the prefix is `k = L*L - 2`. The verifier's walk is fixed by `N` and the subtree height, so a leaf is never read as a parent.
+- A leaf input is `c * L` bytes and a parent input `2 + p + 2L`, so the two coincide at `L*L + 2L` bytes, where `p = L*L - 2`. The verifier's walk is fixed by `N` and the subtree height, so a leaf is never read as a parent.
## Tree structure