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

Part I: The Cost of a Request

Before choosing an algorithm, identify the resource it is meant to protect. This chapter builds the small models that every later design decision is measured against: origin work, puzzle work, session amortisation, and the memory an untrusted client can make a server hold.

Admission Is an Economic Decision

Suppose an origin performs a database lookup and renders a page for each admitted request. Let \(c_o\) be that work, \(c_g\) the gate’s work per request, and \(r\) the arrival rate. With no gate, the origin must sustain \(r c_o\) units of work per second. A gate that admits fraction \(a\) changes that demand to \(r a c_o\), while spending \(r c_g\) itself. The gate is useful only when the saved origin work exceeds its own cost and the cost it imposes on legitimate visitors.

\[r c_g + r a c_o < r c_o \quad \Leftrightarrow \quad c_g < (1-a) c_o.\]

This is a capacity model, not a measurement. It omits bandwidth, connection state, storage, and client delay. Its value is that every missing term is visible. A cache hit may make \(c_o\) small; a costly query may make it large. There is no universal requester-to-server cost ratio.

What a Proof of Work Establishes

A client puzzle establishes that somebody found an input satisfying a public verification rule. It does not establish humanity, identity, or good intent. A requester can rent compute, reuse a valid session within its lifetime, or distribute work across machines. The puzzle changes the admission cost; policy and inspection still decide what admitted requests may do.

Address-based limits are complementary. They constrain one address, but shared addresses can represent many people and one requester can use many addresses. Neither a puzzle nor an address is an identity oracle. Sibuna therefore keeps admission, inspection, and reputation as distinct decisions.

Hash Search as a Random Variable

For an ideal 256-bit digest, requiring \(b\) leading zero bits gives success probability \(p = 2^{-b}\) for each independent trial. Let \(K\) count trials through the first success. Then

\[P(K=k) = (1-p)^{k-1} p, \quad P(K>k) = (1-p)^k, \quad E[K] = 1/p = 2^b.\]

The expectation follows from the tail sum:

\[E[K] = \sum_{k=0}^{\infty} P(K>k) = \sum_{k=0}^{\infty} (1-p)^k = 1/p.\]

A difficulty step doubles expected trials. It does not promise that every puzzle takes twice as long. Some succeed on the first trial; some take far longer than the mean. A client that measures only one solve has mostly measured this randomness.

A curve falling from 1 at x = 0 towards 0 at x = 4. At x = 1 a marked point shows that a search is still running with probability e to the minus 1, about 0.368; at x of about 3.0 a second point shows that 95 percent of searches have ended.
Fig. 1 Survival probability of hash search: the probability that a search is still running after \(x\) times the expected number of trials, in the large-work approximation \(P(K > x/p) \approx e^{-x}\).

Sessions Amortise Work

Suppose a session permits \(m\) requests before expiry, a puzzle costs \(c_p\), verification costs \(c_v\), and a session check costs \(c_s\). Ignoring unsuccessful attempts, the amortized gate cost per request is \(c_v/m + c_s\), while the client’s puzzle cost is \(c_p/m\). Increasing the session lifetime helps people and automated clients alike. Choosing it is a policy decision, not a cryptographic optimization.

Bounded State Is a Second Budget

Moving work off the request path does not make it disappear. Let incidents arrive at rate \(\lambda\), let the storage thread persist them at average rate \(\mu\), and let the queue hold \(Q\) records. When \(\lambda > \mu\), a fluid approximation gives

\[t_{\mathrm{fill}} \approx \frac{Q}{\lambda - \mu}.\]

A larger queue buys time; it does not create throughput. Batching amortizes transaction cost, but retained records still need memory and eventual service. Under overload Sibuna drops new incident records and counts them. It continues making request decisions from in-memory state. The operator must monitor the lost evidence as well as the HTTP success rate.

The Invariants We Will Carry Forward

  1. Untrusted requests cannot create unbounded server state.
  2. A valid admission token does not bypass an application denial.
  3. A buffer remains alive for every slice borrowed from it.
  4. A durable retry cannot multiply an incident or its reputation effect.
  5. A published policy snapshot is immutable until its last reader releases it.

The rest of the book derives the mechanisms that make these statements true, and the tests that would reveal a violation. A fast path is useful only while those statements remain true.