# The store: a design A design, not what the code does: none of this is built. The store holds events. 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. The store starts from a checkpoint, the state at some heads written down, and holds what came after it; moving to a later checkpoint, a node forgets what matters no more, so that it holds what is relevant and nothing else. What the events are, how one is judged, what they read as and when the store moves to a checkpoint 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. The **heads** of a set of events are the events nothing in it builds on. An event is **above** some heads where it has them all in its history, and every event of its history that isn't one of them, nor in their history, has them all in its own: it builds on them, and on nothing written beside them. None of the heads is above them. ## Checkpoints A **checkpoint** is the state at some heads, written down: those heads, the events before them its fold keeps, by their IDs, and what the fold says of the rest (the federation: the version current there, and every event that counts there). It is named by the hash of its encoding, which its fold gives, and built byte for byte from its heads, so every node holding the history up to them builds the same one. A store holds a checkpoint, the events it keeps, byte for byte, and the events after it: each above the checkpoint's heads, its dependencies among those heads and the events after them. The heads are held by their IDs, whether the checkpoint keeps them or not, and a head brought again is taken as held; a root is its own checkpoint's one head (below). A store takes an event only once it holds its dependencies, so it holds every event's history back to its checkpoint. A store's first checkpoint is its **root**, taken without judging, whose ID is the store's: its bytes are a checkpoint's, which no fold reads as an event, so the store takes it as its own before the fold sees any event. A root without heads starts a store anew; one at heads of other stores starts a fork (Forks). Its events build on the root itself, whatever heads it was built at: until the store moves to a later checkpoint, the root's ID is the one head they all have in their history. ### Moving to a checkpoint The fold says when the store moves to a later checkpoint, and at which heads: events after the store's checkpoint, none in another's history (the federation: by a version that names them, once a node takes it). A node then builds the checkpoint at those heads, forgets every event before them that it doesn't keep and every event not above them, and refuses such events from then on. The fold names heads that whatever makes the store move is above, so that moving refuses none of it. Judging an event after those heads needs nothing the node forgot, as the fold keeps what judging reads; and what is read from the checkpoint and the events after it is what the whole history reads, but for what the fold lets a checkpoint forget. Its tests check both (Tests). Until the next remake, the document still holds what a node forgot, and a node that was away syncs it as any (On Automerge); after it, one that can't build the checkpoint takes it where its operator pins it. ### Pinned checkpoints A node builds every checkpoint it moves to itself, from the one before and the events up to the new heads, and judges every event after it. A checkpoint it can't build, as it was away across a move and a remake after it, or as it joins, it takes only where its operator pins it, by its ID, and then judges every event after it as any. A node joining starts from a checkpoint its operator pins; only for a store that never moved does the root its operator names, the swarm's ID, suffice. Once a store moved, what came before its checkpoint can be grown anew from the root by what the fold refuses since (the federation: keys of versions long replaced, [`federation.md`](federation.md), Checkpoints), and a node joining from the root would take it. So a node takes nothing on a peer's word: what it didn't build or judge itself, its operator vouched for. ## 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 checkpoint and the events after it read as**, built by adding the 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 checkpoint at some heads**: what of the history before them it keeps, and what it says of the rest; and when the store moves to one; * **a fork's root**, from the states at heads of one store or of several, and what makes the fork (the federation: its version); * **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; /// What the event builds on; `None` where its bytes are none of this fold's events. fn dependencies(event: &[u8]) -> Option>; /// 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 checkpoint at `heads`, read as `at`: its bytes, and the events it keeps. fn checkpoint(at: &Self::State, heads: &[Id]) -> (Vec, Vec); /// The state a checkpoint reads as, with the events it keeps. fn start(checkpoint: &[u8], kept: &[(Id, Vec)]) -> Result; /// The root of a fork at `heads` of the stores reading as `at`, made by `spec`. fn fork(at: &[&Self::State], heads: &[Id], spec: &[u8]) -> Result<(Vec, Vec), Refused>; /// The heads of a later checkpoint, where a store reading as `now` moves to one. fn moves_to(now: &Self::State) -> Option>; /// The nodes that carry the store, each with its group. fn members(state: &Self::State) -> Vec<(NodeId, String)>; } ``` The state carries what judging and reading need of the events' history: the federation's, the graph of the events it holds, so that it says what is in an event's history, what is above some heads, and what is dead at a history; `start` places every event a checkpoint keeps in the history of every event after it. `keeps` depends, by design, on the order a node takes events in: which events a node takes may differ by it, and the state of the set it takes doesn't. 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, what an operator has its node drop (A node's own), and what moving to a checkpoint refuses. 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 checkpoint and the same events after it 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, less what a checkpoint forgot. Which document carries the events, which changes put them, a remake, a rejoin: the fold sees none of it (On Automerge). 4. **A node takes nothing on a peer's word.** It builds every checkpoint itself and judges every event after it, but for a checkpoint its operator pins (Pinned checkpoints). Not promised: that an event reaches every node, as a node may withhold what it holds; that an event not above a checkpoint's heads is taken once nodes moved to it; that a checkpoint a node takes on its operator's word is the one the others built; that the store 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, and moves to a checkpoint as it takes a version naming one ([`federation.md`](federation.md), Changing the policy, Checkpoints). And an operator may have its node **drop** events it took after its checkpoint; not what the checkpoint keeps or holds by ID, as every event after it builds on that. A node undoes a move only by taking a checkpoint its operator pins. Either way the node refuses the event and everything built on it, from whoever brings it, until its operator says otherwise, and reports it; it keeps what it refuses so, and its operator's drops, in a file of its own, across restarts. 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 is a checkpoint at heads of another, or of several, which its maker chooses, with what the fork's fold says there (the federation: the fork's version). A fork at heads of several stores **merges** them: its root keeps what its fold takes of each (the federation: what counted on each side, as the fork's version has it). A node holding the history up to all those heads builds the root and checks it; one that doesn't takes it on its operator's word, which names the fork anyway. The fork takes only events with its root in their history: what the stores it came from take after those heads, the fork never takes; nor do they 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. 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 and continuum's protocol data. ### What the document holds | Where | What | |---|---| | `_continuum/events/` | an event, as bytes, at its ID: the root, the events a checkpoint keeps, and those after it | | `_continuum/checkpoint` | the store's checkpoint, as bytes, where a snapshot holds one other than the root | | `_continuum/access/policy` | `{"version": 2, "store": ""}`: 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, in this order and nothing else: the policy at its place, as a map with its keys sorted; the swarm's ID at `_continuum/swarm`, as a string, as continuum's genesis records it; and the root at its ID, as bytes; each making the maps on its way as continuum writes a path (`store::write_path`). It is built byte for byte from the root: its writer the first 16 bytes of 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 alone; the events the root keeps follow in changes of the same writer, built the same way and filled in the order of their IDs: an event goes into the change being filled, unless its bytes would take the events there past 1 MiB, and then it begins the next. 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/` the bytes whose ID it is, at a key held nowhere at the change's history; * **its node's own protocol data**: its entry, its acks, a remake's record and proposal, and, as a remake's coordinator, its decision or its abort; or, an epoch's first change, epochs, the swarm's ID, the policy and the checkpoint. 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 carries its node's signature, as a strict swarm's changes do, but for the changes every node builds itself: an epoch's first change, and a fork's changes after it. They carry none, and their writer, derived from the root or from the remake *(checked: `remake::snapshot`)*, writes exactly them: any other change under that writer is refused, so nobody commits under it what every node doesn't build. A change is first of all one Automerge itself writes (Where Automerge sets limits). Every node judges a change by these alone, each a question of the change and its history, and refuses it with everything built on it, as continuum refuses a change its rules refuse ([`access.md`](access.md), Changes judged on every node). It judges no event there: which events it takes is its store's (below). The same event put by two changes at once is one event: its key holds the same bytes twice. ### What the store takes from the document The store reads the events the document holds, by their bytes, and takes them as it would take them from anywhere: each once it holds its dependencies, judged at its history, and by the node's own (A node's own). The rest it reads none of: an event nobody takes, or one a checkpoint forgot, stays in the document until the next remake leaves it out (Remakes). Which change put an event, and how often, changes nothing, so honest nodes hold one document, whatever each reads from it. Continuum still refuses some changes on its own, by what they are or who wrote them: of a writer's two changes of one number, the second (Where Automerge sets limits). A node that refuses such a change puts again, in changes of its own, every event of it, and of what is built on it, read from those changes' own operations, each after its dependencies: so that what it carried still reaches the store, and the documents those two changes part hold the same 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, as its store reads now, and nodes sync with members only. Nothing is judged by who was a member at a change's history: a change reaches a node only through a member, which could carry the same events itself, and the entry of a node that isn't a member counts for nothing where continuum reads entries (a remake's electorate, the entries a snapshot holds). 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, its checkpoint, 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 store as the node reads it at the base: its checkpoint, where it isn't the root, the events it keeps and those after it, each at its ID; the policy; and of continuum's protocol data what a compaction carries, but the entries of nodes that aren't members at the base. What a checkpoint forgot, and events nobody takes, leave the document here. Nodes that read the store differently at the base (the sides of keys that voted twice, in the federation) build different snapshots, and part here. * **A node follows a decision** whichever node coordinated it: a decision reaches it only through a member, which could decide one itself, and a remake changes no event. It builds the snapshot itself, from a base it holds, and checks it against the committed epoch, as continuum's node builds a compaction's and checks it *(checked: `remake::switch`)*; a node that lacks the base rejoins (below). A remake's decision is its coordinator's alone, and so is its abort. **Of two epochs decided for one**, by a coordinator that wrote two decisions or by remakes decided at once, a node follows the one with the lower ID, and a node on the other rejoins it. * **After it switches**, a node puts again what it holds beyond the base that the new document lacks, each event after its dependencies, once a short wait of its own has passed, random, so that not every node puts the same. Each event is taken again as it was: its history is in the new epoch too. A node that moved to a later checkpoint since the base keeps its own, and reads none of what the snapshot holds that its checkpoint forgot, as it read none of it in the old document. * **A node that rejoins**, as it was away, lacks the base, or is on the higher of two epochs, takes the epoch its peers give it, or the one its operator pins, as continuum's node rejoins. It keeps its own checkpoint and reads from the new document what is above its heads, judging every event; a later checkpoint the snapshot holds, which it can't build from what it holds, it takes only where its operator pins it (Pinned checkpoints). It puts again what it held. What its own refusals and its operator's drops refuse, it reads none of. A node with an empty document does the same, from the root its operator names or a checkpoint its operator pins. 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; its document 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 holds its checkpoint and what came after it, which checkpoints bound. ## 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 never come | Taken by no node; it stays in the document until the next remake leaves it out | 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 | The change is taken; the store takes the others, and not that one, nor what is built on it | unit | | 7 | A change by a node that isn't a member, brought by one that is | Taken: its events count by who signed them, its entry for nothing | 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 a 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 another checkpoint, or 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 | Nodes on the higher epoch rejoin the lower: no operator needed | sim | | 14 | A decision or abort written by a node not its coordinator | Refused | unit | | 15 | A node with an empty document handed a made-up epoch | It takes its checkpoint only where it builds it, or its operator named or pinned it, and judges every event after it: the epoch withholds, at worst | sim | | 16 | A node away while the others switch | It rejoins: reads what is above its checkpoint, judging every event, and puts again what it held; a later checkpoint it can't build it takes where its operator pins it | 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, before or after a restart | Not taken, with everything built on it, until its operator says otherwise | unit | | 21 | A node no longer a member decides a remake, its decision brought by a member | Followed as any decision: a remake changes no event | unit | | 22 | A checkpoint a node can't build, handed to it by peers | Taken only where its operator pinned it | unit | | 23 | An event not above the heads of the checkpoint a node moved to | Not taken; the change that carries it is, and stays in the document until the next remake | unit | | 24 | A node away while the others moved to a checkpoint and forgot what came before | It builds the checkpoint from the document, which holds what came before until the next remake; after it, it takes it where its operator pins it | sim | | 25 | Heads for a checkpoint before the store's, or one in another's history | No move: the fold names none such | unit | | 26 | A head brought again after a move | Taken as held, and not read anew | unit | | 27 | An operator has its node drop an event its checkpoint keeps | Refused: a node drops only events after its checkpoint | unit | | 28 | A remake whose base comes before a checkpoint, switched after nodes moved to it | They switch, keep their checkpoint, and read none of what it forgot | sim | | 29 | Flooding: events, writers, history, remakes | Slow, or out of memory; not wrong | bench | | 30 | A member decides compactions, grinding their IDs until the new epoch's ID is lower than the honest one's | Nodes on the honest epoch rejoin the lower, once a generation; no event is lost: slow, not wrong | sim | ## Tests What the tests check of the store, with a fold made for them ([`federation-tests.md`](federation-tests.md) says how they are built): * **Order.** For every order of a set of events that puts each after its dependencies (all of them for small sets, seeded ones for larger), the state of the set a node takes 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. * **Checkpoints.** Judging any event after a checkpoint gives the verdict judging it with the whole history gives, and reading gives what the whole history reads, but for what the fold lets a checkpoint forget; a node moving to a checkpoint reads the same state whenever it moves, as long as it holds the same events after. * **On Automerge.** For any run of events, changes, refusals, drops, checkpoints, remakes, rejoins and writers forked, the events a node takes from its document are those a store given the same events alone takes, and honest nodes hold the same document whatever each takes from it. * **Bytes.** Fixed vectors, byte for byte: events and their IDs, checkpoints, a genesis change, a fork's, a merge'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. * **Every event kept**, so that every node checks everything from the first. Every node would hold what counted no more years ago; a checkpoint its operator pins stands in for what it can't build. * **Remakes of other kinds** (`replace`, `import`, `strict`). Their snapshot is what someone gives; a compaction's, every node builds itself from the base.