diff options
Diffstat (limited to 'docs/federation.md')
| -rw-r--r-- | docs/federation.md | 1253 |
1 files changed, 1253 insertions, 0 deletions
diff --git a/docs/federation.md b/docs/federation.md new file mode 100644 index 0000000..947da71 --- /dev/null +++ b/docs/federation.md @@ -0,0 +1,1253 @@ +# 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. |