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
|
# 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 each
version of its policy: this design is federation 1 (Changing the federation). Any group
carries on with the policy it wants by forking (Forks), and leaves the federation by
starting a swarm of another kind, with what it takes along.
## 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 event, with any dependencies, and any change, under any writer;
* send different events and 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 byte strings with one SHA-256.
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 refuses an event the version current at its history
doesn't let be written, whoever brings it, and reads nothing else as counting. A node
checks every event back to its checkpoint, which it built itself or its operator
pinned ([`store.md`](store.md)).
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 events 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; groups that parted come together the same way.
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, or up. A party that floods the store, or whose nodes start
writers without end or keep remakes from committing ([`store.md`](store.md)), makes
nodes slow, or runs them out of memory, 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, until its operator has it drop it, and one that had
taken neither of two (it lagged behind, or joins) may be shown either first;
* that what isn't above a checkpoint's heads is taken once nodes moved to it: its party
signs it again (Checkpoints);
* that a checkpoint, or a fork's root, that a node takes on its operator's word is the
one the others built ([`store.md`](store.md), Pinned checkpoints).
## The design
It builds on the store ([`store.md`](store.md)): events, each named by the SHA-256 of
its bytes, its **ID**, and naming the events it builds on, its **dependencies**; judged
at that history, every node alike; and read together as one state, from a checkpoint and
the events after it. The federation is the store's fold: what its events are, how one is
judged, and what they read as. What carries the store, a swarm's Automerge document with
its changes and its remakes, the federation never sees.
What it asks of the store:
* **An event's history**, which its ID fixes: what its signer had seen. An event is
judged at its history and nothing else.
* **The state of a set of events**: the same on every node for the same set, whatever
order they came in.
* **A node's own**: a node refusing what its history takes, by what the node took
before, and an operator having its node drop what it took.
* **Checkpoints**: the store starting anew from what counts at heads the parties name,
forgetting the rest.
* **Forks**: a store whose root is a checkpoint at another's heads.
* **Members**: the nodes that carry the store, which the federation names.
### Events
An event is the JCS encoding (RFC 8785) of a JSON object, its bytes those of the JSON
they read as, so that nothing in it is spelled two ways and no key is there twice.
Spread out:
```json
{ "deps": ["<ID>", "<ID>"],
"party": "tv", "key": "ssh-ed25519 AAAA…",
"write": { "path": "names/r/tv/toaster", "value": "10.243.7.3" },
"sig": "<signature>" }
```
* **`deps`**: the IDs of its dependencies, as 64 lower-case hex digits, one at least,
ascending, none twice; a client gives the heads it read.
* **`party`** and **`key`**: the party that signs it, and the key it signs with, an
`ssh-ed25519` key without its comment.
* **What it does**, one of: `write`, a value at a place (The policy); `keys`, the
party's key set (Keys); `nodes`, its node list (Nodes); `proposal` and `vote`
(Changing the policy).
* **`sig`**: an SSH signature by `key` (`ssh-keygen -Y sign`, namespace
`continuum-federation`) over the event's bytes without `sig`, unarmored, in base64.
Three things no party signs, as their bytes need no signer, each without `party`, `key`
and `sig`: a version event (Changing the policy), and a federation's root and a fork's,
which are checkpoints (Checkpoints).
An event is none if its bytes aren't the JCS encoding of the JSON they read as, if a
field is missing or more, or if it is larger than the federation allows, which is within
what a sync message carries. It names no swarm, no version and no ID of its own: its
history says the first two. An event signed in a federation, or in a fork once it
forked, has that store's root in its history, and no other store takes it
([`store.md`](store.md), Forks). An event is **written under** the version current at
its history (Changing the policy).
### The policy
What the policy says is in its **versions**, a chain: each is a JSON object, named by
the SHA-256 of its JCS bytes, numbered, and naming the version it changes (`null` for
the first, number 0, which only the federation's root holds; a fork's changes the one
current at its heads, and a merge's lists those current at its heads, Forks). Spread
out:
```json
{ "federation": 1, "number": 7, "changes": "<hash of the version it changes>",
"keys": { "tv": { "since": 0, "keys": ["ssh-ed25519 AAAA… tv"] },
"lass": { "since": 4, "keys": ["ssh-ed25519 AAAA… lass"] },
"makefu": { "since": 7, "keys": ["ssh-ed25519 AAAA… makefu"] } },
"nodes": { "tv": { "since": 0, "nodes": ["<node ID>"] },
"lass": { "since": 4, "nodes": [] },
"makefu": { "since": 7, "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 (of the highest, for a merge's).
* **The parties and their keys** (`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). Its `since` is the number of the version that
named them anew: this one's where it does (a party new in it, keys the parties
replace, or the same keys named anew), else the `since` the version it changes gives
the party, whose keys it then names unchanged.
* **The node lists** (`nodes`): every party's, a list of node IDs with its `since` as
keys have one. The version that lets a party in names its list anew, empty where it
gives it no nodes, so that a list it wrote before it was taken out counts no more; a
later version may name it anew again; the first version and a fork's name those of the
parties that start it (Nodes).
* **The checkpoint** (`checkpoint`), where the version names one: the heads at which the
store moves to a checkpoint once the version is current (Checkpoints).
* **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). 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. A party writes there by a `write` event,
`{"path": …, "value": …}`: any JSON value, `null` emptying the place. Its value is the
latest its party signed there that counts (What counts). A place is a path, not a key in
a tree: a version may give a place and places below it alike, and nothing is both a
value and the way to others. 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 a field is missing or more (but for `checkpoint`, which it may
leave out), or if it breaks any of the above. It can't pass, and a version event naming
it is refused. A proposal is taken whatever it holds: whether it is a version is asked
where a version event names it, 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).
What the swarm's document holds beyond the events, and what a node takes at its API, is
the store's ([`store.md`](store.md), On Automerge).
### Changing the policy
A **proposal** is a version a party proposes, by a `proposal` event, the version itself,
signed with one of the keys the version it is written under names for its party: the
proposal is **on** that version, and its hash is the version's. It counts as signed by
those keys, whatever keys the party writes since, until it lapses.
A party **votes** on a proposal by a `vote` event,
`{"on": <hash>, "proposal": <hash>, "yes": true}` or `"yes": false`: the version the
proposal is on, and the proposal, by their hashes.
* **A vote is taken only where, at its history, the version it is on is current and its
proposal is proposed on it.** A vote cast at a history from before can't reach a
proposal made since.
* **A vote 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, and nothing takes it back. 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, 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, by a **version** event, `{"deps": […], "version": <hash>}`, which no party
signs: any node may write it, and the same version written by several is one (below).
Every node judges it at its history: the proposal proposed there on the version current
there, passed there, and a version changing that one. A version takes effect where it is
written: it is current at every history that holds it and no version after it.
**A node takes a version only where it changes the version the node reads**, or is one
it took, written again. A version event of any other, valid at its history or not, it
refuses, with everything built on it, reports, and leaves to its operator
([`store.md`](store.md), A node's own); another node's refusal doesn't make it drop what
it took. One valid at its history breaks no rule: the node reports it apart from events
against the rules, and holds nothing against the node that put it. 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, or is one it took, and none is refused.
**An operator may have its node drop what it took**: a version the others refused, or
any event, with everything built on it ([`store.md`](store.md), A node's own), and then
take what the others hold. No peer's word moves a node; its operator's does. The node
refuses what it dropped, from whoever brings it, and any version event naming a version
among it, whoever wrote it anew, and writes none itself, though it holds the votes that
passed it, until its operator says otherwise. So either side of keys that voted twice
may join the other without what parts them, and without a fork.
**The current version** is the written version with the highest number: the end of the
chain the node took.
* **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 events 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** in the votes alone, both signed with keys their
version names for it: its `true` and `false` on one proposal, or its `true` on two
proposals of one version where neither is dead by all the votes cast. Where in history
a vote is, and how often it was signed, changes none of it: a party's votes of one
value on one proposal are one vote. An honest party backs another proposal only once
the first is dead, and a death is never taken back. Two versions changing one still
name a party: where one of the proposals is passed and dead by all the votes, the
party whose `true` and `false` made it so. A tool over the votes the parties' clients
keep reports it, as they are signed and anyone can check them, after a checkpoint left
them out too; a node reports the versions it refused. 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 the keys of its **key
set**: a `keys` event, the list of its keys, signed with a key the version it is written
under names for the party. A set is checked only where it is written, never by the keys
of a set (What counts, 2).
A party's keys are those of its set (What counts, 5) where the set is written under a
version numbered at least the `since` its version gives the party's keys; otherwise, and
while it has written none, those its version names. So once a version names a party's
keys anew, no set written under an earlier version counts, and the party's next set
does. Nothing is written for it: the version says it.
* **A value counts only while the key that signed it is among its party's keys**, as
above: 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 beside
the old, signs again with a new one, at a history holding that set, what should stay,
and writes a set without the old ones (a client does it all). What a key it dropped
signed counts no more, wherever in history it is, and replaces nothing the party
signed. A key added back, from a backup say, brings back what it signed, where nothing
the party signed since replaced it and no checkpoint since left it out.
* **Only a version revokes a key it names.** One lost or stolen is answered by a version
naming the party's keys anew: no set written under an earlier version counts any more.
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
An event is judged at its history, by the version current there, as every node judges it
([`store.md`](store.md)). 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 store as a whole. These count no more, and nothing
else does:
1. a write 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 write signed by a key that isn't among its party's; and a key set or node list
written under a version before the `since` its version gives it (Keys);
3. a proposal on a version that isn't current, and the votes on that version;
4. a version behind the current one;
5. of the writes at a place that 1 and 2 leave, one another of them has in its history,
and of those left, all but the one with the lowest ID; and so of a party's key sets,
and of its node lists.
So a place's value, a party's set and its list are each the latest its party signed that
counts: what the party signed after replaces what it signed before, whatever order the
events came in, and what counts no more replaces nothing. Nothing is deleted: a party
empties its place by writing `null`, and what counts no more stays in the store until a
checkpoint leaves it out (Checkpoints). A place given back to its party, or a key added
back, shows what the party signed before where nothing replaced it since and no
checkpoint left it out, until the party writes there again. Two writes of one party at
one place, neither in the other's history (two of its clients at once), leave the one
with the lower ID; the party writes again, after both, to choose.
### Checkpoints
A **checkpoint** writes down what counts at some heads: those heads, a version (the one
current there, or a fork's), and the IDs of the events that count there with that
version current (What counts; a merge's root keeps otherwise, Forks), as the JCS
encoding of `{"at": [<IDs>], "keeps": [<IDs>], "version": <version>}`, its IDs
ascending, named by its SHA-256 ([`store.md`](store.md), Checkpoints). Every node
holding the history up to those heads builds the same one, and its version counts as
written.
A version names a checkpoint by its heads (`checkpoint`). It is a version only where its
proposal is above those heads, and a vote on it, or a version event writing it, is taken
only where it is above them too ([`store.md`](store.md), Events): so moving to the
checkpoint refuses nothing that decided it. A node that takes the version moves to the
checkpoint: it builds it, forgets everything before those heads that it doesn't keep,
and every event not above them, and refuses such events from then on. Judging an event
after them needs nothing it forgot: the version, every party's keys and node list, and
the proposals on the current version with their votes all count, and are kept. A node
that can't build a checkpoint, as it was away longer than its peers kept what they
forgot, or as it joins, takes it only where its operator pins it
([`store.md`](store.md), Pinned checkpoints).
What a checkpoint loses: what counted no more before it, so that a key added back, or a
place given back, brings back nothing signed before it, and a party that voted twice on
a version behind it shows only in the votes its clients kept; and what isn't above its
heads, which its party signs again. That is rare: the heads are in the proposal's
history, nodes build on them while the vote takes its course, and a client writing once
a checkpoint is proposed builds only on what is above its heads.
A version that changes nothing but its number, what it changes and its checkpoint only
moves the store on. Like any version, it lapses the proposals on the version before, so
a party proposes one where nothing else is proposed on the current version. A
federation's root is its first checkpoint, without heads (Starting a federation), and a
fork's root a checkpoint at the heads it forks at, of one store or of several (Forks).
### Votes a node casts by itself
A party may have one of its nodes vote and propose for it, by rules its operator sets:
the rules are written nowhere in the swarm, and every node judges what such a node signs
as it judges any vote or proposal. The design has two in mind:
* **Following**: back a proposal where a party the rule names proposed or backed it, and
vote `false` where that party did. By default the rule follows only versions that only
move to a checkpoint (Checkpoints); its operator may have it follow on any version,
which hands that party the node's vote.
* **Proposing a checkpoint**: propose a version that only moves to a checkpoint, at
heads the node holds, once conditions its operator sets are met: so many events or
bytes held beyond its checkpoint, so many versions since it, or so long by its own
clock, by which nothing anyone judges goes. It proposes only where nothing else is
proposed on the current version, as such a version lapses what is.
Such a node keeps to what a party's client keeps to: one yes at a time; never `true` and
`false` on one proposal, so a party has one node vote by itself, as two of its nodes
each voting by itself can vote twice; none for a proposal that is no version; and, by a
rule for checkpoints, none for a version that changes more than its number, what it
changes and its checkpoint, which it checks against the current one. Where two
checkpoints are proposed at once, the votes split, as any do; a rule may vote `false` on
the one it doesn't back, so that one dies and its backers are free.
It signs with a key the party's version names, which the party keeps on that node, not
apart: one stolen there votes, and writes the party's key set and node list, as the
party's, until a version names its keys anew (Keys). A party that won't keep one there
votes by hand.
### Nodes
A party lists the nodes that carry for it, by node ID, in its **node list**: a `nodes`
event, the list of its nodes' IDs, signed with a key the version it is written under
names for the party. A party's list is that one (What counts, 5) where it is written
under a version numbered at least the `since` its version gives the party's list,
otherwise the list its version gives, if any, as with keys (Keys). The store's members
are the nodes each party's list names, each as its party's ([`store.md`](store.md),
Members); another party's list does nothing for a node. A party's list counts until the
party writes another or a version names one anew, 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 puts whatever events it is given, its party's and
others' alike: what counts is who signed an event, not which node put it. So a party
without nodes of its own writes through any node that takes its events.
### Forks
Any group can carry on without the rest: too many parties are away for good, a version
the group won't follow passed, or the parties can't agree. It **forks**: it starts a
store of its own from the federation's ([`store.md`](store.md), Forks).
1. One of the group makes the fork's root, a checkpoint at the heads it forks at, which
no party signs, so that one version and one set of heads make one fork (Checkpoints).
Its version changes the version current at those heads, is numbered one past it,
names anew the node lists of the parties that start it, and the keys of any party
whose keys it changes; a root whose version doesn't is no fork. It keeps the events
that count at those heads with that version current. Every proposal is a chance to
fork: the version is usually one that didn't pass.
2. A fork is named by its root's ID, which nobody can steer to a given name, the
federation it came from least of all. It takes only events with its root in their
history: what the stayers sign after it isn't taken there, nor what the fork's
parties sign after it in the federation they left.
3. The others join it as a node joins any swarm, by its ID. A node holding the history
up to those heads builds the root and checks it, says what it holds that those heads
lack, and, 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 node that doesn't hold
that history takes the root on its operator's word, as its operator names the fork.
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.
Groups that parted come together the same way: a fork at heads of several stores
**merges** them, the federation and a fork of it, say, or two forks
([`store.md`](store.md), Forks). Its root differs from a fork's in three things:
* its version's `changes` lists the versions current at those heads, ascending, and its
number is one past the highest of them;
* its version names every party's keys and node list anew, so that no key set or node
list of any side counts in the merge: it may give a party the keys it had on the
sides, or others, and each party writes its set anew;
* it keeps, of each side, the values that count there at places its version gives their
party, and nothing else. One counts in the merge once the key that signed it is among
its party's keys there (Keys), so that what a key one side dropped signed counts only
where the party lists that key again.
Where a party wrote one place on two sides, the lower ID counts until it writes there
again; where the sides gave an identifier to different parties, the merge's rules say
whose values count. What a side writes after those heads isn't taken in the merge, and
its party signs it again. A node holding the history up to all those heads builds the
root and checks it; one holding some of it says, side by side, what it holds that those
heads lack, and party by party what keys the merge gives; one holding none takes the
root on its operator's word.
What a party's nodes do of themselves is their operators' business, written nowhere:
join a fork their operator follows, vote by rules their operator set (Votes a node casts
by itself), 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 store of its own: its root, a checkpoint without heads that
keeps nothing, its version the first, which no party signs (Checkpoints), so one first
version makes one federation, named by the root's ID. Among the node lists the version
gives, one names a node of its founders', so the federation starts with members, and
other nodes come in as their parties list them. Its swarm's genesis change holds the
root, built byte for byte from it ([`store.md`](store.md), On Automerge). So nothing is
from before the federation: it changes by versions, and any group carries on by a fork.
A running swarm doesn't become federated; its parties start one, and sign into it what
they keep.
## Why it holds
1. **What counts.** An event is judged at its history, which its ID fixes, by the
version current there, which the version events in that history fix, each judged by
the votes in its own. Every node judges alike, and refuses the event and everything
built on it ([`store.md`](store.md)). What counts is read from what a node holds, its
checkpoint and the events after it: the current version, the highest number; each
party's keys, by that version and its set; each place's value, the latest its party
signed that counts. None of it depends on the order the events came in, nor on what
carried them, and what counts no more replaces nothing. An event brought again is the
same event; one written at a history from before a version is judged by the version
current there. A checkpoint keeps what judging reads, so moving to one changes no
verdict.
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, or is one it took. 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, or some
party's `true` and `false` on one of them are both there. Without keys voting twice,
at most one version changes a version, and every node takes it, however often it is
written; 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 events still
read the same policy, and the parties fork.
3. **Carrying on.** A fork is a store of its own, named by its root, which nodes holding
its heads' history check and others take on their operator's word, 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; what it does to the store, its document and its
remakes, is the store's ([`store.md`](store.md), Attacks). *Unit*: the fold, with
crafted events. *Sim*: a simulation. *Bench*: measured, not judged.
| # | Attack | What happens | Test |
|---|---|---|---|
| 1 | An event signed by a key that isn't its party's, or by no party where one must sign | Refused at its history | unit |
| 2 | An event not in its JCS bytes, a field missing or more, or larger than the federation allows | None: refused | unit |
| 3 | An event of another federation, or of a fork once it forked, brought in | Never taken: its history lacks the root | unit |
| 4 | An old write brought again | The same event: nothing changes | unit |
| 5 | A former holder writes at a history where it held the place | Taken there; counts no more: the current version gives the place to another | 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, written under a version before the one that named the party's keys anew, it counts no more | unit |
| 7 | A key set without the key that signed it | Counts: a set is checked where it is written | unit |
| 8 | A version event without the votes, or for a proposal not on the version current at its history | Refused at its history | unit |
| 9 | A version with 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; a version event naming it is refused | unit |
| 10 | A proposal naming a federation, or saying what, a node doesn't know | Taken as a proposal; asked where a version event names it | 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 cast at a history from before, on a proposal made since | Refused: its proposal isn't in its history | unit |
| 15 | A party's vote signed again, at another history | One vote; voting twice is read from the votes alone, not from where they are in history | unit |
| 16 | A party changes keys after voting or proposing, or beside its vote or proposal | It counts as cast, by its version's keys | unit |
| 17 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit |
| 18 | The parties beyond two thirds never vote, or vote `false` on everything | Nothing passes; the others fork | unit |
| 19 | A node of the party a version takes out writes that version | Taken: a version counts by its votes, not by who wrote it | unit |
| 20 | 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 |
| 21 | Two versions changing the one a node reads, coming together | It takes the first it judges, and refuses the other | unit |
| 22 | Values signed with a key a party's set holds, stolen | Count until the party drops the key | unit |
| 23 | 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 |
| 24 | A write in another party's namespace, at an identifier of another's, or where no rule matches, `null` included | Refused by the rule | unit |
| 25 | A key its party dropped writes, at a history from before the drop, after what the party signed | Counts no more, and replaces nothing the party signed | unit |
| 26 | Two writes of one party at one place, neither in the other's history | The lower ID is the value, until the party writes again after both | unit |
| 27 | A party taken out signs events at a history where it was one | Taken there; they count no more | unit |
| 28 | Different events to different peers | Honest nodes agree once they hold the same events, but where keys voted twice | sim |
| 29 | A party withholding its events or votes | Not promised | — |
| 30 | Flooding: places, proposals, votes | Slow, or out of memory; not wrong: the others fork | bench |
| 31 | A party lists another party's nodes, or one its party dropped | Nothing changes: a node is a member as its own party's | unit |
| 32 | Events the stayers sign after a fork, brought to the fork | Never taken: their history lacks the fork's root | unit |
| 33 | A fork whose root doesn't read as its heads do: an event kept that doesn't count there, one left out, or heads holding an event no node took | Nodes holding those heads' history build the root, find it differs, and don't join; others take it on their operator's word | sim |
| 34 | A fork whose version doesn't change the one current at its heads, or isn't numbered one past it | No fork | unit |
| 35 | A fork at heads of its founder's choosing | Joiners holding the federation are told what those heads lack | unit |
| 36 | A fork's version giving a party that didn't go keys of its founder's | Joiners holding the federation are told, party by party | unit |
| 37 | Two founders forking one version at one set of heads, or starting a federation from one first version | One store: its root is built byte for byte | unit |
| 38 | A group whose parties list no nodes forks | Its version names their node lists | unit |
| 39 | A federation, or a version, a node doesn't know | It stops taking events | unit |
| 40 | Two parties each writing a key set beside the other's vote, crossed | Nothing: votes go by their version's keys | unit |
| 41 | A federation's root with heads or events kept, or whose version lists no node | None; or nothing after it is taken, as no node is a member | unit |
| 42 | A version replacing every listed party's keys | The lists still count, each its party's until it writes another | unit |
| 43 | A version whose `since` for a party is neither its own number nor the `since` the version it changes gives the party, or that changes a party's keys or list without naming them anew | No version: a version event naming it is refused | unit |
| 44 | A version written again late, at a history from before the next, by a node that was away | Taken: it is one every node took | unit |
| 45 | An honest node writes a version valid where it is written, on the side a node doesn't read | Refused, and reported apart; nothing is held against the node that put it | unit |
| 46 | 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 |
| 47 | A path whose `{party}` segment names no party (`names/r/foo`) | The `{party}` rule doesn't match; a later rule decides | unit |
| 48 | 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 |
| 49 | Keys voting twice part honest nodes | An operator has its node drop what it took and take the other side's; no fork | sim |
| 50 | An honest party backs a second proposal once its first is dead; another party later signs `true` on the first too | It isn't named: its first proposal is dead by all the votes; the party with `true` and `false` on one is | unit |
| 51 | A node whose operator had it drop a version is sent it again, written anew by another node, or holds the votes that passed it | It refuses any event writing that version and writes it no more, until its operator says otherwise | unit |
| 52 | A party taken out and let in again | The list it wrote before counts no more: its list's `since` is the version that let it in | unit |
| 53 | A version naming checkpoint heads its proposal isn't above, or a vote on it, or a version event writing it, that isn't | No version, or refused: moving to a checkpoint refuses nothing that decided it | unit |
| 54 | An event not above a checkpoint's heads (written beside them, or built on one that was), after nodes moved to it | Refused; its party signs it again | unit |
| 55 | A checkpoint a node can't build, handed to it by peers, or a fork's root it can't check | Taken only where its operator pinned it, or named the fork | unit |
| 56 | Two versions changing one, naming different checkpoints | As 12: each node keeps the one it took, and moves to its checkpoint | unit |
| 57 | A key added back, or a place given back, after a checkpoint | Brings back nothing signed before the checkpoint that counted no more there | unit |
| 58 | A party a node follows proposes, or backs, a version that changes more than its checkpoint | A rule for checkpoints doesn't back it; one following on any version does, as its operator chose | unit |
| 59 | Two checkpoints proposed at once, by nodes voting by themselves | The votes split; nays from the nodes backing one make the other dead, and its backers are free | sim |
| 60 | Two nodes of one party, each voting by itself | They can vote twice, answered as any party voting twice: a party has one node vote by itself | — |
| 61 | A key a version names, kept on a node that votes by itself, stolen with it | As 23: it counts while that version is current | unit |
| 62 | A merge whose version doesn't name every party's keys and node list anew, or whose `changes` doesn't list the versions current at its heads | No merge | unit |
| 63 | A key one side dropped, still in the party's set on the other, then a merge | What it signed counts only where the party lists it again | unit |
| 64 | A party wrote one place on two sides, then a merge | The lower ID counts until it writes there again | unit |
| 65 | An identifier given to different parties on two sides, then a merge | The merge's rules say whose values count; the others' aren't kept | unit |
| 66 | A merge's root keeping a value that didn't count on its side, or at a place its version gives another | Nodes holding that side build the root, find it differs, and don't join; others take it on their operator's word | sim |
| 67 | Events a side writes after a merge's heads, brought to the merge | Never taken: their history lacks its root; their party signs them again | unit |
## Roads not taken
* **First come, first served, for identifiers.** Order between two parties that wrote at
once can't be read from the store 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 events look
as old as it likes. Dropping the key takes all of them back (the party drops a key of
its set, a version one it names), 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.** 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 from its own root needs
none of it.
* **Values in the document's tree**, each place's signed values in Automerge's maps,
read by the version each names and its number there. Every reading the tree allows had
to be answered (maps made on the way, values beside maps, deletions, the order of
operations), and every remake had to keep each place's value; an event is read only as
the federation reads it.
* **Numbering a place's writes**, each naming the one it replaces. A write's history
says what it replaces; numbers would be one more thing judged, and one to raise from a
history where the writer still held the place.
* **Votes counted by the keys their party's set held at their history.** A vote would be
checked against the sets around it; by the keys its version names, it is checked from
itself and its version alone, by a client too, and those keys can be kept offline.
* **Checkpoints any member makes**, as a remake's coordinator does. No vote would be
needed, but an adversary's node could make one whenever it likes, forgetting what
counts no more and making nodes that were away take one on their operator's word
again; and two at once would part the nodes until their operators chose.
* **A party's voting rules written in the swarm**, so that every node sees whom it
follows. They are its operator's, as the fork its nodes follow is; in the swarm, a
stolen key would rewrite them.
* **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.
* **Merging in place**: two stores each passing a version that moves them to one
checkpoint. It needs a version that changes two, nodes on each side taking the other
side's part on someone's word, and leaves two swarms, one of whose nodes move to the
other's anyway. A merge is a fork from both: whoever wants to carry on together
follows it.
* **Forks within one store**, each side judging by its own chain of versions. It needs
judging per chain, judging again when a node changes sides, and members per chain. A
store 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 swarm of another kind, with what
its founders take along, 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, an event and its signature, how a
path and a version are spelled and read, the sizes each may have, how an event is judged
and what the events read as, which version a node takes and which is current, what a
checkpoint keeps and how it is spelled; and of the store on Automerge
([`store.md`](store.md)), what the document holds, what a change writes, the snapshot,
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 a version, its swarm has stops taking events 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 root, never as anything before
it;
* a tool reads what counts and writes what kartei's consumers read today.
## Stages
Everything here, and the store, is built behind the `federation` feature: without it,
continuum builds and behaves as it does, and its tests pass untouched.
1. **The store**, generic and in memory, with a fold made for its tests: events,
histories, judging at a history, the state, checkpoints and moving to them, a node's
own refusals and drops, forks ([`store.md`](store.md), Tests).
2. **The federation's fold**, as pure code: events and what makes one, versions and what
makes one valid, rules and paths, places, keys, votes, passing and dead, version
events, which version a node takes and the current one, what counts, node lists and
members, checkpoints: what one keeps, and moving to one; the byte formats, and the
sizes each may have. Its tests are its rows of Attacks, each with events made for it,
and the promises checked over histories generated small enough to try every order,
and larger by seed.
3. **The store on Automerge**: a swarm started from its root, events in its document,
what a change writes, every event put again whichever change carried it, what a
checkpoint forgot read no more, a change carrying an event a move refuses dropped,
and a checkpoint its operator pins; members by the federation, a node's party in its
configuration and its own entry, shown in the handshake before that entry exists,
nodes syncing with members only (a wire change), neighbours by party, and no token
from another node; the API putting events and showing what counts; reports of the
versions a node refused, its operator having it drop what it took, a tool reporting,
from the votes, a party that voted twice; votes a node casts by itself, by its
operator's rules. Until stage 5, a federated swarm takes no remake: from stage 4 on,
one that grows too large starts afresh by a fork whose version names the same
parties, keys and rules.
4. **Forks**: a store whose root is a checkpoint at another's heads, named by its root,
checked by the nodes holding that history; merges, forks at heads of several stores.
5. **Remakes**: compaction only, the snapshot holding the store as it is at its base,
and every event beyond it put again.
6. **The registry**: the rules for krebs, the tool that signs kartei's entries in as
their parties', after the root, and the one that reads them out.
A federated swarm made before the last stage is for tests: a later stage judges it
otherwise.
|