diff options
Diffstat (limited to 'docs/store.md')
| -rw-r--r-- | docs/store.md | 306 |
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. |
