# 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 of
users, their hosts, and the hosts' names, addresses and keys
([krebs/kartei](https://github.com/krebs/kartei)), today plain files in a git
repository that one maintainer merges into.

Claims about the code as it is are marked *(checked)* where they were read in the
code, *(docs)* where they are taken from the docs, and *(assumed)* otherwise; the last
section lists them. How sure each part of the design is, is said with the promises.

## Optional

A swarm is federated if its root carries the federated policy (below). Everything here
holds under that policy, and nothing else changes:

* A swarm started as today has no such policy and stays as it is: its rules, its
  users with their capabilities, its remakes by the members' votes, its tokens, its
  messages.
* The code is apart where it would cost. Judging reads the policy as it does today and
  takes the federated rules under the federated one only; the resolved registry is
  kept there only; envelopes carry their new fields there only; no message changes.
* Shown at every stage by the existing tests passing untouched, and by the cost of
  judging a change (`bench_screening`) staying where it is for a swarm without a
  policy and with today's.

## The parties and the adversary

A **party** is a user and the nodes that carry for it. The user holds SSH keys and
signs; its nodes commit what it signed and sync with the others' nodes. One user
starts the swarm: the **root**. Nobody owns the swarm, and any party may be malicious,
alone or together with others, the root too.

What an adversary can do:

* run nodes, and once it is in, bring in users of its own;
* craft any change: under any actor, with any dependencies (so "made long ago", as
  the document sees it), any operations;
* send different changes to different peers, send none, or pass on only some;
* delay or drop messages between any nodes for as long as it likes, short of forever
  between honest nodes;
* choose its node keys, and so where its nodes fall among the members;
* steal a key of another party (a user's key, a node's key), as a case of its own.

What it can't: forge an Ed25519 signature, or find two changes with one hash.

Out of scope: keeping the registry 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).

## What is promised

To an honest node, whatever the others do, with any number of them malicious:

1. **Only valid changes.** Every change it holds passed the rules, judged as its
   writer saw the document (at its dependencies).
2. **The same document.** Two honest nodes holding the same changes hold the same
   document, and resolve it (Resolving, below) to the same registry.
3. **Signed by its user.** Whatever the resolved registry shows in a user's namespace,
   or as held by a user, was signed with a key that was that user's when it signed, or
   is as the root change has it.
4. **One holder.** The resolved registry gives each name of each kind to one user at
   most, and each user name to one user.
5. **First come, first served, once the root saw it.** A claim is **settled** once a
   node of the root committed a change after receiving it, with no other claim of
   that name around. From then on nobody else ever holds that name while the claim
   stands: every other claim of it, whenever and with whatever dependencies it shows
   up, is late. Two things can still happen to it. Users on the claimant's own line
   (those who vouched it in) can get it **contested**, so that nobody holds the name;
   that shows, with the changes that did it. And a claim made after another user
   released the name stands as long as that release does (Cuts).
6. **Nobody waits for anybody.** An honest user's valid write needs no vote and no
   other party's consent; it counts at once, and reaches every honest node its nodes
   reach.

And for what the swarm decides together, with fewer than a third of the voters
present malicious, then or later (the voters are the users an epoch starts with, of
those the root brought in):

7. **Decisions by two thirds.** A remake, a new root, a change of the voting numbers
   counts only once more than two thirds of the voters present, and more than half
   of all the voters, voted for it and their nodes took it up while the votes ran.
   No two decisions of one matter both count, and none counts that no honest voter
   voted for. With no voter malicious, no two do whatever the network does. A
   remake changes nothing in what counts: every node builds the next epoch itself,
   from the changes it holds. Nobody is moved to other rules: a change of policy is
   followed by choice.

What is not promised:

* **One history at all times.** Both sides of a partition go on. A name claimed on
  both sides goes to the side the root was on, or is contested until one side
  releases it.
* **That a name is never contested.** Before a claim is settled, a claim made out of
  its sight contests it. After, the claimant's line can, by saying it saw another
  first.
* **Protection from a stolen key** before its user notices: what was signed with it
  counts until a key above it cuts it off; then all of it stops counting (Cuts). A
  remake in between makes it final.
* **Agreement in the classic sense, for what users write.** There is no quorum there,
  so no n ≥ 3f+1: promises 1 to 4 and 6 hold against any number of malicious parties,
  and 5 from when the root saw the claim. Only decisions take two thirds, and only
  the voters make them.
* **Decisions against a third of the voters present.** A third or more of them,
  together, can make two decisions of one matter count, and can push the swarm's
  time. So can fewer, across a partition that outlasts the absence period and splits
  the honest voters about evenly, by being present on both sides. Two that count
  undo each other; two remakes are two epochs, and the parties choose (Decisions).
  Nor against the past: the node keys of two thirds of those who were voters once,
  stolen later, make a decision "of then". A node that was up holds it back; one
  that joins later can't tell, until a remake put that past out of reach.
* **Decisions without the voters.** With half an epoch's voters or fewer around,
  nothing more is decided there; what users write goes on. Until the first remake
  the root is the only voter. Those left go on by a fork.
* **A swarm that never splits.** A node that forks its own actor (two changes with one
  number) splits the honest nodes that took one from those that took the other, until
  one side drops its own (Partitions). It is found, proven and named; it isn't
  prevented.

How sure: 1 to 4 follow from how changes are judged today plus rules of the same
shape, and from Kleppmann's result that a hash-linked change graph whose validity
depends on a change and its history alone converges whatever the faulty nodes do
(*Making CRDTs Byzantine Fault Tolerant*, 2022): high, given the conditions under Why
it holds. 6: high. 5 is this design's own construction, argued below: medium. 7 is the
classic two-thirds argument carried over to votes that take days, with a clock read
from the document: medium, less for the clock. 5 and 7 want the tests named under
Attacks, and someone trying to break them.

## The design

It builds on the strict policy ([`access.md`](access.md), Values signed by their
users): values as envelopes their users sign, which every node checks against the
registry as the writer saw it. What it adds: users come in by being vouched for, and
go by being unvouched; each has its namespace; names of declared kinds are held by one
user each; what a key signed can be cut off after the fact; and the swarm decides by
its voters' votes.

### The policy, in the root

A federated swarm's policy is `{"version": 2, "values": "signed", "users": "vouched"}`,
with what the rules read beside it in `_continuum/access`: the kinds of names
(`claims`), the paths in namespaces whose values are signed (`userSigned`, as today),
the limits, and the voting numbers (`window`, 7 days; `absent`, 30 days). All of it is
in the swarm's root, its genesis change, with the root user, its keys and its nodes:

* Nothing is ever written before the policy, so nothing is judged by none.
* Every node is given a root and takes no other: the genesis root (`--genesis-root`),
  or, in a swarm that was remade, the ID of a later epoch. The root is what a party
  trusts, not what its seeds say.
* A node that doesn't know the policy's version doesn't sync at all. (Today it
  receives without judging *(docs)*, which here would let anything in.)

The voting numbers change by a decision. Anything else in the policy changes by a
change of policy, which is a fork (below).

### Users: statements, keys, nodes

`_continuum/users/<name>/<digest>` holds the **statements** about and by a user, each
an envelope kept under its SHA-256, never replaced or deleted: the register only
grows. A statement is signed by one user and says one thing:

| Statement | Signed by | Says |
|---|---|---|
| `create` | another user (the creator) | the name, its first keys, the nodes that carry for it |
| `vouch` | another user | "I vouch for this user too" (no keys) |
| `unvouch` | the signer of a `create` or `vouch` | that one taken back (Unvouching) |
| `key` | the user | one more key |
| `retire` | the user | a key, and the cut after which what it signed doesn't count |
| `node` | the user | a node that carries for it; or one that stops, with a cut |
| `release` | the user | a claim or a vote of its own given up; or itself |
| `ban` | the user | a user that doesn't count for it, with a cut (Bans) |
| `propose`, `vote`, `decide` | a voter (a change of policy: a first user) | Decisions |

* **A user is its creation.** The `create` statement's digest is the **user ID**, and
  every envelope the user signs names it, with the name, the swarm and the epoch it
  was signed in. Two creations of one name are two users with two sets of keys; which
  has the name is decided below, and a key listed in both signs for the one its
  envelope names.
* **Keys form a tree.** A user's first keys are those its creation names. A `key`
  statement adds one, signed with a key the user has, which is **above** the new one,
  as are the keys above itself. Any number over time; 64 at once at most (a limit in
  the policy). Use: the first keys stay offline, a key added below them is on each
  device.
