The Sibuna Book 1.0.0-beta.3 documentation
Language: English
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
On this page

Part III: Foundations from Cryptography Research

We derive the cost models behind Sibuna’s two proof-of-work tiers, present the Cohen-Pietrzak Proof of Sequential Work with its security argument, and justify keyed-hash authentication for challenges and sessions. SID 0006 records the assumptions and references.

Hashcash: The Mathematics of Tier One

Definition and Cost

Sibuna’s Tier One puzzle for challenge string \(C\) and difficulty \(b\) bits is: find \(N \in \mathbb{N}\) such that \(\text{SHA-256}(C \parallel \text{":"} \parallel \mathrm{dec}(N))\) has \(b\) leading zero bits. The decimal rendering of the nonce is deliberate; it keeps the wire format identical between the WebAssembly solver, the JavaScript fallback, and the native verifier without a binary encoding step.

The unit of difficulty is an expected hash trial, not a compression function call. An input can occupy several SHA-256 blocks. Prefix precomputation can also change the work per nonce. The wire rule remains the digest predicate; implementations must agree on the statement and nonce encoding, not on an estimated CPU cost.

For independent ideal digests, the trial count \(X\) is geometric with \(p = 2^{-b}\). Its median is \(\left\lceil \ln(1/2) / \ln(1-p) \right\rceil\), approximately \(2^b \ln 2\) for small \(p\), and its variance is \((1-p)/p^2\). The verifier checks one candidate digest rather than performing the search. Parsing, challenge authentication, fingerprint checks, spent-state insertion, and the response are additional work. A primitive timing cannot be inverted into a server’s flood capacity.

Proof of Sequential Work: Tier Two

Why Sequential Work

A sequential-work construction introduces dependencies between computations: a later label needs a value produced earlier. This addresses a different quantity from aggregate work, namely the depth of the computation. Independent puzzles can still run in parallel, and hardware hash latency still matters.

Sibuna follows the hash-based construction described by Cohen and Pietrzak. Its graph has \(2^{n+1}-1\) labels at depth \(n\), but a fixed label count is not a deterministic browser latency: labels can span several compression blocks, openings may recompute subtrees, and scheduling adds variation. Security statements from oracle-model analyses must not be turned into an unqualified claim about every concrete implementation or adversary.

The Construction

Let \(n\) be the depth and consider the complete binary tree with nodes named by binary strings of length at most \(n\) (root \(\varepsilon\), children \(v0\) and \(v1\), leaves of length \(n\)). Each node \(v\) carries a 32-byte label \(\ell_v = H(\chi, v, \mathrm{parents}(v))\), where \(\chi\) is the challenge statement and \(H\) is SHA-256 with \(\chi\) absorbed once (the same prefix trick as the Hashcash solver):

  • an internal node hashes its two children: \(\ell_v = H(\chi, v, \ell_{v0}, \ell_{v1})\);
  • a leaf \(u = u_1 \dots u_n\) hashes the left siblings of its ancestors wherever the root path turned right: \(\ell_u = H(\chi, u, \{\ell_{u_1 \dots u_{i-1} 0} : u_i = 1\})\).
A complete binary tree of depth 3 with nodes named depth.index. The root path of leaf 3.5 (nodes 0.0, 1.1, 2.2, 3.5) is amber, the siblings 1.0, 2.3 and 3.4 sent in its opening are green, and dashed red arrows run from 1.0 and 3.4 into leaf 3.5. An arrow under the leaves shows that they are labelled from left to right.
Fig. 3 The depth-3 tree: an opening of leaf 3.5 sends the leaf label and the three sibling labels; the dashed edges are the left-sibling dependencies that make labelling sequential.

The left-sibling edges are what make the computation sequential: leaf \(u\) cannot be labelled until every subtree to its left is complete, so a depth-first post-order traversal is forced and the root label \(\varphi = \ell_\varepsilon\) depends on all \(2^{n+1} - 1\) labels in sequence.

Openings. After computing \(\varphi\), the prover derives \(t\) leaves by Fiat-Shamir, \(\gamma_i = H(\chi \parallel \varphi \parallel i) \bmod 2^n\), and for each sends the leaf label and the \(n\) sibling labels along its root path. The verifier recomputes the leaf from the siblings that are its parents, hashes upward through the path, and checks that it arrives at \(\varphi\). The verifier’s cost is \(O(tn)\) label computations with bounded workspace. A label computation may span multiple hash blocks; counting labels is not counting compression calls.

fn verify_opening(base: &Sha256, n: u8, phi: &Label, gamma: u32, opening: &[Label]) -> bool {
    let Some((leaf, siblings)) = opening.split_first() else {
        return false;
    };
    // `siblings` runs from depth n up to depth 1; reversed, it pairs with depths 1..=n.
    let mut hasher = node_hasher(base, n, gamma);
    for (d, sibling) in (1..=n).zip(siblings.iter().rev()) {
        if turns_right(gamma, n, d) {
            hasher.update(sibling);
        }
    }
    if hasher.finalize() != *leaf {
        return false;
    }
    let mut current = *leaf;
    for (d, sibling) in (1..=n).rev().zip(siblings) {
        let mut parent = node_hasher(base, d - 1, gamma >> (n - d + 1));
        if turns_right(gamma, n, d) {
            parent.update(sibling);
            parent.update(&current);
        } else {
            parent.update(&current);
            parent.update(sibling);
        }
        current = parent.finalize();
    }
    current == *phi
}

Sampling, Soundness, and Their Limits

Consider a fixed commitment with an independently detectable bad fraction \(\alpha\). If each opening samples uniformly and independently, the chance of missing every bad location in \(t\) openings is \((1-\alpha)^t\). This elementary calculation explains why more openings help. It is not, by itself, a security proof for a sequential-work protocol.

