diff options
| -rw-r--r-- | docs/federation.md | 59 |
1 files changed, 41 insertions, 18 deletions
diff --git a/docs/federation.md b/docs/federation.md index b08ffcc..ea13273 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -1080,6 +1080,13 @@ statement on its side. ### What every node judges +A change is first of all one that Automerge itself writes, or it is refused before +Automerge sees it: its bytes are the ones Automerge encodes for it; every other actor +it names has changes in its history; and its first operation is numbered one after +the highest of its dependencies. Automerge 0.12 applies changes that are none of +these, and then panics, or saves a document that doesn't load *(measured upstream)*. +All three are read from the change and its history, as the rules are. + A change is valid if, in the document at its dependencies: 1. It has no dependencies and is the root the node was given (the genesis change, or @@ -1338,6 +1345,10 @@ the document. What must hold for this, and doesn't everywhere today: have the registers of users and claims, the decisions and what is uncovered; * nothing a node keeps a bounded number of decides validity: a change pushed out of the waiting ones comes again *(checked: `MAX_WAITING`)*; +* a change being what Automerge itself writes. Automerge 0.12 applies some that + aren't, and then holds another change than the one it was given: under the hash + received it gives back a change with another hash, and its save doesn't load + *(measured upstream)*. Screening refuses those before Automerge sees them; * one change per actor and number. A forked actor breaks "hold the same changes" until one side drops. Automerge names a change by actor and number where Kleppmann's construction needs the hash. @@ -1819,18 +1830,19 @@ Nodes and syncing: | 101 | 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` | | 102 | Writes its own member entry without end; fills the waiting changes; sends changes that say they saw little, each to be judged far back | 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` | | 103 | 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` | +| 104 | Crafts a change Automerge takes and shouldn't: bytes it wouldn't encode itself, an actor named that nobody wrote as, operations numbered far ahead of its dependencies' or below them | Refuse before Automerge sees it: applied, such a change makes a node panic, or its document save to bytes that don't load | 1, 2 | unit: `only_what_automerge_writes` | Rules, and the swarm as it is: | # | The adversary | Honest nodes | Promise | Shown by | |---|---|---|---|---| -| 104 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` | -| 105 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` | -| 106 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` | -| 107 | A root that lies and isn't left out; 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` | -| 108 | 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` | -| 109 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` | -| 110 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` | +| 105 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` | +| 106 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` | +| 107 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` | +| 108 | A root that lies and isn't left out; 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` | +| 109 | 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` | +| 110 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` | +| 111 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` | ## The registry on it ``` @@ -1887,16 +1899,16 @@ the network at large reads. ## Stages Each leaves the system working, and is a few patches with its tests, which leave -their vectors. At every stage the existing tests pass untouched (110). +their vectors. At every stage the existing tests pass untouched (111). 1. **A federated swarm's frame.** `--genesis-policy` (a file, written into the genesis change with the roots, the voters and the users it starts with); a federated node - is given its root, syncs under no policy it doesn't know, takes no remake yet, - takes tokens and logins by key as its operator says, keeps ended sessions to - itself, stamps as the policy says, and writes a member entry of the policy's shape - and size. What the genesis change sets for the swarm as a whole is read from the - policy. Tests: 97 to 100, 106, 110, and the policy's existing tests under a policy - from the root. + is given its root, syncs under no policy it doesn't know, refuses a change that + isn't what Automerge itself writes, takes no remake yet, takes tokens and logins by + key as its operator says, keeps ended sessions to itself, stamps as the policy + says, and writes a member entry of the policy's shape and size. What the genesis + change sets for the swarm as a whole is read from the policy. Tests: 97 to 100, + 104, 107, 111, 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, the epoch and what its signer saw in an envelope; nodes carrying for users by their own word, and the rule for committers by it; nothing plain; the @@ -1926,7 +1938,7 @@ their vectors. At every stage the existing tests pass untouched (110). 8. **Coming back.** The drop an operator asks for, a forked actor proven and shown with what the roots' nodes hold, the budget and the share per party. Tests: 94, 101 to 103. -9. **Bans** for those who follow. Tests: 107, 108. +9. **Bans** for those who follow. Tests: 108, 109. 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 tried: users, hosts, names, a root that settles, names that become final. It isn't to be relied @@ -1938,10 +1950,10 @@ their vectors. At every stage the existing tests pass untouched (110). `GET /registry/decisions`. What is decided: a number, a user's first keys, the names of a user that is out, whose a contested name is, a name the rules leave to the voters. The simulations start from a root change naming several voters, as a - remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 109. + remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 110. 12. **Versions.** The digest with every stamp, a node checking itself before it writes; for every swarm, a node that speaks the wire version before its own, and a - handshake that says which epochs its node keeps. Tests: 104, 105. + handshake that says which epochs its node keeps. Tests: 105, 106. 13. **Remakes.** The proposal with who votes and who the roots are; the coordinator and the base, taking a remake up by its result, the snapshot every node builds, what it leaves out and what can't be written again; carrying over, by every node @@ -1951,7 +1963,7 @@ their vectors. At every stage the existing tests pass untouched (110). its operator gave, and by none that peers advertise. Tests: 55, 56, 75 to 87. 14. **The policy by a decision.** The policy as a matter, a node that doesn't know it, what it no longer covers: shown aside, taken away by its user only, dropped after - a time, moved at a remake. Tests: 73, 74, 106. + a time, moved at a remake. Tests: 73, 74, 107. 15. **Going apart, and refusing.** A fork followed by an operator's word, with who votes and who the roots are on its side. Refusing a decision: a node's bounds, the epoch without the decision, what a node takes along. Tests: 64, 88 to 92. From @@ -1999,6 +2011,14 @@ with the whole batch it came in (`DuplicateSeqNumber`); the change that made an operation is found (`hash_for_opid`), so the change carrying a value is found from the document. +Measured upstream, with Automerge 0.12.0 alone, on histories of small writes to a map: + +* It applies a change that lists an actor none of its operations names, and then + gives back another change under that hash and saves a document that doesn't load; + where the document doesn't hold that actor, applying panics. It applies a change + whose first operation is numbered below its dependencies', and the save doesn't + load; one numbered 2^32 − 1, and the node's next write panics. + From the docs: a node under an unknown policy receives without judging; every node takes a token any member signed, and lets in by key any user of the registry; where a refused member shows; the cost of checking a signature; a node keeps the documents @@ -2039,3 +2059,6 @@ Assumed, to be shown as it is built: * The digest of the registry as it resolves is cheap enough to make with every stamp at a registry's size, and to make at another node's stamp now and then. * A version can speak the wire version before its own. +* The three things asked of a change before Automerge sees it keep out every change + it applies and shouldn't. Six such changes were tried; operations on objects that + don't exist, and others crafted, weren't. |
