scheme.md (12599B)
1 # sfinx scheme spec 2 3 This is the implementable specification. A compatible signer and verifier can be 4 written from this document alone. For the intuition, read `idea.md`; for the 5 command line and file formats, read `cli.md`. 6 7 `sfinx` is a stateless, SPHINCS+-inspired hash-based signature. The tree is 8 binary, stacked as `N` subtrees of height `b = 8`, with a Winternitz one-time 9 key (WOTS) at each subtree leaf. Every key is derived from the seed and the path 10 that reaches it, so the tree is never built or stored. 11 12 ## Constants 13 14 | name | value | meaning | 15 | :------ | ----------: | :--------------------------------------------------------------------------------- | 16 | `L` | 28/32/48/64 | hash output size in bytes, from `sfinx_hash` (SHA3-224/256/384/512). Default `32`. | 17 | `len1` | `L` | message chains, one per byte of the signed value | 18 | `len2` | 2 | checksum chains | 19 | `c` | `L + 2` | chains per WOTS key (`= len1 + len2`) | 20 | `w` | 256 | chain length, `1 << 8`, so one digit is one byte | 21 | `b` | 8 | subtree height in bits, so `1 << b = 256` leaves per subtree | 22 | `N` | 32 | path length in bytes, E4M4-representable. Default `32`. | 23 | `layer` | `1..N` | which WOTS key in the stack; layer-`k` is named by `E4M4(N)` and `k` path bytes | 24 25 - `H` is `SHA3-8*L`, so SHA3-224/256/384/512, and returns `L` bytes. 26 - `SHAKE256(x)` is the XOF; the WOTS pre-image asks for `c * L = (L + 2) * L` bytes. 27 - The seed is any byte string up to `SFINX_SEED_LEN_MAX` (64 MiB), not a fixed length. 28 - `N` is bounded only by E4M4: any representable value up to `SFINX_PATH_LEN_MAX` (507904) is accepted. 29 30 ## E4M4 length byte 31 32 `N` and `L` each travel as one byte called E4M4: high nibble is the exponent 33 `E`, low nibble is the mantissa `M`. 34 35 - `E == 0`: value = `M`, so `0x00..0x0F` = 0..15. 36 - `E >= 1`: value = `(16 + M) << (E - 1)`. 37 - Rows: `0x00..0x0F` = 0..15, `0x10..0x1F` = 16..31, `0x20..0x2F` = 32..62, `0x30..0x3F` = 64..124, doubling each exponent step. 38 - `N = 0` encodes as `0x00`, `N = 32` as `0x20`. `L` encodes as `0x1C` (28), `0x20` (32), `0x28` (48), `0x30` (64). 39 40 ## Node position 41 42 A node is named by a path prefix, not a mask. WOTS keys sit at byte-aligned 43 depths, so their prefix is `E4M4(N)` plus a whole number of path bytes. Merkle 44 internals can sit at any depth, so their position is `prefix` bytes plus a 45 sub-byte remainder carried as `bitlen` (0..8) and `mask` (the partial byte, top 46 `bitlen` bits kept and the rest zeroed). Nothing else is zero-padded, because 47 SHA3 has no length extension, so `seed | prefix` cannot be confused with another 48 prefix. 49 50 ## Path 51 52 - The signer draws `N` bytes from a CSPRNG. This is the randomizer and it is carried in the signature. 53 - `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message). 54 - 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. 55 - A WOTS key is named by `E4M4(N)` and the truncated path that reaches it: a layer-`k` key uses `E4M4(N) | path[0..k-1]`. 56 - `N` must be E4M4-representable, because `E4M4(N)` leads the signature. 57 - The library never draws the path. `sfinx_tree_sign` takes `path` as an argument, and `sfinx_random_bytes` is a helper the caller uses. 58 59 ## WOTS 60 61 One WOTS key signs one `L`-byte value, derived from the seed, the path length 62 and the truncated path that reaches it. 63 64 Pre-image, `c * L = (L + 2) * L` bytes: 65 66 ``` 67 stream = SHAKE256(seed | E4M4(N) | path[0..k-1]) for a layer-k key 68 pre[i] = stream[i*L .. i*L + L-1] for i in 0..c-1 69 ``` 70 71 - `E4M4(N)` is at a fixed offset and the prefix length gives `k`, so the key is a bottom key iff `k = N` and interior otherwise. 72 - `N = 0` is single mode: empty prefix, `stream = SHAKE256(seed)`. 73 74 Digits, from the `L`-byte `value`: 75 76 ``` 77 d[i] = value[i] for i in 0..L-1 78 d[L] = (C >> 8) & 0xff where C = sum(255 - value[i]) 79 d[L+1] = C & 0xff 80 ``` 81 82 `C` max is `L * 255`, which fits in two bytes for every supported `L` (7,140 at 83 `L = 28`, 16,320 at `L = 64`), so `len2 = 2`. 84 85 Key id, once per WOTS key, over public data only so the verifier can recompute 86 it: 87 88 ``` 89 kid = H(E4M4(N) | path[0..k-1])[0 .. K-1] 90 K = min(L, rate - 1 - L - 2) rate = 200 - 2L 91 ``` 92 93 | hash | rate | L | K | block | 94 | -------- | ---- | -- | -- | ----- | 95 | SHA3-224 | 144 | 28 | 28 | 58 | 96 | SHA3-256 | 136 | 32 | 32 | 66 | 97 | SHA3-384 | 104 | 48 | 48 | 98 | 98 | SHA3-512 | 72 | 64 | 5 | 71 | 99 100 `K` is cut so a chain step stays one permutation. SHA3-512 is the tight case: 101 rate 72 leaves 5 bytes, so its key ids separate only 40 bits, and two keys 102 colliding there share a chain pool again. Single mode has an empty suffix, so 103 `kid = H("")`. 104 105 Chain and keys: 106 107 ``` 108 chain_i(x, j, 0) = x 109 chain_i(x, j, n) = chain_i(H(x | kid | i | j), j+1, n-1) 110 111 proof[i] = chain_i(pre[i], 0, d[i]) sign 112 end[i] = chain_i(pre[i], 0, w) pubkey build 113 pubkey = H(end[0] | end[1] | ... | end[c-1]) 114 ``` 115 116 Every step is bound to its key, its chain and its position: `i` is `0..c-1` and 117 `j` is `0..w-1`, both one byte. Without that binding every published chain 118 value across every key sits in one pool, and one precomputation targets all of 119 them at once. 120 121 Verify a proof against a value: recompute the digits from the value, then 122 `end[i] = chain_i(proof[i], d[i], w - d[i])`, then the pubkey hash. An attacker 123 can only hash forward, so raising any `d[i]` lowers `C`, which forces a 124 checksum chain backward, which needs a preimage. 125 126 ## Merkle subtree 127 128 Each subtree is binary with height `b = 8`, so 256 leaves, each leaf a WOTS 129 public key. The parent hash is keyed by the parent's position: 130 131 ``` 132 parent = H(bitlen (1) | mask (1) | prefix (p) | left (L) | right (L)) 133 ``` 134 135 - For a node at depth `8k + d`, `prefix` is `E4M4(N) | path[0..k-1]`, so `p = k + 1`, and `bitlen` is `d`. 136 - `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. 137 - `left` is the child reached by a 0 bit, `right` the child reached by a 1 bit. 138 - Keying by position is what moves the tree from collision resistance to second-preimage resistance. 139 - 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. 140 141 ## Tree structure 142 143 - `N` subtrees, `0` top to `N-1` bottom, and `N` WOTS keys at layers `1..N`. 144 - `R_k` is the root of subtree `k`. `R_0` is the public key. `R_N := org`. 145 - WOTS at layer `k` signs `R_k`, so `k = N` signs `org` and `1 <= k <= N-1` signs `R_k`. 146 - `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. 147 - `N >= 1`: the public key is `R_0`, the top subtree root, with no WOTS above it, matching SPHINCS+. `R_0` depends on the seed, `L` and `N`: one public key per length. 148 - `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)`. 149 150 ## org 151 152 - `N >= 1`: `org = H(path | message)`, so the same message on a different path signs a different value. 153 - `N = 0`: `org = H(message)`. 154 155 ## Signature layout 156 157 ``` 158 offset field size 159 0 N 1 (E4M4) 160 1 PATH N 161 1 + N L 1 (E4M4) 162 2 + N DATA see below 163 ``` 164 165 - `N` is the path length, E4M4-encoded. 166 - `PATH` is `N` bytes, `path[0]` first. 167 - `L` is the hash size in bytes, E4M4-encoded, and must match the public key length. 168 - `N = 0`: `DATA` is one WOTS proof, `c * L` bytes. 169 - `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. 170 171 Sizes: 172 173 - `size(0) = 2 + c * L = 2 + (L + 2) * L` 174 - `size(N) = 2 + N + N * (c + b) * L = 2 + N + N * (L + 10) * L` 175 - At `L = 32`: `size(0) = 1,090` and `size(N) = 2 + 1345 * N`. 176 177 ## Signing 178 179 1. Draw `path`, `N` random bytes. 180 2. `org = H(path | message)` for `N >= 1`, else `H(message)`. 181 3. Emit `E4M4(N)`, then `path`, then `E4M4(L)`. 182 4. `N = 0`: emit the WOTS proof for layer 0 over `org`. Done. 183 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. 184 185 ## Verifying 186 187 1. Read `E4M4(N)` and decode `N`. 188 2. Read the `N`-byte `path`, then read `E4M4(L)` and check it against the public key length. 189 3. `N = 0`: read one WOTS proof, rebuild its pubkey over `H(message)`, compare to the public key. 190 4. `N >= 1`: compute `org = H(path | message)`. 191 5. Set `value = org`. For `k = N` down to `1`: 192 - read a WOTS proof and rebuild its pubkey over `value`; 193 - read `b` neighbours and hash the pubkey up subtree `k-1` to its root, LSB first; 194 - if `k == 1`, that root is the public key, so compare and finish; 195 - else set `value` to that root. 196 197 ## Sizes and hash counts 198 199 With `c = L + 2`, at the default `L = 32` (`c = 34`): 200 201 - keygen `N = 0`: `c * w = 8,704` hashes. 202 - keygen `N >= 1`: `(1 << b) * c * w = 2,228,224` hashes, because the top subtree needs its 256 WOTS pubkeys. 203 - sign `N = 0`: `c * w = 8,704` hashes. 204 - sign `N >= 1`: `N * (1 << b) * c * w`, which is `71,303,168` at `N = 32`. 205 - verify `N >= 1`: about `N * c * w` chain hashes plus `N * b` parent hashes. 206 207 ## Number formats 208 209 - All multi-byte integers are MSB first (big-endian). 210 - `E4M4(N)`, `E4M4(L)`, and the checksum are MSB first. 211 - The Merkle neighbour list is a sequence, not a number, so it follows verification order: LSB (deepest) first, MSB (subtree root) last. 212 - 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. 213 214 ## Pseudocode 215 216 A sketch, not reference code. 217 218 ```c 219 // A key is named E4M4(N) | path[0..k-1] for a layer-k key. 220 pre_image(seed, prefix) = SHAKE256(seed | prefix, c * L) // c = L + 2 221 222 // L message digits, then the 2 checksum digits. 223 digits(value) = value[0..L-1] ++ be16(sum(255 - value[i])) 224 225 // Keyed subtree parent: byte prefix plus the sub-byte remainder. 226 // mask keeps the top bitlen bits of the byte, low bits zeroed. 227 parent(bitlen, mask, prefix, left, right) = 228 H(bitlen | mask | prefix | left | right) 229 230 // WOTS 231 chain(x, kid, i, from, steps): 232 for j = from to from + steps - 1: 233 x = H(x | kid | i | j) 234 return x 235 236 single_sign(seed, prefix, value): 237 pre = pre_image(seed, prefix) 238 kid = H(prefix)[0..K-1] 239 d = digits(value) 240 return [ chain(pre[i], kid, i, 0, d[i]), for i in 0..c-1 ] 241 242 single_pubkey(proof, kid, value): 243 d = digits(value) 244 ends = [ chain(proof[i], kid, i, d[i], w - d[i]), for i in 0..c-1 ] 245 return H(ends[0] | ... | ends[c-1]) 246 ``` 247 248 Signing, with `value` starting at `org` and climbing one subtree per round: 249 250 ```c 251 tree_sign(seed, message, N): 252 path = random(N bytes) 253 value = (N == 0) ? H(message) : H(path | message) 254 255 out = E4M4(N) | path | E4M4(L) 256 257 if N == 0: 258 out += single_sign(seed, "", value) 259 return out 260 261 for k = N down to 1: 262 out += single_sign(seed, E4M4(N) | path[0..k-1], value) 263 out += auth(subtree = k-1, path) // 8 neighbours, LSB first 264 value = root(subtree = k-1, path) // what the next round signs 265 266 return out 267 ``` 268 269 Verifying: 270 271 ```c 272 verify(pubkey, message, sig): 273 N = E4M4_decode(sig) 274 path = read_path(N) 275 L = E4M4_decode(sig) 276 277 if N == 0: 278 return single_pubkey(read_proof(), H(""), H(message)) == pubkey 279 280 value = H(path | message) 281 282 for k = N down to 1: 283 kid = H(E4M4(N) | path[0..k-1])[0..K-1] 284 pub = single_pubkey(read_proof(), kid, value) // proof for layer k 285 if k == 1: 286 return hash_up(pub, read_auth()) == pubkey // root of subtree 0 287 value = hash_up(pub, read_auth()) // root of subtree k-1 288 289 return false 290 ```