sfinx

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

sfinx.c (30388B)


      1 #include "sfinx.h"
      2 
      3 #include <finwo/keccak-fast.h>
      4 #include <stdlib.h>
      5 #include <string.h>
      6 #include <sys/random.h>
      7 #include <unistd.h>
      8 
      9 #ifdef _REENTRANT
     10 #include <pthread.h>
     11 #endif
     12 
     13 // E4M4 {{{
     14 //
     15 // Log-ish number format, only positive
     16 //   E=0: M
     17 //   E>0: (16+M)<<(E-1)
     18 
     19 static inline uint32_t _sfinx_e4m4_decode(uint8_t byte) {
     20   uint8_t exponent = (uint8_t)(byte >> 4);
     21   uint8_t mantissa = (uint8_t)(byte & 0x0f);
     22   if (exponent == 0) {
     23     return mantissa;
     24   }
     25   return (uint32_t)(16 + mantissa) << (exponent - 1);
     26 }
     27 
     28 static inline uint32_t _sfinx_e4m4_encode(uint32_t value, uint8_t *out) {
     29   if (value <= 15) {
     30     *out = (uint8_t)value;
     31     return 1;
     32   }
     33 
     34   uint32_t base  = value;
     35   uint32_t shift = 0;
     36   while (base > 31) {
     37     base >>= 1;
     38     if (++shift > 14) {
     39       return 0;
     40     }
     41   }
     42   if (base < 16 || (base << shift) != value) {
     43     return 0;
     44   }
     45 
     46   *out = (uint8_t)(((shift + 1) << 4) | (base - 16));
     47   return 1;
     48 }
     49 // }}}
     50 
     51 // Hash backend {{{
     52 //
     53 // SHA3 for fixed-size hashing, SHAKE256 for the pre-image XOF
     54 //   _sfinx_hash(hash, in, in_len, out)
     55 //   _sfinx_shake256(in, in_len, out, out_len)
     56 //   the _batch forms drive the equal-length loops over keccak-fast's SIMD kernels
     57 
     58 static inline void _sfinx_hash(sfinx_hash hash, const uint8_t *in, size_t in_len, uint8_t *out) {
     59   switch (hash) {
     60     case SFINX_HASH_224: kf_sha3_224(out, 28, in, in_len); break;
     61     case SFINX_HASH_256: kf_sha3_256(out, 32, in, in_len); break;
     62     case SFINX_HASH_384: kf_sha3_384(out, 48, in, in_len); break;
     63     case SFINX_HASH_512: kf_sha3_512(out, 64, in, in_len); break;
     64   }
     65 }
     66 
     67 static inline void _sfinx_hash_batch(sfinx_hash hash, size_t count, const uint8_t *in, size_t in_len, uint8_t *out,
     68                                      size_t out_len) {
     69   switch (hash) {
     70     case SFINX_HASH_224: kf_sha3_224_batch(count, in, in_len, out, out_len); break;
     71     case SFINX_HASH_256: kf_sha3_256_batch(count, in, in_len, out, out_len); break;
     72     case SFINX_HASH_384: kf_sha3_384_batch(count, in, in_len, out, out_len); break;
     73     case SFINX_HASH_512: kf_sha3_512_batch(count, in, in_len, out, out_len); break;
     74   }
     75 }
     76 
     77 static inline void _sfinx_shake256(const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) {
     78   kf_shake256(out, out_len, in, in_len);
     79 }
     80 
     81 static inline void _sfinx_shake256_batch(size_t count, const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) {
     82   kf_shake256_batch(count, in, in_len, out, out_len);
     83 }
     84 
     85 size_t sfinx_hash_len(sfinx_hash hash) {
     86   switch (hash) {
     87     case SFINX_HASH_224: return 28;
     88     case SFINX_HASH_256: return 32;
     89     case SFINX_HASH_384: return 48;
     90     case SFINX_HASH_512: return 64;
     91   }
     92   return 0;
     93 }
     94 
     95 static inline sfinx_hash _sfinx_hash_from_len(size_t len) {
     96   switch (len) {
     97     case 28: return SFINX_HASH_224;
     98     case 32: return SFINX_HASH_256;
     99     case 48: return SFINX_HASH_384;
    100     case 64: return SFINX_HASH_512;
    101   }
    102   return 0;
    103 }
    104 
    105 #define SFINX_KID_ROOM(L)  (197 - 3 * (L))
    106 #define SFINX_KID_LEN(L)   ((L) < SFINX_KID_ROOM(L) ? (L) : SFINX_KID_ROOM(L))
    107 #define SFINX_CHAIN_FIT(L) ((L) + SFINX_KID_LEN(L) + 2 <= (200 - 2 * (L)) - 1)
    108 
    109 _Static_assert(SFINX_CHAIN_FIT(28), "SHA3-224 chain step is not one permutation");
    110 _Static_assert(SFINX_CHAIN_FIT(32), "SHA3-256 chain step is not one permutation");
    111 _Static_assert(SFINX_CHAIN_FIT(48), "SHA3-384 chain step is not one permutation");
    112 _Static_assert(SFINX_CHAIN_FIT(64), "SHA3-512 chain step is not one permutation");
    113 
    114 static inline size_t _sfinx_kid_len(sfinx_hash hash) {
    115   size_t len = sfinx_hash_len(hash);
    116   return SFINX_KID_LEN(len);
    117 }
    118 
    119 static inline void _sfinx_kid(sfinx_hash hash, const uint8_t *suffix, size_t suffix_len, uint8_t *out) {
    120   uint8_t full[SFINX_HASH_LEN_MAX];
    121   _sfinx_hash(hash, suffix, suffix_len, full);
    122   memcpy(out, full, _sfinx_kid_len(hash));
    123 }
    124 
    125 static inline void _sfinx_chain_batch(sfinx_hash hash, size_t count, uint8_t *x, const uint8_t *tail, size_t tail_len,
    126                                       uint8_t from, uint32_t steps) {
    127   size_t len = sfinx_hash_len(hash);
    128   switch (hash) {
    129     case SFINX_HASH_224: kf_sha3_224_chain(count, x, len, tail, tail_len, 1, from, steps); break;
    130     case SFINX_HASH_256: kf_sha3_256_chain(count, x, len, tail, tail_len, 1, from, steps); break;
    131     case SFINX_HASH_384: kf_sha3_384_chain(count, x, len, tail, tail_len, 1, from, steps); break;
    132     case SFINX_HASH_512: kf_sha3_512_chain(count, x, len, tail, tail_len, 1, from, steps); break;
    133   }
    134 }
    135 // }}}
    136 
    137 // WOTS {{{
    138 //
    139 // One WOTS key over an L-byte value, c = L + 2 chains of length 256
    140 //   preimage = SHAKE256(key), c * L bytes, c elements of L bytes
    141 //   digits   = the value bytes, then 2 checksum bytes of 255 - value[i]
    142 //   pubkey   = H of every element chained w times
    143 //   sign     = every preimage element chained d[i] times
    144 //   rebuild  = chain every proof element w - d[i] times, then the pubkey hash
    145 //   verify   = rebuild over the value and compare to a known pubkey
    146 
    147 #define SFINX_WOTS_BYTES_MAX  ((SFINX_HASH_LEN_MAX + 2) * SFINX_HASH_LEN_MAX)
    148 #define SFINX_WOTS_DIGITS_MAX (SFINX_HASH_LEN_MAX + 2)
    149 #define SFINX_WOTS_TAIL_MAX   ((SFINX_HASH_LEN_MAX + 2) * (SFINX_HASH_LEN_MAX + 1))
    150 
    151 // Cap on the seed-sized key staging buffer, so a large seed cannot force 256 copies at once
    152 #ifndef SFINX_BATCH_KEY_BUDGET
    153 #define SFINX_BATCH_KEY_BUDGET (64u * 1024u)
    154 #endif
    155 
    156 static inline void _sfinx_wots_preimage(sfinx_hash hash, const uint8_t *key, size_t key_len, uint8_t *out) {
    157   size_t len = sfinx_hash_len(hash);
    158   _sfinx_shake256(key, key_len, out, (len + 2) * len);
    159 }
    160 
    161 static inline void _sfinx_wots_digits(sfinx_hash hash, const uint8_t *value, uint8_t *out) {
    162   size_t   len      = sfinx_hash_len(hash);
    163   uint32_t checksum = 0;
    164   for (size_t i = 0; i < len; i++) {
    165     out[i] = value[i];
    166     checksum += 255 - value[i];
    167   }
    168   out[len]     = (uint8_t)(checksum >> 8);
    169   out[len + 1] = (uint8_t)checksum;
    170 }
    171 
    172 static inline void _sfinx_wots_tails(sfinx_hash hash, const uint8_t *kid, uint8_t *out) {
    173   size_t len = sfinx_hash_len(hash);
    174   size_t k   = _sfinx_kid_len(hash);
    175   for (size_t i = 0; i < len + 2; i++) {
    176     memcpy(out + i * (k + 1), kid, k);
    177     out[i * (k + 1) + k] = (uint8_t)i;
    178   }
    179 }
    180 
    181 static inline void _sfinx_wots_chain(sfinx_hash hash, uint8_t *node, const uint8_t *kid, uint8_t index, uint8_t from,
    182                                      uint32_t steps) {
    183   uint8_t tail[SFINX_HASH_LEN_MAX + 1];
    184   size_t  k = _sfinx_kid_len(hash);
    185   memcpy(tail, kid, k);
    186   tail[k] = index;
    187   _sfinx_chain_batch(hash, 1, node, tail, k + 1, from, steps);
    188 }
    189 
    190 static inline void _sfinx_wots_pubkey(sfinx_hash hash, const uint8_t *key, size_t key_len, size_t seed_len,
    191                                       uint8_t *pubkey_out) {
    192   size_t  len   = sfinx_hash_len(hash);
    193   size_t  count = len + 2;
    194   size_t  k     = _sfinx_kid_len(hash);
    195   uint8_t ends[SFINX_WOTS_BYTES_MAX];
    196   uint8_t kid[SFINX_HASH_LEN_MAX];
    197   uint8_t tails[SFINX_WOTS_TAIL_MAX];
    198   _sfinx_wots_preimage(hash, key, key_len, ends);
    199   _sfinx_kid(hash, key + seed_len, key_len - seed_len, kid);
    200   _sfinx_wots_tails(hash, kid, tails);
    201   _sfinx_chain_batch(hash, count, ends, tails, k + 1, 0, 256);
    202   _sfinx_hash(hash, ends, count * len, pubkey_out);
    203 }
    204 
    205 static inline sfinx_status _sfinx_wots_sign(sfinx_hash hash, const uint8_t *key, size_t key_len, size_t seed_len,
    206                                             const uint8_t *value, size_t value_len, uint8_t *proof_out) {
    207   size_t  len = sfinx_hash_len(hash);
    208   uint8_t digits[SFINX_WOTS_DIGITS_MAX];
    209   uint8_t kid[SFINX_HASH_LEN_MAX];
    210   if (len == 0 || value_len != len) {
    211     return SFINX_ERR_ARGS;
    212   }
    213   _sfinx_wots_preimage(hash, key, key_len, proof_out);
    214   _sfinx_wots_digits(hash, value, digits);
    215   _sfinx_kid(hash, key + seed_len, key_len - seed_len, kid);
    216   for (size_t i = 0; i < len + 2; i++) {
    217     _sfinx_wots_chain(hash, proof_out + i * len, kid, (uint8_t)i, 0, digits[i]);
    218   }
    219   return SFINX_OK;
    220 }
    221 
    222 static inline void _sfinx_wots_rebuild(sfinx_hash hash, const uint8_t *value, const uint8_t *proof, const uint8_t *kid,
    223                                        uint8_t *pubkey_out) {
    224   size_t  len = sfinx_hash_len(hash);
    225   uint8_t digits[SFINX_WOTS_DIGITS_MAX];
    226   uint8_t ends[SFINX_WOTS_BYTES_MAX];
    227   uint8_t node[SFINX_HASH_LEN_MAX];
    228   _sfinx_wots_digits(hash, value, digits);
    229   for (size_t i = 0; i < len + 2; i++) {
    230     memcpy(node, proof + i * len, len);
    231     _sfinx_wots_chain(hash, node, kid, (uint8_t)i, digits[i], 256 - digits[i]);
    232     memcpy(ends + i * len, node, len);
    233   }
    234   _sfinx_hash(hash, ends, (len + 2) * len, pubkey_out);
    235 }
    236 
    237 static inline int _sfinx_wots_verify(sfinx_hash hash, const uint8_t *pubkey, const uint8_t *value, const uint8_t *proof,
    238                                      const uint8_t *kid) {
    239   uint8_t want[SFINX_HASH_LEN_MAX];
    240   _sfinx_wots_rebuild(hash, value, proof, kid, want);
    241   return memcmp(want, pubkey, sfinx_hash_len(hash)) == 0;
    242 }
    243 // }}}
    244 
    245 // Pool {{{
    246 //
    247 // Compile-time worker pool for one top-level operation
    248 //   _REENTRANT: a round pulls indices from a shared counter, one scratch per worker
    249 //   otherwise, and for counts under two, the loop runs on the caller
    250 
    251 typedef void (*_sfinx_job_fn)(void *ctx, size_t index, void *scratch);
    252 
    253 #ifdef _REENTRANT
    254 typedef struct {
    255   struct _sfinx_pool *pool;
    256   size_t              index;
    257 } _sfinx_worker;
    258 #endif
    259 
    260 typedef struct _sfinx_pool {
    261   size_t count;
    262 #ifdef _REENTRANT
    263   pthread_t      *threads;
    264   _sfinx_worker  *workers;
    265   pthread_mutex_t mutex;
    266   pthread_cond_t  work;
    267   pthread_cond_t  done;
    268   _sfinx_job_fn   fn;
    269   void           *ctx;
    270   size_t          total;
    271   size_t          next;
    272   size_t          completed;
    273   unsigned long   round;
    274   size_t          scratch;
    275   uint8_t        *scratch_mem;
    276   int             stop;
    277 #endif
    278 } _sfinx_pool;
    279 
    280 static inline size_t _sfinx_pool_scratch(size_t key_len) {
    281   return key_len > SFINX_BATCH_KEY_BUDGET ? key_len : SFINX_BATCH_KEY_BUDGET;
    282 }
    283 
    284 #ifdef _REENTRANT
    285 static void *_sfinx_pool_worker(void *arg) {
    286   _sfinx_worker *worker  = arg;
    287   _sfinx_pool   *pool    = worker->pool;
    288   uint8_t       *scratch = pool->scratch_mem + (worker->index + 1) * pool->scratch;
    289   unsigned long  seen    = 0;
    290 
    291   for (;;) {
    292     pthread_mutex_lock(&pool->mutex);
    293     while (!pool->stop && pool->round == seen) {
    294       pthread_cond_wait(&pool->work, &pool->mutex);
    295     }
    296     if (pool->stop) {
    297       pthread_mutex_unlock(&pool->mutex);
    298       return NULL;
    299     }
    300     seen = pool->round;
    301     pthread_mutex_unlock(&pool->mutex);
    302     for (;;) {
    303       size_t i;
    304       pthread_mutex_lock(&pool->mutex);
    305       if (pool->next >= pool->total) {
    306         pthread_mutex_unlock(&pool->mutex);
    307         break;
    308       }
    309       i = pool->next++;
    310       pthread_mutex_unlock(&pool->mutex);
    311       pool->fn(pool->ctx, i, scratch);
    312       pthread_mutex_lock(&pool->mutex);
    313       pool->completed++;
    314       if (pool->completed == pool->total) {
    315         pthread_cond_broadcast(&pool->done);
    316       }
    317       pthread_mutex_unlock(&pool->mutex);
    318     }
    319   }
    320 }
    321 #endif
    322 
    323 static void _sfinx_pool_destroy(_sfinx_pool *pool) {
    324 #ifdef _REENTRANT
    325   if (!pool) {
    326     return;
    327   }
    328   pthread_mutex_lock(&pool->mutex);
    329   pool->stop = 1;
    330   pthread_cond_broadcast(&pool->work);
    331   pthread_mutex_unlock(&pool->mutex);
    332   for (size_t i = 0; i < pool->count; i++) {
    333     pthread_join(pool->threads[i], NULL);
    334   }
    335   pthread_mutex_destroy(&pool->mutex);
    336   pthread_cond_destroy(&pool->work);
    337   pthread_cond_destroy(&pool->done);
    338   free(pool->scratch_mem);
    339   free(pool->threads);
    340   free(pool->workers);
    341   free(pool);
    342 #else
    343   (void)pool;
    344 #endif
    345 }
    346 
    347 static _sfinx_pool *_sfinx_pool_create(size_t scratch) {
    348 #ifdef _REENTRANT
    349   _sfinx_pool *pool;
    350   long         n;
    351 
    352   if (scratch == 0) {
    353     scratch = 1;
    354   }
    355   n = sysconf(_SC_NPROCESSORS_ONLN);
    356   if (n <= 1) {
    357     return NULL;
    358   }
    359   pool = calloc(1, sizeof(*pool));
    360   if (!pool) {
    361     return NULL;
    362   }
    363   pool->count       = (size_t)n;
    364   pool->scratch     = scratch;
    365   pool->scratch_mem = malloc((pool->count + 1) * scratch);
    366   pool->threads     = calloc(pool->count, sizeof(*pool->threads));
    367   pool->workers     = calloc(pool->count, sizeof(*pool->workers));
    368   if (!pool->scratch_mem || !pool->threads || !pool->workers) {
    369     free(pool->scratch_mem);
    370     free(pool->threads);
    371     free(pool->workers);
    372     free(pool);
    373     return NULL;
    374   }
    375   if (pthread_mutex_init(&pool->mutex, NULL) != 0) {
    376     free(pool->scratch_mem);
    377     free(pool->threads);
    378     free(pool->workers);
    379     free(pool);
    380     return NULL;
    381   }
    382   if (pthread_cond_init(&pool->work, NULL) != 0) {
    383     pthread_mutex_destroy(&pool->mutex);
    384     free(pool->scratch_mem);
    385     free(pool->threads);
    386     free(pool->workers);
    387     free(pool);
    388     return NULL;
    389   }
    390   if (pthread_cond_init(&pool->done, NULL) != 0) {
    391     pthread_cond_destroy(&pool->work);
    392     pthread_mutex_destroy(&pool->mutex);
    393     free(pool->scratch_mem);
    394     free(pool->threads);
    395     free(pool->workers);
    396     free(pool);
    397     return NULL;
    398   }
    399   for (size_t i = 0; i < pool->count; i++) {
    400     pool->workers[i].pool  = pool;
    401     pool->workers[i].index = i;
    402   }
    403   for (size_t i = 0; i < pool->count; i++) {
    404     if (pthread_create(&pool->threads[i], NULL, _sfinx_pool_worker, &pool->workers[i]) != 0) {
    405       pool->count = i;
    406       _sfinx_pool_destroy(pool);
    407       return NULL;
    408     }
    409   }
    410   return pool;
    411 #else
    412   (void)scratch;
    413   return NULL;
    414 #endif
    415 }
    416 
    417 static void _sfinx_parallel_for(_sfinx_pool *pool, size_t count, _sfinx_job_fn fn, void *ctx) {
    418   uint8_t *scratch;
    419 #ifdef _REENTRANT
    420   if (pool && count >= 2) {
    421     scratch = pool->scratch_mem;
    422     pthread_mutex_lock(&pool->mutex);
    423     pool->fn        = fn;
    424     pool->ctx       = ctx;
    425     pool->total     = count;
    426     pool->next      = 0;
    427     pool->completed = 0;
    428     pool->round++;
    429     pthread_cond_broadcast(&pool->work);
    430     pthread_mutex_unlock(&pool->mutex);
    431     for (;;) {
    432       size_t i;
    433       pthread_mutex_lock(&pool->mutex);
    434       if (pool->next >= pool->total) {
    435         pthread_mutex_unlock(&pool->mutex);
    436         break;
    437       }
    438       i = pool->next++;
    439       pthread_mutex_unlock(&pool->mutex);
    440       fn(ctx, i, scratch);
    441       pthread_mutex_lock(&pool->mutex);
    442       pool->completed++;
    443       if (pool->completed == pool->total) {
    444         pthread_cond_broadcast(&pool->done);
    445       }
    446       pthread_mutex_unlock(&pool->mutex);
    447     }
    448     pthread_mutex_lock(&pool->mutex);
    449     while (pool->completed < pool->total) {
    450       pthread_cond_wait(&pool->done, &pool->mutex);
    451     }
    452     pthread_mutex_unlock(&pool->mutex);
    453     return;
    454   }
    455   scratch = pool ? pool->scratch_mem : NULL;
    456 #else
    457   (void)pool;
    458   scratch = NULL;
    459 #endif
    460   for (size_t i = 0; i < count; i++) {
    461     fn(ctx, i, scratch);
    462   }
    463 }
    464 // }}}
    465 
    466 // Subtree {{{
    467 //
    468 // One binary subtree of height 8, 256 WOTS leaves folded into a root
    469 //   leaf i is keyed by SHAKE256(seed | prefix | i)
    470 //   parent = H(bitlen | mask | prefix | left | right), the mask from the leaf index
    471 //   build returns the root, and for one leaf the 8 auth siblings, deepest first
    472 //   verify folds a leaf and its siblings back up to the root
    473 
    474 static inline uint8_t _sfinx_node_mask(uint8_t bitlen, uint8_t index) {
    475   return (uint8_t)(index & (0xFFu << (8 - bitlen)));
    476 }
    477 
    478 static inline void _sfinx_merkle_parent(sfinx_hash hash, uint8_t bitlen, uint8_t mask, const uint8_t *prefix,
    479                                         size_t prefix_len, const uint8_t *left, const uint8_t *right, uint8_t *out) {
    480   size_t  len = sfinx_hash_len(hash);
    481   uint8_t buf[2 + prefix_len + 2 * len];
    482   size_t  at = 0;
    483   buf[at++]  = bitlen;
    484   buf[at++]  = mask;
    485   if (prefix_len > 0) {
    486     memcpy(buf + at, prefix, prefix_len);
    487     at += prefix_len;
    488   }
    489   memcpy(buf + at, left, len);
    490   at += len;
    491   memcpy(buf + at, right, len);
    492   at += len;
    493   _sfinx_hash(hash, buf, at, out);
    494 }
    495 
    496 static inline void _sfinx_subtree_leaves(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *prefix,
    497                                          size_t prefix_len, size_t begin, size_t end, uint8_t *ends, uint8_t *nodes,
    498                                          uint8_t *tails, uint8_t *keybuf) {
    499   size_t len      = sfinx_hash_len(hash);
    500   size_t c        = len + 2;
    501   size_t k        = _sfinx_kid_len(hash);
    502   size_t key_len  = seed_len + prefix_len + 1;
    503   size_t tail_len = k + 1;
    504   size_t chunk    = SFINX_BATCH_KEY_BUDGET / key_len;
    505   size_t n        = end - begin;
    506 
    507   if (chunk == 0) {
    508     chunk = 1;
    509   }
    510   for (size_t base = 0; base < n; base += chunk) {
    511     size_t m = n - base;
    512     if (m > chunk) {
    513       m = chunk;
    514     }
    515     for (size_t i = 0; i < m; i++) {
    516       uint8_t *key = keybuf + i * key_len;
    517       memcpy(key, seed, seed_len);
    518       if (prefix_len > 0) {
    519         memcpy(key + seed_len, prefix, prefix_len);
    520       }
    521       key[key_len - 1] = (uint8_t)(begin + base + i);
    522     }
    523     _sfinx_shake256_batch(m, keybuf, key_len, ends + (begin + base) * c * len, c * len);
    524     for (size_t i = 0; i < m; i++) {
    525       uint8_t  kid[SFINX_HASH_LEN_MAX];
    526       uint8_t *key = keybuf + i * key_len;
    527       _sfinx_kid(hash, key + seed_len, prefix_len + 1, kid);
    528       _sfinx_wots_tails(hash, kid, tails + (begin + base + i) * c * tail_len);
    529     }
    530   }
    531   _sfinx_chain_batch(hash, n * c, ends + begin * c * len, tails + begin * c * tail_len, tail_len, 0, 256);
    532   _sfinx_hash_batch(hash, n, ends + begin * c * len, c * len, nodes + begin * len, len);
    533 }
    534 
    535 typedef struct {
    536   sfinx_hash     hash;
    537   const uint8_t *seed;
    538   size_t         seed_len;
    539   const uint8_t *prefix;
    540   size_t         prefix_len;
    541   size_t         chunk;
    542   size_t         count;
    543   uint8_t       *ends;
    544   uint8_t       *nodes;
    545   uint8_t       *tails;
    546 } _sfinx_subtree_ctx;
    547 
    548 static void _sfinx_subtree_job(void *vctx, size_t index, void *scratch) {
    549   _sfinx_subtree_ctx *ctx   = vctx;
    550   size_t              begin = index * ctx->chunk;
    551   size_t              end   = begin + ctx->chunk;
    552 
    553   if (end > ctx->count) {
    554     end = ctx->count;
    555   }
    556   _sfinx_subtree_leaves(ctx->hash, ctx->seed, ctx->seed_len, ctx->prefix, ctx->prefix_len, begin, end, ctx->ends,
    557                         ctx->nodes, ctx->tails, scratch);
    558 }
    559 
    560 static inline int _sfinx_subtree_build(_sfinx_pool *pool, sfinx_hash hash, const uint8_t *seed, size_t seed_len,
    561                                        const uint8_t *prefix, size_t prefix_len, uint8_t leaf_index, uint8_t *root_out,
    562                                        uint8_t *auth_out) {
    563   size_t   len      = sfinx_hash_len(hash);
    564   size_t   c        = len + 2;
    565   size_t   key_len  = seed_len + prefix_len + 1;
    566   size_t   tail_len = _sfinx_kid_len(hash) + 1;
    567   size_t   count    = 256;
    568   size_t   pos      = leaf_index;
    569   uint8_t  nodes[256 * SFINX_HASH_LEN_MAX];
    570   uint8_t *ends;
    571   uint8_t *tails;
    572 
    573   ends = malloc(count * c * len);
    574   if (!ends) {
    575     return 0;
    576   }
    577   tails = malloc(count * c * tail_len);
    578   if (!tails) {
    579     free(ends);
    580     return 0;
    581   }
    582   if (pool) {
    583     _sfinx_subtree_ctx ctx = {
    584         .hash       = hash,
    585         .seed       = seed,
    586         .seed_len   = seed_len,
    587         .prefix     = prefix,
    588         .prefix_len = prefix_len,
    589         .chunk      = (count + pool->count - 1) / pool->count,
    590         .count      = count,
    591         .ends       = ends,
    592         .nodes      = nodes,
    593         .tails      = tails,
    594     };
    595     size_t jobs;
    596     if (ctx.chunk == 0) {
    597       ctx.chunk = 1;
    598     }
    599     jobs = (count + ctx.chunk - 1) / ctx.chunk;
    600     _sfinx_parallel_for(pool, jobs, _sfinx_subtree_job, &ctx);
    601   } else {
    602     size_t   chunk = SFINX_BATCH_KEY_BUDGET / key_len;
    603     uint8_t *keybuf;
    604     if (chunk == 0) {
    605       chunk = 1;
    606     }
    607     if (chunk > count) {
    608       chunk = count;
    609     }
    610     keybuf = malloc(chunk * key_len);
    611     if (!keybuf) {
    612       free(tails);
    613       free(ends);
    614       return 0;
    615     }
    616     _sfinx_subtree_leaves(hash, seed, seed_len, prefix, prefix_len, 0, count, ends, nodes, tails, keybuf);
    617     free(keybuf);
    618   }
    619   for (size_t bitlen = 8; bitlen-- > 0;) {
    620     if (auth_out) {
    621       memcpy(auth_out + (7 - bitlen) * len, nodes + (pos ^ 1) * len, len);
    622     }
    623     count /= 2;
    624     for (size_t j = 0; j < count; j++) {
    625       _sfinx_merkle_parent(hash, (uint8_t)bitlen, _sfinx_node_mask((uint8_t)bitlen, (uint8_t)(j << (8 - bitlen))),
    626                            prefix, prefix_len, nodes + (2 * j) * len, nodes + (2 * j + 1) * len, nodes + j * len);
    627     }
    628     pos >>= 1;
    629   }
    630   memcpy(root_out, nodes, len);
    631   free(tails);
    632   free(ends);
    633   return 1;
    634 }
    635 
    636 static inline void _sfinx_subtree_verify(sfinx_hash hash, const uint8_t *prefix, size_t prefix_len, const uint8_t *leaf,
    637                                          uint8_t leaf_index, const uint8_t *auth, uint8_t *root_out) {
    638   size_t  len = sfinx_hash_len(hash);
    639   uint8_t node[SFINX_HASH_LEN_MAX];
    640   uint8_t tmp[SFINX_HASH_LEN_MAX];
    641   size_t  pos = leaf_index;
    642   memcpy(node, leaf, len);
    643   for (size_t bitlen = 8; bitlen-- > 0;) {
    644     uint8_t        mask = _sfinx_node_mask((uint8_t)bitlen, (uint8_t)((pos >> 1) << (8 - bitlen)));
    645     const uint8_t *sib  = auth + (7 - bitlen) * len;
    646     if (pos & 1) {
    647       _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, sib, node, tmp);
    648     } else {
    649       _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, node, sib, tmp);
    650     }
    651     memcpy(node, tmp, len);
    652     pos >>= 1;
    653   }
    654   memcpy(root_out, node, len);
    655 }
    656 // }}}
    657 
    658 // API - Sign {{{
    659 //
    660 // Thin wrappers over WOTS and Subtree, one WOTS per layer
    661 //   single = one WOTS over SHAKE256(seed), signs H(message)
    662 //   tree   = N subtrees, layer k signs R_k, R_N = org = H(path | message)
    663 
    664 sfinx_status sfinx_single_public_key(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *pubkey_out,
    665                                      size_t pubkey_cap, size_t *pubkey_len_out) {
    666   size_t len = sfinx_hash_len(hash);
    667   if (len == 0 || !seed || seed_len > SFINX_SEED_LEN_MAX) {
    668     return SFINX_ERR_ARGS;
    669   }
    670   if (!pubkey_out || pubkey_cap < len) {
    671     return SFINX_ERR_NOSPACE;
    672   }
    673   _sfinx_wots_pubkey(hash, seed, seed_len, seed_len, pubkey_out);
    674   if (pubkey_len_out) {
    675     *pubkey_len_out = len;
    676   }
    677   return SFINX_OK;
    678 }
    679 
    680 sfinx_status sfinx_single_sign(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *msg,
    681                                size_t msg_len, uint8_t *sig, size_t sig_cap, size_t *sig_len_out) {
    682   size_t  len  = sfinx_hash_len(hash);
    683   size_t  need = sfinx_signature_len(hash, 0);
    684   uint8_t org[SFINX_HASH_LEN_MAX];
    685   if (len == 0 || !seed || !msg || seed_len > SFINX_SEED_LEN_MAX) {
    686     return SFINX_ERR_ARGS;
    687   }
    688   if (!sig || sig_cap < need) {
    689     return SFINX_ERR_NOSPACE;
    690   }
    691   _sfinx_hash(hash, msg, msg_len, org);
    692   _sfinx_e4m4_encode(0, sig);
    693   _sfinx_e4m4_encode((uint32_t)len, sig + 1);
    694   if (_sfinx_wots_sign(hash, seed, seed_len, seed_len, org, len, sig + 2) != SFINX_OK) {
    695     return SFINX_ERR_ARGS;
    696   }
    697   if (sig_len_out) {
    698     *sig_len_out = need;
    699   }
    700   return SFINX_OK;
    701 }
    702 
    703 sfinx_status sfinx_tree_public_key(sfinx_hash hash, const uint8_t *seed, size_t seed_len, size_t path_len,
    704                                    uint8_t *pubkey_out, size_t pubkey_cap, size_t *pubkey_len_out) {
    705   size_t       len = sfinx_hash_len(hash);
    706   uint8_t      prefix;
    707   _sfinx_pool *pool;
    708   int          ok;
    709   if (len == 0 || !seed || seed_len > SFINX_SEED_LEN_MAX) {
    710     return SFINX_ERR_ARGS;
    711   }
    712   if (path_len == 0 || !sfinx_path_len_valid(path_len)) {
    713     return SFINX_ERR_PATH_LEN;
    714   }
    715   if (!pubkey_out || pubkey_cap < len) {
    716     return SFINX_ERR_NOSPACE;
    717   }
    718   _sfinx_e4m4_encode((uint32_t)path_len, &prefix);
    719   pool = _sfinx_pool_create(_sfinx_pool_scratch(seed_len + 2));
    720   ok   = _sfinx_subtree_build(pool, hash, seed, seed_len, &prefix, 1, 0, pubkey_out, NULL);
    721   _sfinx_pool_destroy(pool);
    722   if (!ok) {
    723     return SFINX_ERR_NOSPACE;
    724   }
    725   if (pubkey_len_out) {
    726     *pubkey_len_out = len;
    727   }
    728   return SFINX_OK;
    729 }
    730 
    731 sfinx_status sfinx_tree_sign(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *path,
    732                              size_t path_len, const uint8_t *msg, size_t msg_len, uint8_t *sig, size_t sig_cap,
    733                              size_t *sig_len_out) {
    734   size_t       len  = sfinx_hash_len(hash);
    735   size_t       c    = len + 2;
    736   size_t       need = sfinx_signature_len(hash, path_len);
    737   uint8_t      org[SFINX_HASH_LEN_MAX];
    738   uint8_t      value[SFINX_HASH_LEN_MAX];
    739   uint8_t      root[SFINX_HASH_LEN_MAX];
    740   uint8_t      auth[8 * SFINX_HASH_LEN_MAX];
    741   uint8_t     *key;
    742   uint8_t     *joined;
    743   size_t       at;
    744   _sfinx_pool *pool;
    745 
    746   if (len == 0 || !seed || !msg || seed_len > SFINX_SEED_LEN_MAX || !path || path_len == 0 ||
    747       !sfinx_path_len_valid(path_len)) {
    748     return SFINX_ERR_ARGS;
    749   }
    750   if (!sig || sig_cap < need) {
    751     return SFINX_ERR_NOSPACE;
    752   }
    753   joined = malloc(path_len + msg_len);
    754   key    = malloc(seed_len + path_len + 1);
    755   if (!joined || !key) {
    756     free(joined);
    757     free(key);
    758     return SFINX_ERR_NOSPACE;
    759   }
    760   pool = _sfinx_pool_create(_sfinx_pool_scratch(seed_len + path_len + 1));
    761   // Sign (path||message)
    762   memcpy(joined, path, path_len);
    763   memcpy(joined + path_len, msg, msg_len);
    764   _sfinx_hash(hash, joined, path_len + msg_len, org);
    765   free(joined);
    766 
    767   // Prep sig header, sig[0..path_len] is also the derivation prefix
    768   _sfinx_e4m4_encode((uint32_t)path_len, sig);
    769   memcpy(sig + 1, path, path_len);
    770   at = 1 + path_len;
    771   _sfinx_e4m4_encode((uint32_t)len, sig + at);
    772   at += 1;
    773 
    774   memcpy(key, seed, seed_len);
    775   memcpy(key + seed_len, sig, path_len + 1);
    776 
    777   // WOTS-sign up the tree
    778   memcpy(value, org, len);
    779   for (size_t k = path_len; k >= 1; k--) {
    780     if (!_sfinx_subtree_build(pool, hash, seed, seed_len, sig, k, sig[k], root, auth)) {
    781       _sfinx_pool_destroy(pool);
    782       free(key);
    783       return SFINX_ERR_NOSPACE;
    784     }
    785     if (_sfinx_wots_sign(hash, key, seed_len + k + 1, seed_len, value, len, sig + at) != SFINX_OK) {
    786       _sfinx_pool_destroy(pool);
    787       free(key);
    788       return SFINX_ERR_ARGS;
    789     }
    790     at += c * len;
    791     memcpy(sig + at, auth, 8 * len);
    792     at += 8 * len;
    793     memcpy(value, root, len);
    794   }
    795 
    796   _sfinx_pool_destroy(pool);
    797   free(key);
    798   if (sig_len_out) {
    799     *sig_len_out = need;
    800   }
    801   return SFINX_OK;
    802 }
    803 
    804 // }}}
    805 
    806 // API - Verify {{{
    807 //
    808 // Parse the layout, then walk from the top round down
    809 //   single: rebuild the one WOTS pubkey over H(message) and compare
    810 //   tree: rebuild layer k over R_k, fold subtree k-1 to R_{k-1}, R_0 is the pubkey
    811 
    812 sfinx_status sfinx_verify(const uint8_t *pubkey, size_t pubkey_len, const uint8_t *msg, size_t msg_len,
    813                           const uint8_t *sig, size_t sig_len) {
    814   size_t         path_len;
    815   size_t         len;
    816   size_t         c;
    817   size_t         at;
    818   sfinx_hash     hash;
    819   uint8_t        org[SFINX_HASH_LEN_MAX];
    820   uint8_t        value[SFINX_HASH_LEN_MAX];
    821   uint8_t        leaf[SFINX_HASH_LEN_MAX];
    822   uint8_t        root[SFINX_HASH_LEN_MAX];
    823   uint8_t        kid[SFINX_HASH_LEN_MAX];
    824   const uint8_t *path;
    825   uint8_t       *joined;
    826 
    827   if (!pubkey || !msg || !sig || sig_len < 2) {
    828     return SFINX_ERR_ARGS;
    829   }
    830   path_len = _sfinx_e4m4_decode(sig[0]);
    831   path     = sig + 1;
    832   at       = 1 + path_len;
    833   if (!sfinx_path_len_valid(path_len) || sig_len < at + 1) {
    834     return SFINX_ERR_FORMAT;
    835   }
    836   len = _sfinx_e4m4_decode(sig[at]);
    837   at += 1;
    838   hash = _sfinx_hash_from_len(len);
    839   if (!hash || len != pubkey_len || sig_len != sfinx_signature_len(hash, path_len)) {
    840     return SFINX_ERR_FORMAT;
    841   }
    842   c = len + 2;
    843   if (path_len == 0) {
    844     _sfinx_hash(hash, msg, msg_len, org);
    845     _sfinx_kid(hash, NULL, 0, kid);
    846     return _sfinx_wots_verify(hash, pubkey, org, sig + at, kid) ? SFINX_OK : SFINX_ERR_VERIFY;
    847   }
    848   joined = malloc(path_len + msg_len);
    849   if (!joined) {
    850     return SFINX_ERR_NOSPACE;
    851   }
    852   memcpy(joined, path, path_len);
    853   memcpy(joined + path_len, msg, msg_len);
    854   _sfinx_hash(hash, joined, path_len + msg_len, org);
    855   free(joined);
    856   memcpy(value, org, len);
    857   for (size_t k = path_len; k >= 1; k--) {
    858     _sfinx_kid(hash, sig, k + 1, kid);
    859     _sfinx_wots_rebuild(hash, value, sig + at, kid, leaf);
    860     at += c * len;
    861     _sfinx_subtree_verify(hash, sig, k, leaf, sig[k], sig + at, root);
    862     at += 8 * len;
    863     if (k == 1) {
    864       return memcmp(root, pubkey, len) == 0 ? SFINX_OK : SFINX_ERR_VERIFY;
    865     }
    866     memcpy(value, root, len);
    867   }
    868   return SFINX_ERR_FORMAT;
    869 }
    870 // }}}
    871 
    872 // API - Utilities {{{
    873 //
    874 // Pure size helpers, status names, and the optional RNG
    875 //   sizes = E4M4(N) | path | E4M4(L) | N rounds of WOTS proof and auth path
    876 
    877 const char *sfinx_strerror(sfinx_status status) {
    878   switch (status) {
    879     case SFINX_OK:                return "ok";
    880     case SFINX_ERR_ARGS:          return "invalid arguments";
    881     case SFINX_ERR_PATH_LEN:      return "invalid path length";
    882     case SFINX_ERR_NOSPACE:       return "no space available";
    883     case SFINX_ERR_FORMAT:        return "invalid signature format";
    884     case SFINX_ERR_VERIFY:        return "verification failed";
    885     case SFINX_ERR_RANDOM:        return "random source failed";
    886     case SFINX_ERR_UNIMPLEMENTED: return "unimplemented";
    887   }
    888   return "unknown error";
    889 }
    890 
    891 #ifndef SFINX_VERSION
    892 #define SFINX_VERSION "n/a-dev"
    893 #endif
    894 
    895 const char *sfinx_version(void) {
    896   return SFINX_VERSION;
    897 }
    898 
    899 size_t sfinx_signature_len(sfinx_hash hash, size_t path_len) {
    900   size_t len = sfinx_hash_len(hash);
    901   if (len == 0) {
    902     return 0;
    903   }
    904   if (path_len == 0) {
    905     return 2 + (len + 2) * len;
    906   }
    907   return 2 + path_len + path_len * (len + 10) * len;
    908 }
    909 
    910 size_t sfinx_signature_len_max(sfinx_hash hash) {
    911   return sfinx_signature_len(hash, SFINX_PATH_LEN_MAX);
    912 }
    913 
    914 int sfinx_path_len_valid(size_t path_len) {
    915   uint8_t byte;
    916   return path_len <= SFINX_PATH_LEN_MAX && _sfinx_e4m4_encode((uint32_t)path_len, &byte);
    917 }
    918 
    919 sfinx_status sfinx_signature_info(const uint8_t *sig, size_t sig_len, sfinx_hash *hash_out, size_t *path_len_out) {
    920   size_t     path_len;
    921   sfinx_hash hash;
    922   if (!sig || sig_len < 2) {
    923     return SFINX_ERR_ARGS;
    924   }
    925   path_len = _sfinx_e4m4_decode(sig[0]);
    926   if (!sfinx_path_len_valid(path_len) || sig_len < 2 + path_len) {
    927     return SFINX_ERR_FORMAT;
    928   }
    929   hash = _sfinx_hash_from_len(_sfinx_e4m4_decode(sig[1 + path_len]));
    930   if (!hash) {
    931     return SFINX_ERR_FORMAT;
    932   }
    933   if (hash_out) {
    934     *hash_out = hash;
    935   }
    936   if (path_len_out) {
    937     *path_len_out = path_len;
    938   }
    939   return SFINX_OK;
    940 }
    941 
    942 sfinx_status sfinx_random_bytes(uint8_t *out, size_t len) {
    943   if (!out) {
    944     return SFINX_ERR_ARGS;
    945   }
    946   while (len > 0) {
    947     size_t chunk = len > 256 ? 256 : len;
    948     if (getentropy(out, chunk) != 0) {
    949       return SFINX_ERR_RANDOM;
    950     }
    951     out += chunk;
    952     len -= chunk;
    953   }
    954   return SFINX_OK;
    955 }
    956 // }}}
    957 
    958 // vim:fdm=marker:fdl=0