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
|
# 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
holds every event back to the federation's first, and checks all of it itself.
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. 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 the store stays small: it keeps every event, and a fork its whole history.
## The design
It builds on the store ([`store.md`](store.md)): a set of events that only grows, 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. 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.
* **Forks**: a store whose root builds on another's events, carrying their history.
* **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 events no party signs, as their bytes need no signer, each without `party`, `key`
and `sig`: a federation's root (Starting a federation), a fork's (Forks), and a version
(Changing the policy).
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, 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.
* **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 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, 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 reports it, as they
are signed and anyone can check them; 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.
* **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. A place
given back to its party, or a key added back, shows what the party signed before where
nothing replaced it since, 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.
### 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, which no party signs: the heads it forks at
as its `deps`, and the fork's version as its `fork`, so that one version and one set
of heads make one fork. 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.
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 carries every event of its root's history,
each counting there as it did, and after them 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, and judge every event of it,
back to the federation's first, whether or not they hold the federation it came from.
A node that holds 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 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 store of its own: its root, `{"genesis": <version>}`, holds
the first version and nothing else, and no party signs it, 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 the events a node
holds: 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.
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, carrying its
history so that anyone checks it, 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 builds on an event no node takes (a version written without votes, say), sent to nobody before | No fork: every event of its history is judged, and one refused takes the root with it | unit |
| 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 holding more than its first version, 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 |
## 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.
* **Events that count no more left out**, by the store or by a fork. Every node checks
every event back to the federation's first, a fork's joiners too; one that left some
out would take the rest on someone's word.
* **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 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; 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, 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; 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; 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, and a tool reporting, from the votes, a party that voted twice.
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 started from another's events, named by its root, every event of
its history judged.
5. **Remakes**: compaction only, the snapshot holding the events 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.
|