aboutsummaryrefslogtreecommitdiffstats
path: root/docs/store.md
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 13:12:01 +0000
committertv <tv@krebsco.de>2026-11-16 15:05:53 +0100
commit4bcb412f95a003d86a0bbad64576259a951e7c80 (patch)
treee7fe68b768553e27c9300ae39c85b4e20f002d8d /docs/store.md
parent7ff0679c77be3e10348599d74941d7a28305311c (diff)
docs/store: a store of events, generic over its fold
A set of events that only grows, each named by the SHA-256 of its bytes and naming those it builds on, judged at that history so that every node judges it alike, and read together as one state. What the events are, how one is judged and what they read as is a fold's, a trait the federation is the first to implement. Its first home is a swarm's Automerge document: each event is bytes at `_continuum/events/<ID>`, a change writes events and continuum's protocol data only, and a node puts again every event it doesn't refuse of a change it refuses or drops, so that which change carries an event changes nothing. A compaction's snapshot holds the events at its base, and every event beyond it is put again: remakes, rejoins and a writer's two changes of one number change no event a node holds, and the fold never sees them. It says what is promised, a node's own refusals and drops, forks carrying their root's history, members by the fold, where Automerge sets limits, its attacks, and what its tests check. Nothing of it is built; all of it is to be behind the `federation` feature.
Diffstat (limited to 'docs/store.md')
-rw-r--r--docs/store.md306
1 files changed, 306 insertions, 0 deletions
diff --git a/docs/store.md b/docs/store.md
new file mode 100644
index 0000000..eddf3cf
--- /dev/null
+++ b/docs/store.md
@@ -0,0 +1,306 @@
+# The store: a design
+
+A design, not what the code does: none of this is built. The store is a set of events
+that only grows. Each event is named by the hash of its bytes and names the events it
+builds on; it is judged where it was written, at that history, so every node judges it
+alike; and the events a node holds read as one state. What the events are, how one is
+judged and what they read as is a **fold**'s, and the store is generic over it. The
+federation ([`federation.md`](federation.md)) is its first fold.
+
+The store asks nothing of what carries its events. It is built first inside a swarm's
+Automerge document (On Automerge): continuum's sync, transports, saving and remakes
+carry it, and none of them changes what it holds. All of it is behind the `federation`
+feature: without it, continuum builds and behaves as it does.
+
+## Events
+
+An **event** is bytes, named by its **ID**: the SHA-256 of its bytes, written as 64
+lower-case hex digits. In its bytes it names the events it builds on, its
+**dependencies**, by their IDs; how it names them is its fold's. An event's **history**
+is everything it builds on: its dependencies, theirs, and so on, which its ID fixes. A
+set of events is **whole** where it holds every event's history; the **heads** of a
+whole set are the events nothing in it builds on.
+
+A store has one **root**, given when the store is made: an event it takes without
+judging, whose ID is the store's. Every other event it takes is in the root's history,
+or has the root in its own: a root that builds on nothing starts a store anew, and one
+that builds on another store's events starts a fork, which carries their history
+(Forks). A store takes an event only once it holds its dependencies, so it is whole at
+all times.
+
+## The fold
+
+A fold says, of its events:
+
+* **what an event builds on**, read from its bytes; bytes that aren't one of its events
+ are none, and are refused;
+* **whether an event is taken where its history reads as a given state**: judging. A
+ root is taken only as its own store's, never by judging;
+* **the state a whole set of events reads as**, built by adding its events one at a
+ time, each after its dependencies, and the same whatever order they come in: the state
+ of a node's store, and the state at an event's history, which judging reads;
+* **the store's members**, the nodes that carry it, at a state, each with the name of
+ its group (Members);
+* where it needs to, **what a node refuses that its history takes**, by what the node
+ took before (A node's own).
+
+In Rust, roughly:
+
+```rust
+pub trait Fold {
+ type State: Clone + Default;
+ /// What the event builds on; `None` where its bytes are none of this fold's events.
+ fn dependencies(event: &[u8]) -> Option<Vec<Id>>;
+ /// Whether the event is taken where its history reads as `at`.
+ fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>;
+ /// Adds the event, whose dependencies are added already.
+ fn add(state: &mut Self::State, id: &Id, event: &[u8]);
+ /// Whether a node whose store reads as `now` takes an event its history takes.
+ fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
+ true
+ }
+ /// The nodes that carry the store, each with its group.
+ fn members(state: &Self::State) -> Vec<(NodeId, String)>;
+}
+```
+
+How the store keeps states, so that judging an event at its history costs little, is its
+own matter: it may keep the state of some events and add to it the rest of a history
+that holds them all. Whatever it keeps reads as adding every event of the history anew,
+which its tests check (Tests).
+
+## What is promised
+
+1. **Every node takes an event or none**, but for what a fold has a node refuse by what
+ it took, and what an operator has its node drop (A node's own). An event is judged at
+ its history, which its ID fixes, so every node judges it alike, whenever and from
+ whomever it comes. An event refused is refused with everything built on it.
+2. **Nodes that hold the same events read the same state**, whatever order the events
+ came in, and whatever carried them.
+3. **Nothing underneath adds an event or takes one away.** What a node holds is what it
+ took. Which document carries the events, which changes put them, a remake, a rejoin:
+ the fold sees none of it (On Automerge).
+
+Not promised: that an event reaches every node, as a node may withhold what it holds;
+that the store stays small, as it keeps every event and nothing in it shrinks; that it
+stays fast.
+
+## A node's own
+
+A fold may have a node refuse an event its history takes, by what the node took before:
+the federation's node takes a version only where it changes the one the node reads
+([`federation.md`](federation.md), Changing the policy). And an operator may have its
+node **drop** events it took. Either way the node refuses the event and everything built
+on it, from whoever brings it, until its operator says otherwise, and reports it. No
+peer's word moves a node; its operator's does. A node that refuses what another took
+holds other events, and reads its own state from them; two that hold the same read the
+same.
+
+## Forks
+
+A **fork** is a store whose root builds on events of another, at heads its maker
+chooses. It carries the root's history, byte for byte, each event judged at its history
+as in the store it came from: a fork is whole from its root back to the first, and any
+node checks it from those events alone, whether or not it holds the store the fork came
+from. Then it takes only events with its root in their history. What the store it came
+from takes beside or after those heads, the fork never takes; nor does that store take
+what the fork takes, as no store takes another's root, nor anything built on it. A
+node's own refusals are its store's: in a fork it follows, it judges the root's history
+afresh. What a fork's root holds, and who makes one, is its fold's: the federation
+builds one byte for byte from its version and its heads, so that one version and one set
+of heads make one fork ([`federation.md`](federation.md), Forks).
+
+## On Automerge
+
+The store's first home is a swarm's document, which continuum's sync, transports, saving
+and remakes carry. A swarm holds a store from its genesis change, or not at all, and its
+document holds nothing but the store's events and continuum's protocol data.
+
+### What the document holds
+
+| Where | What |
+|---|---|
+| `_continuum/events/<ID>` | an event, as bytes, at its ID |
+| `_continuum/access/policy` | `{"version": 2, "store": "<fold>"}`: a store, and its fold |
+| `_continuum/swarm` | the swarm's ID: the root's |
+| elsewhere under `_continuum` | continuum's protocol data, as far as this says |
+
+The **genesis change**, the swarm's first, writes the policy, the swarm's ID, its epoch
+and the root, and nothing else, built byte for byte from the root: its writer from the
+root's ID, time 0, no message. So one root makes one swarm, and a node joining builds
+the genesis change and checks it. A fork's genesis change holds its root's history too,
+each event at its ID, built the same way. Continuum reads the policy as one asking for
+signed changes, as a strict one does, and nothing else of a strict policy: the document
+holds no values but events.
+
+### What a change writes
+
+A change of a swarm holding a store writes nothing but:
+
+* **events**: at `_continuum/events/<ID>` the bytes whose ID it is, at a key held
+ nowhere at the change's history; its dependencies held there, or put before it by the
+ same change; taken by the fold at its history, and by the node's own (A node's own);
+* **continuum's protocol data**: by a member, its own entry, its own acks, a remake's
+ record and proposal; by a remake's coordinator only, its decision or its abort; by an
+ epoch's first change, epochs and the swarm's ID.
+
+Everything else is closed, a write at, within or above it refused: whatever isn't under
+`_continuum`, users, bans, logouts, sessions, forgotten nodes, `_continuum/access` with
+the policy's place, the swarm's topology (`neighbours`, `relays`, `topology`,
+`dissemination`), and whatever a later continuum adds. Nothing deletes or replaces an
+event. A change is taken only from a member (Members), and carries its node's signature,
+as a strict swarm's changes do. Every node judges a change at its history, as continuum
+judges every change under a policy ([`access.md`](access.md), Changes judged on every
+node), and refuses it with everything built on it. The same event put by two changes at
+once is one event: its key holds the same bytes twice.
+
+### Events, whichever change put them
+
+What the store holds is the events the document holds, by their bytes: which change put
+one, and how often, changes nothing. So a node that refuses a change, or drops one, puts
+again, in changes of its own, every event of it, and of what is built on it, that it
+doesn't refuse, read from those changes' own operations, each after its dependencies. An
+event of a change refused for something else it writes, or for its writer, still reaches
+the store; one refused by the fold, or by the node's own, takes with it only the events
+built on it. So two nodes' documents may differ where the events they hold don't: a
+writer's two changes of one number, which part the nodes holding one from those holding
+the other (Where Automerge sets limits), part no events.
+
+### Members
+
+The fold names the members, each with its group: for the federation, the nodes each
+party lists, each as its party's. A node's group is its operator's, in its
+configuration, and its own entry names it. A node is a member while the fold names it
+with that group, at the node's heads, and nodes sync with members only. A change is
+taken only where its node is a member at the change's history with the events it puts
+added (an epoch's first change aside, which every node builds itself), so that a node an
+event makes a member can put that event itself. A swarm holding a store has no swarm
+key: a secret its members share keeps out nobody, and the fold says who syncs. A node
+keeps some of its neighbours among the members of its own group and of the groups its
+operator names, so that a group naming many nodes can't be every node's neighbours.
+
+At its API, a node takes no token another node issued, and whoever its operator lets in
+may have it put events, whoever signed them, and write its own protocol data;
+`--protocol-writers` names nobody. It shows the events, its heads, and what its fold
+reads from them.
+
+### Remakes
+
+A remake is continuum's, for Automerge's sake only (Where Automerge sets limits): the
+store needs none, and asks for none. When to remake, and who acks, is continuum's as in
+every swarm: acks tell an honest coordinator when to commit, and bind nobody. A swarm
+holding a store takes compaction only, whose snapshot is a function of its base and its
+record (its ID, its coordinator): two remakes at one base are two epochs.
+
+* **The snapshot** holds the events at the base, each at its ID, and of continuum's
+ protocol data what a compaction carries, but the entries of nodes that aren't members
+ at the base.
+* **A node follows a decision** only where the fold names its coordinator a member, as
+ the node reads it when it switches. It builds the snapshot itself, from a base it
+ holds, syncing what it lacks of the base from peers that keep the old epoch, and
+ checks it against the committed epoch, as continuum's node builds a compaction's
+ *(checked: `remake::switch`)*. A remake's decision is its coordinator's alone, and so
+ is its abort. A node that holds two decisions for one epoch, from a coordinator that
+ wrote two or from remakes decided at once, follows neither, says so, and leaves it to
+ its operator, who names one; a decision whose coordinator isn't a member, as the node
+ reads it, is none of them.
+* **After it switches**, a node puts again every event it holds beyond the base, each
+ after its dependencies, and, while it keeps the old epoch, syncs it with nodes still
+ on it and puts again what it takes there. Each event is taken again as it was: its
+ history is in the new epoch too.
+* **A node with an empty document**, or one that can't build a remake as no peer keeps
+ its base, takes the epoch its peers give it, or the one its operator pins, judging
+ every event in it from the root, whose ID is the swarm's, and puts again what it held.
+ Where it refuses an event the snapshot holds, it stays where it is. A made-up epoch
+ can withhold events from it, and keep it apart from the others, but make it take
+ nothing it wouldn't.
+
+So a remake changes no event a node holds, only which document carries them, which the
+fold never sees. A swarm that never remakes holds what one that remakes all the time
+holds; it only grows.
+
+### Where Automerge sets limits
+
+* **Bytes.** The nodes of a swarm holding a store run one Automerge version, which its
+ fold names (the federation by its number): two versions that encode a change
+ differently refuse each other's changes.
+* **Changes it shouldn't apply.** A change is first of all one Automerge itself writes,
+ or it is refused before Automerge sees it, in every swarm *(checked:
+ `document::changes::Written`)*.
+
+The rest break no promise, only how fast a node is, whether it stays up, or how long the
+documents stay together.
+
+* **Writers.** Every writer costs every node memory while the epoch lasts, in proportion
+ to the document's history *(measured: about 4 bytes per change)*. A node writes under
+ a fresh writer each time it starts, rejoins or drops. A swarm holding a store remakes
+ before its writers and history make that felt, and a node keeps its writer over a
+ clean restart where it can. Nothing bounds the writers a node starts: one that starts
+ one with every change, by fault or on purpose, runs the others out of memory, until a
+ remake leaves its writers behind. Its writers name it, and its entry its group.
+* **One change a number.** A node that commits two changes under one writer and number
+ parts the documents of the nodes that took one from those that took the other:
+ continuum refuses the second as forged, by whoever brings it *(checked:
+ `Signatures::forks`)*. The events of both reach both sides, each putting them again,
+ so the store isn't parted, only the documents, which remake apart, until an operator
+ has its node drop the change it took; no event is lost by it.
+* **History.** The document keeps every operation, which remakes bound; the store keeps
+ every event, which nothing bounds.
+
+## Attacks
+
+What an attacker does to the store on Automerge, and what happens; a fold's own attacks
+are in its design ([`federation.md`](federation.md), Attacks). *Unit*: the judging, with
+crafted changes. *Sim*: a simulation. *Bench*: measured, not judged.
+
+| # | Attack | What happens | Test |
+|---|---|---|---|
+| 1 | A change writing outside `_continuum/events` and the protocol data listed | Refused | unit |
+| 2 | An event at a key its bytes don't hash to | Refused | unit |
+| 3 | An event whose dependencies aren't held at the change's history | Refused | unit |
+| 4 | An event deleted, or replaced | Refused | unit |
+| 5 | The same event put by two changes at once, or again later | One event | unit |
+| 6 | An event the fold refuses, beside others in one change | Refused, with everything built on it; every node puts the others again | unit |
+| 7 | A change by a node that isn't a member at its history, the events it puts added | Refused | unit |
+| 8 | Bytes that are none of the fold's events, or a root other than the store's | Refused | unit |
+| 9 | A fork's events brought to the store it came from, or the other way | Never taken: their history lacks the root | unit |
+| 10 | A writer forked: two changes, one number | The documents part, the events reach both sides, the state is the same | sim |
+| 11 | A snapshot holding other events than its base's | Not followed: a node builds its own and checks it against the epoch | sim |
+| 12 | Events written beyond a base, on nodes that switch and on nodes that don't yet | Put again in the new epoch: the same events, the same state | sim |
+| 13 | A coordinator shows one of two decisions for an epoch to some nodes, the other to the rest | Each follows the one it holds; a node holding both follows neither; their operators bring them together | sim |
+| 14 | A decision or abort written by a node not its coordinator; a decision whose coordinator isn't a member | Refused; none | unit |
+| 15 | A node with an empty document handed a made-up epoch | It judges every event from the root: the epoch withholds, at worst | sim |
+| 16 | A node away while the others switch | It syncs the rest of the base from a peer that keeps the old epoch, builds, and switches; or takes the epoch its peers give it, judging every event | sim |
+| 17 | A token from another node | Refused: a node takes only its own | unit |
+| 18 | A node writing another node's entry, or under `_continuum` where this doesn't say | Refused | unit |
+| 19 | A group naming many nodes, to be every node's neighbours | Each node keeps some among its own group's and those its operator names | sim |
+| 20 | A node whose operator had it drop an event is sent it again, in another change | Refused, with everything built on it, until its operator says otherwise | unit |
+| 21 | A node no longer a member writes changes at a history where it was one | Taken where valid there: their events count by who signed them, and nobody follows a remake it decides | unit |
+| 22 | Flooding: events, writers, history, remakes | Slow, or out of memory; not wrong | bench |
+
+## Tests
+
+What the tests check of the store, with a fold made for them:
+
+* **Order.** For every order of a whole set of events that puts each after its
+ dependencies (all of them for small sets, seeded ones for larger), the state is the
+ same, and so for the orders in which several nodes get them.
+* **History.** The state at a history is the state of its events added anew, and judging
+ at it gives the same verdict whatever states the store kept.
+* **Refusal.** An event refused is refused with everything built on it, on every node,
+ whatever the order.
+* **On Automerge.** For any run of events, changes, refusals, drops, remakes, rejoins
+ and writers forked, the events a node's document holds are the events it took, and its
+ state is that of a store given those events alone.
+* **Bytes.** Fixed vectors, byte for byte: events and their IDs, a genesis change, a
+ fork's, a snapshot.
+
+## Roads not taken
+
+* **Events as Automerge's own changes**, each change an event and its dependencies the
+ event's. A remake leaves the changes behind, and with them every event's name; and
+ Automerge numbers a writer's changes in a chain, so that a writer's events would build
+ on each other, or each would need a writer of its own, which costs every node memory
+ without end.
+* **Remakes of other kinds** (`replace`, `import`, `strict`). Their snapshot is what
+ someone gives; a compaction's, every node builds itself from the base.