aboutsummaryrefslogtreecommitdiffstats
path: root/docs/federation.md
blob: 37985605925387b8372a5b6060ca1ad22b5aa9cf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
# 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 aims to be simple, and promises little beyond that. 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 (The policy, below). Nothing else
changes: a swarm started as today stays as it is, its registry, rules, remakes and
replay included. The code is apart where it would cost: judging reads the federated
rules under the federated policy only. The wire's version goes up for every swarm, as
with every change to it.

## Parties and the adversary

A **party** is a name in the policy, its keys, and the nodes it lists. Every party is
a voter, and only a voter is a party: 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 is written is what the policy lets be written, as its party signed it.**
   Every honest node refuses anything else, whoever sends it.
2. **The policy changes only by the votes of two thirds of its voters**, and two nodes
   that hold the same votes have the same policy. Nobody can make a node take back a
   change of the policy it took.
3. **A remake changes nothing that counts.** It only starts the document anew, for
   Automerge's sake (Where Automerge sets limits).
4. **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 cooperation of two thirds of the voters (those who
cooperate fork, and carry on); that a party votes well; that a party whose key was
stolen keeps what the thief did before the key was replaced; that what a party's nodes
withhold reaches anyone.

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

The design reads one thing: a set of changes, each naming the changes before it by
their hashes, committed and signed by a node, and writing to paths in one tree of
maps. Of it, the design asks:

* **A change's history**, fixed by its 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, both writes held.
* **A remake** that starts the document anew from a set of changes, every node
  building the same.

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 sets limits the design works around (Where Automerge sets limits).

### The policy

The genesis change writes `_continuum/access/policy` as `{"version": 2, "values":
"signed", "federated": true}`, 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>",
  "voters": { "alice": ["ssh-ed25519 AAAA… alice"],
              "bob": ["ssh-ed25519 AAAA… bob"] },
  "kinds": { "domain": { "chars": "a-z0-9.-", "length": 253 },
             "ip4": { "chars": "0-9.", "length": 15 } },
  "holders": { "domain": { "wiki.r": "alice" }, "ip4": { "10.243.0.5": "bob" } },
  "numbers": { "share": "2/3", "remakeChanges": 10000, "remakeWriters": 1000,
               "replayWindow": 2, "limits": { "nodes": 64, "writers": 64,
               "proposals": 8, "value": 65536 } } }
