24 articles · RSS
Research
The algorithms and mathematics I keep returning to. Each article is written up from first principles, with the definitions, the algorithm and the properties that make it work.
- A log-structured store across trust tiersDraft
A key-value store whose layers sit on tiers of different speed and trust: a volatile tier that answers at once, a durable ordered log, and immutable segments. Reads equal the sequential map, flush and compaction preserve it, tombstones may be dropped exactly at the bottom level, re-encoding with any lossless codec is safe, recovery is exact, finalised state is never rolled back, and a wrong state root has one-step evidence.
Databases · Distributed SystemsLog-structured merge trees · Write-ahead logging · Replay verification - Demurrage at constant costDraft
A holding cost on money, applied through share accounting: only the total supply decays, so every holder is charged in proportion at constant cost per operation. Decay is independent of when updates happen exactly when it is geometric; a linear per-interval rule rewards frequent updates by exactly r²ab·S; floor rounding stays within one unit per operation and never pays out more than the supply; supply plus collected pool is conserved.
EconomicsDemurrage · Share accounting · Functional equations - Upgrading everything but the storeDraft
An architecture in which one persistent key-value store is fixed and every other component, including the registry that names components, can be replaced. Upgrades never touch stored state; only setters write; flattened keys are faithful exactly when the key encoding is injective; positional layouts collide where keyed ones cannot; a two-step role transfer opens a stale-writer window that an atomic or revoke-first transfer closes; registry replacement keeps every name resolvable under a stated ordering; and the set of components that can change a binding is a reachability closure.
Distributed Systems · Formal Methods · Smart ContractsDynamic software updating · Access control · Key-value storage - Small integers at bit granularityDraft
Length functions, prefix-freeness and Kraft sums for 2-bit selector integer codes, compared with LEB128 and Elias-γ, and what they cost under a geometric source.
Data EncodingInteger codes · Prefix codes · Kraft inequality - Trees as columnsDraft
A JSON tree written as two pre-order pointer arrays plus typed value columns, packed at the bit level, and an update scheme in which each edit is a small payload addressed against the previous materialized state.
Data Encoding · DatabasesTree encoding · Columnar layout · Delta coding · Incremental update - Arithmetizing JSONDraft
A canonical, injective encoding of arbitrary JSON into a short vector of field elements, so that an arithmetic circuit can prove the value at one path of a committed document without revealing the rest.
Cryptography · Data Encoding · Smart ContractsCanonical encoding · Arithmetic circuits · Zero-knowledge proofs - Authenticated state with sparse Merkle treesDraft
A document store committed to by one hash: fixed-depth sparse Merkle trees, an injective map from string ids to leaf indices, batched state-transition proofs and value or predicate queries checked against a single stored root.
Cryptography · Databases · Smart ContractsSparse Merkle trees · Validity proofs · Arithmetic circuits - Programs as data: point-free combinators in JSONDraft
A small combinator language whose programs are JSON arrays: its reduction rules, what its combinators can and cannot express, and why programs without variables are easy to store, hash and evaluate deterministically.
Formal MethodsCombinatory logic · Point-free style · Homoiconicity - Composing effects: monads and Kleisli arrowsDraft
Effectful pipelines as Kleisli arrows: the monad laws are exactly the category laws for arrow composition, which makes it possible to build a pipeline before any value exists, run it in a synchronous or an asynchronous monad, and refactor it without changing what it computes.
Formal MethodsMonads · Kleisli category · Program composition - Treasury-backed issuance as a state machineDraft
A token whose supply is backed by a treasury, modelled as a four-field state machine: a floor invariant that survives every operation for any monotone floor curve, backing that never decreases, an exact bound on what a fee sandwich can earn, a dollar cap with a tight drawdown theorem, a criterion for when a cubic Bézier curve is a function and where it turns vertical, and why a proportional contest for a fixed prize cannot clear at backing. Every combinatorial and arithmetic statement is proved in Lean; the real-analysis steps of the graph criterion are standard and stated as such.
EconomicsMechanism design · Invariants · Bézier curves · Tullock contests - Keys that are never stored
A wallet key re-derived on demand from factors: derivability sets as monotone access structures, AND/OR key combination realising every monotone formula, a threshold key-derivation service, a two-of-three construction, and what a pairing check does and does not give, all in a symbolic model checked in Lean.
CryptographyAccess structures · Threshold cryptography · Symbolic protocol models - Checking a batch of state accesses offlineDraft
Offline memory checking for a key–value state: a batch of transactions is verified from a log sorted by key and version, using only checks on single rows, checks on consecutive rows and one permutation argument. A Lean proof shows that the checks force every access to have seen the value of its key just before it and the claimed post-state to equal sequential execution, and that distinct versions cannot be dropped.
Cryptography · DatabasesMemory checking · Permutation arguments · Verifiable computation - Group key schedules as reachabilityDraft
A symbolic theory of group key schedules over an ordered, authenticated log: secrecy as non-reachability in a derivation graph, healing as confinement of wrap keys, the collapse of top-down derived trees, a lower bound on the number of published rules (wraps or KDF edges) under a separation hypothesis, and the epochs a long-term recovery key exposes, with two schedules worked out and every statement checked in Lean.
CryptographyKey schedules · Symbolic security · Lower bounds - Metered verified primitives: data stores whose cost is known before they runDraft
A data primitive as a specification, an executor that reports a usage vector, and a bound computed before execution, tied by three laws. A gate that refuses over-budget requests is sound, atomic and never charges more than the limit, and the laws are closed under composition, so a store assembled from primitives inherits both its meaning and its price.
Databases · Formal MethodsResource bounds · Refinement · Ordered indexes - Auditing a signed log that not everyone may readDraft
A signed, hash-chained log whose rules also limit who may read each event. Validity is a fold over a permission state, a fraud proof about one step convicts the signer and cannot frame an honest one, the parties who can check a step are characterised exactly for those who know the state, and two machine-checked counterexamples show that readers and auditors differ. A zero-knowledge fraud proof discloses only its claim. Everything is proved in an idealised symbolic model and checked in Lean.
Cryptography · Distributed SystemsHash chains · Fraud proofs · Access control · Zero knowledge - Rotating mailboxes over opportunistic forwardingDraft
Signed packets, mailbox ids rotated per epoch by a pseudorandom function of a shared secret, a skew-tolerant polling window and TTL-bounded flooding over contacts, combined so that authentic messages reach their recipient with no server, account or fixed address. Each property is proved for the combination in an idealised symbolic model, with the core statements checked in Lean.
Cryptography · Distributed SystemsOpportunistic forwarding · Temporal graphs · Symbolic cryptography - Taking powers away from a message hostDraft
A host that stores and relays a group's messages can read, alter, reorder, drop, break the group's rules, exclude members and disappear. Combining end-to-end encryption, signed hash-chained heads exchanged among readers, rule checking and migration of a self-certifying log removes, exposes or escapes each of these powers under stated conditions. Proved in a symbolic model without time, together with a limit no combination of this kind can overcome: withholding an entry from every reader leaves no evidence. Serving a stale view is a second, stated limit outside the model.
Cryptography · Distributed SystemsFork consistency · Hash chains · Accountability - Fast test answers that stay soundDraft
After a change, re-run only the test cases that could have seen it, cheapest tier first. Recording each case's read set while it runs, selecting cases by intersection with the changed locations, and ordering tiers by cost combine into one procedure. A Lean proof shows that it reports exactly the verdicts of a full re-run, after any number of changes, while executing no more cases than the change reaches.
Software Engineering · Formal MethodsRegression test selection · Dynamic read sets · Refinement - Many writers, one main lineDraft
Many autonomous agents change one shared state at once. Declared footprints, time-bounded leases, a batching merge queue that bisects on failure, and task groupings with prerequisites combine into one admission protocol. A Lean proof shows that the main line only ever holds checked states, that no admitted change is lost, that disjoint work never conflicts, and how many check runs a drain costs.
Software Engineering · Distributed SystemsMerge queues · Group testing · Leases · Optimistic validation - Metered non-interference over sealed fieldsDraft
A typed rule and query language over sealed fields, with metered evaluation and typed declassification, and a logical-relations proof that results, decisions, receipts and charged usage depend on sealed content only through ciphertext handles, lengths and declassified fields.
Formal Methods · CryptographyInformation flow · Logical relations · Resource metering - Checking a log from its signed headDraft
An outsider who holds only a public key and a signed tree head can check that an entry is in a log, that a row is in a state, and that a later head extends an earlier one. Merkle tree hashing with leaf and node domain separation, inclusion and consistency proofs, a row proof and signed heads are combined, and every soundness theorem is proved in the form "the claim holds, or this computable extractor returns a collision of the hash". Unforgeability is a hypothesis, never an axiom. Everything is checked in Lean.
Distributed Systems · CryptographyMerkle trees · Transparency logs · Inclusion proofs · Consistency proofs · Signed tree heads - Delta packing: nine numbers in sixteen bitsDraft
Runs of identical deltas and repeated types collapse into a single count-and-value pair. Here are the exact bits a bit-level columnar encoding writes, plus the case where this stops working.
Data Encoding · Databasesencoding · columnar · compression - Twelve columns: turning a JSON tree into a bitstreamDraft
A bit-level columnar encoding scans a document once, gives every container and key a slot, and splits the result into twelve column streams. Earlier columns tell the decoder how to read later ones.
Data Encoding · Databasesencoding · columnar · databases - Bits, not bytes: where byte-aligned integer codes leave space on the tableDraft
Byte-aligned integer encodings waste most of a byte on small numbers. A 2-bit width selector recovers most of it, and you can try it yourself below.
Data Encodingencoding · integer codes