commit bac5e9ae8b2c6067de9e768591129852d7503d3b
parent ec0650caea9d9fb6da96f19c192fa97888ee313d
Author: finwo <finwo@pm.me>
Date: Sat, 10 Oct 2026 20:15:01 +0200
Make use of keccak-fast batched methods
Diffstat:
4 files changed, 136 insertions(+), 16 deletions(-)
diff --git a/src/sfinx.c b/src/sfinx.c
@@ -48,6 +48,7 @@ static inline uint32_t _sfinx_e4m4_encode(uint32_t value, uint8_t *out) {
// SHA3 for fixed-size hashing, SHAKE256 for the pre-image XOF
// _sfinx_hash(hash, in, in_len, out)
// _sfinx_shake256(in, in_len, out, out_len)
+// the _batch forms drive the equal-length loops over keccak-fast's SIMD kernels
static inline void _sfinx_hash(sfinx_hash hash, const uint8_t *in, size_t in_len, uint8_t *out) {
switch (hash) {
@@ -58,10 +59,24 @@ static inline void _sfinx_hash(sfinx_hash hash, const uint8_t *in, size_t in_len
}
}
+static inline void _sfinx_hash_batch(sfinx_hash hash, size_t count, const uint8_t *in, size_t in_len, uint8_t *out,
+ size_t out_len) {
+ switch (hash) {
+ case SFINX_HASH_224: kf_sha3_224_batch(count, in, in_len, out, out_len); break;
+ case SFINX_HASH_256: kf_sha3_256_batch(count, in, in_len, out, out_len); break;
+ case SFINX_HASH_384: kf_sha3_384_batch(count, in, in_len, out, out_len); break;
+ case SFINX_HASH_512: kf_sha3_512_batch(count, in, in_len, out, out_len); break;
+ }
+}
+
static inline void _sfinx_shake256(const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) {
kf_shake256(out, out_len, in, in_len);
}
+static inline void _sfinx_shake256_batch(size_t count, const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) {
+ kf_shake256_batch(count, in, in_len, out, out_len);
+}
+
size_t sfinx_hash_len(sfinx_hash hash) {
switch (hash) {
case SFINX_HASH_224: return 28;
@@ -97,6 +112,11 @@ static inline sfinx_hash _sfinx_hash_from_len(size_t len) {
#define SFINX_WOTS_BYTES_MAX ((SFINX_HASH_LEN_MAX + 2) * SFINX_HASH_LEN_MAX)
#define SFINX_WOTS_DIGITS_MAX (SFINX_HASH_LEN_MAX + 2)
+// Cap on the seed-sized key staging buffer, so a large seed cannot force 256 copies at once
+#ifndef SFINX_BATCH_KEY_BUDGET
+#define SFINX_BATCH_KEY_BUDGET (64u * 1024u)
+#endif
+
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(key, key_len, out, (len + 2) * len);
@@ -123,13 +143,14 @@ 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 *key, size_t key_len, uint8_t *pubkey_out) {
- size_t len = sfinx_hash_len(hash);
+ size_t len = sfinx_hash_len(hash);
+ size_t count = len + 2;
uint8_t ends[SFINX_WOTS_BYTES_MAX];
_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);
+ for (uint32_t step = 0; step < 256u; step++) {
+ _sfinx_hash_batch(hash, count, ends, len, ends, len);
}
- _sfinx_hash(hash, ends, (len + 2) * len, pubkey_out);
+ _sfinx_hash(hash, ends, count * len, pubkey_out);
}
static inline sfinx_status _sfinx_wots_sign(sfinx_hash hash, const uint8_t *key, size_t key_len, const uint8_t *value,
@@ -202,23 +223,50 @@ static inline void _sfinx_merkle_parent(sfinx_hash hash, uint8_t bitlen, uint8_t
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;
+ size_t len = sfinx_hash_len(hash);
+ size_t c = len + 2;
+ size_t key_len = seed_len + prefix_len + 1;
+ size_t chunk = SFINX_BATCH_KEY_BUDGET / key_len;
+ 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) {
+ uint8_t *ends;
+ uint8_t *keybuf;
+
+ if (chunk == 0) {
+ chunk = 1;
+ }
+ if (chunk > count) {
+ chunk = count;
+ }
+ ends = malloc(count * c * len);
+ keybuf = malloc(chunk * key_len);
+ if (!ends || !keybuf) {
+ free(ends);
+ free(keybuf);
return 0;
}
- memcpy(key, seed, seed_len);
- if (prefix_len > 0) {
- memcpy(key + seed_len, prefix, prefix_len);
+ for (size_t base = 0; base < count; base += chunk) {
+ size_t n = count - base;
+ if (n > chunk) {
+ n = chunk;
+ }
+ for (size_t i = 0; i < n; i++) {
+ uint8_t *key = keybuf + i * key_len;
+ memcpy(key, seed, seed_len);
+ if (prefix_len > 0) {
+ memcpy(key + seed_len, prefix, prefix_len);
+ }
+ key[key_len - 1] = (uint8_t)(base + i);
+ }
+ _sfinx_shake256_batch(n, keybuf, key_len, ends + base * c * len, c * 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(keybuf);
+ for (uint32_t step = 0; step < 256u; step++) {
+ _sfinx_hash_batch(hash, count * c, ends, len, ends, len);
}
- free(key);
+ _sfinx_hash_batch(hash, count, ends, c * len, nodes, len);
+ free(ends);
for (size_t bitlen = 8; bitlen-- > 0;) {
if (auth_out) {
memcpy(auth_out + (7 - bitlen) * len, nodes + (pos ^ 1) * len, len);
diff --git a/test/04-subtree.c b/test/04-subtree.c
@@ -63,5 +63,33 @@ int main(void) {
}
tap(memcmp(nodes, root, len) == 0, "manual fold matches the builder", "roots differ");
+ // The batched builder must match a per-key fold at every hash size
+ static const sfinx_hash sizes[] = {SFINX_HASH_224, SFINX_HASH_384, SFINX_HASH_512};
+ for (size_t s = 0; s < sizeof(sizes) / sizeof(sizes[0]); s++) {
+ sfinx_hash h = sizes[s];
+ size_t l = sfinx_hash_len(h);
+ size_t cnt = 256;
+ uint8_t broot[SFINX_HASH_LEN_MAX];
+ uint8_t mkey[32];
+ uint8_t mnodes[256 * SFINX_HASH_LEN_MAX];
+
+ tap(_sfinx_subtree_build(h, seed, seed_len, prefix, 3, idx, broot, NULL) != 0, "subtree builds at every size",
+ "build failed");
+ for (size_t i = 0; i < 256; i++) {
+ memcpy(mkey, seed, seed_len);
+ memcpy(mkey + seed_len, prefix, 3);
+ mkey[seed_len + 3] = (uint8_t)i;
+ _sfinx_wots_pubkey(h, mkey, seed_len + 4, mnodes + i * l);
+ }
+ for (size_t bitlen = 8; bitlen-- > 0;) {
+ cnt /= 2;
+ for (size_t j = 0; j < cnt; j++) {
+ _sfinx_merkle_parent(h, (uint8_t)bitlen, _sfinx_node_mask((uint8_t)bitlen, (uint8_t)(j << (8 - bitlen))),
+ prefix, 3, mnodes + (2 * j) * l, mnodes + (2 * j + 1) * l, mnodes + j * l);
+ }
+ }
+ tap(memcmp(broot, mnodes, l) == 0, "batched builder matches the per-key fold at every size", "roots differ");
+ }
+
return tap_plan();
}
diff --git a/test/10-batch.c b/test/10-batch.c
@@ -0,0 +1,40 @@
+// Forces the pre-image batch to chunk, so the multi-chunk path is exercised
+#define SFINX_BATCH_KEY_BUDGET 260u
+
+#include <string.h>
+
+#include "_tap.c"
+#include "ref/sfinx_ref.c"
+#include "src/sfinx.c"
+
+int main(void) {
+ static const uint8_t seed[] = "sfinx batch chunk seed";
+ static const uint8_t prefix[] = {0x11, 0x22, 0x33};
+ static const int bits[] = {224, 512};
+ size_t seed_len = sizeof(seed) - 1;
+
+ // key_len is 22 + 3 + 1 = 26, so the 260 budget makes chunk 10, not a lane multiple
+ tap_begin("sfinx batch chunking");
+
+ for (size_t s = 0; s < sizeof(bits) / sizeof(bits[0]); s++) {
+ int bit = bits[s];
+ sfinx_hash hash = (sfinx_hash)bit;
+ size_t len = sfinx_hash_len(hash);
+ uint8_t lib_root[SFINX_HASH_LEN_MAX];
+ uint8_t ref_root[SFINX_HASH_LEN_MAX];
+ uint8_t lib_auth[8 * SFINX_HASH_LEN_MAX];
+ uint8_t ref_auth[8 * SFINX_HASH_LEN_MAX];
+ char label[64];
+
+ tap(_sfinx_subtree_build(hash, seed, seed_len, prefix, sizeof(prefix), 0x5a, lib_root, lib_auth) != 0,
+ "chunked subtree builds", "build failed");
+ ref_subtree(bit, seed, seed_len, prefix, sizeof(prefix), 0x5a, ref_root, ref_auth);
+
+ snprintf(label, sizeof(label), "L%zu chunked root matches reference", len);
+ tap(memcmp(lib_root, ref_root, len) == 0, label, "root differs");
+ snprintf(label, sizeof(label), "L%zu chunked auth matches reference", len);
+ tap(memcmp(lib_auth, ref_auth, 8 * len) == 0, label, "auth differs");
+ }
+
+ return tap_plan();
+}
diff --git a/test/Makefile b/test/Makefile
@@ -27,6 +27,10 @@ $(HASH):
$(OUT)/09-ref: 09-ref.c ref/sfinx_ref.c ../src/sfinx.c _tap.c $(LIB) $(HASH) | $(OUT)
@$(CC) $(CFLAGS) $< $(LIB) $(HASH) -o $@
+$(OUT)/10-batch: CFLAGS += -Wno-unused-function
+$(OUT)/10-batch: 10-batch.c ref/sfinx_ref.c ../src/sfinx.c _tap.c $(LIB) $(HASH) | $(OUT)
+ @$(CC) $(CFLAGS) $< $(LIB) $(HASH) -o $@
+
$(OUT)/%: %.c ../src/sfinx.c _tap.c $(LIB) $(HASH) | $(OUT)
@$(CC) $(CFLAGS) $< $(LIB) $(HASH) -o $@