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
|
# 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 if its genesis change says so, and which federation it follows:
this design is federation 1. Nothing else changes: a swarm started as today stays as
it is, its registry, rules, remakes and replay included. Continuum's wire version
says only whether a node can take part in a federation at all; which federation a
swarm follows is its own number (Changing the federation).
## 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.
What an adversary can do:
* run nodes, once a party lists them;
* craft any change: under any writer, with any dependencies, any operations;
* send different changes to different peers, send none, or pass on only some;
* delay or drop messages between any nodes, short of forever between honest ones;
* steal another party's key.
What it can't: forge an Ed25519 signature, or find two changes with one hash.
Out of scope: keeping anything from being read (every party reads all of it), hiding
who talks to whom, and a party's own machine taken over whole (then the adversary is
that party). The design rules nothing about what happens on a party's own nodes, only
that nothing coming from any node breaks a promise for the others.
## What is promised
1. **What counts is what a party signed, with a key it holds, where the policy lets it
write.** Every honest node refuses what no policy would let be written, whoever
sends it, and reads nothing else as counting.
2. **The policy changes only by the votes of a share of its parties**, two thirds
unless the parties decide otherwise, and nodes that hold the same changes read the
same policy. That holds as long as fewer than a third of the parties vote twice
(Changing the policy).
3. **Any group carries on as it chooses.** Its parties fork with the policy they want,
and whoever wants to follow does. Nobody is held by parties it doesn't follow.
Not promised: progress without the parties' cooperation (those who cooperate fork,
and carry on); that a party votes well; that what a party's nodes withhold reaches
anyone; that the swarm stays fast. A party that floods the document makes nodes slow,
not wrong: denial of service breaks no promise here.
## The design
It builds on the strict policy ([`access.md`](access.md), Values signed by their
users): values as envelopes their parties sign, which every node checks against who
may write there, as the document stood when they were written.
### What it asks of the document
* **A change's history**, fixed by the change's hash: what its writer had seen. A
change is judged at its history and nothing else.
* **The document at a set of changes**: the tree its writes make, the same on every
node for the same set. Where two changes wrote one place at once, one is shown, the
same on every node, and all are held. A deletion removes what its writer saw, and
nothing written at the same time.
* **Remakes that lose nothing and add nothing**: whatever continuum does to start the
document anew, a node follows it only where the new document holds what the old one
held at the base (Remakes).
Every head of an epoch commits to the epoch's root change, and that root to the epoch
before and the base it was made from, back to the genesis change *(checked:
`access::rules`, one root an epoch; `remake::snapshot`, the previous epoch and the base
heads in the snapshot)*. Continuum's document is an Automerge document, which gives
all of this and has limits worth knowing (Where Automerge sets limits).
### The policy
The genesis change writes `_continuum/access/policy` as `{"version": 2, "values":
"signed", "federation": 1}`, and the policy's first version. From then on, the policy
is a chain of **versions**, each one JSON value, named by the SHA-256 of its canonical
form, naming the version it changes (none for the first):
```json
{ "changes": "<hash of the version it changes>",
"parties": ["tv", "lass", "makefu"],
"keys": { "makefu": ["ssh-ed25519 AAAA… makefu"] },
"rules": [
{ "path": "{party}/**", "writer": "{party}" },
{ "path": "names/{party}.r", "writer": "{party}" },
{ "path": "names/{party}.w", "writer": "{party}" },
{ "path": "names/wiki.r", "writer": "lass" },
{ "path": "ip4/10.243.0.5", "writer": "tv", "value": { "type": "string" } } ],
"numbers": { "share": "2/3", "limits": { "proposals": 8, "nodes": 64 } } }
```
* **The parties**, by name.
* **The keys it sets**: those of a party new in it, or of one whose keys it replaces;
they are written when the version becomes current (Keys).
* **The rules**, in order: the first whose path matches a path says who writes there.
A path is segments separated by `/`; a segment of a rule is literal, `*` (any one
segment), `**` (any number of them, last only), or holds `{party}` (the segment with
a party's name in its place: `{party}.r` matches `tv.r`). The writer is `{party}`
(the party the path names), a party's name, `any` (every party) or `nobody`. A rule
may constrain the value (its type; for a string, its characters and length). A path
no rule matches, nobody writes.
* **The numbers**: `share`, more than a half, and the limits.
The federation's own paths are its number's, not the rules': they are what this
design says below, the same in every version.
| Where | Who writes it |
|---|---|
| `_continuum/federation/proposals/<hash>` | any party |
| `_continuum/federation/votes/<party>/<hash>` | that party |
| `_continuum/federation/current/<chain>` | any party, once a proposal passed |
| `_continuum/federation/keys/<party>/<name>` | that party; a version that becomes current |
| `_continuum/federation/nodes/<party>` | that party |
| `_continuum/federation/forks/<hash>` | any party |
| `_continuum/federation/went/<party>` | that party |
| protocol data of nodes (member entries, remakes, acks) | as in every swarm, by members |
Every value a party writes is an envelope, signed by one of its keys, replacing the
one there (its `prev`), as under the strict policy. A federated swarm has no other
registry: `_continuum/users` and the users API are closed under it, and a party logs
in to its own nodes as its operator sets up.
### Changing the policy
A **proposal** is a version not yet current, written by any party at
`_continuum/federation/proposals/<hash>`, its hash the version's. A party has at most
`limits.proposals` proposals on one version.
A party **votes** by writing, at `_continuum/federation/votes/<party>/<hash of the
version it changes>`, the hash of the proposal it votes for. A vote never changes:
a change writing there another choice than the one it saw is refused (the same
choice, signed again, is fine). Two different ones written at once are both held,
and the party then counts for neither.
A proposal on the current version **passes** once at least `share` of that version's
parties voted for it, each counting once. Then any party writes it at
`_continuum/federation/current/<chain>` (Forks: the chain is that of the genesis
version, unless the swarm forked), together with the keys it sets, in one change;
every node judges that change by the votes in its history. **The current version** at
a set of changes is the one written there, or a proposal that passed on it there and
isn't written yet.
* **Two proposals on one version both pass only if at least a third of the parties
voted for both.** Each needs two thirds, so their voters share a third; a party that
voted twice counts for neither once both votes are seen, but a node that has seen
only one counts it. Honest parties vote once: a party's votes come from one place.
With fewer than a third voting twice, there is never a choice between two, and in
whatever order a node gets the votes, it ends at the same version.
* **Nothing else needs to happen.** No remake: once the votes are there, every node
reads the new version, and judges by it every change written in sight of them.
* **What lapsed goes.** A proposal on a version that isn't current any more, and the
votes on it, may be deleted by any party. Who wrote a proposal doesn't matter once
it is written: it passes or lapses whether its author is still a party or not.
* **A split vote passes nothing.** Forty, forty and twenty on three proposals is
resolved by a new proposal enough parties agree on, or by going apart (Forks).
Everything the federation decides is a change of the policy: who the parties are,
and their keys where they lost them; who writes which identifier, which is giving
one, taking it back and giving it to another; the rules; the numbers.
### What counts
A change is judged at its history, by the version current there, as every node
judges it ([`access.md`](access.md), Changes judged on every node). So a value its
party wrote while it could still write there is taken, even where a version that
passed at the same time says otherwise. What **counts** is read by the version current
in the document as a whole:
* a value counts if the key that signed it is still its party's, and the current
version lets that party write there; where two were written at once, the one shown;
* a proposal and its votes count while the version it changes is current.
What doesn't count may be deleted by any party. That is the federation's own
housekeeping; remakes carry whatever is there.
### Keys
A party's keys are at `_continuum/federation/keys/<party>/<name>`, one line each, as
an `authorized_keys` line has it. The party adds and removes them itself, with a key
it holds; a version that becomes current writes those it sets.
* **A value counts only while the key that signed it is its party's.** So rotating a
key is: add the new one, sign again what should stay (a client does that), remove
the old one. A removed key isn't kept, and what it signed counts no more and may be
deleted.
* **A stolen key.** The party removes it at once: what the thief signed with it
stops counting, and so does what the party signed with it, until signed again. If
the thief removed the party's other keys first, or both removed each other's at
once (the party then has none), the parties give it new keys by a version. A vote
the thief cast on a version that passed stays passed.
* **Deleting a value** is writing an envelope with `null` in its place. It stays
until the key that signed the value it deleted is removed; then anyone may delete
it. Until then, whoever holds the old envelope could put it back where nothing is.
A party that deletes much rotates its keys now and then, and the deletions go.
### Nodes
A party lists the nodes that carry for it, by node ID, at
`_continuum/federation/nodes/<party>`, at most `limits.nodes`. Only a listed node is a
member: it registers, commits changes and syncs, and a node syncs with no other
(Stages). A node commits whatever envelopes it is given, its party's and others'
alike: what counts is who signed a value, not which node committed it. So a party
without nodes of its own writes through any node that takes its envelopes.
### Forks
Any group can carry on without the rest: too many parties are away for good, a
decision the group won't follow passed, or a vote is split. It **forks**: it writes,
at `_continuum/federation/forks/<hash>`, a version of its choosing on the version it
leaves, without any votes: the parties it wants to carry on with, and whatever else
it wants changed. That version begins a **chain** of its own, named by its hash, with
its own `current/<chain>`.
A node follows one chain. It judges by that chain, reads what counts by it, and syncs
only with the nodes that its chain's parties list. So both sides keep the history up
to the fork, in the same document, and go apart from there: nothing is copied, and no
remake is needed. A party a fork leaves out has no member there; to come back, the
fork's parties add it by a version, as they would anyone new. A fork may list parties
that weren't among its founders (every party it considers honest, say), so that they
can follow without asking.
### Following
Each node has a follow rule, its operator's setting: by default, the chain it is on,
until its operator chooses another. Or a list of parties to follow: the node goes to
a fork once more than half of the parties it follows went there and none went to
another, and asks its operator only when they went different ways. A party that
goes says where at `_continuum/federation/went/<party>`, on the chain it leaves,
before its nodes switch.
A party may vote the same way: once more than half of the parties it follows voted
for a proposal, and none for another on the same version. Only one of its nodes
votes, so that it never votes twice.
So a federation that cooperates can have a group that leads without being named: the
active parties the others follow. Those who follow need to act only when the parties
they follow disagree, and a party that won't cooperate is left behind by everyone who
doesn't follow it.
### Shared identifiers
Anything that isn't a party's namespace is shared: names under `.r`, IPv4 and IPv6
addresses, anything a rule names. Who writes one is what a rule says: by its own name
(`names/{party}.r`: a party writes the name that is its own), or given to one party by
a version, which takes `share`, 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/wiki.r`: where the name points); a value a former writer signed stops counting
once a version gives the place to another.
In a federation that cooperates this settles at once: a party proposes what it wants,
those who follow vote with those they follow. A group that gives an identifier to
another against the rest can't, short of `share`; with it, the rest fork with the
policy they want.
### Remakes
A remake starts the document anew, for Automerge's sake only (Where Automerge sets
limits); the federation needs none and asks for none. When to remake, and who acks,
is continuum's as in every swarm. What a federated node asks of a remake, whatever its
kind:
* **It loses nothing and adds nothing.** The new document holds every envelope and
every record of the federation that the old one held at the base, byte for byte,
and nothing else of the parties'. A node checks that before it switches, and stays
where it is otherwise.
* **Writes after the base** are replayed as the policy shapes it: every envelope beyond
the base, in the order of their `prev`, each judged again in the new epoch. One the
new epoch refuses (its key was removed, its place given to another) goes to the
quarantine of the node that holds it, and its party signs it again if it still may.
So a remake decides nothing, and a swarm that never remakes stays as correct as one
that remakes all the time; it only grows slower.
### Where Automerge sets limits
Recommendations, not rules: none of these breaks a promise, only how fast a node is.
* **Writers.** Every writer costs every node memory while the epoch lasts, in
proportion to the document's history *(measured: about 4 bytes per change)*. A node
writes under a fresh writer each time it starts, or rejoins. A federated swarm
remakes before its writers and history make that felt, and a node keeps its writer
over a clean restart where it can.
* **One change a number.** A node that commits two changes under one writer and number
splits the nodes that took one from those that took the other: a node holding one
can't take the other. Continuum refuses the second as forged, by whoever brings it
*(checked: `Signatures::forks`)*; a remake heals the split.
* **Changes it shouldn't apply.** A change is first of all one Automerge itself
writes, or it is refused before Automerge sees it, in every swarm *(checked:
`document::changes::Written`)*.
* **Values written at once.** Where two changes wrote one place at once, the one shown
is chosen by an order a writer can steer. Within a party's namespace that is the
party's own matter; votes are read with all the values a place holds.
* **History.** The document keeps all of it, which remakes bound.
* **Bytes.** Every node builds the same snapshot only with the same Automerge version:
a federated swarm moves to another one at a remake, all its nodes together.
## Why it holds
1. **What counts.** A change is judged at its history, which its hash fixes, by the
version current there, which the records and votes in that history fix. Every node
following one chain judges alike, and refuses the change and everything built on
it. What counts is read by the version current in the document as a whole and the
keys the parties hold there, the same on every such node that holds the same
changes.
2. **The policy.** A proposal passes only with `share` of the parties of the version
it changes, more than a half; a party counts once, and for neither once its two
votes are seen. Two proposals on one version both pass only if their voters share
at least 2·`share` − 1 of the parties, all of whom voted twice: a third, at two
thirds. Votes never change, so a node that holds more is only further along.
3. **Carrying on.** A fork is a version its founders write; nodes follow it by their
own rule only, and sync only with its parties' nodes. A party nobody follows
carries on alone.
## Roads not taken
* **First come, first served, for identifiers.** Order between two parties that wrote
at once can't be read from the document without trusting someone's clock or
someone's witness. Votes need neither.
* **Anything waiting on time** (final after so many days). Clocks are each node's own.
Everything here waits on votes.
* **Taking back what a stolen key signed, from history.** Telling which signatures
came after a theft needs history kept and read. Removing the key takes all of them
back, and the party signs again what was its own.
* **Forks as new documents.** A fork could start a document of its own, as a remake
does. Following a chain and syncing with its parties' nodes only does the same
within one document, and keeps remakes for Automerge alone.
* **Users below the parties.** A party's people and keys within it are its own matter:
it may hand out its keys as it likes. The federation sees parties.
## Changing the federation
Every node of a swarm runs the same version of continuum today. A federated swarm's
parties can't be made to upgrade together, so what all its nodes must agree on is
small: the hash of a change and how it is encoded (Automerge's version), and the
federation's rules, which its number names.
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
a federation its chain moved to stops taking changes and says so. Continuum's wire
version only says whether a node can take part in a federation at all.
## The registry on it
The krebs registry today: users, their hosts, the hosts' names, addresses and keys.
On a federated swarm:
* each krebs user is a party, its hosts in its namespace (`tv/hosts/laptop`: its keys,
its addresses as it uses them);
* its own names under `.r` and `.w` by the rules `names/{party}.r`, `names/{party}.w`;
other names, and the retiolum and wiregrill addresses, given by versions;
* a tool reads what counts and writes what kartei's consumers read today.
## Stages
1. **The federated policy**: versions, rules and their paths, the current version from
votes and records, judging by it. Tests: two proposals on one version with every
order of votes; a vote changed; two votes at once.
2. **Keys**: what counts by the keys held, removing a key, two removing each other's,
a version setting keys, deletions kept until their key goes.
3. **Nodes**: membership by the node lists, and a node syncing with members only, as
a swarm key does today: a wire change.
4. **Housekeeping**: deleting what lapsed or doesn't count.
5. **Remakes**: the check that a remake lost and added nothing; replay of envelopes,
each judged again.
6. **Forks and following**: chains, the follow rule, voting with the parties followed.
7. **The registry**: the rules for krebs, the tool.
Each stage keeps every swarm that isn't federated as it is, its tests passing
untouched.
|