* **A node carries for a user** that named it. A node commits changes only while it
  carries for a user, and an envelope is taken only in a change committed by a node
  that carries for its signer (a `node` statement also in one by the node it names).
  So every change is some party's: its node's signature proves the node
  ([`access.md`](access.md), signatures required), and the user's statement binds the
  node to the user. 8 nodes a user at once (a limit).
* **Names** are 1 to 64 of `A-Z a-z 0-9 . _ @ -`, as today, or fewer characters where
  the policy says (the registry: lower-case letters, digits and `-`, so a name is one
  label of a host name), less the top-level keys the swarm uses otherwise
  (`_continuum`).

### Vouching, the line, the root

A user creates whom it likes, within a limit (16, in the policy), and vouches for whom
it likes. The new user signs, claims and creates in turn from its creation on: in any
change that has the creation in its history. A user is **vouched for** if its creator
is, down from the root, and the creation counts; or if a user vouched for it whose
own line doesn't pass through it. So vouches form a graph, and rings away from the
root hold nobody.

A user's **line** is the users from the root down to its creator, then itself: fixed
when it is created. (If its creation stops counting and a `vouch` keeps it, its line
runs through that voucher.) The line is whom a user answers to for what came first:

* the line's nodes are the witnesses for and against its claims (below);
* a creator's limit bounds how many users come in through it, and each is on its line
  for all to see.

What a second vouch is for: a user stays vouched for when its creator takes the
creation back (Unvouching), cuts off the key that signed it (Cuts), or is banned by a
node (Bans). It changes nothing else.

Bringing someone in means handing over, out of the document, what a party needs: the
swarm key, the root to start from, some seeds; and writing the `create`.