```

* **The voters**: each party's name and the keys the version gives it. A name is a
  path segment no kind uses.
* **The kinds** of shared identifiers, each with the characters and length its
  identifiers may have.
* **The holders**: for each kind, which party holds which identifier. An identifier
  nobody holds is free.
* **The numbers**, which nothing constrains but `share`: a version whose `share` isn't
  more than a half is no version.

What may be written follows from the version that is current:

| Where | Who writes it |
|---|---|
| `<party>/…` | that party, its namespace |
| `<kind>/<identifier>` | the identifier's holder |
| `_continuum/federation/proposals/<hash>` | any voter |
| `_continuum/federation/votes/<voter>/<hash>` | that voter, once |
| `_continuum/federation/keys/<party>` | that party |
| `_continuum/federation/nodes/<party>` | that party |
| `_continuum/federation/forks/<ID>` | any voter |
| `_continuum/federation/went/<party>` | that party |
| protocol data of nodes (member entries, remakes, acks) | as in every swarm, by members |
| anything else | nobody |

Every value at the first eight is an envelope, signed by a key of its party, 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 voter at
`_continuum/federation/proposals/<hash>`, its hash the version's. A voter has at most
`limits.proposals` proposals on one version.

A voter **votes** by writing, at `_continuum/federation/votes/<voter>/<hash of the
version it changes>`, the hash of the proposal it votes for. A vote is never replaced:
a change writing where a vote is, as the change saw it, is refused. Two written at
once by one voter's nodes are both held, and the voter then counts for neither.

**The current version** at a set of changes: start from the version the epoch's root
names; while a proposal that changes it has the votes of at least `share` of its
voters, counting each voter's single vote, that proposal is current. So:

* **There is never a choice between two.** Two proposals that change one version can't
  both have more than half of its voters, as no voter counts for two. In whatever
  order a node gets the votes, it ends at the same version; a node that holds more
  votes is further along the same chain.
* **Nothing else needs to happen.** No record of the decision, no remake: once the
  votes are in the document, every node reads the new version, and judges by it every
  change written in sight of them.
* **A proposal on a version that was replaced lapses**, with its votes. Its proposer
  proposes it again on the current one; a client does that by itself for one that
  touches nothing the version that passed changed. Proposals that don't conflict
  pass in turn.
* **A split vote passes nothing.** Forty, forty and twenty on three proposals is
  resolved by a new proposal two thirds agree on, or by going apart (Forks).

Everything the federation decides is a change of the policy: who votes, with which
keys; who holds an identifier, which is giving one, taking it back and giving it to
another; the kinds; the numbers. A party's namespace is its name in the policy.

### 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 at `<kind>/<identifier>` counts if its holder signed it;
* a value in a namespace, a party's keys and its nodes count if the party is a voter;
* a proposal and its votes count while the version it changes is current.

What doesn't count is still held, and shown as such, until a remake leaves it out.
Where two values were written at once in one party's namespace, both count, and
readers show both until the party writes one replacing them: that is the party's
own matter.

### Keys

A party's keys are the ones the latest version that set them anew gave it (a version
whose keys for it differ from those of the version it changes), unless the party
replaced them since: an envelope at `_continuum/federation/keys/<party>`, signed with
one of its keys, naming its new keys; the first names the version whose keys it
replaces, the latest that set them anew, and each next one replaces the one before
(its `prev`).

* **A stolen key.** The party replaces its keys, and the thief's key signs nothing
  from there on. If the thief replaced them first, or both did at once (two envelopes
  replacing the same keys: the party then has none), two thirds of the voters give
  the party new keys by a version. That version can also undo, by naming it, what the
  thief did that the voters don't want kept: an identifier given away, a proposal.
  What the party's own namespace holds, the party writes again itself. A vote the
  thief cast stays the party's.
* **Rotation** is the same, without a thief.

### 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 may register itself, and commit changes. A node commits whatever its
party's operators send it, its party's envelopes and others' alike: what counts is
who signed a value, not which node committed it.

### Remakes

The document grows with every write, by the time it exists, not by what it holds.
A remake starts it anew. It is continuum's remake, of the kind that keeps the content
(`compact`), with two differences under the federated policy:

* **When**: once the epoch holds `remakeChanges` changes beyond its root, or its
  changes started `remakeWriters` writers. Every node reads that from the document.
* **Who agrees**: acks count by voter, not by node. A voter acks a remake when any of
  its listed nodes does; a voter whose nodes ack two remakes of one epoch counts for
  neither. A remake commits with acks of more than half of the current version's
  voters. With too many voters away, no remake commits; those who are there fork
  (Forks), and the document grows meanwhile.

**The snapshot** holds what counts at the base: the current version and nothing of
the chain before it; the proposals on it and their votes; the values that count; the
parties' keys and node lists; the member entries; and, for `replayWindow` epochs, the
envelopes that deleted a value. It names the epochs of the last `replayWindow`
remakes.

**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
signed in an epoch more than `replayWindow` remakes back, or that the new epoch
refuses (its party no longer holds the identifier, its key was replaced), goes to the
quarantine of the node that holds it, and its party signs it again if it still may.
An envelope names the epoch it was signed in.

So a remake decides nothing: the snapshot is what counted already, every node builds
the same, and a write after the base is judged as any write is.

### Forks

Any party, or group of parties, can carry on without the rest: two thirds of the
voters are away for good, a decision the group won't follow passed, or a vote is
split. It **forks**:

1. It names an epoch, heads in it, and a version of its choosing: the voters it wants
   to carry on with, and whatever else it wants changed.
2. Every node builds the fork's root alike: a snapshot of what counts at those heads,
   with that version as its first. The root names the epoch it came from and the
   heads, so anyone can check what it carries. Its ID is its hash.
3. The founder writes the fork into the epoch it leaves
   (`_continuum/federation/forks/<ID>`, its heads and its version), and each party
   that goes writes where it went (`_continuum/federation/went/<party>`), before its
   nodes switch.
4. Envelopes after the heads, of parties that are voters of the fork, are replayed and
   judged there, as after a remake.

A fork needs nobody's ack: it binds only those who go. Only its voters' nodes are
members of it. A party it leaves out writes nothing there; to come back, the fork's
voters give it a place by a version, as they would to anyone new. The epoch it left
goes on for those who stay. A fork may list parties as voters that weren't among its
founders (every party it considers honest, say), so that they can follow without
asking.

Nodes on different epochs don't sync, so the two go apart as far as the document is
concerned; each party chooses where its nodes are.

### Following

Each node has a follow rule, its operator's setting:

* **Remakes**: by acks, as above.
* **Forks**: by default, none: its operator chooses. 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 elsewhere, and asks its operator only when they went different ways.

The same list may vote: a node holding a key of its party for that votes for a
proposal once more than half of the parties it follows voted for it, and none for
another proposal on the same version.

So a federation that cooperates has a leading group without naming one: the active
parties the others follow. Those who follow need to act only when their leaders
disagree, and a party that won't cooperate is left behind by everyone who doesn't
follow it.

### Shared identifiers

Anything that isn't in a party's namespace is a shared identifier of a kind the policy
lists: a name under `.r`, an IPv4 or IPv6 address, anything else a version adds as a
kind. An identifier is given by a version, which needs two thirds; taken back and
given to another the same way. Nothing is first come, first served. Its holder writes
its value (`domain/wiki.r`: where the name points); a value its former holder wrote
stops counting once a version gives the identifier to another.

In a federation that cooperates this settles at once: a party proposes the addresses
it wants, the parties that follow the leaders vote with them. A group that gives an
identifier to another against the rest of the voters can't, short of two thirds; with
two thirds, the rest fork with the policy they want.

### Where Automerge sets limits

* **Writers.** Every writer costs every node memory while the epoch lasts, in
  proportion to the document's history *(measured upstream: about 4 bytes per change)*.
  A node writes under a fresh writer each time it starts. So a party's nodes start at
  most `limits.writers` writers in an epoch; changes past that wait for the next
  remake, which `remakeWriters` brings. Without that cost, neither limit would be
  needed.
* **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`)*; the next remake heals the split, as the snapshot
  holds only what counts.
