aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-15 12:34:03 +0000
committertv <tv@krebsco.de>2026-11-15 12:34:03 +0000
commit44e9b3920111ae47f116d893b1872bf3e07eab3f (patch)
tree639fea641f215e4dacca1f0ff899a94de3a5b0ba
parentb6fe90fa83238b8ffa10421d876b988152115271 (diff)
federation: order by seq and number, votes of yes and no, forks as swarms
What a place holds is read by its envelopes' `seq`, the current version by its number, a party's keys by one envelope's `seq`: nothing by the order of operations, which a change's writer steers. - A version is a string named by its hash, numbered, written at `versions/<hash>` by any member once it passed, counting by its votes and not its writer, and current only once written. - A vote is `true` or `false` at `votes/<party>/<version>/<proposal>` and never changes. A proposal passes with the share's yeses and is dead once the nays leave too few; a party backs one proposal at a time, and another once the first is dead. So a split ends on its version. Two versions with one number are written only if a party voted twice; the lower hash is read. - A party's keys are one envelope, or what a version set. A first envelope at a place names its party's keys, so it can't be put back once they changed; deletions need no rule of their own. - Rules start with a literal segment; `{party}` is a whole segment; a writer is a party, `{party}` or `false`. How names and addresses are spelled as paths is the application's. - What counts no more: five things; any member deletes them, judged by the document the deleting change makes. - A fork is a swarm of its own, started from the document with the version the group wants. - Becoming federated closes the history before it. A node that didn't hold the epoch before takes a remake on its peers' word, which promise 1 now says. Tokens come from one's own party's nodes only. - A list of attacks, each with what happens and how it is tested.
-rw-r--r--docs/federation.md578
1 files changed, 326 insertions, 252 deletions
diff --git a/docs/federation.md b/docs/federation.md
index 7cd4289..8907915 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -14,13 +14,13 @@ are marked *(checked)* where they were read in it.
## Optional
-A swarm is federated once its policy says so, and which federation it follows: this design
-is federation 1. It can say so from the genesis change, or later, written by one who may
-write the policy (The policy), and stops, or moves to another, by a version of its policy
-(Changing the policy). Nothing else changes: a swarm that doesn't say so stays as it is,
-its registry, rules, remakes and replay included. Continuum's wire version says only
-whether a node can take part in a federation at all; which federation a swarm follows is
-its own number (Changing the federation).
+A swarm is federated once its policy says so. It can say so from the genesis change,
+or later (Becoming federated), and stops by a version of its policy (Changing the
+policy). Nothing else changes: a swarm that doesn't say so stays as it is, its
+registry, rules, remakes and replay included. Continuum's wire version says only
+whether a node can take part in a federation at all; which federation a swarm follows
+is a number of its own, in its policy: this design is federation 1 (Changing the
+federation).
## Parties and the adversary
@@ -50,314 +50,384 @@ that nothing coming from any node breaks a promise for the others.
## What is promised
1. **What counts is what a party signed, with a key it holds, where the policy lets it
- write.** Every honest node refuses what no policy would let be written, whoever
- sends it, and reads nothing else as counting.
+ write.** Every honest node that holds the swarm from its genesis change refuses
+ what no policy would let be written, whoever sends it, and reads nothing else as
+ counting.
2. **The policy changes only by the votes of a share of its parties**, two thirds
- unless the parties decide otherwise, and nodes that hold the same changes read the
- same policy. That holds as long as fewer than a third of the parties vote twice
- (Changing the policy).
+ unless they decide otherwise, as one history saw their votes; and nodes that hold
+ the same changes read the same policy. A version that passed stays, as long as no
+ party votes twice (Changing the policy).
3. **Any group carries on as it chooses.** Its parties fork with the policy they want,
and whoever wants to follow does. Nobody is held by parties it doesn't follow.
-Not promised: progress without the parties' cooperation (those who cooperate fork,
-and carry on); that a party votes well; that what a party's nodes withhold reaches
-anyone; that the swarm stays fast. A party that floods the document makes nodes slow,
-not wrong: denial of service breaks no promise here.
+Not promised:
+
+* progress without the parties' cooperation: those who cooperate fork, and carry on;
+* that a party votes well;
+* that what a party's nodes withhold reaches anyone;
+* that the swarm stays fast. A party that floods the document, or whose nodes keep
+ remakes from committing, makes nodes slow, not wrong: denial of service breaks no
+ promise here, and the others fork away from it;
+* anything to a node that joins, or comes back after a remake without holding the
+ epoch before: it takes the document on its peers' word (Remakes).
## The design
-It builds on the strict policy ([`access.md`](access.md), Values signed by their
-users): values as envelopes their parties sign, which every node checks against who
-may write there, as the document stood when they were written.
+It builds on values signed by their users ([`access.md`](access.md)): a value is an
+envelope its party signs, `cv2.<value>.<meta>.<signature>`, the meta naming the swarm,
+the path, who signed, the envelope it replaces (`prev`) and its number (`seq`, one
+more than that one's). Of the envelopes a place holds, written at once, the one with
+the highest `seq` is its value, of equal ones the one with the lower SHA-256 *(checked:
+`document::store`, `access::envelope`)*. So what a place holds is its party's to say,
+never the order of operations, which whoever writes a change steers.
### What it asks of the document
* **A change's history**, fixed by the change's hash: what its writer had seen. A
change is judged at its history and nothing else.
* **The document at a set of changes**: the tree its writes make, the same on every
- node for the same set. Where two changes wrote one place at once, one is shown, the
- same on every node, and all are held. A deletion removes what its writer saw, and
- nothing written at the same time.
+ node for the same set. A deletion removes what its writer saw, and nothing written
+ at the same time.
* **Remakes that lose nothing and add nothing**: whatever continuum does to start the
- document anew, a node follows it only where the new document holds what the old one
- held at the base (Remakes).
+ document anew, a node follows it only where the new document reads as the old one
+ did at the base (Remakes).
-Every head of an epoch commits to the epoch's root change, and that root to the epoch
-before and the base it was made from, back to the genesis change *(checked:
-`access::rules`, one root an epoch; `remake::snapshot`, the previous epoch and the base
-heads in the snapshot)*. Continuum's document is an Automerge document, which gives
-all of this and has limits worth knowing (Where Automerge sets limits).
+Continuum's document is an Automerge document, which gives all of this and has limits
+worth knowing (Where Automerge sets limits).
### The policy
-A swarm becomes federated by `_continuum/access/policy` being `{"version": 2, "values":
-"signed", "federation": 1}`, written together with the policy's first version: in the
-genesis change, or later by one who may write the policy. What was written before then
-counts only as anything does, where a key of a party signed it and the first version lets
-that party write there; the rest doesn't count. From then on, the policy is a chain of
-**versions**, each one JSON value, named by the SHA-256 of its canonical form, naming the
-version it changes (none for the first):
+A federated swarm's `_continuum/access/policy` is `{"version": 2, "federated": true}`.
+What the policy says is in its **versions**, a chain: each is a string of JSON, named
+by the SHA-256 of its bytes, numbered, and naming the version it changes (none for
+the first, number 0):
```json
-{ "changes": "<hash of the version it changes>",
+{ "federation": 1, "number": 7, "changes": "<hash of the version it changes>",
+ "share": [2, 3],
"parties": ["tv", "lass", "makefu"],
"keys": { "makefu": ["ssh-ed25519 AAAA… makefu"] },
"rules": [
- { "path": "{party}/**", "writer": "{party}" },
- { "path": "names/{party}.r", "writer": "{party}" },
- { "path": "names/{party}.w", "writer": "{party}" },
- { "path": "names/wiki.r", "writer": "lass" },
- { "path": "ip4/10.243.0.5", "writer": "tv", "value": { "type": "string" } },
- { "path": "names/*", "writer": false } ],
- "numbers": { "share": [2, 3], "limits": { "proposals": 8, "nodes": 64 } } }
+ { "path": "home/{party}/**", "writer": "{party}" },
+ { "path": "names/r/{party}/**", "writer": "{party}" },
+ { "path": "names/r/wiki", "writer": "lass" },
+ { "path": "ip4/10/243/7/*", "writer": "tv" },
+ { "path": "names/**", "writer": false } ] }
```
+* **The federation** it follows, and its **number**, one more than that of the version
+ it changes.
+* **The share** of the parties a proposal needs, two whole numbers: with `[2, 3]`, the
+ votes of two of every three (3·votes ≥ 2·parties). More than a half, at most all.
* **The parties**, by name.
-* **The keys it sets**: those of a party new in it, or of one whose keys it replaces.
- The version holds them only to set them: the change that writes it as current writes
- them as the party's keys, in place of any it had (Keys).
-* **The rules**, in order: the first whose path matches a path says who writes there. A
- path is segments separated by `/`; a segment of a rule is literal, `*` (any one
- segment), `**` (any number of them, last only), or holds `{party}` (the segment with a
- party's name in its place: `{party}.r` matches `tv.r`). The writer is `"{party}"` (the
- party the path names), a party's name, `true` (every party) or `false` (none). A rule
- may constrain the value (its type; for a string, its characters and length). A path no
- rule matches, nobody writes.
-* **The numbers**: `share`, two whole numbers: a proposal passes with votes of
- `share[0]` of every `share[1]` parties (3·votes ≥ 2·parties, for `[2, 3]`), which
- must be more than a half; and the limits.
+* **The keys it sets**: those of a party new in it, or of one whose keys the parties
+ replace (Keys).
+* **The rules**, in order: the first whose path matches a path says who writes there.
+ A path is segments separated by `/`. A rule's first segment is literal, and not
+ `_continuum`; any other is literal, `{party}` (a party's name), `*` (any one
+ segment) or, last only, `**` (one segment or more). The writer is `"{party}"` (the
+ party the path names, where the rule's path holds `{party}`), a party's name, or
+ `false`: nobody. A path no rule matches, nobody writes. A **place** is a path where
+ an envelope is written; nothing is written within one.
+
+How names and addresses are spelled as paths is the application's: the registry
+writes a name by its labels, last first (`names/r/tv/toaster` for `toaster.tv.r`), and
+an address by its parts, so that a party's zone or block is one rule.
-The federation's own paths are its number's, not the rules': they are what this
-design says below, the same in every version.
+A version that doesn't read as one, or breaks any of the above, is none: it can't
+pass, and a change writing it is refused.
-| Where | Who writes it |
-|---|---|
-| `_continuum/federation/proposals/<hash>` | any party |
-| `_continuum/federation/votes/<party>/<hash>` | that party |
-| `_continuum/federation/current/<chain>` | any party, once a proposal passed |
-| `_continuum/federation/keys/<party>/<name>` | that party; a version that becomes current |
-| `_continuum/federation/nodes/<party>` | that party |
-| `_continuum/federation/went/<party>` | that party |
-| protocol data of nodes (member entries, remakes, acks) | as in every swarm, by members |
+The federation's own paths are its number's, not the rules': the same in every
+version.
-Every value a party writes is an envelope, signed by one of its keys, replacing the
-one there (its `prev`), as under the strict policy. A federated swarm has no other
-registry: `_continuum/users` and the users API are closed under it, and a party logs
-in to its own nodes as its operator sets up.
+| Where | What | Who writes it |
+|---|---|---|
+| `_continuum/federation/versions/<hash>` | a version that passed | any member, once it passed |
+| `_continuum/federation/proposals/<party>/<hash>` | a version proposed | that party |
+| `_continuum/federation/votes/<party>/<version>/<proposal>` | `true` or `false` | that party |
+| `_continuum/federation/keys/<party>` | its keys | that party |
+| `_continuum/federation/nodes/<party>` | its nodes' IDs | that party |
+
+What a party writes is an envelope, signed by one of its keys, everywhere but at
+`versions`. Of continuum's own data, a federated swarm keeps what nodes write for the
+protocol (member entries, remakes and their votes, epochs), written by members as in
+every swarm. It has no user registry: `_continuum/users`, bans, and every other entry
+of `_continuum/access` are closed, and nothing reads them. A party logs in to its own
+nodes as its operator sets up, and a node takes tokens only from the nodes its own
+party lists.
### Changing the policy
-A **proposal** is a version not yet current, written by any party at
-`_continuum/federation/proposals/<hash>`, its hash the version's. The document holds at
-most `limits.proposals` of one party's proposals on one version at a time; it deletes
-one to make room. A proposal is its content, named by its hash, so whoever holds it
-may write it again.
+A **proposal** is a version a party writes at
+`_continuum/federation/proposals/<party>/<hash>`, its hash the version's.
+
+A party **votes** on a proposal by writing `true` or `false` at
+`_continuum/federation/votes/<party>/<version>/<proposal>`: the version the proposal
+changes, and the proposal, by their hashes. No vote there is no vote.
-A party **votes** by writing, at `_continuum/federation/votes/<party>/<hash of the
-version it changes>`, the hash of the proposal it votes for. A vote never changes:
-a change writing there another choice than the one it saw is refused (the same
-choice, signed again, is fine). Two different ones written at once are both held,
-and the party then counts for neither.
+* **A vote never changes.** A write where a vote is keeps its value (a party signs its
+ votes again when it changes keys). A `true` and a `false` written there at once read
+ as `false`.
+* **A proposal passes** once at least the share of its version's parties voted `true`.
+ It is **dead** once so many voted `false` that the rest are fewer than the share.
+* **One yes at a time.** A party's `true` is taken only if, at its history, every other
+ proposal on that version it voted `true` for is dead. So a party backs one proposal,
+ and is free again when that one can't pass any more.
-A proposal on the current version **passes** once at least `share` of that version's
-parties voted for it, each counting once. Then any party writes it at
-`_continuum/federation/current/<chain>` (the chain named by the first version's hash, or
-by the proposal a fork followed: Forks), together with the keys it sets, in one change;
-every node judges that change by the votes in its history. **The current version** at a
-set of changes is the one written there, or a proposal that passed on it there and isn't
-written yet.
+Once a proposal passed on the current version, any member writes it at
+`_continuum/federation/versions/<hash>`, as it is, unsigned; every node judges that
+change by the votes in its history, and by the version it changes being written
+there. **The current version** is the written one with the highest number; of equal
+ones, the one with the lower hash. A version takes effect when it is written, and
+judges every change in sight of it.
-* **Two proposals on one version both pass only if at least a third of the parties
- voted for both.** Each needs two thirds, so their voters share a third; a party that
- voted twice counts for neither once both votes are seen, but a node that has seen
- only one counts it. Honest parties vote once: a party's votes come from one place.
- With fewer than a third voting twice, there is never a choice between two, and in
- whatever order a node gets the votes, it ends at the same version.
-* **Nothing else needs to happen.** No remake: once the votes are there, every node
- reads the new version, and judges by it every change written in sight of them.
-* **What lapsed goes.** A proposal on a version that isn't current any more, and the votes
- on it, may be deleted by any member (What counts). Who wrote a proposal doesn't matter
- once it is written: it passes or lapses whether its author is still a party or not.
-* **A split vote passes nothing.** Forty, forty and twenty on three proposals is
- resolved by a new proposal enough parties agree on, or by going apart (Forks).
+* **Votes that split pass nothing**, like a proposal that gets only nays: three for
+ one proposal and three for another, of six. Those who didn't back a proposal vote
+ `false` on it; once it is dead, its backers are free, and another proposal can pass
+ on the same version. Clients vote for the proposal that leads, so that splits are
+ rare. Parties that won't wait fork.
+* **Two versions with one number** are written only if a party voted twice: `true` and
+ `false` on one proposal, each shown to some, or `true` on two. Then every node that
+ holds both reads the one with the lower hash, so nodes still agree once they sync;
+ but a node may have read the other for a while. One party is enough for that, where
+ a vote is close. Both its votes are in the document for all to see, and the parties
+ can take it out.
+* **A proposal on a version that isn't current lapses**, with the votes on that
+ version. Its party proposes it again on the current one; a client does that by
+ itself for one that touches nothing the version that passed changed.
+* **Who proposed doesn't matter** once it is written: a proposal passes whether its
+ party is still one or not.
Everything the federation decides is a change of the policy: who the parties are, and
-their keys where they lost them; who writes which identifier, which is giving one, taking
-it back and giving it to another; the rules; the numbers; and the federation itself. A
-version may name another federation by its number (Changing the federation), or none, with
-the policy the swarm goes on with (`"federation": null, "policy": {…}`), which the change
-that makes it current writes at `_continuum/access/policy`. From then on, that policy is
-the swarm's, whatever it is.
+their keys where they lost them; who writes where, which is giving an identifier,
+taking it back and giving it to another; the share; and the federation itself. A
+version may name another federation (Changing the federation), or none, with the
+policy the swarm goes on with (`"federation": null, "policy": {…}`, and the registry
+it starts with, where that policy has one), which the change that writes it puts at
+`_continuum/access/policy`. From then on, that policy is the swarm's, whatever it is.
-### What counts
+### Keys
-A change is judged at its history, by the version current there, as every node judges it
-([`access.md`](access.md), Changes judged on every node). So a value its party wrote while
-it could still write there is taken, even where a version that passed at the same time
-says otherwise. What **counts** is read by the version current in the document as a whole.
-These count no more, and nothing else is stale:
+A party's keys are those the latest version that set its keys gave it, unless the
+party replaced them since: an envelope at `_continuum/federation/keys/<party>`, naming
+that version and the keys, signed with a key of the set it replaces. The envelope's
+`seq` orders a party's sets, so an older one put back is behind.
-1. a value at a place its party may not write by the current version: the party is no
- longer one, the place went to another, a rule changed, or the value no longer fits its
- rule; and of a party that is no longer one, its keys, its node list and its `went`;
-2. a value signed by a key its party no longer holds;
-3. a deletion, once its party holds none of the keys it names (Keys);
-4. a proposal on a version that isn't current, and the votes on that version;
-5. of two values written at once at one place, the one not shown.
+* **A value counts only while the key that signed it is among its party's keys.** So
+ changing keys is: write the new set, and sign again what should stay (a client does
+ that). Nothing remembers a key that was dropped.
+* **A stolen key.** The party writes a set without it: what the thief signed stops
+ counting, and so does what the party signed with it, until signed again. If the
+ thief wrote a set first, without the party's other keys, the party has none it can
+ answer with: the parties give it new keys by a version, which is ahead of every set
+ written before. A vote the thief cast on a proposal that passed stays cast.
+* **The first envelope at a place names its party's keys**: where it replaces nothing,
+ its `prev` is the digest of its party's key envelope (or the hash of the version
+ that set its keys). So one that was replaced or deleted can't be put back later
+ where the place is empty again, once its party changed keys.
+* **Deleting a value** is writing an envelope with `null` in its place, which stays as
+ any value does, while its key is among its party's.
-**Who deletes it.** Any member, in a change that every node judges by whether what it
-deletes counted at its history; but what stopped counting because its key went (2) only
-its party, until the party holds no keys at all. The fifth isn't deleted apart, as a
-deletion removes every value it saw at a place: its party's next write replaces both. That
-is the federation's own housekeeping; remakes carry whatever is there. So that deletions
-don't flood the document, the party whose write made something stop counting deletes it in
-the same change, or soon after; others delete only what they find stale, as in a swarm
-whose parties went quiet. What is deleted doesn't come back where it would count again:
-its party writes it again.
+### What counts
-**Nothing comes back.** An envelope that replaced nothing, the first at its place, could
-be put back wherever its place is empty, by anyone who holds it; it counts if its key is
-still its party's and its party may write there. Housekeeping empties a place only where
-that can't be: by (1), where its party may not write; by (2), once its party holds no
-keys; by (3), once its party holds none of the keys it held when it deleted, the only ones
-that can have signed what came before. A party never adds a key it removed again: nothing
-remembers removed keys, and it can bring back what that key signed.
+A change is judged at its history, by the version current there, as every node judges
+it ([`access.md`](access.md), Changes judged on every node). So a value its party wrote
+while it could write there is taken, even where a version written at the same time
+says otherwise. What **counts** is read by the version current in the document as a
+whole. These count no more, and nothing else is stale:
-### Keys
+1. a value at a place its party may not write by the current version: the party is no
+ longer one, the place went to another, a rule changed; and of a party that is no
+ longer one, its keys and its node list;
+2. a value signed by a key that isn't among its party's;
+3. a proposal on a version that isn't current, and the votes on that version;
+4. a version behind the current one;
+5. the member entry of a node no party lists.
-A party's keys are at `_continuum/federation/keys/<party>/<name>`, one line each, as
-an `authorized_keys` line has it. The party adds and removes them itself, with a key
-it holds; a version that becomes current writes those it sets.
+**Any member may delete what counts no more**, place by place, never a map holding
+places; every node judges the deletion by the document the deleting change makes. That
+is the federation's own housekeeping; remakes carry whatever is there. So that
+deletions don't flood the document, the one whose write made something stale deletes
+it in the same change; others delete only what they find stale, as in a swarm whose
+parties went quiet.
-* **A value counts only while the key that signed it is its party's.** So rotating a
- key is: add the new one, sign again what should stay (a client does that), remove
- the old one. A removed key isn't kept, and what it signed counts no more.
-* **A stolen key.** The party removes it at once: what the thief signed with it
- stops counting, and so does what the party signed with it, until signed again. If
- the thief removed the party's other keys first, or both removed each other's at
- once (the party then has none), the parties give it new keys by a version. A vote
- the thief cast on a version that passed stays passed.
-* **Deleting a value** is writing an envelope with `null` in its place, naming the keys
- its party holds then. It stays while its party holds any of them: what came before it at
- its place may have been signed by one of those, and could be put back. A party that
- deletes much rotates its keys now and then, and its deletions go.
+What is deleted this way can come back only as its party's own: an envelope first at
+its place, put back where the place is empty, counts if its party still has the keys
+it named and may write there. So a place taken from a party and given back may show
+what the party had there, until the party writes there again.
### Nodes
A party lists the nodes that carry for it, by node ID, at
-`_continuum/federation/nodes/<party>`, at most `limits.nodes`. Only a listed node is a
-member: it registers, commits changes and syncs, and a node syncs with no other
-(Stages). A node commits whatever envelopes it is given, its party's and others'
-alike: what counts is who signed a value, not which node committed it. So a party
-without nodes of its own writes through any node that takes its envelopes.
+`_continuum/federation/nodes/<party>`. Only a listed node is a member: it registers,
+commits changes and syncs, and a node syncs with no other (Stages). A node commits
+whatever envelopes it is given, its party's and others' alike: what counts is who
+signed a value, not which node committed it. So a party without nodes of its own
+writes through any node that takes its envelopes.
### Forks
-Every proposal is a chance to fork. A group that wants one, on whatever version and
-whoever voted for it, follows it: its nodes follow the **chain** that begins with that
-proposal, named by its hash. Nothing needs to be written for that. Versions on the new
-chain pass by votes of its parties and are written at `current/<chain>`, as on any chain.
-The group might be all but a few who won't cooperate, a few trying something the others
-may follow later or never, or anyone who won't follow a version that passed.
+Any group can carry on without the rest: too many parties are away for good, a version
+the group won't follow passed, the parties can't agree. It **forks**: it starts a
+swarm of its own from the document.
-A node follows one chain: its operator's choice, by default the one it is on. It judges by
-that chain, reads what counts by it, and syncs only with the nodes that its chain's
-parties list. So the sides keep the history up to the fork, in the same document, and go
-apart from there: nothing is copied, and no remake is needed. A party a chain leaves out
-has no member there; to come back, its parties add it by a version, as they would anyone
-new. A proposal may name parties that won't be among the first to go (every party its
-proposer considers honest, say), so that they can go whenever they like, without asking.
+1. One of the group starts the new swarm. Its genesis change holds what the old
+ document read as at heads it names, as a remake's snapshot does, with a version of
+ the group's choosing written as its first: the parties it wants to carry on with,
+ and whatever else it wants changed. It names the swarm and the heads it came from.
+ Every proposal is a chance to fork: the version is usually one that didn't pass.
+2. The others join it as a node joins any swarm, by its genesis change's hash. A node
+ that holds the old document checks the new one against it first: the same at those
+ heads, but for the version.
+3. What the genesis change holds counts as it did, signed for the swarm it came from.
+ Everything written from then on is signed for the new swarm.
-A party that goes may say where, at `_continuum/federation/went/<party>` on the chain it
-leaves, so that others can follow. Voting is apart from it: a vote moves nobody, so voting
-for a proposal that doesn't pass strands no one.
+A fork needs nobody's vote and nobody's ack: it binds only those who go, and the swarm
+they left goes on for those who stay. A party the fork's version leaves out writes
+nothing there, and what it had counts no more; to come back, the fork's parties let it
+in by a version, as they would anyone new. A fork may name parties that weren't among
+the first to go (every party its founders consider honest, say), so that they can
+follow whenever they like, without asking.
-### Following
+What a party's nodes do of themselves is their operators' business, written nowhere:
+join a fork where parties their operator follows went, vote as those voted, vote by
+bounds their operator set, or do nothing without their operator. So a federation that
+cooperates can have a group that leads without being named: the active parties the
+others follow. A party votes from one node only, so that it never votes twice.
-What a party's nodes do of themselves is their operators' business, and nothing of it
-is written into the document. A node may go where the parties its operator follows
-went, by their `went`, and ask only when they went different ways; vote as they voted;
-vote by bounds its operator set on the numbers; or do nothing without its operator. A
-party votes from one node only, so that it never votes twice.
+### Shared identifiers
-So a federation that cooperates can have a group that leads without being named: the
-active parties the others follow. Those who follow need to act only when the parties
-they follow disagree, and a party that won't cooperate is left behind by everyone who
-doesn't follow it.
+Anything outside a party's namespace is shared: names, addresses, anything a rule
+names. Who writes one is what a rule says: by its own name (`names/r/{party}/**`: a
+party writes the names under its own), or given to one party by a version, and taken
+back and given to another the same way. Nothing is first come, first served. The
+value is what its writer signs there (`names/r/wiki`: where the name points); what a
+former writer signed counts no more once a version gives the place to another.
-### Shared identifiers
+Routine work needs no vote: a version gives a party a zone or a block by one rule
+(`ip4/10/243/7/*`), and a new host is a write where its party may write. Votes are
+for parties, zones, blocks and names that are nobody's by their spelling.
-Anything that isn't a party's namespace is shared: names under `.r`, IPv4 and IPv6
-addresses, anything a rule names. Who writes one is what a rule says: by its own name
-(`names/{party}.r`: a party writes the name that is its own), or given to one party by
-a version, which takes `share`, and taken back and given to another the same way.
-Nothing is first come, first served. The value is what its writer signs there
-(`names/wiki.r`: where the name points); a value a former writer signed stops counting
-once a version gives the place to another.
+### Becoming federated
-In a federation that cooperates this settles at once: a party proposes what it wants,
-those who follow vote with those they follow. A group that gives an identifier to
-another against the rest can't, short of `share`; with it, the rest fork with the
-policy they want.
+A swarm becomes federated by one change: it writes the federated policy and the first
+version, by one who may write the policy. From then on a node refuses every change it
+doesn't hold yet whose history lacks that change: nothing is added to the time before.
+What was written before counts only as anything does, where a party's key signed it
+and the first version lets that party write there: the parties sign again what they
+keep.
### Remakes
A remake starts the document anew, for Automerge's sake only (Where Automerge sets
limits); the federation needs none and asks for none. When to remake, and who acks,
-is continuum's as in every swarm. What a federated node asks of a remake, whatever its
-kind:
+is continuum's as in every swarm. What a federated node asks of a remake:
-* **It loses nothing and adds nothing.** The new document holds every envelope and
- every record of the federation that the old one held at the base, byte for byte,
- and nothing else of the parties'. A node checks that before it switches, and stays
- where it is otherwise.
+* **It loses nothing and adds nothing.** A node follows a remake only where the new
+ document reads as the old one did at the base, at every place and every path of the
+ federation. A node checks that before it switches, stays where it is otherwise, and
+ never rejoins an epoch it refused.
* **Writes after the base** are replayed as the policy shapes it: every envelope beyond
- the base, in the order of their `prev`, each judged again in the new epoch. One the
- new epoch refuses (its key was removed, its place given to another) goes to the
+ the base, in the order they were written, each judged again in the new epoch. One
+ the new epoch refuses (its key was dropped, its place given to another) goes to the
quarantine of the node that holds it, and its party signs it again if it still may.
+ Housekeeping after the base isn't replayed: what it deleted is stale again, and is
+ deleted again.
So a remake decides nothing, and a swarm that never remakes stays as correct as one
that remakes all the time; it only grows slower.
+A node that doesn't hold the epoch before (it joins, or was away) can't check: it
+takes the epoch its peers give it. Its operator gives it the swarm's genesis change
+and, to be sure of the policy, the hash of the version it expects to be current.
+
### Where Automerge sets limits
Recommendations, not rules: none of these breaks a promise, only how fast a node is.
* **Writers.** Every writer costs every node memory while the epoch lasts, in
proportion to the document's history *(measured: about 4 bytes per change)*. A node
- writes under a fresh writer each time it starts, or rejoins. A federated swarm
+ writes under a fresh writer each time it starts, rejoins or drops. A federated swarm
remakes before its writers and history make that felt, and a node keeps its writer
over a clean restart where it can.
* **One change a number.** A node that commits two changes under one writer and number
splits the nodes that took one from those that took the other: a node holding one
can't take the other. Continuum refuses the second as forged, by whoever brings it
- *(checked: `Signatures::forks`)*; a remake heals the split.
+ *(checked: `Signatures::forks`)*. A remake brings the two sides together again, and
+ so does a fork.
* **Changes it shouldn't apply.** A change is first of all one Automerge itself
writes, or it is refused before Automerge sees it, in every swarm *(checked:
`document::changes::Written`)*.
-* **Values written at once.** Where two changes wrote one place at once, the one shown
- is chosen by an order a writer can steer. Within a party's namespace that is the
- party's own matter; votes are read with all the values a place holds.
* **History.** The document keeps all of it, which remakes bound.
-* **Bytes.** Every node builds the same snapshot only with the same Automerge version:
- a federated swarm moves to another one at a remake, all its nodes together.
+* **Bytes.** The nodes of an epoch run one Automerge version; a swarm moves to another
+ at a remake.
## Why it holds
1. **What counts.** A change is judged at its history, which its hash fixes, by the
- version current there, which the records and votes in that history fix. Every node
- following one chain judges alike, and refuses the change and everything built on
- it. What counts is read by the version current in the document as a whole and the
- keys the parties hold there, the same on every such node that holds the same
- changes.
-2. **The policy.** A proposal passes only with `share` of the parties of the version
- it changes, more than a half; a party counts once, and for neither once its two
- votes are seen. Two proposals on one version both pass only if their voters share
- at least twice `share` less one of the parties, all of whom voted twice: a third,
- at two thirds. Votes never change, so a node that holds more is only further along.
-3. **Carrying on.** A fork is a chain from a proposal a group follows; nodes go there by
- their operators' choice only, and sync only with its parties' nodes. A party nobody
- follows carries on alone.
+ version current there, which the versions written in that history fix, each judged
+ by the votes in its own. Every node judges alike, and refuses the change and
+ everything built on it. What counts is read from what the document holds: the
+ current version, the highest number written; each party's keys, by that version and
+ the highest `seq`; each place's value, by the highest `seq`. None of it depends on
+ the order of operations, so a change made to look older or newer than it is moves
+ nothing.
+2. **The policy.** A version is written only where, at one history, the share of the
+ parties of the version it changes voted `true` for it. An honest party backs one
+ proposal on a version at a time, and another only once the first is dead: a
+ proposal can't pass at one history and be dead at another unless some party's
+ `true` and `false` for it are both there. So without a party voting twice, at most
+ one version is written per number. With one, nodes still read the same version
+ once they hold the same changes: the lower hash.
+3. **Carrying on.** A fork is a swarm of its own, joined by its operators' choice
+ only. A party nobody follows carries on alone.
+
+## Attacks
+
+What an attacker does, and what happens. *Unit*: the judging, with crafted changes.
+*Sim*: a simulation. *Bench*: measured, not judged.
+
+| # | Attack | What happens | Test |
+|---|---|---|---|
+| 1 | An envelope signed by a key that isn't its party's, or by no party | Refused at its history | unit |
+| 2 | An envelope for another path, or another swarm | Refused: its meta names both | unit |
+| 3 | An older envelope written where a newer one is | Refused: `prev`, `seq` | unit |
+| 4 | An older envelope put beside the newer by a change that saw neither, its operations numbered to win | Taken, and behind: the highest `seq` is the value | unit |
+| 5 | An older version written again | The same place, the same bytes; behind the current one by its number | unit |
+| 6 | An older key set, or node list, put back beside the newer | Behind, by `seq` | unit |
+| 7 | A version written without the votes, or on a version that isn't written | Refused at its history | unit |
+| 8 | A version that doesn't read, a share of a half, a rule under `_continuum` or without a literal first segment | No version: can't pass, refused when written | unit |
+| 9 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit |
+| 10 | `true` on two proposals at once, from two nodes | Both taken; two versions may be written; the lower hash is read. Not promised to stay; the votes show | unit, every order |
+| 11 | `true` and `false` on one proposal at once | Reads as `false`; a node that saw only the `true` may write the version. As 10 | unit, every order |
+| 12 | A vote changed | Refused | unit |
+| 13 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit |
+| 14 | A third of the parties never votes, or votes `false` on everything | Nothing passes; the others fork | sim |
+| 15 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit |
+| 16 | A lapsed proposal, or votes on it, written again | Count no more at once | unit |
+| 17 | Values signed with a stolen key | Count until the party drops the key, then none of them | unit |
+| 18 | The thief writes a key set without the party's keys | The parties set its keys by a version, ahead of every set before | unit |
+| 19 | The thief writes changes that look older than the key's loss | Count no more: counting is by the keys now | unit |
+| 20 | A deleted or replaced first envelope put back where its place is empty | Refused once its party changed keys; else its party's own value again | unit |
+| 21 | A place taken and given back, a party taken out and let in | What it had may be put back until it writes there | unit |
+| 22 | A write in another party's namespace, or at an identifier of another's | Refused by the rule | unit |
+| 23 | Housekeeping of something that counts | Refused, by the document the change makes | unit |
+| 24 | Housekeeping by a change that saw a time when it didn't count | Taken; the party writes again | unit |
+| 25 | A map holding places deleted | Refused: places only | unit |
+| 26 | A change with a history from before the swarm was federated, sent later | Refused | unit, sim |
+| 27 | A remake whose document reads otherwise than the base | Nodes holding the base stay, and never rejoin it | sim |
+| 28 | A remake at a base where a place holds two envelopes | The one that was the value stays the value | unit |
+| 29 | A joining node handed a made-up epoch | Taken, unless it lacks the version its operator named. Not promised | sim |
+| 30 | The party with most nodes remakes often, or never acks | Slow, not wrong; the others fork | sim |
+| 31 | A writer forked: two changes, one number | Honest nodes split until a remake, or a fork | sim |
+| 32 | Different changes to different peers | Honest nodes agree once they sync | sim |
+| 33 | A party withholding its changes or votes | Not promised | — |
+| 34 | Flooding: namespace, proposals, history, writers | Slow, not wrong | bench |
+| 35 | A node taken off its list writes changes that look older | Taken where valid at their history; they move nothing (4 to 6) | unit |
+| 36 | A token from another party's node | Refused | unit |
+| 37 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit |
+| 38 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join | sim |
+| 39 | A federation, or a policy, a node doesn't know | It stops taking changes | unit |
## Roads not taken
@@ -366,13 +436,16 @@ Recommendations, not rules: none of these breaks a promise, only how fast a node
someone's witness. Votes need neither.
* **Anything waiting on time** (final after so many days). Clocks are each node's own.
Everything here waits on votes.
-* **Taking back what a stolen key signed, from history.** Telling which signatures
- came after a theft needs history kept and read. Removing the key takes all of them
- back, and the party signs again what was its own.
-* **Forks as new documents.** A fork could start a document of its own, as a remake
- does. Following a chain and syncing with its parties' nodes only does the same
- within one document, and keeps remakes for Automerge alone.
-* **Forks apart from proposals.** Every proposal is one already.
+* **Taking back what a stolen key signed, from history.** A thief makes its changes
+ look as old as it likes. Dropping the key takes all of them back, and the party
+ signs again what was its own.
+* **One vote per version**, never to be cast again. It bounds what parties voting
+ twice can do at a third of them, and leaves a split for good. With nays a split
+ ends, and one party voting twice on a close vote can have a version replaced by
+ another that also had its votes; the votes show who.
+* **Forks within one document**, each side judging by its own chain of versions. It
+ needs judging per chain, judging again when a node changes sides, node lists and
+ remakes per chain. A swarm of its own needs none of it.
* **Users below the parties.** A party's people and keys within it are its own matter:
it may hand out its keys as it likes. The federation sees parties.
@@ -380,41 +453,42 @@ Recommendations, not rules: none of these breaks a promise, only how fast a node
Every node of a swarm runs the same version of continuum today. A federated swarm's
parties can't be made to upgrade together, so what all its nodes must agree on is
-small: the hash of a change and how it is encoded (Automerge's version), and the
-federation's rules, which its number names.
+named by the federation's number: the rules of this design, the envelope and how the
+value of a place is read, what makes a change one Automerge writes, and how a path
+and a version are spelled. The hash of a change and its encoding are Automerge's
+version's.
A change to the federation is a design like this one, with the next number. A swarm
moves to it by a version of its policy that names it (`"federation": 2`), which the
parties pass once their nodes run a continuum that knows it. A node that doesn't know
-a federation its chain moved to stops taking changes and says so. Continuum's wire
-version only says whether a node can take part in a federation at all.
+the federation, or the policy, its swarm has stops taking changes and says so.
## The registry on it
The krebs registry today: users, their hosts, the hosts' names, addresses and keys.
On a federated swarm:
-* each krebs user is a party, its hosts in its namespace (`tv/hosts/laptop`: its keys,
- its addresses as it uses them);
-* its own names under `.r` and `.w` by the rules `names/{party}.r`, `names/{party}.w`;
- other names, and the retiolum and wiregrill addresses, given by versions;
+* each krebs user is a party, its hosts in its namespace (`home/tv/hosts/laptop`: its
+ keys, its addresses as it uses them);
+* its names under `names/r/tv/` and `names/w/tv/` by one rule each, its address blocks
+ by a rule each; other names given by versions;
* a tool reads what counts and writes what kartei's consumers read today.
## Stages
-1. **The federated policy**: versions, rules and their paths, the current version from
- votes and records, judging by it. Tests: two proposals on one version with every
- order of votes; a vote changed; two votes at once.
-2. **Keys**: what counts by the keys held, removing a key, two removing each other's,
- a version setting keys, deletions kept until their key goes.
-3. **Nodes**: membership by the node lists, and a node syncing with members only, as
- a swarm key does today: a wire change.
-4. **Housekeeping**: deleting what doesn't count, judged by what counted at the
- deleting change's history.
-5. **Remakes**: the check that a remake lost and added nothing; replay of envelopes,
+1. **The federated policy**: versions and what makes one valid, rules and paths, keys,
+ votes, passing and dead, the current version, judging by it. A node that doesn't
+ know the policy stops taking changes. Until stage 4, a federated swarm takes no
+ remake.
+2. **What counts**, read by the current version and the keys; shown in the API.
+ Housekeeping.
+3. **Nodes**: membership by the node lists, a node syncing with members only, as a
+ swarm key does today (a wire change); tokens from one's own party's nodes only.
+4. **Remakes**: the check that a remake lost and added nothing; replay of envelopes,
each judged again.
-6. **Forks**: chains, a node following one, syncing with its parties' nodes.
+5. **Forks**: a swarm started from another's document, and the check against it.
+6. **Becoming federated** in a running swarm, and leaving.
7. **The registry**: the rules for krebs, the tool.
-Each stage keeps every swarm that isn't federated as it is, its tests passing
-untouched.
+Each stage's tests are its rows of Attacks. Each stage keeps every swarm that isn't
+federated as it is, its tests passing untouched.