**What the root is.** A user like any other, but for three things. It is in the root
change, so nobody vouched for it, and its name can't be created again. It is on every
line, so its nodes' changes are what settles claims. And the users it creates are the
**first users**, who come to vote for the swarm (Decisions). It can't write in another's
namespace, nor take a settled name. It can contest any name, in the open. Who the
root is can be decided anew (The root's seat).

### Unvouching

A user takes back a `create` or a `vouch` it signed: `unvouch`, naming it. Nobody else
can, but the root for what a root before it signed (The root's seat). What it does,
exactly:

* **From where.** From the unvouch on, as far as the user had been seen. What the
  unvouched user signed stays if it is in the history of the unvouch, or of a change
  that a node of the unvoucher or of the root committed without the unvouch in its
  history. Everything else it signed doesn't count through this vouch, whenever it
  shows up. So an unvouch crafted with old dependencies undoes nothing that its
  signer's own nodes, or the root's, had seen: no more than what reached neither.
* **Another vouch keeps the user.** With another creation or vouch that counts, the
  user stays as it is in everything; its line then runs through that voucher.
* **Else the user is out, from there.** It holds nothing: its names are free for a
  claim made in sight of the unvouch, and so is its user name. Its namespace doesn't
  count. Its nodes witness nothing, and what they commit in sight of the unvouch is
  refused.
* **Those it brought in go with it,** from the same point: a user whose line ran
  through it stops counting there too, with the same consequences, unless another
  user that counts vouches for it, before or after. A vouch given after brings a user
  back whole, with what it signed in between.
* **What it did before stays done.** A name it released and another claimed stays the
  other's; a user it created and another vouched for stays.
* **Out of sight.** What the user signs with dependencies from before the unvouch (on
  the other side of a partition, or crafted) is valid as written, so nodes hold it;
  it is past the point, and doesn't count. A node takes changes of an unvouched
  user's nodes only as part of another party's history, not from those nodes, so they
  can't fill the document.
* **Undoing it**: a new `vouch`.

A user gives itself up the same way: a `release` of its own creation, from that
release on.

### Namespaces

A user's namespace is the top-level key with its name. One rule: below `<name>`, only
envelopes signed by a user of that name, at the depths `userSigned` lists (for the
registry, `["*", "hosts", "*"]`: a host is one signed value). A value there is
replaced as today, by an envelope naming the one it replaces (`prev`). Nothing plain
is written anywhere but a node's own member entry.

Delegating (another user writing below `<name>/shared`, say) would be a statement in
the user's register granting a capability within its namespace: for later; the rule
has room for it.

### Claims: names held by one user

What must be unique across users (a host's name, an address, a top-level domain) is
**claimed**. The swarm declares the kinds, as data in the policy:

```json
{ "name": { "rules": [ { "match": ["*", "{user}", "**"], "by": "{user}" },
                       { "match": ["*"], "by": ["tv"] } ] },
  "ip4":  { "rules": [ { "match": ["10", "243", "*", "*"], "by": "*" } ],
            "limit": 64 },
  "user": { "rules": [ { "match": ["*"], "by": "*" } ] } }
```

* A name is a list of segments: a host name's labels from the top (`toaster.tv.r` is
  `["r", "tv", "toaster"]`), an address's parts. In the document it is one key, the
  segments joined by dots (`r.tv.toaster`, `10.243.0.7`).
* The first rule whose `match` fits decides who may hold the name (`*` fits any one
  segment, `**` any number more): one user, a list, anyone vouched for (`"*"`), the
  user whose name stands where `{user}` does, or whoever is the root (`"{root}"`). No
  rule, no holder.
* A name a rule gives to `{user}` is **kept**: it is that user's without a claim,
  since nobody else could claim it. So above, `*.tv.<tld>` is tv's, for any top-level
  domain, whatever tv claimed; a top-level domain is claimed by tv only; an address by
  whoever comes first, 64 a user.
* The kind `user` is the users' names themselves: its rules say who may create which
  (a swarm can keep names for one creator).

`_continuum/claims/<kind>/<name>/<digest>` holds the statements about one name, again
only growing: `claim` (by the user who wants it) and `release` (by that user, of its
claim: how a name is given up). A claim is taken, as its writer saw the document, if a
rule lets the user, the user is within the kind's limit, and every claim of that name
there is released. That is first come, first served wherever one claim was made in
sight of the other: the later one is refused by every node.

A claim says nothing else. What the name is for is in the namespace: a host's entry
names its addresses and names, and they count while its user holds them.

### Two claims out of each other's sight

Two users claim one name at once, or on two sides of a partition, or one of them
pretends to: it crafts a claim whose dependencies are old, from before the other's. No
node can tell these apart, and both claims are valid as their writers saw the
document, so every node holds both. What decides is who can be shown to have seen
what. The witnesses for a claim are its **side**: the nodes of its user and of the
users on its line, the root's among them.

* A claim is **late** against another if a change committed by a node of its side
  (one carrying for such a user when it committed it) has the other in its history
  and not the claim itself: the claimant's side had seen the other while the claim
  wasn't there yet.
* Of the claims of a name that count and aren't released, those not late against any
  other remain. If one remains, its user holds the name. If none or several do, the
  name is **contested**: nobody holds it, until releases leave one.

Being late never goes away (changes aren't taken back), and it is read from the
changes alone, so every node finds the same.

What this gives:

* Every node writes its member entry about daily (its alive stamp, *docs*), and such
  a change has in its history everything the node had received. The root is on every
  line. So once the root's node wrote after receiving a claim, while it had received
  no other of that name that isn't released, every claim of the name surfacing later
  is late against it, however old its dependencies look: the claim is settled. A node
  tells (`settled`, below). The root's node writes when a claim reaches it that it
  hadn't seen, a minute apart at most, so a claim is settled within a minute of
  reaching it.
* A user that is up is bound by its own node: after its node wrote once with a claim
  in its history, it never holds that name against it.
* To take a name from a claim, a rival needs the claim to be late and its own not to
  be: a node on the claimant's line saying it saw the rival first, and nobody on the
  rival's side having written after seeing the claim. After the root saw the claim,
  the second can't be.
* Before a claim is settled, a claim out of its sight contests it. Honest users
  claiming at once see "contested", and one releases.

A user's name is claimed the same way: the `create` statement is the claim, its side
the creator's side and the new user's own nodes. Two creations of one name out of
each other's sight are decided as above; while it is contested, no user has the
name, and neither namespace counts.

A user that doesn't have its name still holds what it claimed where anyone may claim:
those claims stand, so contesting a user's name frees none of them. What a rule gives
to a name (a kept name, a name only `tv` claims) is nobody's while the name is.

### Cuts: what stops counting

A **cut** is a set of changes, named by their hashes: "as far as I saw". A statement
is within the cut if a change that carries it is in the history of the cut. Whether
it is doesn't depend on who asks or when: a change's history is fixed by its hash.

* **Retiring a key** names the key and a cut. What the key signed within the cut
  counts as before; what it signed outside doesn't count, for anyone, whenever it
  shows up. A statement signed with a retired key and offered later with old
  dependencies is outside the cut. That is how retiring reaches a node that was away:
  it needs no order of arrival.
* **Who retires what.** A key above another retires it with any cut: a user whose
  device key was stolen cuts it off from before the theft. A key retires itself only
  from where it stands (its cut must hold everything it signed that the retiring
  change's history holds): rotating, not rewriting. No key retires one beside or above
  it, so a stolen device key can't cut off the keys above it, nor undo what it signed
  before.
* **A node that stops carrying** is named with a cut the same way, by the key that
  named it or one above: what it committed outside the cut is nobody's, as a witness
  or as a carrier.

What stops counting stays in the document, and every node holds the same. It is left
out when resolving. In a namespace, where a value that doesn't count replaced one
that does, the one that does is read again (Resolving).

The price: a key above retiring one below with an early cut takes back what that key
signed since, a vouch or a release among them, further back than an unvouch reaches.
Whoever relies on another's statement relies on that; a second vouch is what makes a
user independent of its creator's keys. And a user's first keys have none above them:
one of those stolen is that user lost, to be unvouched, and created again under
another name.

A cut reaches no further back than the epoch (Remakes).

### Bans: for those who follow

A user may state that another doesn't count for it, from a cut on: `ban`. A node
resolves with the bans of the users it **follows** (`--follow`; its own user by
default): what the banned user signed and what its nodes committed outside the cut is
left out, as a holder and as a witness. Bans are taken in the order they were made;
of two made out of each other's sight, the one by the user nearer the root first; and
none by a user that a ban taken before leaves out.

A ban changes what a node reads and writes out, never what it takes or refuses: every
node still holds every valid change, so banning splits nothing. It is what a party
does about a user it can't unvouch: one that squats, a line that contests its names,
a root it no longer trusts and can't get replaced. Its registry goes on without them.
Parties following the same users read the same registry. A node refuses its own
user's write that only its bans make valid (a claim of a name the banned user holds):
the others would refuse it, and everything the node writes after.

This is the trust root a user has beyond the swarm's: the root every node is given,
and whom it follows. In a dispute, the nodes following a user read its side.

### Decisions

Some things are the swarm's to decide: its voting numbers, who the root is, when to
compact, which change of policy is the swarm's. They are decided by votes of users,
signed by them, over days.

**Who votes.** The **voters** are the users the epoch's root change names. A swarm's
first names the root alone. A remake's names the **first users** that count at its
base and aren't absent there: the root, those who were the root, and the users each
created as the root. So a first user votes from the next remake on, one that left
is no voter after it, and until the first remake the root decides alone. A root
can't fill the votes with users of its own: those who vote see who would, before
they vote for the remake, and can seat another root first. Users further down the
lines don't vote: whoever brought them in speaks for them, and a vote a user would
be a vote a puppet.

A change in who votes takes a remake because a remake is what puts the votes of
before out of reach (below).

**Who is away.** The document gives a time. Each node's alive stamp says what its
clock read *(checked: `alive`, Unix ms)*. The **swarm's time**, at a set of changes,
is the latest time that a third of the voters have a node stamped at or after. A
voter whose nodes' last stamp is more than `absent` behind it, or that has no node,
is **absent**: it neither votes nor counts, until a node of it stamps again. The
voters **present** are those not absent. Fewer than a third of the voters can't move
the swarm's time forward by lying, so they can't make the others absent; and those
who left hold up nothing.

A decision also takes more than half of all the epoch's voters, absent or not
(below). So with no voter malicious, no two decisions of one matter both count,
however long a partition lasts: each would be taken up by more than half, and an
honest voter takes up one. Where half or fewer are left for good, they go on by a
fork that names who votes (A change of policy is a fork).

**How.**

1. A voter **proposes**: a statement saying what.
2. Voters **vote** for it: each a statement signed by the user, saying when the
   vote runs out, `window` from signing unless the user says sooner. One vote on a
   matter at a time; `release` takes one back.
3. Once more than two thirds of the voters present have votes for it in the
   document, any of them **decides**: a statement naming the proposal, the votes, and
   the decision of that matter before it, if there is one. Every node judges it as
   written: the votes are there and not released, their users are more than two
   thirds of the voters present there and more than half of all the voters, and no
   other decision following the same one is there.
4. Every voter **takes it up**, by one node: the one it named first of those
   that carry for it. When the decision reaches that node while the votes it names
   still run, by the node's clock, the node records so in its member entry. Of the
   decisions following one, it takes up the first that reaches it and no other.
5. The decision **counts** once more than two thirds of the voters present at
   its dependencies, and more than half of all the voters, took it up. That is read
   from the document, the same by every node, and never goes away.

Every node acts on a decision that counts, unless another following the same one
counts too.

**Two that count.** Two decisions following the same one both come to count only
by what isn't promised against: a third of the voters present malicious, or fewer
of them present on both sides of a partition that outlasts the absence period.
Where a set of changes has both counting, nodes act on neither there: the matter is
as the decision before them left it, every node shows both, and the next decision
of the matter names both. Two remakes are two epochs: a node is in the one it built
first, and moves to the other by its operator's word.

**Decisions don't come from the past.** One that is crafted with old dependencies, or
kept back until its votes ran out, is taken up by no honest voter, so it has only
its makers' records. Those are enough only if they were two thirds of the voters
then: their keys, stolen later. Against that, a node that was up holds back a
decision that comes to count more than the absence period after its votes ran out,
and shows it, for its operator to say. A node that joins later takes the decisions
that count as it finds them; a remake puts everything before it out of reach.

The votes are the users' own, signed with their keys, and take the days people take.
Taking up is their nodes', and takes as long as syncing does.

**What is decided.**

* **The voting numbers**, `window` and `absent`: they hold for what is proposed in
  sight of the decision.
* **The root's seat** (below).
* **A remake** (below).
* **A change of policy** (below): proposed and voted on the same way, made and
  followed by choice.

### The root's seat

The root is whoever holds the seat: at first the user in the root change. A decision
gives the seat to any user. From the decision on, in every change that has it in its
history:

* the new root is on every line, so its nodes' changes settle claims, and the users
  it creates are first users. Like them, it votes from the next remake on if it
  didn't before;
* the old root is a first user like the others, and votes on. It keeps its name, its
  namespace and what it holds, and stays on the lines of those it brought in;
* what a root signed as the root is the seat's: the new root may unvouch the users
  the old one created, and the old root itself, which goes alone (those it brought
  in stay, their lines running through the seat). The old root no longer may.

What the old root did that the decision's history doesn't hold is an ordinary
user's: users it created while away, or crafts later with old dependencies, are not
first users.

So a root that disappears is replaced by two thirds of the voters present, and so is
one that turns on them. (Before the first remake there is nobody to do it: a swarm
remakes once its root brought the first of them in.) A root that comes back finds
itself a first user; it may be voted in again. While the seat's holder is away
nothing new is settled: claims count, and can be contested, until there is a root
again.

### Remakes

A federated swarm compacts by a remake its voters decide. What the next epoch
holds isn't voted on: it is the registry as it resolves, which every node works out
itself.

* **The base** is the history of the decision. A voter takes a remake up only
  if that holds all its node holds but the last ten minutes, so a decision can't
  leave out what the swarm has.
* **Every node builds the snapshot** itself once the decision counts, from the base
  as it holds it, and switches after the switch delay, as today. The snapshot holds
  the registry as it resolves at the base: the policy and the voting numbers; who the
  root is, and who votes (the first users that count and aren't absent); the users
  that count, with their names (or that they are contested), IDs, keys, nodes,
  creators and vouchers; the names held or contested, each marked settled or not;
  the values in the namespaces that count, as the envelopes they are; the members'
  entries, as today. It leaves out what doesn't count, and all history.
* **Carried over.** A node writes again, as they are, the statements of its user
  that the base lacks. An envelope names the epoch it was signed in. A claim signed
  in an earlier epoch is in sight of the claims the snapshot holds settled, and is
  refused where the name is held; it is out of the sight of those it holds unsettled,
  and contests them, until what nodes commit from then on shows one late.
* **What a remake makes final.** A cut reaches no further back than the snapshot.
  What a key signed that counted at the base counts for good, though the key be cut
  off later from before; so for an unvouch. The days a vote takes are the time to cut
  off a stolen key and to sort out what is contested. After, what a thief did stands
  until it is undone by hand.
* **A node that was away** gets the rest of the old epoch from its peers' archives
  (they answer for an epoch they left as long as they keep it, `archiveRetention`),
  sees the decision count, builds the snapshot itself and carries its own over. Where
  no peer keeps the old epoch any more, its operator gives it the new epoch's ID, and
  it takes the snapshot by that.
* **A node that joins** is given a root to start from, by whoever brings its user in:
  the genesis root, or the ID of a later epoch.
* **No other kinds.** `replace` and `import` put content nobody signed: they start a
  new swarm.

For the registry the document is small: a statement is under a KiB, a node's alive
stamp with its signature about 300 bytes, so a hundred nodes write some 10 MiB a
year. A remake a year is plenty.

### A change of policy is a fork

A change of policy (a new kind of name, another rule, a version of continuum that
judges differently) can't be made to bind anyone: a node judges by the rules it knows
and its operator chose. So it is a fork, by design:

* A first user proposes the new policy, and voters vote. Any first user decides,
  with whatever votes there are: the decision names the proposal and, by its history,
  the base. It takes no two thirds to be made, only to be the swarm's, and it stands
  in no other decision's way: there can be several.
* The proposal may name who votes on its side. Where it doesn't, those vote who
  would after a remake at the base. Whoever follows it chose them with it.
* A node follows it if it knows the policy's version and its operator said so
  (`POST /admin/policy`, naming the decision): it builds the snapshot at the base
  with the new policy in it, and goes on in that epoch; a voter's node records
  taking it up. A node that doesn't stays in the epoch it is in, which goes on as it
  was.
* Both sides have the same history up to the base and the same swarm ID, and from
  there different epochs. Their nodes don't sync, and a statement signed on one side
  counts for nothing on the other: it names its epoch.
* Once as many voters took it up as make a decision count, the change is the
  swarm's, and nodes show it so. It still moves no node whose operator didn't say so.
* On each side, the voters who went the other way are absent after the absence
  period, and decisions go on without them where more than half of that side's
  voters are there. A side with fewer names its own: those who stay propose the
  policy they have, naming who votes.

So a fork is also the way out for those the swarm's decisions leave behind: with a
root that went before the first remake, with half the voters or fewer left, or with
two thirds of them turned against the rest. It moves nobody, and takes nothing
along but the history: each party chooses its side, and a side its root didn't come
to seats one.

This is how Bitcoin changes its rules. Nobody decides for anyone: nodes run the rules
their operators chose. A change that isn't compatible takes effect at a block height
named beforehand, and nodes with the old rules go on with the old chain, the same up
to there. Miners signalling for a change says how many will go, not who must. And a
transaction that would count on both chains is kept to one by naming its chain. Here
the height is the decision's base, the signalling is the vote, and the epoch in every
envelope keeps a statement on its side.

### What every node judges

A change is valid if, in the document at its dependencies:

1. It has no dependencies and is the root the node was given (the genesis change, or
   the epoch's snapshot). Else:
2. Its committer is a node that carries for a user there, one that isn't out and
   hasn't stopped there, proven by the node's signature.
3. Apart from the node's own member entry, it writes only envelopes, each naming the
   swarm, its epoch (this one, or for what is carried over one before it), its path,
   its user and user ID, signed with a key that is that user's there and not retired
   there, and (but for a `node` statement) the committer carries for that user.
4. In a register (`_continuum/users/<name>`, `_continuum/claims/<kind>/<name>`): only
   a new entry under its own digest. Nothing replaced, nothing deleted, nor anything
   that holds a register.
5. A `create`: its name has no creation there that isn't released or out, a rule of
   the kind `user` lets the signer, and the signer is within its limit. `key`, `node`,
   `vouch`, `ban`: within the limits. `unvouch`: by the signer of what it takes back.
   `retire`, a node stopping: by the key itself or one above, the cut in the change's
   history, and for a key retiring itself as said under Cuts. `release`: by the user
   of what it releases.
6. A `claim`: the kind is declared, a rule lets the signer, the signer is within the
   kind's limit, and every claim of that name there is released or its user out.
7. In a namespace: at a listed depth, an envelope by a user of that name, replacing
   what is there (`prev`); nothing within one, nothing replacing what holds one.
8. `propose`, `vote`: by a voter present there (a change of policy: proposed by a
   first user), signed in this epoch; a vote where the user has none on that matter
   that isn't released. `decide`: as said under Decisions, and for a change of
   policy by a first user, naming the proposal.
9. `_continuum/access`, the swarm ID, the epochs: never.

Where a rule goes by a user's name (6, 7) and the name has several creations there, a
user that lost it, as far as the change's history shows (another remains, Two claims),
is refused; while none remains, each of them may write. So a user whose late creation
of a name is known can't scribble over the namespace, and one whose name a liar got
contested goes on writing, for those who ban the liar to read.

Judging reads the registers at the change's dependencies, and nothing else: no cut is
applied beyond a retiring or an unvouch that is there. A statement in a register was
valid when it was taken, so judging the next needs no look further back.

### Resolving

The **resolved registry** is a function of a set of changes that holds each change's
history (and, for reading, of the users followed). In five steps, each reading only
the steps before:

1. **Who counts, and where.** The first root counts. A user counts at a statement if
   a `create` or `vouch` for it counts whose signer counts there (nearer the root, so
   this ends), and the statement is within what every `unvouch` of that one leaves.
   A statement counts if its user counts at it, its key was the user's (added by
   statements that count, up to its creation), it is within every cut a counting
   `retire` sets for that key, and a node carrying for the user committed it, within
   that node's cut if it has one. Bans of followed users cut the same way. Past a
   limit, a user's creations and vouches don't count: those made in sight of the
   others first, then by digest.
2. **Decisions.** Which count (Decisions), one after the other as each names the one
   of its matter before it, two following the same one undoing each other: the
   voting numbers, and who the root is.
3. **Users' names.** Of the creations of a name that count: the one that remains (Two
   claims) has the name.
4. **Names.** A claim counts as a claim if its statement does and a rule lets its
   user: anyone vouched for where the rule says `"*"`, else the user that has the name
   the rule gives. Past the kind's limit, a user's claims don't count, as in 1. Of
   the claims of a name: one that has another unreleased one in its history loses to
   it; of the rest, the one that remains holds the name. A kept name is held by the
   user that has the user name.
5. **Values.** A value in a namespace counts if its envelope does and its user has the
   name. Where the document holds several at one place (written at once), those that
   count, in Automerge's order. Where the one there doesn't count, the last that does,
   back along `prev` (read in the document at the dependencies of the change that
   replaced it).

A node keeps the resolved registry as it goes (a statement changes it around its own
name), and answers from it:

* `GET /registry/users/<name>`: the user that has the name, its keys and nodes, its
  line; or that it is contested, between whom; or out, since where.
* `GET /registry/claims/<kind>/<name>`: the holder, and whether the claim is settled;
  or contested, between whom, with the changes that make each claim late and whose
  nodes committed them. A user whose nodes showed both orders of two claims is
  marked: it lied, or its nodes were apart.
* `GET /registry/decisions`: the root, the voting numbers, the swarm's time, the
  voters present and absent; what is proposed, who voted, until when; what was
  decided, who took it up, whether it counts, and what this node holds back.
* `GET /store`, as today, with a value that doesn't count marked, and the one that
  counts in its place.

### Partitions, and coming back

Three things are "conflicting data", and are dealt with apart.

**Names claimed twice** are no partition: every node holds both claims and finds the
same holder, or contested. The users see it and one releases; nobody drops anything.

**Two epochs**, after a change of policy or after two remakes that both count, are
a fork: each node is where its operator put it, or where it got to first, and moves
to the other side by being told to (it builds that side's snapshot from the base it
holds, and carries its own over).

**Changes one side refuses** are a partition nobody chose. A node is cut off from the
others when it holds a change they refuse, as everything it writes after builds on
it. That happens by three things, and each shows:

* **Its own node broke a rule**, by a bug or on purpose. The others refuse the change
  and, its signature proving it its own, the node as a whole: `GET /peers` (`refused`,
  with the change and why), the dashboard, `sync.refusedPeers` *(docs)*.
* **The two sides judge differently**: versions that differ, a bug in a rule. Each
  refuses what the other takes; a node told so judges what it holds again and logs
  that the policies disagree *(docs)*.
* **An actor forked.** A node committed two changes under one actor and number and
  gave each to some. Automerge holds one change per actor and number, so a node
  holding one can't take the other, nor anything built on it *(checked)*. Both carry
  the same node's signature: a node offered the second holds proof, shows it, and
  refuses the forking node from then on.

Coming back is the side's own choice, never forced: an operator has the node **drop**
what the others refuse (`POST /admin/refused/drop`, naming the peer whose word it
takes). The node's document becomes what it would be without those changes and what
was built on them, as a drop does today *(checked: `AppState::drop_taken`)*. Its own
user's statements among them go to the quarantine and are written again as they are:
an envelope doesn't name the change that carried it, so it is as valid in a new one.
Those that no longer fit stay there for the user to sign again: one replacing a value
that is gone, or a cut naming a change that was dropped.

Which side drops, for a fork of an actor? No rule can say: the forking node may have
ground the hash of the change it kept back, and a rule by hash would let it make
everyone drop a year's work. A node shows which of the two its line holds (its
creator's nodes, up to the root's), and the operator follows its line or doesn't. A
node that just joined and got the lone change from the forking node drops and loses
nothing.

A side that doesn't want to come back stays as it is: the same swarm ID, another
history.

### Reaching one's line

A node's neighbours come from the member list: a ring by key hash, and the pairs with
the lowest scores *(checked: `swarm::topology`)*. An adversary choosing its node keys
places its nodes around a victim, and then holds back what the victim writes, or what
it should receive: a claim that never reaches the root is never settled.

So in a federated swarm a node also keeps as neighbours the other nodes of its user,
and the nodes of its user's creator, and they it. A claim then reaches the root along
the line whatever the graph gives, and cutting a party off takes its creator. The
root's nodes link to the users the root created, not to everyone.

### The API, tokens, reading

* **Writing** through a node is handing it envelopes: it carries those of the users
  it carries for, judged before they leave, as today. `scripts/continuum-signed`
  signs them, votes among them.
* **A node's API users** (`--htpasswd`, a proxy's header) are its party's: they read,
  and use the node's admin endpoints. The registry gives nobody anything on another
  party's node.
* **Tokens** are taken only from the node itself and from nodes that carry for the
  same user. (Today every node takes a token any member signed *(docs)*: a party's
  node could let itself in anywhere.) Ended sessions are each node's, as in a swarm
  without a registry.
* **Reading**: every party reads everything. The registry holds public keys, names
  and addresses, nothing secret; a value only some should read is sealed for them, as
  today.
* **The swarm key** stays a secret all nodes share: it keeps those who aren't parties
  from connecting and reading, as far as every party keeps it. It is no boundary
  between the parties.

## Why it holds

**Promise 1**, by how a change is judged: every node judges a change before applying
it, at its dependencies, and refuses it with everything built on it *(checked:
`access::rules::judge_reading`, `access::screen`)*. The rules above read the document
at the change's dependencies alone.

**Promise 2.** Whether a change is valid depends on the change and its history; its
hash covers both. So honest nodes agree on every change, hold the same valid changes
once each has what the other has, and Automerge gives the same document for the same
changes. Resolving is a function of the changes and the follows; a node's clock
enters only into what its own node writes (taking a decision up), never into what it
reads from the document. What must hold for this, and doesn't everywhere today:

* the root given, never learned;
* no window without a policy (it is in the root), and no syncing under a policy the
  node doesn't know;
* a batch judged at heads that differ from a change's dependencies only where nothing
  the rules read changed in between: the registers must be among what screening takes
  as read by rules *(checked: `screen::relevant` lists members, users, remakes, votes,
  access and bans; claims must join)*;
* nothing a node keeps a bounded number of decides validity: a change pushed out of
  the waiting ones comes again *(checked: `MAX_WAITING`)*;
* one change per actor and number. A forked actor breaks "hold the same changes"
  until one side drops. Automerge names a change by actor and number where
  Kleppmann's construction needs the hash.

**Promise 3.** A value counts only with an envelope whose signature checks against a
key that step 1 gives its user for the change that carries it. A key is a user's only
by statements signed with keys above it, up to its creation, signed by its creator,
and so on up to the root, in the root every node was given. A node that carries
doesn't sign in the user's place: the envelope names its swarm, epoch, path, user and
user ID *(checked for swarm, path and user: `access::envelope::check`)*, so it counts
nowhere else and for nobody else. Across a remake: every node builds the snapshot
from changes it judged, so the snapshot holds only what counted.

**Promise 4.** Steps 3 and 4 name a holder only where exactly one claim remains.

**Promise 5.** Let c be a claim that counts and isn't released, and s a change the
root's node committed with c in its history and no other claim of the name that isn't
released (c is settled). Let c' be any other claim of that name. It isn't in the
history of s. The root is on every line, so s is a change by the side of c' with c in
its history and not c': c' is late against c, in every set of changes holding s, for
good. A late claim never holds a name while a rival that counts stands. So nobody
takes the name by a claim out of its sight. (A claim in its sight is one c was made
after, released then: c loses to it if that release stops counting, which is the
release's signer cutting off the key that signed it.) A new root changes nothing in
this: the old one stays on the lines of everyone it was on, and its changes stay what
they are.

What is left to an adversary: making c late too, so that none remains. That takes a
change by a node of c's own side with c' in its history and not c. An honest node
that received c first never commits one: everything it commits after has c in its
history. So it takes a node of the claimant's line that lies, or that truly received
c' first. If that node also committed changes with c and not c' (it was up), both
orders are in the document under its user's name, and the registry says so.

Before the root saw c: a claim c' out of its sight isn't late unless its own side
shows otherwise, so the two contest each other, or, where c's line saw c' first and
says so, c' holds. That is first come, first served as far as anyone can witness it.

What the assumptions are: signatures and hashes hold; an honest node's changes build
on all it has received (Automerge does that); the changes the root's nodes commit
count (their node keys aren't stolen, or are cut off once they are).

**Promise 6.** No rule for what users write reads a vote or waits for another party;
a write is refused only by what its own history holds, and counts from the start.

**Promise 7.** Let E be the voters present at a decision's dependencies, n of
them, fewer than a third malicious.

* *None that honest users didn't want.* A decision that counts was taken up by more
  than 2n/3 of E, so by the nodes of more than n/3 honest ones. An honest node takes
  up only a decision that is valid as written, so one with the votes of more than
  2n/3 of E, more than n/3 of them honest, and only while those votes ran.
* *One per matter.* Take two decisions following the same one, each made out of the
  other's sight (in sight, the second is refused). An honest voter takes up, by its one
  node, the first that reaches it and no other. Each was taken up by more than half
  of all the voters, so some voter took up both: with no voter malicious that can't
  be, whatever the network does. With malicious ones: where both have the same
  voters present, each needs more than 2n/3 of them, so more than n/3 took up both,
  one of them honest, which can't be. The voters present are the same, but for those
  who went absent in between, as long as voters that are up reach each other within
  the absence period. Across a partition longer than that they differ, and the
  voters that took up both may all be malicious: that is not promised against.
  Decisions of an earlier epoch are out of reach: a node acts on those of its own.
* *Not from the past.* An honest voter takes a decision up only while its votes
  run, so one crafted later with old dependencies, or kept back, has only its
  makers' records: it counts only if they were two thirds of the voters then,
  and write the records now. That is what "then or later" is for, and why a node
  that was up holds such a decision back.
* *The clock.* The swarm's time is a time that a third of the voters stamped at
  or after. Fewer than a third, stamping ahead, leave it at an honest stamp or
  before: nobody honest and up is made absent. Stamping behind, or not at all, makes
  only themselves absent.
* *A remake changes nothing.* The snapshot is a function of the base, the decision's
  history, which every node holds and judged itself. A decision chooses the base, and
  an honest voter's node takes up none that leaves out what it holds. Who votes
  next is in the snapshot: the first users present at the base, for all to see
  before they vote for it.
* *Nobody is moved.* A node follows a change of policy only by its operator's word,
  and with it whoever the proposal names to vote.

**Unvouching** takes away no more than its signer could have kept from seeing: what
the unvouched user signed stays if a node of the unvoucher or the root committed a
change that has it in its history and not the unvouch. Those changes can't be taken
back, so the point only moves forward as more of them show up.

## Roads not taken

* **Agreement among the parties for every write** (PBFT and the like) would give one
  order of claims, final at once. It needs a fixed set of voters of which fewer than
  a third fail, halts the smaller side of a partition, and makes every claim wait for
  a round. It works against what continuum is for: no node special, each working on
  its own, both sides of a partition going on. Here only decisions take it, a few a
  year.
* **A registrar**: every claim signed by the root before it counts. That is the
  root's witnessing made a condition: one order, but nothing counts while the root is
  away, and the root decides alone. Here the same witness only makes final what
  already counts.
* **Deciding by a hash or a timestamp** of the claims: whoever crafts later chooses
  the lower hash and the earlier time.
* **Deciding by seniority** (the user nearer the root holds the name): always a
  holder, but a senior user whose line kept silent takes a junior's name by
  backdating, and a root that lies takes any. Contested, with `release` to give a
  name up, fails safer: a name is blocked in the open, not taken.
* **Votes by nodes, or by every user**: a party runs as many nodes, and brings in as
  many users, as it likes. Only whom the root brought in itself can't be multiplied
  by anyone but the root.
* **Two thirds of all the voters**, absent or not: no two decisions whatever the
  network does, malicious voters or not, but a third that left for good ends all
  decisions. Leaving the absent out, down to half, lets those who stay decide; the
  price is a malicious voter on both sides of a long partition.
* **A majority, not two thirds**: with votes that take days and nodes that take a
  decision up one by one, a voter that takes up two decisions of one matter must
  not be able to tip both. Two thirds stand that against fewer than a third; a
  majority stands it against nobody.
* **The root's clock** for who is absent and when votes run out: the root is the one
  being replaced.
* **A document per user**, each written by one party, a claim counted across them (as
  in Secure Scuttlebutt's feeds). A fork of an actor then spoils only the forker's
  own document, not the swarm, which is the one thing this design can't give. It
  needs what continuum doesn't have: many documents, and what one had seen of the
  others recorded by hand. One Automerge document records that by itself.

## What members are trusted with, then

[`trust.md`](trust.md) lists what a member can do today. In a federated swarm:

| Today | Then |
|---|---|
| Write or delete any user data | Only envelopes, of users it carries for; nothing plain, nothing deleted from a register |
| Write as any user | An envelope needs the user's key |
| Edit the member and user registries | Its own member entry; users come and go by statements, which only add |
| Forge votes, commit a remake alone | Votes are users', signed; a decision takes two thirds of the voters; every node builds the snapshot itself |
| Make the swarm forget peers | A forget record of another's node is refused; whom a node talks to is its own |
| Advertise an epoch a rejoining node follows | A node follows a decision it sees count, or an epoch its operator gave it |
| Be a joining node's first sync | Judged from the root on, by the policy in it |
| Say it is ready, be a catch-up source | Still believed: it can hold changes back, not add any. A joiner syncs with the others after |
| Sign a token every node takes | Taken by its own party's nodes only |
| Say whom it reaches, how stable it is | Still believed: it bends who syncs with whom, which the links along the line bound |
| Say when it was alive | Believed for itself only; a third of the voters together move the swarm's time |

"Member" stays the word for a node in the swarm; the unit that is trusted or not is
the party.

## Continuum, or the application

In continuum, as rules every node judges by and data that parametrizes them: users by
statements (creating, vouching and unvouching, keys, cuts, nodes that carry), the
namespace rule, claims by kind with their rules and limits, late and contested, bans,
decisions by the voters with the swarm's time, the root's seat, remakes that
every node builds, a change of policy as a fork, resolving and its API, the drop an
operator asks for, the links along the line. All of it is general: a swarm with other
kinds, or none, uses the same.

In the application, for the registry: which kinds there are and their rules (data in
the root), what a host's entry holds, the client that signs (an extension of
`scripts/continuum-signed`), moving the repository in, and writing out the files the
consumers read. Whether a host's entry may use a name is the application's check
against the resolved registry, when it writes the files out.

More policies later are more data where a rule has a parameter, and a new rule in
continuum, with a policy version, where it hasn't; either way a change of policy.

What changes in continuum besides the rules, under the federated policy only: policy
version 2; the envelope's payload names the user ID and the epoch; a node is given
its root, syncs under no policy it doesn't know, takes tokens from its party only,
writes no sessions into the document, keeps its creator's nodes as neighbours,
answers for an epoch it left while it keeps it, and takes no remake but one its first
users decided. No message changes. [`trust.md`](trust.md), [`access.md`](access.md),
[`remakes.md`](remakes.md) and the glossary get the federated case: party, statement,
line, first user, voter, claim, cut, late, contested, settled, the swarm's time, and a ban
of a user beside a ban of a node.

## Attacks

Each with what honest nodes do, the promise it touches, and what shows it: `unit` in
the module named (`access::statements`, `access::claims`, `access::resolve`,
`access::decisions` are new), `sim` a simulation in `src/simtest/federation.rs`,
`argued` where no test can.

Statements and users:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 1 | Signs a statement with a key that isn't the user's | Refuse | 3 | unit, statements: `a_statement_needs_its_users_key` |
| 2 | Puts another user's statement into a change of its own node | Refuse: its node doesn't carry for the signer | 3 | unit: `only_a_users_node_carries_it` |
| 3 | Replaces or deletes a statement, or what holds the register | Refuse | 2, 3 | unit: `a_register_only_grows` |
| 4 | Offers a statement again; or an envelope signed for another swarm, epoch, path or user ID | Nothing where it is there under its digest; refuse elsewhere | 3 | unit, exists for swarm and path: `what_an_envelope_must_be`; `signed_for_its_user_id_and_epoch` |
| 5 | Creates a user listing a victim's public key beside its own | The victim's envelopes name the victim's ID: they count for no other | 3 | unit: `a_key_in_two_creations` |
| 6 | Users vouch for each other in a ring away from the root; a user vouches for its creator | None is vouched for by it | 3 | unit, resolve: `no_line_no_user` |
| 7 | Creates a name in sight of its creation | Refuse | 4 | unit: `a_name_created_once` |
| 8 | Creates a name another has, with old dependencies | Hold both; late once the root saw the first; contested at worst before | 4, 5 | unit: `a_backdated_creation_is_late` |
| 9 | Gets a user's name contested to free its names | Its claims stand without the name | 5 | unit: `claims_stand_without_the_name` |
| 10 | Creates many users, each claiming many names (sybils); creates them out of each other's sight to pass the limit | Refuse past the limits in sight; out of sight, those past them don't count. The limits bound how fast users come, not how many: each is on its creator's line, for all to see, to ban, and to go with it when it is unvouched | 6 | unit: `limits_on_creating`, `past_a_limit_out_of_sight` |
| 11 | Adds keys, nodes or statements without end | Refuse past the limits | 6 | unit: `limits_on_a_register` |

Unvouching:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 12 | Unvouches a user it didn't vouch for | Refuse | 3 | unit: `only_the_voucher_unvouches` |
| 13 | Unvouches with old dependencies, to undo what the user did since | What its own nodes or the root's had seen of the user stays | as said under Unvouching | unit: `an_unvouch_undoes_nothing_seen` |
| 14 | The unvouched user signs on, with dependencies from before, or across a partition | Hold it as part of another's history only; it doesn't count; after healing every node finds the same | 2, 3 | unit: `past_an_unvouch`; sim: `an_unvouch_across_a_partition` |
| 15 | A user is unvouched: what of those it brought in, and its names? | They stop counting from the same point unless another vouches for them; a vouch after brings them back whole. Its names are free in sight of the unvouch | 4 | unit: `those_it_brought_in`, `a_vouch_brings_back`, `free_in_sight_of_the_unvouch` |
| 16 | An unvouched user's nodes keep sending | Refused as peers; nothing taken from them | 6 | sim: `nothing_from_an_unvouched_node` |

Namespaces:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 17 | Writes into another's namespace, signed by itself | Refuse, and the node as a whole | 3 | unit: `a_namespace_is_its_users`; sim, as `a_member_writing_against_the_rules` today |
| 18 | Writes plain values, or protocol data but its own member entry | Refuse | 3 | unit: `nothing_plain` |
| 19 | Puts an old envelope back | Refuse: it doesn't replace what is there | 3 | unit, exists: `what_an_envelope_must_be` |
| 20 | A user with a late creation of a name writes in the namespace | Refuse where its change's history shows it lost the name; else hold it and leave it out | 3 | unit: `a_user_that_lost_its_name` |

Claims:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 21 | Claims a held name in sight of the claim | Refuse | 4 | unit, claims: `first_come_first_served` |
| 22 | Claims a settled name with old dependencies, long after | Hold both; it is late, the holder holds | 5 | unit: `a_backdated_claim_is_late`; sim: `a_backdated_claim_loses` |
| 23 | Two honest users claim on two sides of a partition | Hold both; every node finds the same: one holder, or contested; a release leaves one | 2, 4 | sim: `a_partition_heals_to_one_answer`; unit: `a_release_ends_a_contest` |
| 24 | Claims `x.tv.r` as another; claims a top-level domain, as another or as a late creation of the name `tv` | Refuse: the kind's rule; a kept name needs no claim; a claim by a user that doesn't have the name its rule gives doesn't count | 4 | unit: `a_kinds_rules`, `a_kept_name`, `a_rule_goes_by_who_has_the_name` |
| 25 | Claims past its limit, in sight or out of sight of its other claims | Refuse in sight; out of sight, those past the limit don't count | 4, 6 | unit: `a_limit_in_sight`, `past_a_limit_out_of_sight` |
| 26 | A user on the claimant's line says it saw a rival first, after the claim is settled | The name is contested; the registry names the changes and the user, and marks it if it showed both orders | not promised | unit: `a_line_contests`; sim: `both_orders_show` |
| 27 | A whole line kept silent, then claims with old dependencies | Before the claim is settled: contested. After: late | 5 | unit: `silence_before_settling` |
| 28 | Releases a claim with a stolen key, an accomplice claims | Once the key is cut off the release doesn't count: the accomplice's claim, in sight of the first, loses to it | 3, 4 | unit: `a_release_cut_off` |

Keys:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 29 | Steals a device key and signs with it | Take it until a key above cuts it off, then leave out what is outside the cut; a value it replaced is read again | 3 | unit: `a_retired_key_counts_within_its_cut`, `the_value_before_counts_again`; sim: `a_stolen_key_cut_off` |
| 30 | Signs with a retired key and old dependencies | Hold it (valid as written), leave it out | 3 | unit: `backdated_past_a_cut` |
| 31 | With a stolen device key, retires the keys above or beside it | Refuse | 3 | unit: `no_key_retires_one_above` |
| 32 | With a stolen device key, retires that key from long ago, to undo what its user signed | Refuse: a key retires itself from where it stands | 3 | unit: `a_key_retires_itself_forward` |
| 33 | Steals a user's first key | That user is lost: it is unvouched, and created again under another name | not promised | argued (Cuts) |
| 34 | Cuts its own key off early to take back a vouch or a release | It is taken back; a user with a second vouch stays | not promised | unit: `a_second_vouch_stands` |
| 35 | A key is retired on one side of a partition while it signs on the other | After healing, every node leaves out the same | 2 | sim: `a_cut_across_a_partition` |
| 36 | Steals a node's key: commits changes as a witness | They count until the node is stopped with a cut, then not | 5 | unit: `a_stopped_node_witnesses_nothing` |

Decisions, the root, remakes:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 37 | Forges a vote; votes as a user that isn't a voter, or one absent | Refuse | 7 | unit, decisions: `a_vote_is_a_voters` |
| 38 | Brings in many users to vote | They don't: only those a root created come to vote | 7 | unit: `who_votes` |
| 39 | The root creates many first users to carry a vote | They vote from the next remake on, which takes two thirds of the voters there are; these see who would vote, and can replace the root first | 7 | unit: `voters_are_the_epochs` |
| 40 | Decides without the votes, or with released ones | Refuse | 7 | unit: `a_decision_as_written` |
| 41 | Crafts or keeps back a decision until its votes ran out, then shows it | No honest voter takes it up: it doesn't count. One that counts by its makers' own records, long after (two thirds of their node keys stolen), is held back by every node that was up, and shown | 7 | unit: `taken_up_while_the_votes_run`; sim: `a_decision_from_the_past` |
| 42 | Two decisions of one matter, out of each other's sight | Each node takes up the first it receives; at most one counts | 7 | sim: `one_decision_a_matter` |
| 43 | Stamps its nodes far ahead, to make the others absent | The swarm's time stays at a stamp a third reached | 7 | unit: `the_swarms_time_by_a_third` |
| 44 | Stays away to hold decisions up | Absent after 30 days: it doesn't count. Half the voters staying away do hold them up: the rest fork | 7 | unit: `absent_users_dont_count`, `more_than_half_of_all` |
| 45 | Decides a remake at a base that leaves out what the swarm holds | No honest voter's node takes it up | 7 | sim: `a_stale_base_is_not_taken_up` |
| 46 | Runs most of the nodes; serves a snapshot of its own | Nothing reads a count of nodes; every node builds the snapshot itself | 7 | sim: `every_node_builds_the_snapshot` |
| 47 | Signs a claim "in the epoch before" after a remake, to pass as carried over | It contests only what the snapshot holds unsettled, until the root's node wrote in the new epoch; then it is late | 5 | unit: `carried_over_or_pretending` |
| 48 | A thief's statements are in the base of a remake | They stand: a remake makes final. The vote's days are the time to cut the key off | not promised | unit: `a_cut_reaches_to_the_snapshot` |
| 49 | Tells a node that was away of an epoch that isn't the swarm's | The node finishes the old epoch from archives and builds the next itself; or takes the ID its operator gave | 1 | sim: `away_over_a_remake` |
| 50 | The old root comes back after its seat went; crafts users "from before" | It is a first user; what the decision's history doesn't hold of it is an ordinary user's | 7 | unit: `the_old_root_comes_back` |
| 51 | Two thirds of the voters turn on the rest | They remake, seat a root, set the numbers. They forge nothing, take no settled name, move nobody to other rules; the rest ban, stay, or fork | not promised | argued (A change of policy is a fork) |
| 52 | Offers a statement signed on the other side of a fork | Refuse: it names its epoch | 3 | unit: `signed_for_its_user_id_and_epoch` |
| 53 | A change of policy with two thirds; a fork naming its proposer the only voter | A node follows only by its operator's word, which names the decision; what that says shows | 7 | sim: `a_fork_by_choice` |

Nodes and syncing:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 54 | Sends different changes to different peers, each under its own number | Take all: changes made at once | 2 | sim: `two_histories_merge` |
| 55 | Forks its node's actor | The nodes that took each split; one offered both holds proof and refuses the node; a side drops by its operator's choice | not promised | sim: `a_forked_actor_is_proven`, `a_side_drops_a_fork` |
| 56 | Holds changes back, or passes on some | They come by other nodes; a joiner caught up with it syncs on | 6 | sim: `withheld_changes_arrive` |
| 57 | Places its nodes around a victim by choosing their keys | The victim's node also syncs with its creator's | 5, 6 | sim: `around_a_victim` |
| 58 | Hands a joining node another root, or changes from before the policy | Refuse the handshake; there is no before | 1 | sim: `a_joiner_takes_its_root_only` |
| 59 | Signs a token for any user with its node's key | Not taken by another party's node | 3 | unit: `a_token_of_ones_party` |
| 60 | Lies in its member entry (ready, reached, stable) | Sync and trees bend; nothing gets in that way | 6 | argued (Reaching one's line) |
| 61 | Sends envelopes that don't check, without end | Refuse each (a signature costs about 30 µs to check *(docs)*); the node is refused as a whole after the first of its own | 6 | sim: `a_refused_node_costs_little` |
| 62 | Writes its own member entry without end; fills the waiting changes | Take them no faster than a budget per party: put off, never refused; a share of the waiting each | 6 | sim: `a_party_past_its_budget_waits` |
| 63 | Crafts a change Automerge won't take, or that writes in an object nowhere to be found | Refuse *(checked: the rules refuse the second today)*; only the message that brought it fails | 1 | unit: `a_change_writing_nowhere` |

Rules, and the swarm as it is:

| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
| 64 | A rule differs between versions (a bug) | Each side refuses, logs that the policies disagree, shows the peer refused; one side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back` |
| 65 | A policy version a node doesn't know | It doesn't sync | 1 | unit: `no_sync_under_an_unknown_policy` |
| 66 | A root that lies and isn't replaced; a user nobody unvouches | The parties ban it from a cut on and read on without it | not promised | unit: `a_ban_for_those_who_follow` |
| 67 | A banned user's name claimed by one who bans it | The node refuses its own user's write: the others would | 1 | unit: `no_write_by_ones_bans_alone` |
| 68 | A partition that outlasts the absence period | One side at most decides: a decision takes more than half of all the voters. With a malicious voter on both sides of an even split, both may: the two undo each other, or are two epochs the parties choose between | 7, not promised | sim: `one_side_decides`; unit: `two_that_count` |
| 69 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |

## The registry on it

```
_continuum/users/tv/<digest>            statements about and by tv
_continuum/claims/ip4/10.243.0.7/<d>    tv's claim of 10.243.0.7
_continuum/claims/name/r/<d>            tv's claim of the top-level domain r
tv/hosts/toaster                        envelope: {"nets": {"retiolum": {
                                          "ip4": "10.243.0.7", "ip6": "42:0:…",
                                          "aliases": ["toaster.tv.r"],
                                          "ed25519": "…" }}}
```

`toaster.tv.r` is kept for tv by the kind's rule and needs no claim. An IPv6 address
is generated from the net, the user's name and the host's today; a kind `ip6`, first
come, first served like `ip4`, holds whether or not anyone generates honestly.

**Moving in.** The root is made from the repository by a script
(`scripts/kartei-import`): the kinds and their rules; the maintainer as the root, with
its keys and nodes; and for each namespace of the repository its hosts as they are,
plain, their addresses as claims in the namespace's name, and the name kept for the
root to create (a rule of the kind `user`), so nobody else creates a user over a
namespace that is there. The root is trusted as it is (every party is given its
hash), so what it holds counts without signatures: a host from the root counts until
its user signs over it, and a claim from the root is held by whoever has its name.
The maintainer then creates each user as it comes with a key; from then on the user
signs its own, and is a first user: it votes from the next remake on. A namespace
whose user never comes stays as the root has it.

**Writing out.** `scripts/kartei-export` reads the resolved registry from a node its
operator trusts (its own) and writes the tree the consumers read
(`<user>/hosts/<host>/retiolum/{aliases,ip4,ip6,ed25519.key}`), leaving out what
doesn't count and any address or name its host's user doesn't hold. Run on each
change of the document (the store's stream), it replaces the merge button.

## Stages

Each leaves the system working, and is a few patches with its tests. At every stage
the existing tests pass untouched (69).

1. **A federated swarm's frame.** `--genesis-policy` (a file, written into the
   genesis change with the root, its keys and nodes); a federated node is given its
   root, syncs under no policy it doesn't know, takes no remake yet, takes tokens
   from its party only, keeps ended sessions to itself. Tests: 58, 59, 65, 69, and
   the policy's existing tests under a policy from the root.
2. **Statements.** The users' registers (`create`, `key`, `node`, `vouch`,
   `release`), the user ID and the epoch in envelopes, nodes carrying for users and
   the rule for committers by it, nothing plain, limits. Resolving, step 1 without
   cuts, and `GET /registry/users`. The client signs statements. Tests: 1 to 7, 10,
   11, 18.
3. **Namespaces.** The rule, with `userSigned` below a name. Tests: 17, 19. From here
   the registry runs with users and hosts, names not yet unique.
4. **Claims in sight.** Kinds, rules, kept names, limits, `claim` and `release`,
   judged as written; resolving step 4 for claims in sight. Tests: 21, 24, 25.
5. **Out of sight.** Late, contested and settled, for names and for users' names;
   the root's node writing when a claim reaches it; `GET /registry/claims` with what
   makes a claim late; values marked in `GET /store`. The links along the line.
   Tests: 8, 9, 20, 22, 23, 26, 27, 54, 56, 57.
6. **Cuts.** `retire` and the keys above, a node that stops, what doesn't count left
   out, the value before read again, the client listing what stopped counting. Tests:
   28 to 32, 34, 35, 36.
7. **Unvouching.** `unvouch`, a user giving itself up, those brought in going with
   it, nothing taken from an unvouched user's nodes. Tests: 12 to 16.
8. **Coming back.** The drop an operator asks for, a forked actor proven and shown
   with what the line holds, the budget and the share per party. Tests: 55, 61, 62,
   63, 64.
9. **Bans** for those who follow. Tests: 66, 67.
10. **The registry.** Import, export, and a federated swarm of the simulations with
    the registry's kinds and a few hundred hosts. From here it can be used; it only
    grows.
11. **Decisions.** The voters a root change names, the swarm's time and who is
    absent, `propose`, `vote` and `decide`, taking up, what counts,
    `GET /registry/decisions`; the voting numbers. The simulations start from a root
    change naming several voters, as a remake's does. Tests: 37 to 44, 68.
12. **The root's seat.** Tests: 50.
13. **Remakes.** The base, the snapshot every node builds, carrying over, what
    becomes final; peers answering for an epoch they left; a node given an epoch's
    ID. Tests: 45 to 49.
14. **A change of policy.** The fork, followed by an operator's word, with who votes
    on its side. Tests: 52, 53.

## Open questions

Each with what I'd choose.

1. **Who votes.** The first users an epoch starts with (as designed): nobody but the
   root brings one in, and none votes before two thirds of the voters remade, so a
   root can't fill the votes. The price: the root decides alone until the first
   remake. Or first users from when they come: then a root that turns bad stays. Or
   after a wait without a remake, which needs a user's age read from what others
   saw of it. Or users further down, to a depth the policy names: then every first
   user brings voters in. *As designed.*
2. **Two thirds, or a majority?** Two thirds of those present (as designed) stand
   against fewer than a third malicious; a majority is easier to gather and stands
   against nobody who takes up two decisions. And of whom: with the absent left out
   down to half of all (as designed), those who stay decide, and a malicious voter
   can make two decisions across a long partition; with two thirds of all, none
   can, and a third leaving ends all decisions. *As designed.*
3. **Throwing a user out by decision**, for everyone, where its voucher won't unvouch
   it. Not designed: bans are each party's. It would make two thirds of the voters
   the judges of who is in. *Later, if bans prove too weak.*
4. **Does cutting a key off take back what others rely on**, a vouch, a release? Yes
   (as designed): what a thief signed must be undone. Or not for what another user
   built on: then a thief's puppets stay for good. *Yes*, with the second vouch as
   the remedy.
5. **How far an unvouch reaches back**: to what its signer's nodes and the root's had
   seen (as designed). Or only forward from where each node receives it, which no
   node can read from the document. *As designed.*
6. **A user's first keys** have none above them: stolen, the user is lost. Several
   first keys of which a number must sign to cut one off would mend that; continuum
   has no rule for several signatures yet. *Later.*
7. **The numbers**: `window` 7 days, `absent` 30 days; 64 keys and 8 nodes a user
   at once, 16 users a creator (the root: no limit), 64 addresses a user; ten
   minutes a remake's base may lack. Guesses; the policy carries them, and the
   first two change by decision.
8. **How long peers answer for an epoch they left**: `archiveRetention`, 30 days
   today. A node away for longer needs the new epoch's ID from its operator. *90 days
   in a federated swarm.*
9. **A user without a node** names another party's to carry for it. Allowed as
   designed: that node's changes then witness for both. Fine?
10. **What the root holds unsigned** (the repository as it is) counts until signed
    over. Or the import waits until every user has a key. *Count unsigned*: the
    repository is what is trusted today.

Settled: a name is contested, not the senior's, with `release` to give it up; one
root, whose seat is decided anew; votes by users, over days, by numbers a decision
changes, the absent left out; unvouching as above; a change of policy as a fork; the
mode optional.

## What was checked, and what is assumed

Checked in the code:

* A change is judged at its dependencies, or at heads that hold the same for what
  rules read, before it is applied; a refused change keeps out what builds on it; a
  member whose own change broke a rule is refused as a whole (`access::rules`,
  `access::screen`).
* What screening takes as read by rules is a list (`screen::relevant`).
* An envelope is checked for its swarm, path, `prev`, signature, and its user's key
  in the registry as the writer saw it (`access::envelope::check`).
* The genesis node writes the users it starts with and their keys in its first change
  (`access::registry`), so the policy can be written with them.
* Automerge refuses a second change at an actor's number (`DuplicateSeqNumber`), and
  gives the change that made an operation (`hash_for_opid`), so the change carrying a
  value is found from the document.
* A drop exists and does what coming back needs (`AppState::drop_taken`); what is new
  is an operator asking for one its own rules wouldn't make.
* Neighbours are computed from the member list by key hashes (`swarm::topology`).
* A member's entry holds its alive stamp as Unix milliseconds (`swarm::members`).

From the docs: a node under an unknown policy receives without judging; every node
takes a token any member signed; alive stamps about daily; where a refused member
shows; the cost of checking a signature; a node keeps the documents of epochs it left
for a while, and every node builds a remake's snapshot itself today.

Assumed, to be shown as it is built:

* Whether a change is in the history of a cut, or of a witness's change, can be
  answered cheaply enough: per actor, the last number within that history, kept per
  cut and per claim that has a rival. Statements and rivals are few.
* Resolving kept as the node goes costs little per change. Judging at old
  dependencies reads the registers there (`document::at`), as an envelope's check
  does today.
* Writing a quarantined statement again as it is works after a drop wherever what it
  builds on still holds.
* A node can keep neighbours beside those the graph gives (its creator's nodes).
* A limit counted at a change's dependencies (a kind's claims by one user) is read
  fast enough from the register; an index kept beside it otherwise.
* Who lost a user name as a change's history shows it (judging, 6 and 7) is worked out
  only where a name has several creations there, which is rare.
* The snapshot of a federated remake, built from the resolved registry, comes out
  byte for byte the same on every node, as today's does from the document.
* A node can answer sync for an epoch it left, from its archive.