* **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, reading shows
  one, in an order a writer can steer. Votes and keys are read with all the values a
  place holds, never the one shown.
* **History.** The document keeps all of it; remakes keep it bounded.
* **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
  (Continuum changing under a swarm).

### What it costs

The document holds what counts and what was written since the last remake:
`remakeChanges` changes at most, of `limits.value` bytes each at most, plus open
proposals and their votes. A version is held once, the current one. Judging a change
reads the current version at its history: the votes on the proposals there.

## Why it holds

1. **What is written.** A change is judged at its history, which its hash fixes, by
   the version current there, which the votes in that history fix. Every node 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, the same on every node that holds
   the same changes.
2. **The policy.** A proposal becomes current only with at least `share` of the
   voters of the version it changes, and `share` is more than a half; a voter's vote
   counts only alone. So at most one proposal changes a version, and the chain is the
   same on every node, however the votes arrived. Votes are never replaced, so a node
   that holds more is only further along.
3. **A remake.** Its snapshot is what counted at the base, built alike by every node,
   checked against the ID committed. What comes after the base is judged again, so a
   remake from any base commits nothing that wouldn't count anyway; at worst it makes
   parties sign again what they wrote more than `replayWindow` remakes back.
4. **Carrying on.** A fork's root is what counted at the heads it names, with the
   founders' version. Nodes follow it only by their own rule. 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, or on how much the document holds.
* **Taking back what a stolen key signed.** Telling from the document which signatures
  came after a theft needs its history kept and read. Voters decide what to undo, by
  naming it.
* **Acks by node.** Nodes cost nothing to run; a party with many would decide remakes.
* **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.

## Continuum changing under a swarm

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); the snapshot
a remake builds, to its byte; the federated rules. A rule changes only with a version
of the policy that names it (`"rules": 2`), which the voters pass once their nodes run
a continuum that knows it; the Automerge version moves only at a remake.

## 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 (`alice/hosts/laptop`: its
  keys, its addresses as it uses them);
* names under `.r`, and the retiolum and wiregrill addresses, are kinds; the policy
  says who holds each;
* a tool reads what counts and writes what kartei's consumers read today.

## Stages

1. **The federated policy**: versions, the current one read from votes, judging by
   it: namespaces, identifiers, proposals, votes. Tests: two proposals on one version
   with every order of votes; a vote replaced; two votes at once.
2. **Keys and nodes**: a party's keys and their replacement, two replacements at once,
   a version setting keys anew; membership by the node lists.
3. **What counts**, read by the current version; shown in the API.
4. **Remakes**: acks by voter, the snapshot of what counts, replay of envelopes, the
   window in epochs.
5. **Forks and following**: the fork's root, `went`, the follow rule, voting with the
   parties followed.
6. **The registry**: the kinds, the tool.

Each stage keeps every swarm that isn't federated as it is, its tests passing
untouched.