aboutsummaryrefslogtreecommitdiffstats
path: root/docs/federation.md
blob: 6bdc4e4f7610442519f8b28cbb317137ec81b12a (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
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
# 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. 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, building each itself, 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 two thirds of its parties**, as one
   history saw their votes; and nodes that hold the same changes read the same policy.
   Without keys voting twice, a version that passed stays, on every node; with them,
   the nodes part, and the parties fork (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 keys voted twice (Changing the policy): each
  node keeps the version it took, and one that had taken neither of two (it lagged
  behind, or joins) may be shown either first;
* that honest nodes stay together where a node commits two changes under one writer
  and number: they are apart until a fork (Where Automerge sets limits);
* that a remake reaches every node: one that can't build it itself stays where it is;
  nor that nodes follow one remake where two were decided for one epoch: each follows
  the one it holds, until operators name one (Remakes);
* that a node taken off its party's list can't still commit at a history from before:
  from the next remake's base on, it can't;
* anything to a node with an empty document: it takes the epoch its peers give it, or
  the one its operator pins (Remakes).

## The design

It builds on values signed by their users ([`access.md`](access.md)): continuum's
signed value, `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). A federated swarm's value is an envelope its party signs, the
same with a prefix of its own, `cv3.<value>.<meta>.<signature>`, whose meta names also
the **version** of the policy current where it was written, by number (`version`, The
policy). A swarm that isn't federated reads a `cv3.` string as the string it is.

A change writing an envelope that names another version than the one current at its
history is refused, but for an epoch's first change (a remake's snapshot, a fork's
genesis), which is judged by none, and for the key sets and node lists a version sets,
which name the version being written (Keys). Of the envelopes a place holds, written at
once, its value is the one with the highest version number, then the highest `seq`, then
the lower SHA-256, among those signed by a key their party holds (Keys); where none is,
nothing there counts. Judging a change goes by all of them, as they stand: its `prev`
names the first of all, whoever signed it, so a party's first envelope where another's
is (a place given to it, an envelope a dropped key wrote) names that one, its `seq` one
more. So what a place holds is its party's to say, never the order of
operations, which whoever writes a change steers, nor a key the party dropped; 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 a node builds itself**: whatever continuum does to start the document
  anew, a node follows it only where it built the new document itself, from a base it
  holds (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 (`null` for
the first, number 0, which only the genesis change writes; a fork's first, Forks).
Spread out:

```json
{ "federation": 1, "number": 7, "changes": "<hash of the version it changes>",
  "keys": { "tv": ["ssh-ed25519 AAAA… tv"],
            "lass": ["ssh-ed25519 AAAA… lass"],
            "makefu": ["ssh-ed25519 AAAA… makefu"] },
  "nodes": {},
  "rules": [
    { "path": "names/r/wiki", "writer": "lass" },
    { "path": "home/{party}/**", "writer": "{party}" },
    { "path": "names/r/{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 parties and their keys**: one party at least, each by name, as continuum's
  user names, 1 to 64 of `A-Z a-z 0-9 . _ @ -` but not `@`, with one `ssh-ed25519` key
  or more, compared as keys (their comments aside), none twice in the version. With
  them the party signs its votes and proposals on this version, its key set and its
  node list (Keys, Nodes). 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 node lists it sets** (`nodes`), by party, each a list of node IDs: the first
  version and a fork's set those of the parties that start it (Nodes).
* **The rules**, in order: the first whose path matches a path says who writes there.
  A path is segments separated by `/`, none empty. A rule's first segment is literal,
  and not `_continuum`; any other is literal, `{party}` (the name of a party of the
  version, once in a rule at most: a segment naming none doesn't match, and a later rule
  decides), `*` (any one segment) or, last only, `**` (one segment or more); none is
  `@`. A rule matches a path key by key: a key holding `/` is one segment, which only
  `*` and `**` match. The writer is `"{party}"` (the party the path names, only where
  the rule's path holds `{party}`), a party of the version, or `false`: nobody. A path
  no rule matches, nobody writes.

A **place** is a path a rule matches. Its value is the envelope in its `@` key
(`names/r/tv/toaster/@`). An envelope goes only in an `@` key, an `@` key never holds a
map, and a change writes nothing else where rules say who writes but the maps on the way
to the `@` keys it writes, each only where none is, never deleting or replacing one: so
no key is both a value and the way to places, whatever the rules of any version say, a
version may give a place and places below it alike, no map is left empty, and no change
plants keys in another's namespace. Nothing is written within a list. How names and
addresses are spelled as paths is the application's: the registry writes a name by its
labels, last first (`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 takes a rule or two. 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 `wiki` while `wiki.r` is lass's).

A version is none if its bytes aren't the JCS encoding (RFC 8785) of the JSON they read
as, so that nothing in it is spelled two ways and no key is there twice; if a field is
missing or more; if its bytes don't hash to its place; or if it breaks any of the above.
It can't pass, and a change writing it as a version is refused. A proposal is taken
whatever its text, but for its hash, which must be its place's: its party and version
are read from its place and its envelope, and whether it is a version is asked where it
is written as one, so that nodes knowing more of what a version may say don't part from
those knowing less. A node shows whether a proposal is a version by the federation it
knows, and a party's client backs none that isn't: two thirds backing one that can never
be written bind the federation to its version, as a yes binds (Changing the policy).

The federation's own paths are its number's, not the rules': the same in every
version. They hold their values directly, and never nest; a change makes the maps on
the way to what it writes there as it does to `@` keys.

| 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, by a key its version names; the change writing a version that sets them |
| `_continuum/federation/nodes/<party>` | its nodes' IDs | that party, by a key its version names; the change writing a version that sets them |

What a party writes is an envelope, signed by one of its keys. A version is written as
its text, a plain string; the key sets and node lists it sets, as envelopes without a
signature; all of them count by the votes the version had. A proposal's place takes
only the proposal.

A federated swarm has no user registry, and of `_continuum` takes only these writes:

* at `_continuum/federation`, as the table says;
* 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 (the genesis change, a remake's snapshot): epochs and the
  swarm's ID.

Everything else is closed, a write at, within or above it refused: 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. The topology is continuum's own, as the genesis change writes none; each
node picks its own relays, and some of its neighbours by party (Nodes). Nothing but the
policy is read of the rest. A member's change carries its node's signature, as
signatures are required in a strict swarm. 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).
Whoever a node lets in through its API may have it commit what the rules take:
envelopes, whoever signed them, and the node's own protocol data; `--protocol-writers`
names nobody in a federated swarm.

### 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 is on the version its
envelope names, the one current at its history. It counts as written by those keys,
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
is on, 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 a remake left it
  out. Nobody deletes it, and a write at a vote's place is refused. A party's client
  keeps what its party voted, and votes by that, never by what a node shows.
* **A proposal passes** once at least two thirds of its version's parties voted `true`
  (3·yes ≥ 2·parties). It is **dead** once so many voted `false` that the rest can't
  pass it (3·(parties − no) < 2·parties). A party whose `true` and `false` on one
  proposal are both in a history counts for both there, whatever its vote's place reads
  as, so that a history holding more votes never takes back a pass or a death.
* **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.

So a yes binds its party while its proposal can pass. Of nine parties, five back X, two
prefer Y and two never vote: X needs one more and can't die, as that takes four nays.
The five back nothing else on this version, and the others take X or fork. A proposal
that could pass at one history and be taken back at another would let two versions be
written without anyone voting twice.

Once a proposal passed on the current version, a node writes it as soon as it holds it
passed, at `_continuum/federation/versions/<hash>`, with the key sets and node lists it
sets (Keys, Nodes): any member may, and the same version written by several is one
(below). Every node judges that change by its history: the proposal written there, on
the version the text changes, its votes there, and that version current. A version takes
effect when it is written, and judges every change in sight of it.

**A node takes a version only where it changes the version the node reads**, or is one
it took, written again. A change writing any other, valid at its history or not, it
refuses, with everything built on it, reports, and leaves to its operator; another
node's refusal doesn't make it drop what it took. One valid at its history breaks no
rule: its committer isn't refused as a whole, as a member whose own change broke a rule
is ([`access.md`](access.md)), and the node reports it apart from changes against the
rules. Of two that change the one it reads, it takes the first it judges. Without keys
voting twice, every version written changes the one every node reads, and none is
refused.

**The current version** is the written version with the highest number: the end of the
chain the node took, read from what the document holds without the versions behind it,
which a remake leaves out (Remakes).

* **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 changing one** are written only where keys voted twice: a party
  voting `true` and `false` on one proposal, each shown to some, or `true` on two; or
  the keys an earlier version named, for two thirds of its parties, passing another
  proposal on it at a history from before the version that followed: some party among
  them backed that one too (two shares of two thirds share a party). Each node keeps the
  version it took and refuses the other, so nodes holding the same changes still read
  the same policy; the sides are apart, and a node that lagged behind, or joins, may be
  shown either first. The parties answer by forking, without the party that voted
  twice, or with its keys named anew (Forks).
* **A party that voted twice shows**: its two votes on one version, both signed with
  keys the version names for it. A node reports it (a log, the API), with both votes,
  as it reports every version it refused. Anyone can commit a vote again at another
  history, so two `true`s are voting twice only where no copy of either was taken at a
  history where the other's proposal was dead; two envelopes of one value at one vote's
  place are one vote. A client keeps the votes, as they are signed and anyone can check
  them after a remake left them out. 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, their
keys where they lost them, and their node lists where they have none; who writes where,
which is giving an identifier, taking it back and giving it to another; and the
federation itself, by naming another (Changing the federation).

### Keys

A party votes and proposes with the keys its version names for it, and signs with them
its key set and its node list. Everything else it signs with its keys at
`_continuum/federation/keys/<party>`: one envelope, the set, signed with a key the
version current at its history names for the party, numbered as any envelope. A set is
checked only where it is written, never by the keys of a set (What counts, 2).

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 (`cv3.<value>.<meta>.`),
the keys the version names for the party and no others, its meta naming the swarm, its
path, that version and the party, `at` 0, `prev` empty and `seq` 0, so that it is the
same wherever the version is written. It is ahead of every set naming an earlier
version, and the party's next set replaces it.

* **A value counts only while the key that signed it is among its party's keys**, those
  of its set: votes, proposals, sets and node lists aside, which go by the keys their
  version names. A party changes its keys by itself: it writes a set with the new keys,
  signs again with one of them what should stay (a change is judged at its history,
  where only the set it replaces is the party's), writes a set without the old ones,
  and signs again after it what should stay (a client does it all). What a key it
  dropped signed counts no more; what that key writes at a history from before the drop
  can't name what the party signed after it as replaced, and counts no more either, so
  it takes nothing out. A key added back, from a backup say, brings back what it signed
  where it is still there.
* **Only a version revokes a key it names.** One lost or stolen is answered by a version
  naming the party's keys anew, whose set is ahead of every set before it. What the
  party then signs names that version, and is ahead of anything the old key writes at a
  history from before it. Until then, the old key votes, and writes the party's set and
  node list, as the party's.
* **A party's own key change reaches its votes and proposals** once a version names its
  new keys. A party can keep the keys its version names apart, offline, and sign its
  values with a set of its own.

### 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 does:

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 key set and its node list;
2. a value signed by a key that isn't among its party's, votes, proposals, key sets
   and node lists aside, 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;
5. an envelope behind another at its place, of those 2 leaves;
6. the member entry of a node its own party doesn't list (Nodes).

Nothing is deleted within an epoch but by a party at its own place, writing `null`.
Automerge keeps every operation, so a deletion shrinks nothing: only a remake shrinks
the document. What counts no more stays until a remake's snapshot or a fork's genesis
leaves it out, where it is or names a version before the one current there, or is a
member entry (Remakes).
Until then, a place given back to its party, or a key added back, shows what the party
signed before, until the party writes there again.

### Nodes

A party lists the nodes that carry for it, by node ID, at
`_continuum/federation/nodes/<party>`: one envelope, signed with a key its version
names, or set by a version as a version sets keys (Keys). 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 party's list counts until the party writes another or a
version sets one, whatever keys its version names since, so that no change of keys
leaves a swarm without members; a list a stolen key wrote stays until the party writes
one under the version that replaced that key, which it can at once, through any member.
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.

A node keeps some of its neighbours among its own party's nodes and those of the
parties its operator names, so that a party listing many nodes can't be every node's
neighbours. A federated swarm has no swarm key: a secret its parties share keeps out
nobody, and the node lists say who syncs.

### 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 from the fork's first version and
   those heads alone, with the swarm's Automerge version: its writer from the fork's
   name, time 0, no message, nothing of a remake's metadata but what the heads fix; so
   one version and one set of heads make one swarm, and a node with an empty document
   takes it on its peers' word, as it takes an epoch. It holds all of it but for what a
   snapshot leaves out, by the version current at those heads (Remakes), the
   federation's versions, and continuum's own data (member entries, remake records and
   acks, earlier epochs' metadata, the swarm's name): of versions, only the group's own,
   the fork's first, with the key sets and node lists it sets. It names the highest
   version at those heads as the one it changes, is numbered one past it, and sets the
   node lists of the parties that start it, and the keys of any party it names anew;
   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 takes it only where it holds the heads' history, syncing
   what it lacks from the old swarm, each change judged there; otherwise it says it
   can't check, and leaves it to its operator. It checks the new one against the old
   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.

What a party's nodes do of themselves is their operators' business, written nowhere:
join a fork their operator follows, vote as parties their operator follows 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 a 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,
holds the federated policy, the swarm's name and the first version, with the key sets
and node lists it sets, and nothing else; among those lists, one naming a node of its
founders', so the federation starts with members, and other nodes come in as their
parties list them. It is built byte for byte from the first version alone, as a fork's
genesis is from its version and heads (Forks): its writer from the swarm's name, time 0,
no message; and the swarm is named by the first version's hash, so one first version
makes one swarm, and a node joining builds the genesis change and checks it. A swarm
strict from its start records its policy in its genesis change too
(`--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. A federated swarm takes compaction only, whose
snapshot is a function of its base. What a federated node asks of a remake:

* **It builds it itself.** A node that holds an epoch leaves it only for one whose
  snapshot it built itself, as continuum's node builds a compaction's and checks it
  against the committed epoch *(checked: `remake::switch`)*, from a base it holds, where
  it is a member (its party lists it there) and the version it reads is written, as it
  reads it when it switches: a version it takes while it builds leaves it where it is,
  as one taken before. Never on its peers' word, however it hears of the new epoch: a
  node that lacks some of the base (it was away) syncs it from peers that keep the old
  epoch, each change judged there, and builds then; where it can't build it, it stays
  where it is, says so, and never rejoins an epoch it refused. A remake's decision is
  its coordinator's alone, and so is its abort: whether one expired is no node's to say,
  and one its coordinator leaves undecided binds nobody. How long a node keeps the old
  document is its own setting, not the remake's, and while it keeps it, it syncs it with
  nodes still on that epoch.
* **Two decisions for one epoch** come from a coordinator that wrote two, or from
  remakes decided at once. A node that holds both follows neither, says so, and leaves
  it to its operator. On its operator's word, a node builds the remake named of the
  epoch before its own, from the old document it keeps, as it builds any, and switches,
  what it wrote since replayed: so nodes that followed different decisions come
  together where their operators choose.
* **The snapshot** holds what the old document read as at the base, but for what counts
  no more by the version current there and is or names a version before it, a party's
  `null` naming a version before it, and the member entry of a node its party doesn't
  list there: nothing naming an earlier version can be written in the new epoch, an
  empty place reads as one holding `null` does, and a node listed again registers
  again.
* **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`)*. No version is among them: a node that took one written after the
  base doesn't switch, so what it replays names the version current at the base, or one
  before. Votes and proposals go by the keys their version names, which the snapshot
  holds, 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 is tried again once the rest is replayed, as the
  clocks may have put it before what it builds on (a vote committed again at another
  history, before the nays that freed its party); what it refuses then (its key was
  dropped, 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.

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, a write after it on what the snapshot left out, or an envelope
written after it at a history where a version before the base's was current (its node
lagged), 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. A remake does end one
thing: nothing is written at a history from before its base, so what a node taken off
its list could still commit there ends with it.

A remake that races a version or a listing leaves the nodes that took it where they
are, apart from those that switched, until their operators move them or a fork. A node
with an empty document can't check: it takes the epoch its peers give it, or the one
its operator pins.

### Where Automerge sets limits

* **Bytes.** The nodes of a federated swarm run one Automerge version, which its
  federation's number names (Changing the federation): a rule, as 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 are recommendations: none breaks a promise, only how fast a node is, or how
long nodes 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 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`)*. No remake brings the two sides together, as neither
  builds from a base holding what it refused; a fork at heads both hold does.
* **History.** The document keeps every operation, which only remakes bound.

## 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, among the envelopes their party's keys signed, by version number, then `seq`.
   None of it depends on the order of operations, and no key is both a value and the way
   to places. 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, two thirds of the
   parties of the version it changes voted `true` for it, and a node takes it only
   where it changes the version the node reads. 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, and two proposals on one version pass only
   where some party backed both while neither was dead. Without keys voting twice, at
   most one version changes a version, and every node takes it; keys an earlier version
   named move no node that took the version after it. With them, each node keeps the
   version it took, nodes holding the same changes still read the same policy, and the
   parties fork.
3. **Remakes.** A node follows a remake only where it built the snapshot itself, from a
   base it holds, a member there, the version it reads written there; its peers' word
   never moves it. What came after, under that version, is replayed in history's order,
   each change judged as every node judges it: votes and proposals by the keys their
   version names; 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, its members those its lists name, 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 key set signed by a key the version doesn't name, or by one a later version replaced, at a history from before | Refused; or behind the set the later version set | unit |
| 7 | A key set without the key that signed it | Counts: a set is checked where it is written | unit |
| 8 | A version written without the votes, or not changing the current one at its history | Refused at its history | unit |
| 9 | A version not in its JCS bytes, a field missing or more, a rule under `_continuum`, without a literal first segment, with `@`, `**` not last, `{party}` twice, or a writer that is no party of it | No version: can't pass, refused where written as one | unit |
| 10 | A proposal naming a federation, or saying what, a node doesn't know | Taken as a proposal; asked where it is written as a version | unit |
| 11 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit |
| 12 | `true` on two proposals at once, from two nodes | Both taken; two versions changing one may be written; each node keeps the one it took and refuses the other; reported; the parties fork | unit, every order |
| 13 | `true` and `false` on one proposal at once | Both held; a node that saw only one may write a version. As 12 | unit, every order |
| 14 | A vote changed or deleted | Refused | unit |
| 15 | A vote cast at a history from before, on a proposal made since | Refused: its proposal isn't written there | unit |
| 16 | A party's vote committed again at another history | One vote; voting twice only where no copy of either was taken where the other's proposal was dead | unit |
| 17 | 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 |
| 18 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit |
| 19 | The parties beyond two thirds never vote, or vote `false` on everything | Nothing passes; the others fork | sim |
| 20 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit |
| 21 | The keys an earlier version named, for two thirds of its parties, pass another proposal on it at a history from before, and raise its number | Refused by every node that took the version after it, and reported; a node that lagged may take it: keys voted twice | unit |
| 22 | Two versions changing the one a node reads, coming together | It takes the first it judges, and refuses the other | unit |
| 23 | Values signed with a key a party's set holds, stolen | Count until the party drops the key | unit |
| 24 | A key a version names, stolen, votes, or writes its party's set or list | Counts while that version is current; the party's own vote beside it is voting twice, answered by a fork | unit |
| 25 | A write in another party's namespace, or at an identifier of another's | Refused by the rule | unit |
| 26 | A deletion of a value of another party, or of what counts no more | Refused: only a party's `null`, at its own place | unit |
| 27 | An envelope outside an `@` key, a map in one, or a map on the way to one deleted or replaced | Refused | unit |
| 28 | An envelope and a map at one key, written at once | None: envelopes go only in `@` keys, which hold no maps | unit |
| 29 | A remake whose snapshot isn't the one a node builds, whose base it lacks, or where it isn't a member | It stays, and never rejoins it | sim |
| 30 | A coordinator records an old base, before the version nodes read | They stay | sim |
| 31 | Two members advertise an epoch ahead, or offer a rejoin | Not taken: a node leaves its epoch only for one it built | sim |
| 32 | A remake's decision or abort written by a node not its coordinator | Refused | unit |
| 33 | Two envelopes at one place beyond a remake's base | The chain to the one read is replayed | unit |
| 34 | A version taken while a node builds a remake's snapshot | It stays, as with one taken before | sim |
| 35 | 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 |
| 36 | A write after a base on what the snapshot left out, or naming a version before the base's | Quarantined; its party writes again | unit |
| 37 | A node with an empty document handed a made-up epoch | Taken. Not promised | sim |
| 38 | A coordinator remakes often, or a party never acks | Slow, not wrong; the others fork | sim |
| 39 | A writer forked: two changes, one number | Honest nodes split until a fork. Not promised | sim |
| 40 | Different changes to different peers | Honest nodes agree once they sync | sim |
| 41 | A party withholding its changes or votes | Not promised | — |
| 42 | Flooding: namespace, proposals, history, writers | Slow, not wrong | bench |
| 43 | 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 |
| 44 | A token from another party's node | Refused: a node's party is its configuration's | unit |
| 45 | A party lists another party's nodes, or one its party dropped | Nothing changes: a node is its own party's | unit |
| 46 | A party lists many nodes, to be every node's neighbours | Each node keeps some among its own party's and those its operator names | sim |
| 47 | A party's node writing another node's member entry | Refused: an entry is its member's | unit |
| 48 | A party's node writing under `_continuum` where the list doesn't say | Refused: closed | unit |
| 49 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit |
| 50 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join, and say what differs | sim |
| 51 | A fork at heads of its founder's choosing | Joiners holding the document are told what those heads lack | sim |
| 52 | 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 |
| 53 | Two founders forking one version at one set of heads | One swarm: the genesis change is built byte for byte | sim |
| 54 | A group whose parties list no nodes forks | Its version sets their node lists | sim |
| 55 | A federation, or a policy, a node doesn't know | It stops taking changes | unit |
| 56 | 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 |
| 57 | Content written before a federation's genesis change, and a change built on it | None: the genesis change is the swarm's first | unit |
| 58 | A federation's genesis change whose first version lists no node | Nothing after it is taken: no node is a member | unit |
| 59 | A version replacing every listed party's keys | The lists still count, each its party's until it writes another | unit |
| 60 | A version written without the key sets or node lists it sets, or those written by another change, or numbered otherwise | Refused | unit |
| 61 | A version written again late, at a history from before the next, by a member that was away | Taken: it is one every node took | unit |
| 62 | A proposal whose text doesn't hash to its place | Refused | unit |
| 63 | An honest member writes a version valid where it is written, on the side a node doesn't read | Refused, and reported apart; its committer isn't refused as a whole | unit |
| 64 | Nodes reinstalled under new IDs, their old entries left behind | Each counts no more, and the next snapshot leaves it out | unit |
| 65 | A fork at heads holding a change sent to nobody (a version written without votes, say) | A node holding the old document takes the fork only where it holds the heads' history, each change judged | sim |
| 66 | 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; it stays where none keeps it | sim |
| 67 | A key its party dropped writes, from a history before the drop, ahead of what the party signed | Counts no more, and takes out nothing the party signed again after the drop | unit |
| 68 | 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 |
| 69 | A party's `true` and `false` on one proposal, both in a history | Both count there: a history holding more votes takes back no pass and no death | unit |
| 70 | A path whose `{party}` segment names no party (`names/r/foo`) | The `{party}` rule doesn't match; a later rule decides | unit |
| 71 | A map made where no `@` key is written below it, or where one is (hiding what it holds) | Refused | unit |
| 72 | A party's first envelope at a place another's envelope holds | Names that one as `prev`, its `seq` one more; anew, refused | unit |
| 73 | A federation's genesis change holding more than its first version gives (values, votes, a topology) | A node joining builds it and doesn't join one that differs | sim |
| 74 | Two federations started under one swarm name | None: a federation is named by its first version's hash | unit |
| 75 | A version, set, list, path or value larger than the federation allows | Refused; none can be too large for a sync message | unit |
| 76 | Two thirds back a proposal that is no version | It can't be written, nor die; the federation is bound to its version. A node shows that it is none, and clients don't back it | unit |
| 77 | A party's vote committed again at a history before the nays that freed it, its clock set between, then a remake | The replay refuses it at first, and takes it once the rest is in | 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.
* **Every node moving to one of two versions changing one**, the lower hash, say.
  Whoever holds the keys an earlier version named, for two thirds of its parties, could
  put another policy on every node at any time, raising its number alone, and grind
  its hash. A node keeps the version it took, and the parties fork.
* **The longest chain from the first version.** It needs every version kept, and old
  keys could still grow a chain longer than the one nodes took.
* **A share each federation sets.** Two thirds is the federation's number's: another
  share is another federation (Changing the federation).
* **Becoming federated in a running swarm.** It needs the time before closed, which
  continuum doesn't do for a swarm turned strict either, 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.
* **Housekeeping within an epoch**: members deleting what counts no more. Automerge
  keeps every operation, so it shrinks nothing; and a place it empties reads whatever
  its party once signed there and anyone puts back. A remake's snapshot and a fork's
  genesis leave it out.
* **Versions replayed across a remake**, so that a node that took one written after the
  base follows too. It needs versions, their votes and what names each replayed in an
  order of their own, and two `true`s cast at once, replayed one after the other, can
  undo a version that passed. A remake racing a version is rare; the nodes that took it
  stay.
* **Remakes of other kinds** (`replace`, `import`, `strict`), followed where the new
  document reads as the old one did. A snapshot judged by none could swap an envelope
  for one naming a later version, and a node would take it on its peers' word wherever
  it can't read the old one. A compaction's snapshot every node builds itself.
* **Rules of a fixed depth**, without `**`, so that the rules alone say whether a key is
  a place or the way to places. A party's namespace would be flat; values in `@` keys do
  the same with `**`.
* **A place where a party says which fork it went to.** A node following it by itself
  would follow a stolen key into a swarm with any policy; parties say where they went as
  they like.
* **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 from the first federated swarm on,
continuum's releases work together in one, and 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, the sizes each may have, which version a node takes and which is
current, the remake's snapshot, its replay and its order, and the Automerge version,
whose encoding fixes a change's hash.

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:

* the krebs users who will vote are its parties, each its hosts in its namespace
  (`home/tv/hosts/laptop`: its keys, its addresses as it uses them). The others are in
  a party that is a group, which holds its keys as it likes, their hosts in its
  namespace, until a version makes one a party of its own. Every decision takes two
  thirds of all parties, quiet ones counted, so the first version names only those
  that will vote;
* a party's names `names/r/tv` and those under it by a rule each, and so for
  `names/w`; 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, with the
   key sets and node lists its first version sets; versions and what makes one valid,
   rules and paths, values in `@` keys, keys, votes, passing and dead, which version a
   node takes and the current one, judging by it; votes and proposals by their version's
   keys; the protocol data as listed, all else closed; the `cv3.` envelope with the
   meta's version, and the order by it; node lists, a node's party in its configuration,
   and tokens from one's own party's nodes only; what every reading of a strict policy
   in continuum (`strict()`) makes of the federated one; screening's frontier moved by
   every change touching what the federation reads (versions, proposals, votes, key
   sets, node lists), as `access::screen` moves it today for what continuum's rules
   read; the byte formats (a version's JCS bytes, hashes in paths and how two compare,
   the envelopes a version sets, the meta's version), and the sizes a version, a set, a
   list, a path and a value may have, each within what a sync message carries. 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.
   Reports of a party that voted twice, and of versions a node refused.
3. **Nodes**: membership by the node lists and the party a node's own entry names, the
   party shown in the handshake before that entry exists, a node syncing with members
   only (a wire change), neighbours by party.
4. **Remakes**: compaction only, each node building it from a base it holds, never on
   its peers' word; the old epoch synced, while a node keeps it, with nodes still on it;
   replay under the version current at the base.
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. A federated swarm made before the last
stage is for tests: a later stage judges it otherwise. Until stage 5, a writer forked
splits the nodes for good.