The referenced sequential-work construction has a security analysis in an oracle model. Sibuna’s domain separation, parameter mapping, truncation, and implementation must still be checked against the construction’s assumptions. Fiat-Shamir sampling makes openings reproducible from a commitment; reproducibility alone does not prove resistance to grinding. We make no unconditional claim that cheating is never cheaper.

Prover Memory

A naive prover stores every label (\(2^{n+1} - 1\) of them). Sibuna’s prover keeps a stack of the current path’s left-sibling labels (\(n + 1\) labels) during the first pass and retains only the top \(m = \min(n, 10)\) levels (\(2^{m+1} - 1\) labels, at most 64 KB). To open a leaf it recomputes the subtree of the leaf’s depth-\(m\) ancestor, \(2^{n-m+1} - 1\) hashes, seeding the stack from the retained levels. Total prover cost is \(2^{n+1} - 1 + t\,(2^{n-m+1} - 1)\) hashes and the whole workspace, including the output proof, is under 100 KB: a browser tab and a native test share the same Workspace type (sibuna_pow::posw::Workspace).

Parameters Are Not Timings

Sibuna maps work bits to depth using \(n = b - 3\), clamped to the supported interval \([4, 24]\). This is a work-scale convention, not a guarantee of equal wall-clock time between algorithms. A leaf can hash several parent labels, while Hashcash repeatedly tests a nonce. Compiler, browser, processor, and parameter choices all affect their relative costs. The committed primitive benchmark measures verification; it does not establish browser solve latency.

Proof size is \(32(1 + t(n+1))\) bytes. At depth 13 with sixteen openings, this is \(32(1 + 16 \times 14) = 7200\) bytes. Raising the opening count increases both the proof and the verifier’s work, even if the dominant cost of constructing the tree stays the same.

Choosing a Construction

The relevant comparison is a resource budget, not an algorithm’s reputation. Record the prover’s memory, the verifier’s worst-case work, the proof bytes, and the assumptions needed for the claimed property. Memory-hard search can be useful, but a verifier that must repeat expensive work gives an attacker another place to spend the server’s resources. Publicly verifiable delay constructions serve a different trust model from a shared-secret gate.

Sibuna retains cheap hash verification and a hash-based sequential-work option. The latter requires more proof bytes and more careful parameter analysis. Neither choice removes the need to reject malformed proofs before entering expensive verification.

Symmetric Authentication: Challenges and Sessions

Issuer Equals Verifier

A digital signature lets anyone holding the public key verify, which is the right tool when verifiers must not be able to mint. Sibuna’s verifier is the issuer (or a cluster sharing one seed). A message authentication code built from a pseudorandom function supplies authentication within that trust domain. It does not supply public verification: anyone holding the MAC key can also mint tokens. The benchmark chapter compares the implemented token operations.

A second consequence matters for the long term: Ed25519 rests on discrete logarithms in an elliptic-curve group, which Shor’s algorithm breaks; a keyed hash rests only on the hash function, against which quantum algorithms give at most a quadratic speedup. Sibuna keeps Ed25519 as an option (--token-scheme ed25519) for deployments that need non-minting verifiers.

The Key Schedule

One 32-byte master seed (from --secret-file, SIBUNA_SECRET, or a fresh random value) derives every purpose key with keyed BLAKE3 and a domain string: the token, challenge, Ed25519 and fingerprint keys, and the requirement key that seals requirement tickets (Part IV).

pub fn derive(seed: &Seed) -> Keys {
    Keys {
        token: subkey(seed, "sibuna/token/v1"),
        challenge: subkey(seed, "sibuna/challenge/v1"),
        ed25519_seed: subkey(seed, "sibuna/ed25519/v1"),
        fingerprint: subkey(seed, "sibuna/fingerprint/v1"),
        requirement: subkey(seed, "sibuna/requirement/v1"),
    }
}

fn subkey(seed: &Seed, purpose: &str) -> [u8; 32] {
    blake3::keyed_hash(seed.as_bytes(), purpose.as_bytes())
}

In a cluster, Keys::bind_node replaces the challenge key by keyed BLAKE3 under it over sibuna/challenge-node/v1 and the node id, so a challenge must return to the node that issued it, while session tokens and requirement tickets stay valid on every member.

Domain separation prevents accidental reuse across purposes; compromise of the master seed compromises every derived key. A cluster only has to agree on one seed.

Stateless Challenges

Two byte layouts. The challenge identifier: ver, alg, diff and t of one byte each, then issued_at, fingerprint, nonce and rule_hash of eight bytes each, a 36-byte payload, followed by a 16-byte BLAKE3 tag; 52 bytes, sent as 70 URL-safe base64 characters. The session token: ver, alg and bits of one byte each, res of five bytes, then timestamp, expiry, rule_hash and fingerprint of eight bytes each, a 40-byte payload, followed by a 16-byte BLAKE3 tag; 56 bytes, sent as 75 URL-safe base64 characters.
Fig. 4 Wire formats of the challenge identifier and the session token. The numbers above each record are byte offsets.

A challenge identifier is a self-authenticating record: version, algorithm, difficulty, opening count, issue time, the client’s keyed fingerprint, a PRF-derived nonce, and the hash of the policy rule that demanded the challenge, followed by a 16-byte tag under the challenge key. Issuing one writes nothing. Verification decodes the record, checks the tag in constant time, checks the age against the challenge TTL, checks the fingerprint against the submitting client, and only then examines the proof.

The spent set is 16 shards of Robin Hood open addressing over the 16-byte tags (Part V). The fingerprint is a keyed hash of the client address and User-Agent, length-separated so no two inputs collide by concatenation, and keyed so fingerprints of other clients cannot be computed offline.