aboutsummaryrefslogtreecommitdiffstats
path: root/docs/store.md
blob: 952953c3c5745798c1979e36368f599bf9aaa88a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
# 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 so has every event in its
history that isn't one of them or in their history: it builds on them, and on nothing
written beside 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; 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. 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 (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). A node keeps what it forgot for as long as its operator sets, and gives it to
nodes catching up.

### 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 longer than its peers kept what they forgot, 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 the root its operator names, the swarm's ID, or from a
checkpoint its operator pins. 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;
* **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<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 checkpoint at `heads`, read as `at`: its bytes, and the events it keeps.
    fn checkpoint(at: &Self::State, heads: &[Id]) -> (Vec<u8>, Vec<Id>);
    /// The state a checkpoint reads as, with the events it keeps.
    fn start(checkpoint: &[u8], kept: &[(Id, Vec<u8>)]) -> Result<Self::State, Refused>;
    /// The heads of a later checkpoint, where a store reading as `now` moves to one.
    fn moves_to(now: &Self::State) -> Option<Vec<Id>>;
    /// 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, 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. 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 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/<ID>` | 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": "<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 the events its root
keeps too, each 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, the swarm's ID 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 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. A node moving to a checkpoint
drops, the same way, every change it holds that carries an event the move refuses. Until
the next remake, the document still holds what the node forgot, and the node reads none
of it.

### 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, 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 it is at the base: its checkpoint, where it isn't
  the root, the events it keeps and those after it, 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. What a checkpoint forgot leaves the document here.
* **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 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 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, where the
  snapshot's checkpoint is one it can build, one before its own, the root its operator
  names, or one its operator pins (Pinned checkpoints); it judges every event after it,
  and puts again what it held. Where it refuses an event the snapshot holds, by its own
  refusals or its operator's drops, it stays where it is; what a checkpoint of its own
  forgot, it reads none of. 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 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 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 | 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 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 syncs the rest of the base from a peer that keeps the old epoch, builds, and switches; or takes an epoch as a node with an empty document does | 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 | 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 | Refused; a change the node holds that carries one is dropped, its other events put again | unit |
| 24 | A node away while the others moved to a checkpoint and forgot what came before | It builds the checkpoint from what a peer kept, or takes it where its operator pins it | sim |
| 25 | 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 |
| 26 | 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
([`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 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's document holds, but for what
  it forgot, 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, 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.