Notes on abstract algorithms and theory: data encodings, authenticated data structures, symbolic cryptography, distributed logs and small economic mechanisms. Each result comes with definitions and theorems checked in Lean 4 (core library only).
Everything is published at tn.ms. Most items are drafts: the Lean checks pass, and independent review is ongoing.
- Canonical Arithmetization of JSON Documents, with Authenticated Stores and Zero-Knowledge Path Queries (40 pp.)
- Bit-Level Columnar Coding of JSON Trees with Append-Only Delta Chains (12 pp.)
- Arithmetizing JSON: 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.
- Authenticated state with sparse Merkle trees: A document store committed to by one hash.
- Group key schedules as reachability: A symbolic theory of group key schedules over an ordered, authenticated log.
- Taking powers away from a message host: A host that stores and relays a group's messages can read, alter, reorder, drop, break the group's rules, exclude members and disappear.
- Keys that are never stored · reviewed: A wallet key re-derived on demand from factors.
- Checking a batch of state accesses offline: Offline memory checking for a key–value state.
- Auditing a signed log that not everyone may read: A signed, hash-chained log whose rules also limit who may read each event.
- Rotating mailboxes over opportunistic forwarding: 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.
- Metered verified primitives: data stores whose cost is known before they run: A data primitive as a specification, an executor that reports a usage vector, and a bound computed before execution, tied by three laws.
- A log-structured store across trust tiers: 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.
- Upgrading everything but the store: An architecture in which one persistent key-value store is fixed and every other component, including the registry that names components, can be replaced.
- Checking a log from its signed head: 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.
- Small integers at bit granularity: 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.
- Trees as columns: 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.
- Composing effects: monads and Kleisli arrows: Effectful pipelines as Kleisli arrows.
- Metered non-interference over sealed fields: 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.
- Programs as data: point-free combinators in JSON: A small combinator language whose programs are JSON arrays.
- Many writers, one main line: Many autonomous agents change one shared state at once.
- Fast test answers that stay sound: After a change, re-run only the test cases that could have seen it, cheapest tier first.
- Demurrage at constant cost: 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.
- Treasury-backed issuance as a state machine: A token whose supply is backed by a treasury, modelled as a four-field state machine.
Proofs: Lean 4 · Site: tn.ms