aboutsummaryrefslogtreecommitdiffstats
path: root/docs/store.md
diff options
context:
space:
mode:
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.