diff options
| author | tv <tv@krebsco.de> | 2026-11-12 05:36:14 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-12 15:26:36 +0100 |
| commit | a4da3a94cb51b893dc259a1741df0071c46e1ac3 (patch) | |
| tree | 73be601a97014b4ff29fcf58c13d9e594439417f /docs/federation.md | |
| parent | 4411fa278fec38f0c5e3520bd38d416c793ba1f7 (diff) | |
docs: federation: the answers to its open questions
What the maintainer answered to the design's open questions, in the
design:
* The numbers. The limits and the times are the policy's numbers, set
in the genesis policy and changed by a decision: 64 keys, 64 nodes
and 256 addresses a user for a start; `window`, `absent`, `gone`,
`archiveRetention`. A lowered limit takes nothing away.
* A user nobody vouches for is out, and its names wait for it: nobody
else claims them. Out for 30 days, as the stamps of a third of the
voters show, it is gone: its names are free, and no vouch brings it
back. So whoever relied on a vouch that an unvouch or a cut took
back has that long to find another, and loses nothing meanwhile.
* First keys by a decision. The voters are above every user's first
keys: they give a user that lost them new ones, with a cut for the
old. The promises say so, and what isn't promised: a name against
two thirds of the voters.
* What a decision is made of (a proposal, a vote, its release, the
decision) is taken in any node's change, so a user without a node
votes at whatever node it reaches, or by a vote carried to one. Such
a user names another party's node to carry for it.
* Coming back after remakes: by the archives on nobody's word, epoch
by epoch, as far as peers keep them; else by an ID the operator
gives, never because peers advertise an epoch. A statement is
carried over from the epoch before only; older ones are quarantined
for the user to sign again.
* Resolving reads the decisions first: nothing below changes them.
* The questions that remain are put with their options: who has a
vote and from when, whether the voters put a user out against those
who vouch for it, from where an unvouch undoes, whether gone is for
good, the price of first keys by a decision, and what the root
holds unsigned.
The attacks are 76; the stages name them by their numbers.
future-work.md: barring a user by a decision, and voting made easy for
a user without a node.
Diffstat (limited to 'docs/federation.md')
| -rw-r--r-- | docs/federation.md | 605 |
1 files changed, 387 insertions, 218 deletions
diff --git a/docs/federation.md b/docs/federation.md index 947da71..d3183d7 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -51,7 +51,8 @@ adversary is that party). ## What is promised -To an honest node, whatever the others do, with any number of them malicious: +To an honest node, whatever the others do, with any number of them malicious (3 to 5 +but for what the voters can do to a user, said with each and below): 1. **Only valid changes.** Every change it holds passed the rules, judged as its writer saw the document (at its dependencies). @@ -59,7 +60,8 @@ To an honest node, whatever the others do, with any number of them malicious: 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. + is as the root change has it. A key is a user's by what its own keys signed, or by + a decision that gave it first keys anew (7). 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 @@ -69,7 +71,9 @@ To an honest node, whatever the others do, with any number of them malicious: 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). + released the name stands as long as that release does (Cuts). A claim stands + while its user does: the names of a user nobody vouches for any more wait for it, + 30 days by the voters' clocks, and are free after (Unvouching). 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. @@ -78,14 +82,14 @@ 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. +7. **Decisions by two thirds.** A remake, a new root, first keys for a user that lost + its own, a change of the 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: @@ -102,6 +106,13 @@ What is not promised: 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. +* **A name against the voters.** Two thirds of them give a user's first keys anew. + Meant for a user that lost them, it hands a name to whoever they say: in the open, + over the days a vote takes. And a third of them, lying about the time, make a user + that is out gone at once. +* **A name through a long partition, for a user that is out.** Unvouched on one side + of a partition that outlasts the 30 days, it is gone, though someone vouched for it + in time on the other. * **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 @@ -124,7 +135,8 @@ 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 +from the document: medium, less for the clock. A user gone after 30 days out reads +the same clock. 5 and 7 want the tests named under Attacks, and someone trying to break them. ## The design @@ -141,8 +153,10 @@ its voters' votes. 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: +and the **numbers**: the limits (how many keys, nodes, users and names of a kind a +user may have) and the times (`window`, 7 days; `absent`, 30 days; `gone`, 30 days; +`archiveRetention`, 90 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`), @@ -151,8 +165,8 @@ in the swarm's root, its genesis change, with the root user, its keys and its no * 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). +The 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 @@ -184,10 +198,15 @@ grows. A statement is signed by one user and says one thing: 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). + that carries for its signer (a `node` statement also in one by the node it names; + what a decision is made of, in any node's: Decisions). 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. 64 nodes + a user at once (a limit). +* **A user without a node** names another party's, which carries for it too if it + agrees (it commits the `node` statement). That node's changes witness for both, + its alive stamp is the presence of both, and it takes decisions up for both. The + user trusts that party with those; nothing is signed in its place. * **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 @@ -238,14 +257,22 @@ exactly: 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. +* **Else the user is out, from there.** Nothing of it counts: its namespace doesn't, + its nodes witness nothing, and what they commit in sight of the unvouch is + refused. Its names **wait** for it, its user name among them: its claims stand, + so nobody else claims them, and nobody holds them. * **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. + through it is out too, with the same consequences, unless another user that counts + vouches for it, before or after. +* **A vouch brings a user back whole,** with its names and what it signed in + between, as long as it isn't gone. +* **Out for long is gone.** A user is **gone**, at a set of changes, once a third of + the voters each have a node with two alive stamps `gone` (30 days) or more apart, + the user out at both and at every stamp of that node between. Then its claims and + its creation stand no more: whoever comes first claims its names, and no vouch + brings it back. It comes in again by being created anew. Gone is read from the + changes alone and never goes away. Fewer than a third of the voters can't bring it + about early, and the time between two stamps is by one node's own clock. * **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 @@ -253,10 +280,12 @@ exactly: 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. +So whoever relied on a user that is out has 30 days to find another who vouches: for +itself, and for those it brought in. Until then nothing it holds can be taken. + +A user gives itself up by a `release` of its own creation: from that release on it is +gone, and its names are free at once. ### Namespaces @@ -279,7 +308,7 @@ What must be unique across users (a host's name, an address, a top-level domain) { "name": { "rules": [ { "match": ["*", "{user}", "**"], "by": "{user}" }, { "match": ["*"], "by": ["tv"] } ] }, "ip4": { "rules": [ { "match": ["10", "243", "*", "*"], "by": "*" } ], - "limit": 64 }, + "limit": 256 }, "user": { "rules": [ { "match": ["*"], "by": "*" } ] } } ``` @@ -293,16 +322,17 @@ What must be unique across users (a host's name, an address, a top-level domain) * 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. + whoever comes first, 256 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. +claim: how a name is given up). A claim **stands** while it counts, isn't released, +and its user isn't gone. 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 no claim of that name stands +there. 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. @@ -320,9 +350,9 @@ users on its line, the root's among them. (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. +* Of the claims of a name that stand, those not late against any other remain. If + one remains, its user holds the name, or has it wait while it is out. 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. @@ -383,9 +413,9 @@ 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. +user independent of its creator's keys. And a user's first keys have none of its own +above them: above those are the voters, who give a user first keys anew by a +decision (Decisions). A cut reaches no further back than the epoch (Remakes). @@ -411,9 +441,9 @@ 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. +Some things are the swarm's to decide: its numbers, who the root is, a user's first +keys where it lost its own, 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 @@ -466,6 +496,12 @@ fork that names who votes (A change of policy is a fork). Every node acts on a decision that counts, unless another following the same one counts too. +**By any node.** A proposal, a vote, a vote's release and a decision are taken in any +node's change: the signature is the voter's. So a voter votes at whatever node it +reaches, or signs a vote that someone carries to one. A vote kept back counts while +it runs, as its signer wrote, and no longer. What brings a vote from a person to a +node (a client, a page, paper) is the application's. + **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. @@ -487,13 +523,25 @@ 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 numbers**: a limit or a time of the policy, named by its place there. It + holds for what is made in sight of the decision. A lowered limit takes nothing + away: what a user has stays, and it gets no more until it is below. * **The root's seat** (below). +* **A user's first keys**, for a user that lost them or had them stolen. The proposal + names the user, the first keys it is to have, and a cut for those it has: what + they signed outside the cut doesn't count, as with a key above them (Cuts). The + voters are above every user's first keys. A user that lost its keys comes in again + under another name, so that it has a voice and the voters know whom they give the + name back to. Decided, it signs under its name as before, with its names, its line + and those it brought in, and releases the other name. * **A remake** (below). * **A change of policy** (below): proposed and voted on the same way, made and followed by choice. +A decision that counts stays, whatever is cut off after: a vote signed with a key +that is retired later, from before, stays in it. The days a vote takes are the time +to cut a stolen key off. + ### The root's seat The root is whoever holds the seat: at first the user in the root change. A decision @@ -531,12 +579,15 @@ itself. 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 + the registry as it resolves at the base: the policy and the 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. + entries, as today. A user that is out and not gone is in it with all it has, and + with the time since when a third of the voters saw it out, which stands for the + first of the two stamps after. It leaves out what doesn't count otherwise, 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 @@ -547,11 +598,7 @@ itself. 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 was away** comes back as said below (Coming back after remakes). * **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 @@ -561,6 +608,45 @@ For the registry the document is small: a statement is under a KiB, a node's ali stamp with its signature about 300 bytes, so a hundred nodes write some 10 MiB a year. A remake a year is plenty. +### Coming back after remakes + +A node that was away holds an epoch the swarm left, one remake back or several. Its +peers name their epoch in the handshake and don't sync with it; `GET /admin/epochs` +shows the epochs they name, and which of them the nodes of its line are in. A +federated node never rejoins because peers advertise an epoch, however many do. It +gets there in one of two ways: + +1. **By the archives, on nobody's word.** A peer answers for an epoch it left as long + as it keeps that epoch's document (`archiveRetention`). From such a peer the node + syncs the rest of the epoch it is in, judging every change; sees the remake's + decision count; builds the snapshot itself; and is in the next epoch, whose ID is + the snapshot's hash. So on, epoch by epoch, as far as peers keep them. +2. **By an ID, on its operator's word.** Where no peer keeps the epoch any more, the + node can't check how the swarm got from there to here. Its operator gives it the + ID of the epoch to go to (`POST /admin/epochs/rejoin`), from a party it trusts: + as when the node first joined, whoever brought its user in. The node rejoins as + today: it downloads that epoch's snapshot from any peer, checked against the ID, + and syncs what was written since. + +Either way, what follows: + +* **What its user signed and the swarm never got.** A statement signed in the epoch + just before the one the node arrives in is carried over: written again as it is. + One signed further back isn't: an envelope is taken in its epoch and the next, no + later. Those go to the quarantine, and the client lists them for the user to sign + again. A claim signed again is a new claim, after what was claimed since. +* **What it finds of its user**, as the snapshot has it. There, with its keys, nodes + and names: the node carries for it as before, and writes its member entry anew. Or + out, its names waiting. Or gone, and so not in the snapshot: then no node takes the + node's changes, it shows why, and its user comes in again as anyone does. +* **As a voter** the user was absent, is no voter after a remake it missed, and is + one again after the next. A root that was away is still the root, unless a decision + gave the seat to another. +* **Its old document** goes to the archive, as today. + +A node moves to an older epoch, or to another of the same age, only by its operator's +word. + ### A change of policy is a fork A change of policy (a new kind of name, another rule, a version of continuum that @@ -613,18 +699,20 @@ A change is valid if, in the document at its dependencies: 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. + there, and the committer carries for that user (but for a `node` statement, and + for what a decision is made of). 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. +5. A `create`: its name has no creation there that stands (one not released, its + user not gone), a rule of the kind `user` lets the signer, and the signer is within + its limit. `key`, `node`, `vouch`, `ban`: within the limits; a `vouch` for a user + that isn't gone there. `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. + kind's limit, and no claim of that name stands there. 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 @@ -640,8 +728,9 @@ of a name is known can't scribble over the namespace, and one whose name a liar 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. +applied beyond a retiring or an unvouch that is there, and the numbers, the root and +the first keys are as the decisions that count there leave them. A statement in a +register was valid when it was taken, so judging the next needs no look further back. ### Resolving @@ -649,26 +738,30 @@ The **resolved registry** is a function of a set of changes that holds each chan 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 +1. **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 + numbers, who the root is, and the first keys given. They are read from statements + valid as written and from what the nodes recorded, so nothing below changes them. +2. **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. + statements that count, up to its creation, or given by a decision), it is within + every cut set for that key (by a `retire` that counts, or a decision), 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. A statement past its user's limit, as the limit + was where it was made, doesn't count: of a user's creations, vouches or claims, + those made in sight of the others come first, then by digest. A user is **out** + where no `create` or `vouch` for it counts any more, and **gone** as said under + Unvouching. +3. **Users' names.** A creation stands while it counts, isn't released, and its user + isn't gone. Of the creations of a name that stand: the one that remains (Two + claims) has the name, or has it wait while it is out. +4. **Names.** A claim stands the same way, where a rule lets its user: anyone vouched + for where the rule says `"*"`, else the user that has the name the rule gives. Of + the claims of a name that stand: one that has another in its history loses to it; + of the rest, the one that remains holds the name, or has it wait while it is out. + 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, @@ -679,12 +772,13 @@ A node keeps the resolved registry as it goes (a statement changes it around its 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. + line; or that it is contested, between whom; or out, since where, and until when + its names wait; or gone. * `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 +* `GET /registry/decisions`: the root, the 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 @@ -796,9 +890,10 @@ reads from the document. What must hold for this, and doesn't everywhere today: 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 +key that step 2 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 +and so on up to the root, in the root every node was given; or by a decision, which +is promise 7's. 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 @@ -811,12 +906,13 @@ root's node committed with c in its history and no other claim of the name that 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. +good. A late claim never holds a name while a rival stands, and c stands until it is +released or its user is gone: out for 30 days by a third of the voters' own stamps, +one of them honest. 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 @@ -929,7 +1025,7 @@ back, so the point only moves forward as more of them show up. | 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 | +| Say when it was alive | Believed for itself only; a third of the voters together move the swarm's time, and say how long a user was out | "Member" stays the word for a node in the swarm; the unit that is trusted or not is the party. @@ -939,10 +1035,10 @@ the party. 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. +decisions by the voters with the swarm's time, the numbers, the root's seat, a user's +first keys, 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 @@ -954,14 +1050,15 @@ More policies later are more data where a rule has a parameter, and a new rule i 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. +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, takes no remake but one its voters decided, and +rejoins no epoch because peers advertise it. 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, out, gone, the swarm's time, and a ban of a user beside +a ban of a node. ## Attacks @@ -975,7 +1072,7 @@ 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` | +| 2 | Puts another user's statement into a change of its own node | Refuse, its node not carrying for the signer; but for what a decision is made of | 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` | @@ -993,91 +1090,98 @@ Unvouching: | 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` | +| 15 | A user is unvouched: what of those it brought in, and its names? | They are out from the same point unless another vouches for them; a vouch after brings them back whole. Their names wait | 4 | unit: `those_it_brought_in`, `a_vouch_brings_back` | | 16 | An unvouched user's nodes keep sending | Refused as peers; nothing taken from them | 6 | sim: `nothing_from_an_unvouched_node` | +| 17 | Claims a name of a user that is out, or creates its user name | Refuse: the names wait until the user is gone | 5 | unit: `names_wait_while_out` | +| 18 | Has a user unvouched, then stamps its nodes 30 days apart at once, to free the names | Gone takes a third of the voters | 5 | unit: `gone_by_a_third_of_the_voters` | +| 19 | Vouches for a gone user with old dependencies, over a name claimed since | Gone stays: no vouch brings it back | 4 | unit: `gone_stays_gone` | 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` | +| 20 | 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 | +| 21 | Writes plain values, or protocol data but its own member entry | Refuse | 3 | unit: `nothing_plain` | +| 22 | Puts an old envelope back | Refuse: it doesn't replace what is there | 3 | unit, exists: `what_an_envelope_must_be` | +| 23 | 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` | +| 24 | Claims a held name in sight of the claim | Refuse | 4 | unit, claims: `first_come_first_served` | +| 25 | 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` | +| 26 | 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` | +| 27 | 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` | +| 28 | 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` | +| 29 | 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` | +| 30 | A whole line kept silent, then claims with old dependencies | Before the claim is settled: contested. After: late | 5 | unit: `silence_before_settling` | +| 31 | 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` | +| 32 | 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` | +| 33 | Signs with a retired key and old dependencies | Hold it (valid as written), leave it out | 3 | unit: `backdated_past_a_cut` | +| 34 | With a stolen device key, retires the keys above or beside it | Refuse | 3 | unit: `no_key_retires_one_above` | +| 35 | 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` | +| 36 | Steals a user's first key | The name is the thief's too, until a decision gives the user first keys anew, with a cut for the stolen one | 7 | unit: `first_keys_by_a_decision` | +| 37 | 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` | +| 38 | 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` | +| 39 | 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` | +| 40 | Forges a vote; votes as a user that isn't a voter, or one absent | Refuse | 7 | unit, decisions: `a_vote_is_a_voters` | +| 41 | Brings in many users to vote | They don't: only those a root created come to vote | 7 | unit: `who_votes` | +| 42 | 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` | +| 43 | Decides without the votes, or with released ones | Refuse | 7 | unit: `a_decision_as_written` | +| 44 | 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` | +| 45 | 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` | +| 46 | 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` | +| 47 | 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` | +| 48 | Asks the voters for another user's first keys, saying it is that user | It takes two thirds of them, and the days a vote takes, shown to all; the user signs on meanwhile | not promised | argued (Decisions) | +| 49 | Puts a voter's vote into a change of its own node; keeps one back; offers one again | Taken: the signature is the voter's. It counts while it runs; the register holds it once | 7 | unit: `a_vote_by_any_node` | +| 50 | A decision lowers a limit below what users have | Nothing is taken away; no more is taken until below | 6 | unit: `a_lowered_limit_takes_nothing` | +| 51 | 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` | +| 52 | 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` | +| 53 | 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` | +| 54 | 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` | +| 55 | Tells a node that was away of an epoch that isn't the swarm's | The node rejoins no epoch that peers advertise: it finishes the old one from archives and builds the next itself, or takes the ID its operator gave | 1 | sim: `away_over_a_remake`, `back_by_an_id` | +| 56 | A node back after several remakes offers what its user signed epochs ago | Refuse: an envelope is taken in its epoch and the next. Quarantined, for the user to sign again | 3 | unit: `carried_over_one_epoch_only` | +| 57 | 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` | +| 58 | Two thirds of the voters turn on the rest | They remake, seat a root, set the numbers, and give a user's first keys to another: a name taken, in the open. They forge no signature and move nobody to other rules; the rest ban, stay, or fork | not promised | argued (A change of policy is a fork) | +| 59 | 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` | +| 60 | 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` | +| 61 | Sends different changes to different peers, each under its own number | Take all: changes made at once | 2 | sim: `two_histories_merge` | +| 62 | 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` | +| 63 | 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` | +| 64 | 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` | +| 65 | 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` | +| 66 | 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` | +| 67 | Lies in its member entry (ready, reached, stable) | Sync and trees bend; nothing gets in that way | 6 | argued (Reaching one's line) | +| 68 | 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` | +| 69 | 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` | +| 70 | 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` | +| 71 | 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` | +| 72 | A policy version a node doesn't know | It doesn't sync | 1 | unit: `no_sync_under_an_unknown_policy` | +| 73 | 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` | +| 74 | 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` | +| 75 | 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` | +| 76 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` | ## The registry on it @@ -1107,6 +1211,10 @@ The maintainer then creates each user as it comes with a key; from then on the u 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. +The limits in the genesis policy: 64 keys, 64 nodes and 256 addresses a user for a +start. The import may set keys and addresses to twice the most any user has in the +repository; a decision changes them after. + **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 @@ -1116,95 +1224,153 @@ 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). +the existing tests pass untouched (76). 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 + from its party only, keeps ended sessions to itself. Tests: 65, 66, 72, 76, 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 + the rule for committers by it, nothing plain, limits. Resolving, step 2 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 + 11, 21. +3. **Namespaces.** The rule, with `userSigned` below a name. Tests: 20, 22. 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. + judged as written; resolving step 4 for claims in sight. Tests: 24, 27, 28. 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. + Tests: 8, 9, 23, 25, 26, 29, 30, 61, 63, 64. 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. + 31 to 35, 37, 38, 39. 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. + it, the names of a user that is out waiting, nothing taken from an unvouched + user's nodes. Tests: 12 to 17. 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. + with what the line holds, the budget and the share per party. Tests: 62, 68, 69, + 70, 71. +9. **Bans** for those who follow. Tests: 73, 74. 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. + absent, `propose`, `vote` and `decide` taken from any node, taking up, what + counts, `GET /registry/decisions`. What is decided: the numbers, a user's first + keys. A user gone. The simulations start from a root change naming several + voters, as a remake's does. Tests: 18, 19, 36, 40 to 47, 49, 50, 75. +12. **The root's seat.** Tests: 57. +13. **Remakes.** The base, the snapshot every node builds, carrying over from the + epoch before and no further, what becomes final; peers answering for an epoch + they left; a node rejoining by an ID its operator gave, and by none that peers + advertise. Tests: 51 to 56. 14. **A change of policy.** The fork, followed by an operator's word, with who votes - on its side. Tests: 52, 53. + on its side. Tests: 59, 60. ## Open questions -Each with what I'd choose. +Each with the options, and what I'd choose. + +1. **Who has a vote, and from when?** Two things pull: votes must not be multiplied by + whoever brings users in, and whoever adds voters at will is never voted out. + * *The first users an epoch starts with* (as designed). The root brings them in, + and each votes from the first remake after it came, which two thirds of the + voters before it decide. Nobody fills the votes. The price: until the first + remake the root decides alone, a first user waits for a remake, and a user + someone else brought in never votes. + * *The first users, as soon as they are created.* No waiting. But the root creates + as many as it likes: it carries every decision, and is never replaced against + its will. + * *The first users, let in by a decision of the voters*, without a remake. No + waiting for a remake, and nobody fills the votes. But the voters of before can + make a decision "of then" later (the root alone, for the time it was the only + one), which only nodes that were up can tell: a remake is what puts that out + of reach. + * *Every user*, or users down to a depth. Then whoever creates users creates + votes, and it takes a weight that thins out down the line to mean anything. + + *The first.* +2. **Should the voters be able to put a user out against those who vouch for it?** + As designed a user is in while one user that counts vouches for it. One that + squats names up to its limits, or gets others' names contested, stays as long as + a friend stands by it: a party bans it for itself, which changes what that party + reads; the root can unvouch a first user and with it all below, who then need + other vouches; and a vouch from anyone brings it back. + * *No* (as designed): who is in is the vouchers' business, and what a party reads + its own. + * *Yes, a decision bars a user*: it is out for everyone, and no vouch brings it + back until another decision says so. Two thirds of the voters then judge who is + in. + + *No for now*; the second if bans prove too weak. +3. **From where does an unvouch undo?** Its signer chooses its dependencies and can + make them old: an unvouch written in June with January's dependencies looks like + one from January, with everything the user signed since coming after it. What + comes after doesn't count through that vouch, which matters for what stays done + (a name the user released and another claimed) and for what a vouch brings back. + * *From what the unvoucher's own nodes, or the root's, had seen* (as designed). + What the user signed stays if one of those nodes committed a change on top of + it without the unvouch. They write daily, so backdating undoes a day at most. + * *Everything the user ever signed.* Simple, and nothing to backdate. But an + unvouch then takes back the user's releases, and no vouch brings it back as it + was. + * *Only what the user signs in sight of the unvouch.* Then the user goes on by + never building on it, which is no unvouch. + * *From where each node received it.* What one would expect day to day, but it is + in no document: two nodes would resolve the same changes differently. + + *The first.* +4. **Is a user that was out for 30 days gone for good?** As designed, yes: its names + are free, no vouch brings it back, it is created anew. That costs a user who was + vouched for in time on the far side of a partition as long as that. + * *For good* (as designed): whoever claims a name after can rely on it. + * *Back by a vouch made before it was gone*, names claimed since contested: then + a vouch crafted with old dependencies blocks any name claimed in good faith + after a user went. + * *No end*: the names wait until someone vouches. Nothing is lost by mistake, and + nothing a user held is ever free again unless it releases it. + + *For good*, and 30 days. +5. **First keys by a decision: is the price right?** It is the way back for a user + that lost its first keys, and the one way a name is taken against its user: two + thirds of the voters give any user's keys to whoever they say, in the open, over + a week. + * *The voters* (as designed). + * *Those who vouch for the user*, all of them signing: fewer to convince, but + then a user's creator takes its name where nobody else vouched. + * *Nobody*: a lost first key is a lost name, free once the user is unvouched and + gone. + + *The voters*; several first keys of which a number must sign, later, make it + rare. +6. **What the root holds unsigned.** The registry starts from the repository, and no + user of it has a key in the swarm yet. What of their hosts, names and addresses? + * *They count unsigned* (as designed). The root change holds every namespace's + hosts as plain values and its addresses as claims in the namespace's name. + Every party is given the root's hash, and the root is the repository, which is + what is trusted today. Nobody changes a host until its user came: the root + creates the user for the name (kept for the root to create), and the user signs + over what is there. The price: the root says who gets which namespace, as the + maintainer does today, and what nobody ever comes for stays, unsigned. + * *Only what is signed.* The import takes the users who handed in a key, each + signs its hosts, the rest stays in the repository until its user comes. Nothing + unsigned ever counts; the registry is incomplete for as long as users take, and + what reads it needs both sources meanwhile. + * *Unsigned until a day*, then left out and its names free. A clean end, and + hosts that work today stop working because their user didn't look. -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. + *They count unsigned.* 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 +root, whose seat is decided anew; votes by users, over days, two thirds of those +present and more than half of all, the absent left out; unvouching as above, with a +cut taking back what others relied on and their names waiting meanwhile; first keys +by a decision, several first keys later; the limits in the genesis policy, changed +by a decision; a node back after many epochs as said under Coming back after +remakes; a user without a node voting at any node; a change of policy as a fork; the mode optional. ## What was checked, and what is assumed @@ -1231,7 +1397,10 @@ Checked in the code: 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. +for a while (`archiveRetention`: 2 epochs, 30 days), and every node builds a remake's +snapshot itself today; a node that was away rejoins the epoch enough ready members +advertise, and has its own writes carried over within the replay window, the rest +quarantined. Assumed, to be shown as it is built: |
