- Number
-
0006
- Title
-
Mathematical Foundations of Sibuna: Sequential Work, Symmetric Authentication, Bounded State, and Linear-Time Inspection
- State
-
published
- Status
-
Published
- Type
-
Architectural Specification
- Authors
-
Sibuna Contributors <team@sibuna.local>
- Created
-
2026-09-07
- Updated
-
2026-10-15
- Discussion
-
No external discussion URL assigned
- Summary
-
A paper-style record of the mathematics behind every Sibuna hot-path primitive: the Cohen-Pietrzak proof of sequential work and the geometric hashcash tier, keyed-hash tokens and stateless challenges with work-bounded state, GCRA rate limiting, Robin Hood spent sets, Aho-Corasick and single-pass tokenizers for inspection, read-copy-update engine slots, adaptive difficulty, and feature-hashed campaign clustering, each with definitions, lemmas, proofs, citations, and the exact pure-Zig implementation and measurement that realises it.
- Labels
-
mathematics, cryptography, proof-of-work, posw, rate-limiting, hashing, automata
Mathematical Foundations of Sibuna: Sequential Work, Symmetric Authentication, Bounded State, and Linear-Time Inspection¶
Revision note¶
2026-10-15: Ported from the Typst original in the Zig repository. The record describes the Zig implementation as it was decided; SID 0010 maps its packages to the Rust crates of the port.
2026-10-15 (Rust port, Parts A to C): SHA-256 in sibuna-crypto detects the x86-64 SHA extensions and the ARMv8 SHA-2 instructions at run time, where Zig’s standard library chose at build time from the target features, so one binary uses the instructions on every CPU that has them; a build without the std feature still decides at compile time. Digests, and therefore every Hashcash and PoSW result, are unchanged. The PoSW verifier derives the challenged leaves \(\gamma_i\) from one SHA-256 state that has absorbed the statement \(\chi\) once, instead of rehashing \(\chi\) for every \(i\). The digests and the count of hash evaluations in Lemma 12 are the same, and verification costs \(t\) fewer SHA-256 compressions. Ed25519 tokens are verified with width-5 non-adjacent-form digits for the public key and width-8 digits over a precomputed table of base-point multiples, instead of Zig’s signed 4-bit windows, and the public key is decoded once when the coordinator starts instead of on every verification. Decoding now rejects off-curve, identity and small-order keys, which Zig rejected only in verify. Exactly the same signatures are accepted, and verification is faster. The rule hash of Definitions 17 and 20 and the ban-table key are Wyhash; sibuna-crypto counts the input length in a u64 where Zig used usize. The two agree bit for bit on every 64-bit target and differ only on 32-bit targets for inputs of 4 GiB or more, which Sibuna never hashes. The measurements quoted in this record are those of the Zig build.
2026-10-15 (Rust port, Parts D, E and H): the GCRA limiter, the spent set and the adaptive controller keep their definitions, table layouts and probe rules. Zig’s limiter already saturated its arithmetic; the port also saturates the conversion of a window in seconds to milliseconds in its convenience entry point. The adaptive controller and the coordinator saturate where Zig would have trapped on overflow (a difficulty plus the bump past u32::MAX, an EWMA product, a smoothing factor alpha_256 above 256, a time near u64::MAX plus a lifetime). Theorem 23 and Definition 32 hold unchanged for every value the daemon can produce.
2026-10-15 (Rust port, Part F): the automata of sibuna-patterns index their rows by byte class instead of by byte. A class is a byte that occurs in some pattern, with both cases of a letter forming one class under case folding, or the one class of all other bytes. Each row holds one u32 successor per class, so construction takes \(O(m c)\) time and space for \(c \le \sigma\) classes instead of \(O(m \sigma)\), and a scan is still one dependent load per input byte with failure links folded in: Theorem 29 holds with \(c\) in place of \(\sigma\). Match states are numbered after all other states, so the scan detects a match with one comparison. Patterns equal under case folding are all kept, and the one added first wins a first-match scan, where Zig overwrote the earlier one; Sibuna’s signature tables contain no such duplicates. Tags run from 0 to 63, so a set of tags is one 64-bit word. Findings are unchanged.
2026-10-15 (Rust port, Part G): the slot protocol of Definition 30 is not ported. The daemon publishes each rebuilt engine as an owned value behind an Arc (SID 0010). Each request thread reads it through a cache that checks a generation counter with one acquire load per request and clones the Arc only after a publication; an engine is freed when the last thread holding it moves on, and no writer waits for readers to drain. An engine is never rebuilt in place, so the property of Lemma 31 holds by reference counting, and the fourth open problem does not apply to the port. The incident ring is unchanged.
2026-10-15 (Rust port, Part I): sqlite-vec is gone with Zaxonlite. The storage thread keeps the most recent 16,384 embeddings of all nodes in memory and assigns an incident to the campaign of its nearest neighbour among them (SID 0011), instead of a nearest-neighbour query over every recorded incident. An incident older than that window is not compared, so a variant that recurs after 16,384 newer incidents founds a new campaign. The embedding, the cosine threshold of 0.35 and the campaign identifiers are unchanged.
2026-10-15 (Rust port, security fix, Parts A to C): the ban-table key is no longer Wyhash with a public seed; see SID 0004.
2026-10-15 (Rust port, security fix, Parts D and E): the limiter evicts the oldest-TAT cell of a full probe window instead of refusing (Theorem 23 holds for every client whose cell is not evicted; an evicted client restarts from an idle state). The spent set’s capacity is configurable (--spent-tags, default 1,048,576 tags, 24 MiB, 24-byte slots); the Zig set’s 65,536 tags were exhausted by about 220 verified solutions per second within a five-minute challenge lifetime, after which honest solutions were refused.
2026-10-15 (Rust port, security fix, Part H): the adaptive controller’s input is the rate of verified solutions, not of issued challenges, which cost a flooder nothing; issuance only advances the bucket clock so the average decays. Arithmetic and bounds are unchanged.
2026-10-15 (Rust port, Parts A to C, primitives): BLAKE3 in sibuna-crypto is portable code only. Zig’s SIMD paths hash large inputs several times faster, but Sibuna hashes only inputs under 100 bytes with BLAKE3 (token tags, fingerprints, the key schedule), where the portable code is faster. Ed25519 signing cannot fail; Zig’s sign returned an error when the nonce reduced to zero, an event of probability about \(2^{-252}\). Signing keys, the master seed and the derived keys are wiped when dropped.
2026-10-15 (Rust port, Parts A and B, solvers): functions that Zig defined only for valid parameters are total and never panic. challenge_leaf keeps all 32 bits for depths of 32 or more, where Zig’s shift would be illegal; leaf_count saturates; and meets_hex refuses a hexadecimal difficulty whose bit count overflows. Valid parameters (depth 4 to 24, 1 to 32 challenges, as in Zig) never reach these cases, and the prover keeps Zig’s depth-first recursion, at most 25 frames deep. The native reference solver and the browser solver share one Hashcash search, which absorbs the challenge and the colon once and clones that SHA-256 state for each nonce, as the Zig browser solver did; the Zig reference solver rehashed the prefix for every nonce. The nonce found is the same.
2026-10-15 (Rust port, Part E): a spent-set slot no longer stores the probe distance or an occupied flag. The distance follows from the slot index and the tag’s home slot, and a zero expiry marks an empty slot (an expiry of zero is stored as one), so a slot is 24 bytes. The 16 shards share the configured capacity, which is clamped to 65,536 to 16,777,216 tags and rounded up to a power of two. Definition 25 and Lemmas 26 to 28 apply unchanged, because the distances are the same numbers, computed instead of stored. Lookup is still capped at 64 probes.
2026-10-15 (Rust port, Part F, construction): the capacity of an automaton is a value given to its builder instead of a compile-time parameter, with the same failures. A failed add leaves the builder unchanged; Zig kept the states it had created. The built-in signature sets are sized from their pattern lengths, as before.
Abstract¶
A paper-style record of the mathematics behind every Sibuna hot-path primitive: the Cohen-Pietrzak proof of sequential work and the geometric hashcash tier, keyed-hash tokens and stateless challenges with work-bounded state, GCRA rate limiting, Robin Hood spent sets, Aho-Corasick and single-pass tokenizers for inspection, read-copy-update engine slots, adaptive difficulty, and feature-hashed campaign clustering, each with definitions, lemmas, proofs, citations, and the exact pure-Zig implementation and measurement that realises it.
Sibuna is a web firewall whose admission decisions must cost the server almost nothing and cost an unverified client a measurable, unavoidable amount of work. This record states the mathematics that makes that asymmetry a theorem rather than a hope. It gives, for every hot-path primitive, a definition, the lemmas or theorems that bound its cost and its security, a citation to the primary literature, and the exact pure-Zig function that realises it together with the number we measured on the reference host.
The central design decision is the choice of the client puzzle. SID 0002 proposed three tiers (SHA-256 hashcash, HashX, Argon2id). On review, HashX carries no formal proof and requires an interpreter, Argon2id makes verification as expensive as solving, and the memory-hard puzzle we considered as a replacement (Equihash) is a generalised-birthday construction with a cryptocurrency lineage and known quantum speedups for its underlying \(k\)-XOR problem. Sibuna therefore adopts the Cohen-Pietrzak proof of sequential work [4] as its research-grade tier: a construction with a sequentiality theorem in the random oracle model, a post-quantum proof in the parallel quantum random oracle model [6], deterministic solve time, \(O(\log N)\) prover memory, and \(O(t \log N)\) verification. Bit-granular hashcash [1] remains as the lightweight tier.
Around the puzzle, the record proves: that a 16-byte keyed-BLAKE3 tag bounds forgery by \(q/2^{128}\) and makes both challenges and session tokens stateless and post-quantum; that the only server state the design keeps, the spent set, is bounded by work the adversary actually performed; that the GCRA limiter admits at most \(N + \lfloor L/T \rfloor\) requests in any interval of length \(L\) with sixteen bytes of state per client; that Robin Hood lookups may terminate early and may overwrite expired occupants exactly when the incoming probe distance is not smaller; that the inspection pipeline is linear in the input with one automaton pass and one byte-class pass; and that the read-copy-update slot protocol never rebuilds an engine a request is still reading. Every measurement quoted is ours, from benchmarks/results/latest.json on an Apple M1; reference figures for other systems are labelled as models and never as measurements.
Introduction and Adversary Model¶
Setting¶
A request arrives at the daemon from a client that is either a human browser, an authorised crawler, or an unverified automaton. The daemon must decide, within a bounded request-classification budget, whether to forward the request to the origin, refuse it, or demand a proof of work. The client that presents a valid proof receives a session token and is not asked again for the token’s lifetime.
The adversary controls unbounded parallel hardware (GPU farms, ASICs, botnets with fresh IP addresses for every request), sees every byte the daemon emits, may replay, forge, or reorder messages, and may submit arbitrary garbage to every endpoint at line rate. The adversary does not hold the daemon’s master seed.
Axioms¶
The engineering priorities of SID 0001 (safety, then performance, then developer experience) become four axioms that every primitive in this record must satisfy. They are stated as axioms because the rest of the design is derived from them, not because they are self-evident.
Cost calculus¶
Write \(c_{\mathrm{iss}}\) for the server cost to issue a challenge, \(c_{\mathrm{ver}}\) for the cost to verify a submission, \(W\) for the expected client work per accepted submission, and \(\lambda\) for the adversary’s request rate. The adversary’s spend rate to obtain admission tokens is \(\lambda W\); the server’s spend rate to resist is \(\lambda (c_{\mathrm{iss}} + c_{\mathrm{ver}})\). Axiom 1 requires the ratio \(W/(c_{\mathrm{iss}} + c_{\mathrm{ver}})\) to be large. With stateless challenges (Part C) \(c_{\mathrm{iss}}\) is one keyed hash, and with the tiers of Parts A and B \(c_{\mathrm{ver}}\) is one SHA-256 compression or \(t(n+1)\) compressions respectively. Measured on the reference host the ratio is \(2^{16} \cdot 300\,\mathrm{ns} / 62.6\,\mathrm{ns} \approx 3 \cdot 10^5\) for the hashcash tier at 16 bits and \(138\,\mathrm{ms} / 16.9\,\mu\mathrm{s} \approx 8 \cdot 10^3\) for the sequential tier at depth 16 in a browser.
The figure below fixes the pipeline that the rest of the record analyses; each box names the part that proves its properties.
Part A: The Hashcash Tier¶
The tail is what an operator feels: at any difficulty, about 5% of honest clients need more than three times the mean, and 0.7% need more than five times. This variance is inherent to nonce search and is the first reason the sequential tier of Part B is preferred for the human-facing default.
Part B: Proof of Sequential Work¶
Why sequential work¶
Nonce search is embarrassingly parallel: an adversary with \(P\) processors divides the expected wall-clock time by \(P\), and Grover divides the query count by \(2^{b/2}\). Memory-hard puzzles raise the per-processor cost by forcing a memory footprint, but they remain parallel across processors and, as puzzles, remain nonce searches. A proof of sequential work changes the axis: the prover must perform \(N\) hash evaluations one after the other, so \(P\) processors and a quantum computer alike gain at most a constant factor from parallelism, and the honest client’s time is deterministic.
The construction¶
We follow Cohen and Pietrzak [4]. Let \(n\) be the depth and \(N = 2^{n+1} - 1\) the number of nodes.
The extra leaf edges are the whole point: leaf \(u\) cannot be labelled until every left sibling of its ancestors is labelled, which in turn requires every leaf to the left of \(u\). A depth-first post-order traversal is therefore the only order in which the labels can be computed, and it performs exactly \(N\) hash evaluations one after the other.
The verifier recomputes the leaf label from the siblings that the leaf’s extra edges name (exactly the left siblings at positions where \(\gamma_i\) has a 1 bit, all of which are among the transmitted siblings), then folds upward, hashing the pair of children at each level, and accepts if the result equals \(\varphi\) for every \(i\).
Theorems¶
For intuition only, if a fixed commitment has an invalid fraction \(\alpha\) of leaf openings and \(t\) independent uniformly sampled leaves are checked, the chance of missing all invalid leaves is \((1-\alpha)^t\). Sibuna derives samples from the commitment. An adversary can try many commitments and reuse work, so this elementary fixed-commitment calculation does not prove that cheating is unprofitable, nor that two openings suffice. The previous unconditional “cheating never pays” lemma is withdrawn. Default \(t=16\) is an engineering parameter requiring independent adversarial calibration, not a 128-bit soundness guarantee.
With \(m = 10\) the retained labels occupy \(2047 \cdot 32 = 64\) KB, and for \(n = 16, t = 16\) the openings add \(16 \cdot 127 = 2032\) hashes to the \(131071\) of the commitment: 1.6% overhead. The prover therefore fits in under 90 KB including the proof buffer, which is what makes it acceptable on a phone and what makes the WebAssembly module 8.8 KB.
We cite the theorem rather than reprove it; its proof uses the compressed-oracle technique to track which labels a quantum adversary has “computed”. This motivates the sequential tier under the cited oracle assumptions. It does not independently certify Sibuna’s concrete protocol or parameter choices.
Why not the alternatives¶
| Construction | Server verify | Parallel/quantum | Proof status | Verdict |
|---|---|---|---|---|
| Hashcash [1] | 1 hash | fully parallel; Grover \(\sqrt{\cdot}\) | random oracle, folklore | Kept as Tier 1: cheapest verification, high variance |
| Cohen-Pietrzak PoSW [4] | \(t(n+1)\) hashes | sequential; QROM-secure [6] | EUROCRYPT 2018 theorem; ITC 2021 quantum | Adopted as Tier 2 |
| Equihash [7] | \(2^k\) hashes | parallel; GPU-friendly; \(k\)-XOR quantum speedups [9] | NDSS 2016; Wagner [8] analysis; cryptocurrency lineage | Rejected: memory hardness does not stop parallelism and the nonce search inherits Grover |
| Argon2id (RFC 9106) [10] | full memory-hard evaluation | parallel across instances | PHC winner; MHF proofs | Rejected as a puzzle: verification costs as much as solving, violating Axiom 1 |
| HashX (Tor) | program generation + interpretation | parallel | no formal proof | Rejected: needs an interpreter on the server (Axiom 3) |
| RSA / class-group VDFs | 1 modexp with trapdoor | sequential | group-of-unknown-order assumptions | Rejected: Shor [25] breaks the group assumptions |
The Argon2id row deserves emphasis. A puzzle whose verification is the same memory-hard function forces the server to spend the same 16 to 64 MB and tens of milliseconds as the client on every submission. Since submissions are free to send, an adversary who fetches challenges and posts garbage converts each of its cheap requests into a full memory-hard evaluation on the server: the inverse of Axiom 1.
Implementation and calibration¶
The reproducible suite measures native verification at depth 13 with sixteen openings. Browser solve-time calibration from earlier drafts depended on a scratch harness absent from this repository, so those timing tables are withdrawn. Work-bit parity between the two tiers is an engineering approximation and must be calibrated on target client hardware.
Part C: Stateless Challenges and Symmetric Tokens¶
Pseudorandom functions and message authentication¶
Sibuna uses BLAKE3 in keyed mode [13] as \(F_K\). BLAKE3’s keyed mode is its compression function with the key in place of the IV, the same structural argument that makes HMAC a PRF under the assumption that the compression function is one [12]; the BLAKE3 specification states the keyed mode as a PRF directly.
At the observed verification rate of \(7.5 \cdot 10^6\) tags per second, \(q = 2^{64}\) guesses would take 78 000 years and succeed with probability \(2^{-64}\). Comparison is performed with std.crypto.timing_safe.eql, so no byte-position information leaks through response time.
Stateless challenge identifiers¶
Because the payload carries the issue time, difficulty, algorithm, opening count, client fingerprint, and the hash of the policy rule that demanded the challenge, the verifier needs no lookup to know what a submission must satisfy, and a client cannot lower its own difficulty without breaking the tag. Verification order matters for Axiom 1: tag, then expiry, then fingerprint, then the proof. All three cheap checks run before a single proof hash is computed, so garbage submissions cost the server one keyed hash.
This theorem is the discharge of Axiom 4. In the design it replaces (SID 0002’s original coordinator) the store was written at issuance, so 30 free requests per second filled a 16 384-entry table in nine minutes and denied service to everyone. Now the table fills only at the rate the adversary pays for admission tokens, which is the rate the puzzle already prices.
Session tokens¶
The fingerprint binds the token to the client identity the daemon can observe (address and User-Agent, hashed under a third key with length separation so ("ab","c") and ("a","bc") differ), which is what defeats the solver-farm pattern in which one strong machine solves puzzles and distributes cookies.
Ed25519 tokens remain available (--token-scheme ed25519) for the one deployment shape where verifiers must not be able to mint: they are then a deliberate trade of \(400\times\) verification cost and post-quantum security for key separation.
Part D: Rate Limiting by the Generic Cell Rate Algorithm¶
The theorem is deliberately stated as an inequality rather than the marketing phrase “sliding window”. SID 0004 described the earlier fixed-window implementation as sliding; the present record corrects that: the guarantee is the token-bucket bound above, which is what NGINX’s limit_req and Envoy’s local limiter also provide, with the difference that Sibuna’s state is a 16-byte cell in a lock-striped open-addressed table with lazy reclamation (a cell whose TAT is older than \(t - \tau\) is fully drained and free).
Part E: Robin Hood Hashing for the Spent Set¶
Insertion first simulates the bounded displacement path without mutation and refuses if no safe destination exists. This prevents a failed insertion from losing a live tag. This lemma is why the insert path overwrites an expired entry only when carry.dist >= e.dist and otherwise swaps and drops the expired key when it becomes the carried one; both cases reclaim without a sweeper and without ever moving a live key backwards. Expected probe costs depend on load and hash distribution; results for other probing models do not prove a universal variance bound for this linear-probing implementation. Lookup is capped at 64 probes. Insertion preflight can inspect up to one shard and refuses before mutation when it cannot preserve all live keys. Saturation is a correctness case, not something an average-case bound allows us to ignore.
Part F: Linear-Time Inspection¶
Multi-pattern matching¶
Sibuna uses the dense form: 256 successors of two bytes each per state, 512 bytes per state, failure links folded into the table so that scanning is exactly one load per input byte and never follows a failure chain. Case folding uses a comptime table so the automaton is byte-oriented and branch-free. Every pattern carries a tag (category), so one pass over a field returns both the match and its class. Each automaton capacity is one plus the sum of its pattern lengths; both live inside the Engine value so an engine can be rebuilt and swapped as one object (Part G).
The semantic layer¶
Signatures alone are either too loose (a bare /* flags every browser’s Accept: */*, which is how the first WAF blocked every real browser) or too tight. The structural layer adds three single-pass recognisers:
- A byte-class scan: one loop that ORs a 256-entry class table over the field, yielding eight booleans (quote, equals,
<, shell separator, percent, NUL, canonicalisation-needed, double space). Every structural detector and the decision to run canonicalisation are gated on these bits, so a field without a quote or an equals sign never enters the SQL tokenizer at all. - A SQL word tokenizer: one pass extracting alphanumeric words, folding case into a 7-byte buffer, looking each up in a 21-entry keyword list pruned by length, and, on
or/and, checking the tautology grammarliteral = literalin place. The verdict is a small score: a quote is mandatory, up to two keywords, a comment marker, and an equals sign add one point each, and four points deny. Prose such as it’s a group order from the shop scores three;name='x' union all from t--scores four. - Tag/attribute and separator/command recognisers for XSS and command injection that fire only in attribute or separator position.
This is a deliberate middle between two extremes. Regular-expression rule sets (backtracking engines) run hundreds of backtracking engines per request, each its own pass with its own match state, and are neither linear nor allocation-free. Full SQL/HTML parsers are linear but carry parser state, memory for ASTs, and a large surface of grammar edge cases; their precision advantage is real for a general-purpose WAF, but for an edge gate the fingerprint approach pioneered by libinjection captures most of it with a fixed-size tokenizer state.
Vectorised matchers¶
Hyperscan [17] and its portable fork Vectorscan reach multi-gigabyte-per-second literal scanning with SIMD prefilters (Teddy, FDR) that test several pattern prefixes per 16- or 32-byte block using byte shuffles, then verify candidates. Three facts decide against them here. First, our inputs are short: a User-Agent is about 120 bytes and the whole set of non-structural headers a few hundred; the automaton scans a User-Agent in 85 ns, below the cost of one cache miss, so the prefilter’s constant setup cost dominates. Second, portable Zig @Vector has no runtime byte shuffle, so Teddy needs per-architecture inline assembly and cannot run in the WASM solver. Third, Hyperscan is a multi-megabyte C++ dependency with a compile-time pattern database, which contradicts the single-binary and pure-Zig constraints. Where SIMD would pay, on 8 KB bodies that we scan at about 2.9 ns per byte (23.7 microseconds), the body scan is already three orders of magnitude below origin latency, and the body inspection is bounded at 8 KB by design.
Part G: Read-Copy-Update Engine Slots¶
The policy engine is a fixed-capacity value (rules, both automata, the reputation trie). Dynamic policy from Part I’s storage layer must replace it without stopping workers. Sibuna uses the read-copy-update discipline [23] with an explicit reader count per slot.
The cost includes an atomic increment and decrement per classification on a cache-line-aligned counter; contention must be measured. The response copies its rule name before releasing the slot, so origin I/O does not prolong the writer’s wait. Incidents flow from workers to the storage thread through a bounded multi-producer single-consumer ring (Vyukov’s sequence-stamped design [19]): each slot carries a sequence number that tells producers whether it is free and the consumer whether it is full, so neither side locks, and a full ring drops the newest record rather than blocking a response.
Part H: Load-Adaptive Difficulty¶
The cap \(\beta_{\max}\) (default 6 bits, \(64\times\)) bounds what a human on a slow device is ever asked, so a flood degrades the human experience by at most a fixed factor rather than locking humans out. The state is three atomics and needs no lock.
Part I: Campaign Clustering by Feature Hashing¶
Incidents recorded by the WAF are embedded so that the storage layer can group variants of one attack template without a model.
This is the hashing trick of Weinberger et al. [20] over Broder’s shingles [21]; the random sign makes the estimator of the inner product unbiased, and the fold makes id=1' and id=42' share almost all trigrams. Cosine similarity is then a dot product, and sqlite-vec’s cosine KNN (the vector table is declared with distance_metric=cosine) returns the nearest recorded incident. An incident joins the nearest campaign when the cosine distance is at most 0.35 and otherwise founds a new campaign whose identifier is its own. The storage test in apps/sibuna/src/persistent.zig verifies that two SQL injection variants against different paths share a campaign and a honeypot hit does not.
Verification and Benchmark Gates¶
zig build test runs library, server, solver, storage and live HTTP regressions. The standalone primitive harness records seven batches after untimed warmup and resets mutable state before each batch. Failed insertions are errors, not accepted benchmark samples. Both bot algorithms search the same patterns with any-match semantics. Compiler barriers keep pure calls in their loops without per-operation clocks. The harness does not measure heap allocations; its zero allocation expectation is based on the inspected APIs and sources.
See benchmarks/results/latest.json for primitive measurements and exact @sizeOf values, and benchmarks/results/distributed-latest.json for three-process loopback measurements. Older numerical examples in this paper describe the pre-review build and are illustrative, not current performance claims. Unsupported fixed competitor cost rows were removed.
The external distributed harness checks session sharing, authenticated WAF denial, issuer-bound challenge rejection, ban propagation, and HTTP service with one member down. It does not establish WAN latency, production mTLS performance, global quotas or durable replay protection.
Security Considerations¶
- Trust boundary for client identity. The fingerprint uses the peer address unless
--trust-forwardedis set, in which caseX-Forwarded-Foris trusted; that flag must be set only when an ingress that overwrites the header is the sole peer, as in forward-auth mode where it defaults on. - Secret handling. Without
--secret-fileorSIBUNA_SECRETthe seed is random per process: tokens and challenges do not survive restarts and are not shared across nodes. The banner says so. A cluster must share one seed. - Replay. Challenges are single-use within a process lifetime. Cluster node ids derive distinct challenge keys, so verification must return to the issuing node; tokens remain cluster-wide. Spent state is not durable across restarts; tokens are bound to the fingerprint and expire; both carry the issue time so clock skew beyond sixty seconds forward is rejected.
- Amplification. Every endpoint is bounded: heads over 16 KB are refused, bodies over 64 KB are refused for the verify endpoint, proofs are length-checked before any hash, and the expensive verification is reached only after the constant-cost tag, expiry, and fingerprint checks.
- Side channels. Tag comparison is constant-time. Hashing time is independent of secrets. Response codes distinguish malformed, expired, mismatched, and invalid submissions for the honest client’s benefit; none of these outcomes depends on secret material beyond the tag verdict, which is uniform.
- WAF false negatives. The structural layer is a fingerprint classifier, not a parser; it will miss injections that avoid keywords, quotes, and separators entirely. Operators needing parser-grade coverage should treat Sibuna’s shield profile as the first layer and keep an application-level defence.
Open Problems¶
- Memory-hard and asymmetric with proof. No construction we know is simultaneously memory-hard for the prover, cheap for the verifier, non-parallelisable, and proven in the quantum random oracle model. Depth-robust graph labelling with sequential openings is the natural candidate; without a proof it stays out of the daemon.
- JA4H fingerprints as a policy signal (not as a token binding, because browsers vary header sets between navigation and fetch).
- HTTP/2 and TLS termination in the reverse-proxy mode; forward-auth mode already delegates both to the ingress.
- Formal proof of the RCU slot protocol in a model checker; the argument in Part G is a paper proof.
References¶
- A. Back. Hashcash: A Denial of Service Counter-Measure. Technical report, 2002 (announced 1997).
- C. Dwork and M. Naor. Pricing via Processing or Combatting Junk Mail. CRYPTO 1992.
- A. Juels and J. Brainard. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks. NDSS 1999.
- B. Cohen and K. Pietrzak. Simple Proofs of Sequential Work. EUROCRYPT 2018.
- M. Mahmoody, T. Moran, and S. Vadhan. Publicly Verifiable Proofs of Sequential Work. ITCS 2013.
- J. Blocki, S. Lee, and S. Zhou. On the Security of Proofs of Sequential Work in a Post-Quantum World. ITC 2021.
- A. Biryukov and D. Khovratovich. Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem. NDSS 2016.
- D. Wagner. A Generalized Birthday Problem. CRYPTO 2002.
- L. Grassi, M. Naya-Plasencia, and A. Schrottenloher. Quantum Algorithms for the k-XOR Problem. ASIACRYPT 2018.
- A. Biryukov, D. Dinu, D. Khovratovich, and S. Josefsson. Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications. RFC 9106, 2021.
- M. Bellare, R. Canetti, and H. Krawczyk. Keying Hash Functions for Message Authentication. CRYPTO 1996.
- M. Bellare. New Proofs for NMAC and HMAC: Security without Collision-Resistance. CRYPTO 2006.
- J. O’Connor, J.-P. Aumasson, S. Neves, and Z. Wilcox-O’Hearn. BLAKE3: One Function, Fast Everywhere. Specification, 2020.
- P. Celis. Robin Hood Hashing. PhD thesis, University of Waterloo, 1986.
- L. Devroye, P. Morin, and A. Viola. On Worst-Case Robin Hood Hashing. SIAM Journal on Computing 33(4), 2004.
- A. V. Aho and M. J. Corasick. Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM 18(6), 1975.
- X. Wang, Y. Hong, H. Chang, K. Park, G. Langdale, J. Hu, and H. Zhu. Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs. NSDI 2019.
- ATM Forum. Traffic Management Specification Version 4.0, af-tm-0056.000, 1996 (the Generic Cell Rate Algorithm).
- D. Vyukov. Bounded MPMC Queue. 1024cores.net, 2010 (sequence-stamped ring used here in its MPSC form).
- K. Weinberger, A. Dasgupta, J. Langford, A. Smola, and J. Attenberg. Feature Hashing for Large Scale Multitask Learning. ICML 2009.
- A. Z. Broder. On the Resemblance and Containment of Documents. SEQUENCES 1997.
- M. Charikar. Similarity Estimation Techniques from Rounding Algorithms. STOC 2002.
- P. E. McKenney and J. D. Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems. PDCS 1998; P. E. McKenney et al., Read-Copy Update, Ottawa Linux Symposium 2001.
- L. K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. STOC 1996.
- P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26(5), 1997.
Lifecycle event
2026-10-15: prediscussion -> discussion. Ported from the Zig repository's
Typst record
Lifecycle event
2026-10-15: discussion -> published. State carried over from the Zig
repository's registry