idea.md (8228B)
1 # sfinx, the idea 2 3 `sfinx` is a stateless, SPHINCS+-inspired hash-based signature. Think of it as a 4 tree you never build. The public key is a hash, and below it sit subtrees whose 5 leaves are one-time signature keys. Nothing is stored: every key is derived from 6 the seed plus the path that reaches it, so the whole keyspace is a function 7 rather than a pile of bytes on disk. 8 9 This document is the intuition and the vocabulary. The precise formulas are in 10 `scheme.md`. 11 12 ## Glossary 13 14 - `L`: hash output size in bytes, one of `28`, `32`, `48`, `64` (SHA3-224, SHA3-256, SHA3-384, SHA3-512). Every example uses `32`. 15 - `H`: the hash function, `SHA3-8*L`. 16 - `seed`: the secret, any byte string up to 64 MiB. Random bytes are recommended, a passphrase is allowed. 17 - `w`: Winternitz chain length (256, so one chain digit is one byte). 18 - `len1`: message chains (`= L`). 19 - `len2`: checksum chains (`= 2`). 20 - `c`: chains per WOTS (`= len1 + len2 = L + 2`). 21 - `b`: bits per subtree (8, one path byte, so 256 leaves). 22 - `N`: path length in bytes, E4M4-representable. `N` subtrees and `N` WOTS keys for `N >= 1`. 23 - `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. 24 - `layer`: which WOTS key in the stack, `1..N`. A layer-`k` key is named by `E4M4(N)` and the first `k` path bytes. 25 - `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)`. 26 - `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. 27 28 ## The shape 29 30 The tree is binary, stacked as `N` subtrees of height `b = 8`. 31 32 - Each subtree has 256 leaves, and each leaf is a WOTS public key. 33 - Each subtree root is only a hash of its children. 34 - The WOTS at layer `k` signs the root of the subtree below it. 35 - The bottom WOTS has no subtree below it, so it signs `org = H(path | message)`. 36 - The public key is the top subtree root, with nothing above it. 37 - The path length is part of every key derivation, so each depth has its own public key. 38 39 `N = 0` collapses the whole thing: no subtrees, no path, and the public key is a 40 single WOTS key over `org = H(message)`. 41 42 ## The path 43 44 The signer picks a random path of `N` bytes. It is the randomizer, so it never 45 derives from the message, and signing the same message twice lands on different 46 keys. 47 48 - `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). 49 - One path byte selects a leaf in one subtree, most significant bit first. 50 - A one-time key is named `E4M4(N) | path[0..k-1]` for a layer-`k` key. No mask, because the path is already split into bytes and SHA3 resists length extension. 51 - `N` must be E4M4-representable, because the signature carries it as an E4M4 byte. 52 53 ## WOTS 54 55 Each key is a Winternitz one-time signature over an `L`-byte value. 56 57 - Pre-image: `SHAKE256(seed | E4M4(N) | path[0..k-1])` for a layer-`k` key, `c * L` bytes, split into `c = L + 2` chains of `L` bytes. 58 - A step is `H(x | kid | i | j)`, where `kid = H(E4M4(N) | path[0..k-1])` truncated, `i` is the chain and `j` the position. 59 - Chain `i` signs digit `i` by stepping its pre-image `digit[i]` times. 60 - The first `L` digits are the signed value. The last `len2 = 2` digits are the checksum `C = sum(255 - digit[i])`. 61 - The pubkey is `H(chain_end[0] | ... | chain_end[c-1])`, where a chain end is the pre-image stepped `w = 256` times. 62 63 Binding the key, chain and position into every step keeps published chain 64 values apart. A plain `H(x)` chain puts every value from every key in one pool, 65 where a single precomputation targets all of them at once. The `kid` is public, 66 so a verifier recomputes it; it is truncated to keep a step inside one Keccak 67 block, which at SHA3-512 leaves only 5 bytes. 68 69 The checksum is what stops a chain from being reversed. Increasing any digit 70 decreases `C`, and an attacker can only hash forward, so a checksum chain would 71 have to run backward, which needs a preimage. `len2 = 2` because `L * 255` fits 72 in two base-256 bytes for every supported `L` (7,140 at `L = 28`, 16,320 at 73 `L = 64`). 74 75 ## The Merkle tree 76 77 Each subtree is a plain binary hash tree, but the hash is keyed by position: 78 79 ``` 80 H(bitlen | mask | prefix | left | right) 81 ``` 82 83 `prefix` is `E4M4(N)` plus the byte-aligned path prefix above the node. `bitlen` 84 (0..8) and `mask` carry the sub-byte remainder, so a node at depth `8k + d` is 85 named by `k` path bytes plus `d` bits. `mask` keeps the top `bitlen` bits and 86 zeroes the rest, so `0xff` and `0xfc` are the same prefix at `bitlen = 4`. The 87 prefix itself is never padded. No node hash can be replayed at another depth or 88 in another subtree, so the tree rests on second-preimage resistance instead of 89 collision resistance. An `L`-byte hash is not silently cut in half. 90 91 ## Signing 92 93 - Output `E4M4(N)`, the random path, then `E4M4(L)`, then the proof data. 94 - `N = 0`: no path, just the single WOTS proof for `org = H(message)`. 95 - `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. 96 97 ## Verifying 98 99 Verification walks from the bottom up. 100 101 - Read `N`, then the path, then `L`, and check `L` against the public key length. 102 - Recompute `org = H(path | message)`. 103 - Advance each of the `c` proof values to `w = 256`, hash the chain ends into the WOTS pubkey, and check the checksum digits. 104 - Hash up the `b = 8` Merkle neighbours to this subtree root, one level at a time, LSB first. 105 - Repeat with the next WOTS up, each one signing the subtree root below it. 106 - The last subtree root is the public key. 107 108 When `N = 0` there is nothing to climb, so the WOTS pubkey over `org = H(message)` 109 is compared to the public key directly. 110 111 ## Wire order 112 113 - 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). 114 - The Merkle neighbour list is a sequence, not a number, so it follows the verification algorithm: LSB (deepest) first, MSB (top) last. 115 116 ## How many times can a seed sign? 117 118 A key is named `E4M4(N) | path[0..k-1]`, which fixes what it signs: the subtree 119 root beneath it when `k < N`, `org` when `k = N`. Two signatures share a key 120 only at the same `N` and the same prefix. 121 122 The limit is therefore a path collision: same `N`, same path, different message. 123 The bottom key is named by the full path, so at the default `N = 32` the 124 collision space is 256 bits. 125 126 - Random path, what the library does: the birthday bound gives a 50 percent chance of one collision at about `2^128` signatures. 127 - Tracked paths, where the caller never repeats one: the limit is the path space, `2^256`. The library tracks nothing, so the caller builds this. 128 - Single-key mode (`N = 0`): one key signs `H(message)` every time, so two messages break it. 129 130 ## No state 131 132 A signature is a proof that you can produce the path to a given root, not a 133 record that you did. 134 135 ## Cost and parallelism 136 137 - `size(0) = 2 + c * L`, `size(N) = 2 + N + N*(c*L) + N*(b*L) = 2 + N + N*(L + 10)*L` for `N >= 1`. 138 - `keygen(N)`: `c * w` hashes for `N = 0`, `2^b * c * w` hashes for `N >= 1`. 139 - `sign(N)`: `c * w` hashes for `N = 0`, `N * 2^b * c * w` hashes for `N >= 1`. 140 141 | N | WOTS | subtrees | size | keygen | sign hashes | 142 |---:|-----:|---------:|---------:|-------:|------------:| 143 | 0 | 1 | 0 | 1,090 B | 8.7k | 8.7k | 144 | 1 | 1 | 1 | 1,347 B | 2.2M | 2.2M | 145 | 16 | 16 | 16 | 21,522 B | 2.2M | 35.7M | 146 | 32 | 32 | 32 | 43,042 B | 2.2M | 71.3M | 147 148 Hash chains are independent, so the library runs the 256-leaf subtree build on 149 a worker pool when compiled with pthread support, and sequentially when it is 150 not. The switch is compile-time only, and the output is identical either way, so 151 it is invisible in the signature.