commit 2fc824e2073a38fda6d3d9b72d8aa1213fe7c9ef
parent ad26bdfbb0084e39ea2710ae56984b7dec86e5f1
Author: finwo <finwo@pm.me>
Date: Fri, 9 Oct 2026 18:21:17 +0200
Implement subtrees
Diffstat:
| M | src/sfinx.c | | | 109 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------ |
| M | src/sfinx.h | | | 9 | +++++++++ |
| A | test/03-merkle.c | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/04-subtree.c | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
4 files changed, 268 insertions(+), 7 deletions(-)
diff --git a/src/sfinx.c b/src/sfinx.c
@@ -1,6 +1,7 @@
#include "sfinx.h"
#include <coruus/keccak-tiny.h>
+#include <stdlib.h>
#include <string.h>
// E4M4 {{{
@@ -74,7 +75,8 @@ size_t sfinx_hash_len(sfinx_hash hash) {
// WOTS {{{
//
// One WOTS key over an L-byte value, c = L + 2 chains of length 256
-// preimage = SHAKE256(seed), c * L bytes, c elements of L bytes
+// key = seed for N = 0, seed | path for a tree leaf
+// preimage = SHAKE256(key), c * L bytes, c elements of L bytes
// digits = the value bytes, then 2 checksum bytes of 255 - value[i]
// pubkey = H of every element chained w times
// proof = every element chained d[i] times
@@ -83,9 +85,9 @@ size_t sfinx_hash_len(sfinx_hash hash) {
#define SFINX_WOTS_BYTES_MAX ((SFINX_HASH_LEN_MAX + 2) * SFINX_HASH_LEN_MAX)
#define SFINX_WOTS_DIGITS_MAX (SFINX_HASH_LEN_MAX + 2)
-static inline void _sfinx_wots_preimage(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *out) {
+static inline void _sfinx_wots_preimage(sfinx_hash hash, const uint8_t *key, size_t key_len, uint8_t *out) {
size_t len = sfinx_hash_len(hash);
- _sfinx_shake256(seed, seed_len, out, (len + 2) * len);
+ _sfinx_shake256(key, key_len, out, (len + 2) * len);
}
static inline void _sfinx_wots_digits(sfinx_hash hash, const uint8_t *value, uint8_t *out) {
@@ -108,21 +110,21 @@ static inline void _sfinx_wots_chain(sfinx_hash hash, uint8_t *node, uint32_t st
}
}
-static inline void _sfinx_wots_pubkey(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *pubkey_out) {
+static inline void _sfinx_wots_pubkey(sfinx_hash hash, const uint8_t *key, size_t key_len, uint8_t *pubkey_out) {
size_t len = sfinx_hash_len(hash);
uint8_t ends[SFINX_WOTS_BYTES_MAX];
- _sfinx_wots_preimage(hash, seed, seed_len, ends);
+ _sfinx_wots_preimage(hash, key, key_len, ends);
for (size_t i = 0; i < len + 2; i++) {
_sfinx_wots_chain(hash, ends + i * len, 256);
}
_sfinx_hash(hash, ends, (len + 2) * len, pubkey_out);
}
-static inline void _sfinx_wots_proof(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *value,
+static inline void _sfinx_wots_proof(sfinx_hash hash, const uint8_t *key, size_t key_len, const uint8_t *value,
uint8_t *proof_out) {
size_t len = sfinx_hash_len(hash);
uint8_t digits[SFINX_WOTS_DIGITS_MAX];
- _sfinx_wots_preimage(hash, seed, seed_len, proof_out);
+ _sfinx_wots_preimage(hash, key, key_len, proof_out);
_sfinx_wots_digits(hash, value, digits);
for (size_t i = 0; i < len + 2; i++) {
_sfinx_wots_chain(hash, proof_out + i * len, digits[i]);
@@ -147,4 +149,97 @@ static inline int _sfinx_wots_verify(sfinx_hash hash, const uint8_t *pubkey, con
}
// }}}
+// Merkle {{{
+//
+// Position-keyed parent hash of a binary subtree of height 8, 256 leaves
+// parent = H(bitlen | mask | prefix | left | right)
+// bitlen = the sub-byte depth d, mask = index & (0xFF << (8 - d)), low bits dropped
+
+static inline uint8_t _sfinx_node_mask(uint8_t bitlen, uint8_t index) {
+ return (uint8_t)(index & (0xFFu << (8 - bitlen)));
+}
+
+static inline void _sfinx_merkle_parent(sfinx_hash hash, uint8_t bitlen, uint8_t mask, const uint8_t *prefix,
+ size_t prefix_len, const uint8_t *left, const uint8_t *right, uint8_t *out) {
+ size_t len = sfinx_hash_len(hash);
+ uint8_t buf[2 + SFINX_PATH_LEN_MAX + 2 * SFINX_HASH_LEN_MAX];
+ size_t at = 0;
+ buf[at++] = bitlen;
+ buf[at++] = mask;
+ if (prefix_len > 0) {
+ memcpy(buf + at, prefix, prefix_len);
+ at += prefix_len;
+ }
+ memcpy(buf + at, left, len);
+ at += len;
+ memcpy(buf + at, right, len);
+ at += len;
+ _sfinx_hash(hash, buf, at, out);
+}
+// }}}
+
+// Subtree {{{
+//
+// One subtree of height 8, 256 WOTS leaves folded into a root
+// leaf i is keyed by SHAKE256(seed | prefix | i)
+// parent = H(bitlen | mask | prefix | left | right), the mask from the leaf index
+// build returns the root, and for one leaf the 8 auth siblings, deepest first
+// verify folds a leaf and its siblings back up to the root
+
+static inline int _sfinx_subtree_build(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *prefix,
+ size_t prefix_len, uint8_t leaf_index, uint8_t *root_out, uint8_t *auth_out) {
+ size_t len = sfinx_hash_len(hash);
+ size_t count = 256;
+ size_t pos = leaf_index;
+ uint8_t nodes[256 * SFINX_HASH_LEN_MAX];
+ uint8_t *key = malloc(seed_len + prefix_len + 1);
+ if (!key) {
+ return 0;
+ }
+ memcpy(key, seed, seed_len);
+ if (prefix_len > 0) {
+ memcpy(key + seed_len, prefix, prefix_len);
+ }
+ for (size_t i = 0; i < 256; i++) {
+ key[seed_len + prefix_len] = (uint8_t)i;
+ _sfinx_wots_pubkey(hash, key, seed_len + prefix_len + 1, nodes + i * len);
+ }
+ free(key);
+ for (size_t bitlen = 8; bitlen-- > 0;) {
+ if (auth_out) {
+ memcpy(auth_out + (7 - bitlen) * len, nodes + (pos ^ 1) * len, len);
+ }
+ count /= 2;
+ for (size_t j = 0; j < count; j++) {
+ _sfinx_merkle_parent(hash, (uint8_t)bitlen, _sfinx_node_mask((uint8_t)bitlen, (uint8_t)(j << (8 - bitlen))),
+ prefix, prefix_len, nodes + (2 * j) * len, nodes + (2 * j + 1) * len, nodes + j * len);
+ }
+ pos >>= 1;
+ }
+ memcpy(root_out, nodes, len);
+ return 1;
+}
+
+static inline void _sfinx_subtree_verify(sfinx_hash hash, const uint8_t *prefix, size_t prefix_len, const uint8_t *leaf,
+ uint8_t leaf_index, const uint8_t *auth, uint8_t *root_out) {
+ size_t len = sfinx_hash_len(hash);
+ uint8_t node[SFINX_HASH_LEN_MAX];
+ uint8_t tmp[SFINX_HASH_LEN_MAX];
+ size_t pos = leaf_index;
+ memcpy(node, leaf, len);
+ for (size_t bitlen = 8; bitlen-- > 0;) {
+ uint8_t mask = _sfinx_node_mask((uint8_t)bitlen, (uint8_t)((pos >> 1) << (8 - bitlen)));
+ const uint8_t *sib = auth + (7 - bitlen) * len;
+ if (pos & 1) {
+ _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, sib, node, tmp);
+ } else {
+ _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, node, sib, tmp);
+ }
+ memcpy(node, tmp, len);
+ pos >>= 1;
+ }
+ memcpy(root_out, node, len);
+}
+// }}}
+
// vim:fdm=marker:fdl=0
diff --git a/src/sfinx.h b/src/sfinx.h
@@ -22,6 +22,15 @@ typedef enum {
size_t sfinx_hash_len(sfinx_hash hash);
// }}}
+// Path {{{
+//
+// N is the number of subtrees, and the path length in bytes
+// 32 by default, at most 64
+
+#define SFINX_PATH_LEN_DEFAULT 32
+#define SFINX_PATH_LEN_MAX 64
+// }}}
+
#endif // __SFINX_H__
// vim:fdm=marker:fdl=0
diff --git a/test/03-merkle.c b/test/03-merkle.c
@@ -0,0 +1,90 @@
+#include <string.h>
+
+#include "_tap.c"
+#include "src/sfinx.c"
+
+static void check_u8(uint8_t got, uint8_t want, const char *what) {
+ tap(got == want, what, "got 0x%02x, want 0x%02x", got, want);
+}
+
+int main(void) {
+ static uint8_t tree[9][256][SFINX_HASH_LEN_MAX];
+ static uint8_t auth[8][SFINX_HASH_LEN_MAX];
+ uint8_t manual[2 + SFINX_PATH_LEN_MAX + 2 * SFINX_HASH_LEN_MAX];
+ uint8_t prefix[4] = {0xde, 0xad, 0xbe, 0xef};
+ uint8_t parent[SFINX_HASH_LEN_MAX];
+ uint8_t other[SFINX_HASH_LEN_MAX];
+ uint8_t node[SFINX_HASH_LEN_MAX];
+ uint8_t tmp[SFINX_HASH_LEN_MAX];
+ size_t len = sfinx_hash_len(SFINX_HASH_256);
+ size_t idx = 0x5a;
+ size_t pos;
+
+ tap_begin("sfinx Merkle");
+
+ check_u8(_sfinx_node_mask(0, 0xff), 0x00, "mask depth 0");
+ check_u8(_sfinx_node_mask(1, 0x80), 0x80, "mask depth 1, right");
+ check_u8(_sfinx_node_mask(1, 0x7f), 0x00, "mask depth 1, left");
+ check_u8(_sfinx_node_mask(6, 0x96), 0x94, "mask depth 6");
+ check_u8(_sfinx_node_mask(7, 0xff), 0xfe, "mask depth 7");
+ check_u8(_sfinx_node_mask(8, 0xab), 0xab, "mask depth 8");
+
+ for (size_t i = 0; i < SFINX_HASH_LEN_MAX; i++) {
+ tree[8][0][i] = (uint8_t)i;
+ tree[8][1][i] = (uint8_t)(255 - i);
+ }
+
+ manual[0] = 3;
+ manual[1] = 0x28;
+ memcpy(manual + 2, prefix, 4);
+ memcpy(manual + 6, tree[8][0], len);
+ memcpy(manual + 6 + len, tree[8][1], len);
+ _sfinx_hash(SFINX_HASH_256, manual, 2 + 4 + 2 * len, other);
+ _sfinx_merkle_parent(SFINX_HASH_256, 3, 0x28, prefix, 4, tree[8][0], tree[8][1], parent);
+ tap(memcmp(parent, other, len) == 0, "parent matches manual assembly", "parent differs");
+
+ _sfinx_merkle_parent(SFINX_HASH_256, 4, 0x28, prefix, 4, tree[8][0], tree[8][1], tmp);
+ tap(memcmp(parent, tmp, len) != 0, "bitlen changes the parent", "parents match");
+ _sfinx_merkle_parent(SFINX_HASH_256, 3, 0x29, prefix, 4, tree[8][0], tree[8][1], tmp);
+ tap(memcmp(parent, tmp, len) != 0, "mask changes the parent", "parents match");
+ _sfinx_merkle_parent(SFINX_HASH_256, 3, 0x28, prefix, 3, tree[8][0], tree[8][1], tmp);
+ tap(memcmp(parent, tmp, len) != 0, "prefix changes the parent", "parents match");
+ _sfinx_merkle_parent(SFINX_HASH_256, 3, 0x28, prefix, 4, tree[8][1], tree[8][0], tmp);
+ tap(memcmp(parent, tmp, len) != 0, "child order changes the parent", "parents match");
+
+ for (size_t i = 0; i < 256; i++) {
+ uint8_t leaf = (uint8_t)i;
+ _sfinx_hash(SFINX_HASH_256, &leaf, 1, tree[8][i]);
+ }
+
+ for (size_t d = 8; d-- > 0;) {
+ size_t n = (size_t)1 << d;
+ for (size_t j = 0; j < n; j++) {
+ _sfinx_merkle_parent(SFINX_HASH_256, (uint8_t)d, _sfinx_node_mask((uint8_t)d, (uint8_t)(j << (8 - d))), NULL, 0,
+ tree[d + 1][2 * j], tree[d + 1][2 * j + 1], tree[d][j]);
+ }
+ }
+
+ pos = idx;
+ for (size_t k = 0; k < 8; k++) {
+ memcpy(auth[k], tree[8 - k][pos ^ 1], len);
+ pos >>= 1;
+ }
+
+ pos = idx;
+ memcpy(node, tree[8][idx], len);
+ for (size_t k = 0; k < 8; k++) {
+ uint8_t pd = (uint8_t)(7 - k);
+ uint8_t pi = (uint8_t)((pos >> 1) << (8 - pd));
+ if (pos & 1) {
+ _sfinx_merkle_parent(SFINX_HASH_256, pd, _sfinx_node_mask(pd, pi), NULL, 0, auth[k], node, tmp);
+ } else {
+ _sfinx_merkle_parent(SFINX_HASH_256, pd, _sfinx_node_mask(pd, pi), NULL, 0, node, auth[k], tmp);
+ }
+ memcpy(node, tmp, len);
+ pos >>= 1;
+ }
+ tap(memcmp(node, tree[0][0], len) == 0, "auth path rebuilds the root", "root differs");
+
+ return tap_plan();
+}
diff --git a/test/04-subtree.c b/test/04-subtree.c
@@ -0,0 +1,67 @@
+#include <string.h>
+
+#include "_tap.c"
+#include "src/sfinx.c"
+
+int main(void) {
+ static const uint8_t seed[] = "sfinx subtree seed";
+ uint8_t prefix[3] = {0x11, 0x22, 0x33};
+ uint8_t prefix2[3] = {0x11, 0x22, 0x34};
+ uint8_t root[SFINX_HASH_LEN_MAX];
+ uint8_t root2[SFINX_HASH_LEN_MAX];
+ uint8_t auth[8 * SFINX_HASH_LEN_MAX];
+ uint8_t leaf[SFINX_HASH_LEN_MAX];
+ uint8_t leaf2[SFINX_HASH_LEN_MAX];
+ uint8_t built[SFINX_HASH_LEN_MAX];
+ uint8_t key[32];
+ uint8_t nodes[256 * SFINX_HASH_LEN_MAX];
+ uint8_t idx = 0x5a;
+ size_t len = sfinx_hash_len(SFINX_HASH_256);
+ size_t seed_len = strlen((const char *)seed);
+ size_t count;
+
+ tap_begin("sfinx subtree");
+
+ tap(_sfinx_subtree_build(SFINX_HASH_256, seed, seed_len, prefix, 3, idx, root, auth), "subtree builds",
+ "build failed");
+
+ memcpy(key, seed, seed_len);
+ memcpy(key + seed_len, prefix, 3);
+ key[seed_len + 3] = idx;
+ _sfinx_wots_pubkey(SFINX_HASH_256, key, seed_len + 4, leaf);
+ _sfinx_subtree_verify(SFINX_HASH_256, prefix, 3, leaf, idx, auth, built);
+ tap(memcmp(built, root, len) == 0, "auth path rebuilds the subtree root", "root differs");
+
+ auth[5] ^= 0x01;
+ _sfinx_subtree_verify(SFINX_HASH_256, prefix, 3, leaf, idx, auth, built);
+ tap(memcmp(built, root, len) != 0, "tampered auth fails", "root matched");
+ auth[5] ^= 0x01;
+
+ memcpy(leaf2, leaf, len);
+ leaf2[0] ^= 0x01;
+ _sfinx_subtree_verify(SFINX_HASH_256, prefix, 3, leaf2, idx, auth, built);
+ tap(memcmp(built, root, len) != 0, "tampered leaf fails", "root matched");
+
+ tap(_sfinx_subtree_build(SFINX_HASH_256, seed, seed_len, prefix2, 3, idx, root2, NULL), "second subtree builds",
+ "build failed");
+ tap(memcmp(root, root2, len) != 0, "prefix changes the subtree root", "roots match");
+
+ for (size_t i = 0; i < 256; i++) {
+ memcpy(key, seed, seed_len);
+ memcpy(key + seed_len, prefix, 3);
+ key[seed_len + 3] = (uint8_t)i;
+ _sfinx_wots_pubkey(SFINX_HASH_256, key, seed_len + 4, nodes + i * len);
+ }
+ count = 256;
+ for (size_t bitlen = 8; bitlen-- > 0;) {
+ count /= 2;
+ for (size_t j = 0; j < count; j++) {
+ _sfinx_merkle_parent(SFINX_HASH_256, (uint8_t)bitlen,
+ _sfinx_node_mask((uint8_t)bitlen, (uint8_t)(j << (8 - bitlen))), prefix, 3,
+ nodes + (2 * j) * len, nodes + (2 * j + 1) * len, nodes + j * len);
+ }
+ }
+ tap(memcmp(nodes, root, len) == 0, "manual fold matches the builder", "roots differ");
+
+ return tap_plan();
+}