aboutsummaryrefslogtreecommitdiffstats
path: root/docs/federation.md
blob: 5ada12245cfa0c197e4b3e42a13878bd68cd8347 (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
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
# Federation: a design

A design, not what the code does: none of this is built. It says how a swarm can be
kept by parties that don't trust each other, for a first use: the krebs registry
([krebs/kartei](https://github.com/krebs/kartei)), today plain files in a git
repository that one maintainer merges into. What it is for is narrow: to hand out
identifiers (names, addresses, keys), and to give every party a namespace of its own
that everyone reads.

It asks as little as it can of continuum and promises the least that makes a
federation possible. A federation that cooperates settles fast; one that doesn't
comes apart, and whoever wants to carry on with whom does so. Claims about the code
are marked *(checked)* where they were read in it.

## Optional

A swarm is federated from its genesis change, or not at all (Starting a federation).
Nothing else changes: a swarm that isn't stays as it is, its registry, rules, remakes
and replay included. Continuum's wire version
says only whether a node can take part in a federation at all; which federation a
swarm follows is a number of its own, in its policy: this design is federation 1
(Changing the federation). A swarm leaves the federation as any group carries on: by
forking, with the policy it wants (Forks).

## Parties and the adversary

A **party** is a name in the policy, with its keys. Parties write, and parties vote:
who isn't in the policy writes nothing, and comes in by a decision of those who are.
Nobody owns the swarm, and any party may be malicious, alone or with others.

A party is whoever holds its keys: several people may keep one party together, and one
person may be in several, each with its vote. The parties decide whom they let in,
groups included; nothing tells a group from a person.

What an adversary can do:

* run nodes, once a party lists them;
* craft any change: under any writer, with any dependencies, any operations;
* send different changes to different peers, send none, or pass on only some;
* delay or drop messages between any nodes, short of forever between honest ones;
* steal another party's key.

What it can't: forge an Ed25519 signature, or find two changes with one hash.

Out of scope: keeping anything from being read (every party reads all of it), hiding
who talks to whom, and a party's own machine taken over whole (then the adversary is
that party). The design rules nothing about what happens on a party's own nodes, only
that nothing coming from any node breaks a promise for the others.

## What is promised

1. **What counts is what a party signed, with a key it holds, where the policy lets it
   write.** Every honest node that holds the swarm from its genesis change, or
   followed every remake since, checking each, refuses what the version current at a
   change's history doesn't let be written, whoever sends it, and reads nothing else as
   counting.
2. **The policy changes only by the votes of a share of its parties**, two thirds
   unless they decide otherwise, as one history saw their votes; and nodes that hold
   the same changes read the same policy. Without a party voting twice, a version that
   passed stays; with one, the parties fork without it (Changing the policy).
3. **Any group carries on as it chooses.** Its parties fork with the policy they want,
   and whoever wants to follow does. Nobody is held by parties it doesn't follow.

Not promised:

* progress without the parties' cooperation: those who cooperate fork, and carry on;
* that a party votes well;
* that what a party's nodes withhold reaches anyone;
* that the swarm stays fast. A party that floods the document, or whose nodes keep
  remakes from committing, makes nodes slow, not wrong: denial of service breaks no
  promise here, and the others fork away from it;
* that honest nodes stay together where a node commits two changes under one writer
  and number: they are apart until a remake, or a fork (Where Automerge sets limits);
* that a node taken off its party's list, or a key a party dropped by itself, can't
  still commit or sign at a history from before: only a version ends what a key signs
  (Keys), and a remake ends what is written at the time before it;
* anything to a node that joins, or comes back after a remake without holding the
  epoch before: it takes the document on its peers' word (Remakes);
* that what nodes read stays put after a party voted twice, until the parties fork.

## The design

It builds on values signed by their users ([`access.md`](access.md)): a value is an
envelope its party signs, `cv2.<value>.<meta>.<signature>`, read the one way every part
of continuum reads it *(checked: `document::signed`)*. The meta names the swarm, the
path, who signed, when, the envelope it replaces (`prev`) and its number there (`seq`,
one more than that one's). Under the federation it names also the **version** of the
policy current where it was written, by number (`version`, The policy): a change writing
one that names another is refused, but for an epoch's first change (a remake's snapshot,
a fork's genesis), which is judged by none. Of the envelopes a place holds, written at
once, the one with the highest version number is its value, then the highest `seq`, then
the lower SHA-256. So what a place holds is its party's to say, never the order of
operations, which whoever writes a change steers; and what was signed under a later
version is ahead of anything written at a history from before it.

A swarm under a strict policy reads by `seq` alone, the same way, and replays a value
its user signed as the chain of envelopes that leads to it *(checked:
`document::store::candidates`, `remake::delta`)*; the version number is the
federation's.

### What it asks of the document

* **A change's history**, fixed by the change's hash: what its writer had seen. A
  change is judged at its history and nothing else.
* **The document at a set of changes**: the tree its writes make, the same on every
  node for the same set. A deletion removes what its writer saw, and nothing written
  at the same time.
* **Remakes that lose nothing and add nothing**: whatever continuum does to start the
  document anew, a node follows it only where the new document reads as the old one
  did at the base (Remakes).

Continuum's document is an Automerge document, which gives all of this and has limits
worth knowing (Where Automerge sets limits).

### The policy

A federated swarm's `_continuum/access/policy` is `{"version": 2, "federated": true}`.
What the policy says is in its **versions**, a chain: each is a string of JSON, named
by the SHA-256 of its bytes, numbered, and naming the version it changes (none for
the first, number 0, which only the genesis change writes; a fork's first, Forks):

```json
{ "federation": 1, "number": 7, "changes": "<hash of the version it changes>",
  "share": [2, 3],
  "keys": { "tv": ["ssh-ed25519 AAAA… tv"],
            "lass": ["ssh-ed25519 AAAA… lass"],
            "makefu": ["ssh-ed25519 AAAA… makefu"] },
  "rules": [
    { "path": "names/r/wiki/@", "writer": "lass" },
    { "path": "home/{party}/**", "writer": "{party}" },
    { "path": "names/r/{party}/**", "writer": "{party}" },
    { "path": "ip4/10/243/7/*", "writer": "tv" },
    { "path": "names/**", "writer": false } ] }
```

* **The federation** it follows, and its **number**, one more than that of the version
  it changes.
* **The share** of the parties a proposal needs, two whole numbers `[a, b]`, 0 < a ≤ b,
  2·a > b: with `[2, 3]`, the votes of two of every three (3·votes ≥ 2·parties).
* **The parties and their keys**: each party by name, as continuum's user names, 1 to
  64 of `A-Z a-z 0-9 . _ @ -`, with the keys its votes and proposals on this version
  are signed with. Where a party's keys differ from those the version it changes names
  (a party new in it, or one whose keys the parties replace), the version **sets**
  them (Keys).
* **The rules**, in order: the first whose path matches a path says who writes there.
  A path is segments separated by `/`. A rule's first segment is literal, and not
  `_continuum`; any other is literal, `{party}` (a party's name), `*` (any one
  segment) or, last only, `**` (one segment or more). The writer is `"{party}"` (the
  party the path names, where the rule's path holds `{party}`), a party's name, or
  `false`: nobody. A path no rule matches, nobody writes.

A **place** is a map key where an envelope is written: never within a list, nothing
written within one, and a path that holds places is no place. How names and addresses
are spelled as paths is the application's: the registry writes a name by its labels,
last first, its own value at `@` (`names/r/tv/toaster/@` for `toaster.tv.r`,
`names/r/tv/@` for `tv.r`), and an address by its parts, so that a party's zone or
block is one rule. Rules go by first match, so a party named like a shared name takes
it where a `{party}` rule comes before it: the application keeps party names apart
from its spelling (no party named `@`, nor `wiki` while `wiki.r` is lass's).

A version is none if it doesn't read as one (JSON with a key twice, fields missing or
more), its bytes don't hash to its place, or it breaks any of the above: it can't
pass, and a change writing it is refused.

The federation's own paths are its number's, not the rules': the same in every
version.

| Where | What | Who writes it |
|---|---|---|
| `_continuum/federation/versions/<hash>` | a version that passed | any member, once it passed |
| `_continuum/federation/proposals/<party>/<hash>` | a version proposed | that party |
| `_continuum/federation/votes/<party>/<version>/<proposal>` | `true` or `false` | that party |
| `_continuum/federation/keys/<party>` | its keys | that party; the change that writes a version setting them |
| `_continuum/federation/nodes/<party>` | its nodes' IDs | that party |
| `_continuum/federation/went/<party>` | the fork it went to | that party |

What a party writes is an envelope, signed by one of its keys. A version, and the keys a
version sets, are written unsigned, and count by the votes the version had. A proposal's
place takes only the proposal. Of continuum's own data, a federated swarm keeps what
nodes write for the protocol (member entries, remakes and their acks, epochs), written
by members as in every swarm, but a member's entry by that member only; a member's
change carries its node's signature, as signatures are required in a strict swarm. It
has no user registry: `_continuum/users`, bans, logouts, sessions, forgotten nodes, and
every entry of `_continuum/access`, the policy's place included, are closed: a write
there is refused, and nothing reads them. A party logs in to its own nodes as its
operator sets up, and a node takes tokens only from the nodes of its own party (Nodes).

### Changing the policy

A **proposal** is a version a party writes at
`_continuum/federation/proposals/<party>/<hash>`, its hash the version's, signed with
one of the keys the version it changes names for its party. It counts as written by
those, whatever keys the party writes since, until it lapses.

A party **votes** on a proposal by writing `true` or `false` at
`_continuum/federation/votes/<party>/<version>/<proposal>`: the version the proposal
changes, and the proposal, by their hashes. No vote there is no vote.

* **A vote is taken only where, at its history, its version is current and its
  proposal is written.** A vote cast at a history from before can't reach a proposal
  made since.
* **A vote never changes**, and **counts as cast**: signed with one of the keys its
  version names for its party, whatever keys the party writes since. So a vote is
  checked from itself and its version alone, by a client too, after the document
  dropped it. It goes only with its version, when that is replaced (What counts), and
  nobody deletes it before. A write at a vote's place is refused.
* **A proposal passes** once at least the share of its version's parties voted `true`.
  It is **dead** once so many voted `false` that the rest are fewer than the share.
* **One yes at a time.** A party's `true` is taken only if, at its history, every other
  proposal on that version it voted `true` for is dead. So a party backs one proposal,
  and is free again when that one can't pass any more.

Once a proposal passed on the current version, any member writes it at
`_continuum/federation/versions/<hash>`, as it is, unsigned, with the keys it sets
(Keys); every node judges that change by its history: the proposal written there, the
votes it had, and the version it changes current. A version takes effect when it is
written, and judges every change in sight of it.

**The current version** is the written version with the highest number; of two with
one number, the lower hash. A number is checked where its version is written, so the
highest is the end of the chain, read from what the document holds without the
versions behind it, which may go (What counts).

* **Votes that split pass nothing**, like a proposal that gets only nays: three for
  one proposal and three for another, of six. Nays end it: once a proposal is dead,
  its backers are free, and another proposal can pass on the same version. Parties
  that won't wait fork.
* **Two versions with one number** are written only if a party voted twice: `true` and
  `false` on one proposal, each shown to some, or `true` on two; one party is enough
  where a vote is close. Nodes that hold both read the one with the lower hash, so
  they agree once they sync, and where nothing was built on the other, that settles
  it. Where both were built on before the sides met, what nodes read can change again
  while votes cast on the other side before then come in: each is taken where it was
  cast, as every vote is. And what was written under the version not read ranks with
  what was written under the other, both naming one number: a key set a thief writes
  there is ahead of the one the other version set. So the parties answer a double
  vote by forking without the party that voted twice, the fork's version setting
  every party's keys (Forks). What the side not read deleted as housekeeping, and
  counts by the version read, its party's client puts back.
* **A party that voted twice shows**: its two votes on one version, both signed with
  keys the version names for it, each taken where it was cast. A node reports it (a log,
  the API), with both votes, from the history: a place holding two votes counts by its
  read like any place, and two `true`s are voting twice only where neither proposal was
  dead at the other's history. A client keeps the votes, as they are signed and anyone
  can check them after the document has dropped them. That proves its keys signed both,
  not that it meant to: two of its nodes voting each by itself, or a stolen key, look
  the same. Taking it out is the parties' choice, and a fork.
* **A proposal on a version that isn't current lapses**, with the votes on that
  version.

Everything the federation decides is a change of the policy: who the parties are, and
their keys where they lost them; who writes where, which is giving an identifier,
taking it back and giving it to another; the share; and the federation itself, by
naming another (Changing the federation).

### Keys

A party votes and proposes with the keys its version names for it; everything else it
writes, with its keys at `_continuum/federation/keys/<party>`: one envelope, the set,
signed with a key of the set it replaces, numbered as any envelope. The change that
writes a version setting a party's keys writes them there too, and only that change,
or it is refused: an envelope without a signature (`cv2.<value>.<meta>.`), the keys the
version sets and no others, its meta naming that version, the party as its user, `at`
0, `prev` and `seq` as any envelope's, the same from every member at one history. It is
ahead of every set written under an earlier version, and the party's next set names it
as the one it replaces.

* **A value counts only while the key that signed it is among its party's keys**,
  votes and proposals excepted, which go by their version's. Changing keys is: write
  the new set, and sign again, in the same change, what should stay, its node list
  among it (a client does that, its deletions too). A key added back, from a backup
  say, can bring back what it signed, and what a `null` of its party covered once that
  `null` went (What counts).
* **Only a version revokes a key.** A party changing its keys by itself adds keys and
  tidies; but a key it drops can still sign, at a history from before the drop, a set
  of its own numbered past the party's, and nothing in the document tells which of two
  chains from one set is the party's. A key lost, stolen, or retired and not
  destroyed, is answered by a version setting the party's keys, which is ahead of every
  set before it. What the party then signs again names that version, and is ahead of
  anything the old key writes at a history from before it.
* **A party's own key change reaches its votes and proposals** once a version names
  its new keys; until then its version's keep voting, as only a version revokes a key.
  After a version replaces a party's keys, the party signs its node list again, through
  any node that takes its envelopes.

### What counts

A change is judged at its history, by the version current there, as every node judges
it ([`access.md`](access.md), Changes judged on every node). So a value its party wrote
while it could write there is taken, even where a version written at the same time
says otherwise. What **counts** is read by the version current in the document as a
whole. These count no more, and nothing else is stale:

1. a value at a place its party may not write by the current version: the party is no
   longer one, the place went to another, a rule changed; and of a party that is no
   longer one, its keys and its node list;
2. a value signed by a key that isn't among its party's, votes and proposals
   excepted, which go by the keys their version names;
3. a proposal on a version that isn't current, and the votes on that version;
4. a version behind the current one: of a lower number, or of its number with the
   higher hash;
5. an envelope behind another at its place;
6. the member entry of a node its own party doesn't list (Nodes);
7. a party's `null` where the deleting change's history holds everything its place held
   before it or beside it in this epoch, from empty, all signed by keys its party no
   longer holds. A `null` the epoch's first change holds goes only at a remake
   (Remakes), as what it covers isn't in this epoch's history to judge by. Judging it
   reads the place's history: slow, not wrong.

**Any member may delete what counts no more**, place by place, never a map holding
places, and a member entry whole; every node judges the deletion by the document the
deleting change makes. That is the federation's own housekeeping; remakes carry whatever
is there. So that deletions don't flood the document, the one whose write made something
stale deletes it in the same change; others delete only what they find stale, as in a
swarm whose parties went quiet.

**What is deleted can be put back** where its place is empty, by anyone who holds it,
at a history where the version it names is current, and counts if its key is among its
party's and its party may write there: a place taken from a party and given back may
show what the party had there. Whatever the party writes there under a later version
is ahead of it. So a party's `null` stays while what it covers could come back and
count: it goes once that was all signed by keys its party dropped (7, above), or at a
remake (Remakes). Neither happens by itself; either can, so that a swarm that never
remakes can be kept from growing with every name ever deleted.

### Nodes

A party lists the nodes that carry for it, by node ID, at
`_continuum/federation/nodes/<party>`. A node's party is its operator's, in its
configuration, and its own member entry names it. A node is a member while that party
lists it: it registers, commits changes and syncs, and nodes sync with members only
(Stages); it takes tokens only from the nodes that party lists. Another party's list
does nothing. A node commits whatever envelopes it is given, its party's and others'
alike: what counts is who signed a value, not which node committed it. So a party
without nodes of its own writes through any node that takes its envelopes.

### Forks

Any group can carry on without the rest: too many parties are away for good, a version
the group won't follow passed, the parties can't agree, or it leaves the federation. It
**forks**: it starts a swarm of its own from the document.

1. One of the group starts the new swarm. Its genesis change holds what the old
   document read as at heads it names, built byte for byte as a remake's snapshot is,
   so that one version and one set of heads make one swarm, but for the
   federation's versions, the keys they set, continuum's member entries and the swarm's
   name: of versions, only the group's own, the fork's first. It names the highest
   version at those heads as the one it changes, is numbered one past it, and sets
   every party's keys; judged by none, as an epoch's first change is. Every proposal is
   a chance to fork: the version is usually one that didn't pass. To leave the
   federation, the genesis holds another policy instead, and what it needs.
2. A fork is named by the hash of its first version together with the heads it names,
   which nobody can steer to a given name, the old swarm's least of all: its genesis
   change writes it at `_continuum/swarm`, as every node checks, and an envelope's meta
   names it. The genesis change holds envelopes as the old document read them, and they
   count, whatever swarm they name; beyond them, nothing signed for one swarm is taken
   in another.
3. The others join it as a node joins any swarm, by its genesis change's hash. A node
   that holds the old document checks the new one against it first, the same at those
   heads but for what step 1 leaves out; says what it holds that those heads lack; and
   says, party by party, whether the fork's version gives it the keys it had there: a
   founder may give a party that didn't go keys of its own.

A fork needs nobody's vote and nobody's ack: it binds only those who go, and the swarm
they left goes on for those who stay. A party the fork's version leaves out writes
nothing there, and what it had counts no more; to come back, the fork's parties let it
in by a version, as they would anyone new. A fork's version may name parties that
weren't among the first to go (every party its founders consider honest, say), so that
they can follow whenever they like, without asking. A party that goes may say where,
at `went/<party>`: the fork's genesis change, for those who follow it.

What a party's nodes do of themselves is their operators' business, written nowhere:
join a fork where parties their operator follows went (`went/<party>`), vote as those
voted, vote by
bounds their operator set, or do nothing without their operator. So a federation that
cooperates can have a group that leads without being named: the active parties the
others follow.

### Shared identifiers

Anything outside a party's namespace is shared: names, addresses, anything a rule
names. Who writes one is what a rule says: by its own name (`names/r/{party}/**`: a
party writes the names under its own), or given to one party by a version, and taken
back and given to another the same way. Nothing is first come, first served. The
value is what its writer signs there (`names/r/wiki/@`: where the name points); what
a former writer signed counts no more once a version gives the place to another.

Routine work needs no vote: a version gives a party a zone or a block by one rule
(`ip4/10/243/7/*`), and a new host is a write where its party may write. Votes are
for parties, zones, blocks and names that are nobody's by their spelling.

### Starting a federation

A federation starts with a swarm of its own: its genesis change, the swarm's first,
writes the federated policy and the first version, with the keys it sets, as a swarm
strict from its start records its policy (`--bootstrap-policy`) *(checked:
`swarm::bootstrap`)*, which starts it empty: content before it would be a change from
before the federation, judged by none. So nothing is from before the federation, and
nothing writes the policy's place after the genesis change: the federation changes by
versions, and is left by a fork. A running swarm doesn't become federated; its parties
start one, and sign into it, after the genesis change, what they keep.

### Remakes

A remake starts the document anew, for Automerge's sake only (Where Automerge sets
limits); the federation needs none and asks for none. When to remake, and who acks,
is continuum's as in every swarm. What a federated node asks of a remake:

* **It loses nothing and adds nothing.** A node follows a remake only where the new
  document reads as the old one did at the base, at every place and every path of the
  federation, as continuum reads it. A node checks that before it switches, stays
  where it is otherwise, and never rejoins an epoch it refused.
* **Writes after the base** are replayed as the policy shapes them: at each place, the
  chain of envelopes that leads from what the new document holds there to what the old
  one reads, each in a change of its own, judged again in the new epoch, the other
  writes with them, each after those its change builds on, clocks only between changes
  neither of which saw the other, as continuum replays under a strict policy *(checked:
  `remake::delta`)*. Versions written after the base go with them, each in one change
  with the keys it sets, whatever names a version before the next, each judged by the
  votes replayed before it. Votes and proposals go by the keys their version names,
  which is replayed before them, so they count as cast in the new epoch too, whatever
  key sets of their party are replayed around them. Whether a place is held already goes
  by version number, then `seq`. What the new epoch refuses (its key was dropped by a
  version, its place given to another) goes to the quarantine of the node that holds it,
  and its party signs it again if it still may.
* **Housekeeping after the base** isn't replayed: what it deleted is stale again, and is
  deleted again, but for a `null` that went by rule 7 (What counts), which the snapshot
  holds, so that it goes only at the next remake. And where a chain starts on an empty
  place (`prev` empty) and what the new document holds there counts no more by what was
  replayed so far, the replaying node deletes that in the first link's own change,
  judged by the document that change makes, as housekeeping is; the link is checked
  against the place as the deletion leaves it.
* **A party's `null`** is left out of the snapshot once a version later than the one
  it names is current: nothing naming an earlier one can be written in the new epoch,
  and an empty place reads as one holding `null` does. One the snapshot keeps goes
  only at a later remake (What counts).

A remake's base is its coordinator's word, so all this holds for any base, not only a
recent one. So a remake decides nothing that counts, but what it can't hold: of two
envelopes of one version and `seq` at a place at the base, the snapshot keeps one, and a
write after the base on the other, an envelope put back after it on one the snapshot
lacks, or a write after it on a `null` the snapshot left out, goes to the quarantine,
and its party writes again. A swarm that never remakes stays as correct as one that
remakes all the time; it only grows slower. A remake does end one thing: nothing is
written at a history from before it, so what a dropped key or a node taken off its list
could still write there ends with it.

A node that doesn't hold the epoch before (it joins, or was away) can't check: it
takes the epoch its peers give it.

### Where Automerge sets limits

Recommendations, not rules: none of these breaks a promise, only how fast a node is.

* **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 federated swarm
  remakes before its writers and history make that felt, and a node keeps its writer
  over a clean restart where it can.
* **One change a number.** A node that commits two changes under one writer and number
  splits the nodes that took one from those that took the other: a node holding one
  can't take the other. Continuum refuses the second as forged, by whoever brings it
  *(checked: `Signatures::forks`)*. A remake brings the two sides together again, and
  so does a fork.
* **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`)*.
* **History.** The document keeps all of it, which remakes bound.
* **Bytes.** The nodes of an epoch run one Automerge version; a swarm moves to another
  at a remake.

## Why it holds

1. **What counts.** A change is judged at its history, which its hash fixes, by the
   version current there, which the versions written in that history fix, each judged
   by the votes in its own. Every node judges alike, and refuses the change and
   everything built on it. What counts is read from what the document holds: the
   current version, the highest number; each party's keys, by that version and its
   set; each place's value, by version number, then `seq`. None of it depends
   on the order of operations. A copy of an older envelope is behind; a new one written
   at a history from before a version is behind what is written under it.
2. **The policy.** A version is written only where, at one history, the share of the
   parties of the version it changes voted `true` for it. An honest party backs one
   proposal on a version at a time, and another only once the first is dead; its votes
   count as cast. So a proposal can't pass at one history and be dead at another
   unless some party's `true` and `false` for it are both there. Without a party voting
   twice, at most one version changes a version. With one, nodes still read the same
   version once they hold the same changes, and the parties fork.
3. **Remakes.** A node follows a remake only where its snapshot reads as the old
   document did at the base, which it checks. What came after is replayed in history's
   order, each change judged as every node judges it: versions by the votes replayed
   before them; votes and proposals by the keys their version names, which comes
   before them; envelopes as chains, from what the snapshot holds, by version, then
   `seq`. So what counted, counts, but what a remake can't hold (Remakes), each of which
   its party writes again.
4. **Carrying on.** A fork is a swarm of its own, named by its first version and the
   heads it names, joined by its operators' choice only. A party nobody follows carries
   on alone.

## Attacks

What an attacker does, and what happens. *Unit*: the judging, with crafted changes.
*Sim*: a simulation. *Bench*: measured, not judged.

| # | Attack | What happens | Test |
|---|---|---|---|
| 1 | An envelope signed by a key that isn't its party's, or by no party | Refused at its history | unit |
| 2 | An envelope for another path, swarm or version | Refused: its meta names all three | unit |
| 3 | An older envelope written where a newer one is | Refused: `prev`, `seq` | unit |
| 4 | An older envelope put beside the newer by a change that saw neither | Taken, and behind | unit |
| 5 | A former holder writes a chain at a history where it held the place | Behind what is written under the version that gave the place away | unit |
| 6 | A dropped key writes a key-set chain at a history before the drop | Ahead of the party's own set, until a version sets the party's keys; then behind | unit |
| 7 | A version written without the votes, or not changing the current one at its history | Refused at its history | unit |
| 8 | A version that doesn't read, has a key twice, a share of a half, a rule under `_continuum` or without a literal first segment | No version: can't pass, refused when written | unit |
| 9 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit |
| 10 | `true` on two proposals at once, from two nodes | Both taken; two versions of one number may be written; the lower hash is read; reported; the parties fork | unit, every order |
| 11 | `true` and `false` on one proposal at once | Both held; a node that saw only one may write a version. As 10 | unit, every order |
| 12 | A vote changed, or deleted while its version is current | Refused | unit |
| 13 | A vote cast at a history from before, on a proposal made since | Refused: its proposal isn't written there | unit |
| 14 | A party changes keys after voting or proposing, or beside its vote or proposal | It counts as cast, by its version's keys, at a remake too | unit |
| 15 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit |
| 16 | The parties beyond the share never vote, or vote `false` on everything | Nothing passes; the others fork | sim |
| 17 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit |
| 18 | A version written late beside one the parties went on from | A lower number: changes nothing | unit |
| 19 | A proposer grinds its version's hash | Wins a tie of two versions of one number; only with a double vote, which a fork answers | unit |
| 20 | Values signed with a stolen key | Count until a version drops the key, then none of them; under a version sharing its number with another, until a fork | unit |
| 21 | A deleted value put back where its place is empty | Counts if its key and its place are still its party's; behind whatever the party writes there later | unit |
| 22 | A write in another party's namespace, or at an identifier of another's | Refused by the rule | unit |
| 23 | Housekeeping of something that counts | Refused, by the document the change makes | unit |
| 24 | Housekeeping by a change that saw a time when it didn't count | Taken; the party writes again | unit |
| 25 | A map holding places deleted, or a place written within | Refused | unit |
| 26 | A remake whose document reads otherwise than the base | Nodes holding the base stay, and never rejoin it | sim |
| 27 | Two envelopes at one place beyond a remake's base | The chain to the one read is replayed | unit |
| 28 | A version written after a remake's base, an envelope written beside it | Replayed, the envelope first, as it names the version before | unit |
| 29 | A joining node handed a made-up epoch | Taken. Not promised | sim |
| 30 | The party with most nodes remakes often, or never acks | Slow, not wrong; the others fork | sim |
| 31 | A writer forked: two changes, one number | Honest nodes split until a remake, or a fork. Not promised | sim |
| 32 | Different changes to different peers | Honest nodes agree once they sync | sim |
| 33 | A party withholding its changes or votes | Not promised | — |
| 34 | Flooding: namespace, proposals, history, writers | Slow, not wrong | bench |
| 35 | A node taken off its list writes changes at a history where it was on | Taken where valid there; behind what is written under later versions | unit |
| 36 | A token from another party's node | Refused: a node's party is its configuration's | unit |
| 37 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit |
| 38 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join, and say what differs | sim |
| 39 | A fork at heads of its founder's choosing | Joiners holding the document are told what those heads lack | sim |
| 40 | A federation, or a policy, a node doesn't know | It stops taking changes | unit |
| 41 | A party lists another party's nodes, or one its party dropped | Nothing changes: a node is its own party's | unit |
| 42 | The versions behind the current one deleted | The current one is still the highest number | unit |
| 43 | A vote cast on the side not read, before the sides met, sent after | That side may gain a version, and be read. Not promised: the parties fork | unit |
| 44 | A key set written under the version not read, of two with one number | Ahead of the set the other wrote, until a fork | unit |
| 45 | A place given to another and emptied after a base, its new holder writing after that | Replay deletes what counts no more there, then writes the new holder's chain | unit |
| 46 | Two envelopes of one version and `seq` at a base, a write after it on the one not kept | Quarantined; its party writes again | unit |
| 47 | A `null` deleted while what it covers could still count, or one the epoch's first change holds | Refused, by the deleting change's history | unit |
| 48 | A fork's version giving a party that didn't go keys of its founder's | Joiners holding the document are told, party by party | sim |
| 49 | Two parties each writing a key set beside the other's vote, crossed | Nothing: votes go by their version's keys, at a remake too | unit |
| 50 | Content written before a federation's genesis change, and a change built on it | None: the genesis change is the swarm's first | unit |
| 51 | A party's node writing another node's member entry | Refused: an entry is its member's | unit |
| 52 | A `null` and an envelope of its party at once, the `null` read | Rule 7 waits for both: the `null` stays while the envelope could count | unit |
| 53 | Two founders forking one version at one set of heads | One swarm: the genesis change is built byte for byte | sim |
| 54 | A party's node writing logouts, sessions or forgotten nodes | Refused: closed | unit |
| 55 | A coordinator records an old base | Everything after it is replayed, each as every node judges it | sim |
| 56 | A write after a base on a `null` the snapshot left out | Quarantined; its party writes again | unit |
| 57 | A version written without the keys it sets, or keys written by another change | Refused | unit |

## Roads not taken

* **First come, first served, for identifiers.** Order between two parties that wrote
  at once can't be read from the document without trusting someone's clock or
  someone's witness. Votes need neither.
* **Anything waiting on time** (final after so many days). Clocks are each node's own.
  Everything here waits on votes.
* **Taking back what a stolen key signed, from history.** A thief makes its changes
  look as old as it likes. A version dropping the key takes all of them back, and the
  party signs again what was its own.
* **One vote per version**, never to be cast again. It bounds what parties voting
  twice can do at a third of them, and leaves a split for good. With nays a split
  ends, and one party voting twice on a close vote can have two versions written; the
  votes show who, and the parties fork without it.
* **A recount without a party that voted twice.** Its second vote can come at any
  time, at a history from before, and would undo a version long after it passed; and
  honest parties who backed one proposal, then another once the first was dead, would
  look as if they had voted twice.
* **The longest chain from the first version.** It reads the same as the highest
  number, but needs every version kept, and a tie decided where two chains part, long
  behind both.
* **Becoming federated in a running swarm.** It needs the time before closed, as
  continuum closes it for a swarm turned strict, values from before counting only
  where a party signed them, and of two federating changes at once neither preferred,
  as a tie broken by hash would let a change made later to look as old take the
  place of the one every node took. A federation started by its genesis change needs
  none of it.
* **Votes counted by the keys their party had at their history.** A remake replays a
  vote and its party's key set in an order of its own, and where two parties' key sets
  and votes cross, no order keeps every vote. The keys a version names don't move.
* **Freezing the policy once two versions share a number.** One party could stop the
  federation at every close vote; the lower hash keeps nodes agreeing until the parties
  fork.
* **Forks within one document**, each side judging by its own chain of versions. It
  needs judging per chain, judging again when a node changes sides, node lists and
  remakes per chain. A swarm of its own needs none of it.
* **Leaving the federation by a version.** The closed registry, and the time during
  the federation, would be read again by the next policy. A fork with that policy
  starts clean.
* **Users below the parties.** A party's people and keys within it are its own matter:
  it may hand out its keys as it likes. The federation sees parties.

## Changing the federation

Every node of a swarm runs the same version of continuum today. A federated swarm's
parties can't be made to upgrade together, so what all its nodes must agree on is named
by the federation's number: the rules of this design, the envelope and how the value of
a place is read, what makes a change one Automerge writes, how a path and a version are
spelled and read, which version is current, the remake's check, its replay and its
order. The hash of a change and its encoding are Automerge's
version's.

A change to the federation is a design like this one, with the next number. A swarm
moves to it by a version of its policy that names it (`"federation": 2`), which the
parties pass once their nodes run a continuum that knows it. A node that doesn't know
the federation, or the policy, its swarm has stops taking changes and says so.

## The registry on it

The krebs registry today: users, their hosts, the hosts' names, addresses and keys.
On a federated swarm:

* each krebs user is a party, its hosts in its namespace (`home/tv/hosts/laptop`: its
  keys, its addresses as it uses them). Every decision takes two thirds of all
  parties, quiet ones counted: the first version names the parties that will vote,
  and lets the others in as they turn up;
* its names under `names/r/tv/` and `names/w/tv/` by one rule each, its address blocks
  by a rule each; other names given by versions;
* kartei's entries signed in by their parties after the genesis change, never as
  content before it;
* a tool reads what counts and writes what kartei's consumers read today.

## Stages

1. **The federated policy**: a swarm started federated by its genesis change; versions
   and what makes one valid, rules and paths, keys, votes, passing and dead, the current
   version, judging by it; votes and proposals by their version's keys; the protocol
   data closed but for member entries, each its member's, remakes, acks and epochs; the
   meta's version number and the order by it; node lists, a node's party in its
   configuration, and tokens from one's own party's nodes only; continuum's readings of
   a policy and of an envelope taking the federated policy and the meta's version beside
   the six fields it has today. A node that doesn't know the policy stops taking
   changes. Until stage 4, a federated swarm takes no remake.
2. **What counts**, read by the current version and the keys; shown in the API.
   Housekeeping. Reports of a party that voted twice.
3. **Nodes**: membership by the node lists and the party a node's own entry names, a
   node syncing with members only, as a swarm key does today (a wire change).
4. **Remakes**: the check that a remake lost and added nothing; replay of versions with
   the envelopes.
5. **Forks**: a swarm started from another's document, named by its first version and
   the heads it names, and the check against it.
6. **The registry**: the rules for krebs, the tool that signs kartei's entries in as
   their parties', after the genesis change, and the one that reads them out.

Each stage's tests are its rows of Attacks. Each stage keeps every swarm that isn't
federated as it is, its tests passing untouched.