diff options
| author | tv <tv@krebsco.de> | 2026-11-16 14:38:16 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 16:26:55 +0100 |
| commit | f2ed3e1e9e9c6199fb0bc3b1e2efb4eeb5f89b05 (patch) | |
| tree | 4ccdd3eb355ec436dd5f9eb32b1fcc32780577bb /docs | |
| parent | 0dde043f1e8c6e8c99a876b4d0dffdd499a9c961 (diff) | |
docs/federation-tests: how the store and the federation are tested
A plan, the contract the code is built to: the fold and the store tested as pure code,
events in and verdicts and states out; a model written plainly from the design, which
the store is checked against; every rule by its smallest scenarios; every attack row a
test named by its table and number, and a test that every row has one; the promises as
properties over generated histories, every order for small ones and seeded ones beyond,
cut down before they are printed; the store on Automerge checked against the store in
memory; simulations with an adversary node; fixed vectors for every encoding; fuzzing
and mutants in longer runs. All of it behind the `federation` feature, by stage.
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/federation-tests.md | 149 | ||||
| -rw-r--r-- | docs/federation.md | 2 | ||||
| -rw-r--r-- | docs/store.md | 3 |
3 files changed, 152 insertions, 2 deletions
diff --git a/docs/federation-tests.md b/docs/federation-tests.md new file mode 100644 index 0000000..fa23ae7 --- /dev/null +++ b/docs/federation-tests.md @@ -0,0 +1,149 @@ +# Testing the store and the federation: a plan + +A plan, not what the code does: none of this is built. It says how the store +([`store.md`](store.md)) and the federation ([`federation.md`](federation.md)) are +tested, so that nothing in continuum breaks the federation, and no change made later +breaks it apart. It is the contract the code is built to: a stage is done when its tests +are. + +## What the tests rest on + +* **The core is pure.** The fold and the store in memory take events as values and give + verdicts and states: no network, no clock, no disk, no Automerge. Everything that can + be checked there is checked there. What Automerge and the network add is tested for + that alone: that they carry the events and change nothing the store holds. +* **Every run is the same run.** Randomness comes from a seed, as + `what_passes_leaves_automerge_sound` takes it (SplitMix64); a failing test prints its + seed, and a seed that failed once stays as a fixed case. +* **Every attack is a test.** Every row of the attack tables (`federation.md` and + `store.md`, Attacks) has a test named by its table and number (`federation_attack_12`, + `store_attack_23`), of the kind its row says. A test reads both tables from the + documents and checks that every row has its test, and that no test names a row that + isn't there. +* **Every byte is fixed.** Every encoding the nodes must agree on has vectors, byte for + byte (Fixed bytes). +* **Nothing else changes.** All of it is behind the `federation` feature. A build + without it runs the tests continuum has today, untouched, and passes them. + +## The harness + +* **Keys.** Ed25519 keys made from seeds, signing as `ssh-keygen -Y sign` does; a vector + checks one signature against `ssh-keygen` itself. +* **Events.** A builder for every kind (writes, key sets, node lists, proposals, votes, + version events, checkpoints, roots, forks and merges), each from a party, a key and + its dependencies, encoded and signed as the design says; and for what is none: bytes + that aren't JCS, a field missing or more, another key, a broken signature, too large. +* **Scenarios.** A scenario is a value: the parties and the first version, events by + name with their dependencies, which node is given which events in which order, and + what is expected (each node's verdicts, the current version, what counts, the + members). It prints as the builder calls that make it, so a failure found by + generating pastes in as a test. +* **The model.** A second fold, written from `federation.md` as plainly as it can be: it + reads every history by adding all of its events anew, keeps no state, makes no + checkpoint. It is slow and short, and it is what the store is checked against: both + given the same events in the same order must give the same verdicts and the same + state. + +## The fold and the store, by example + +* **The rules.** Every rule of `federation.md` by the smallest scenarios that show it: + passing and dead, for every number of parties from 1 to 20; one yes at a time; which + version a node takes, and the current one; a party's keys and node list by their + `since`; a place's value; rules matching (`{party}`, `*`, `**`, first match); what + counts, item by item; checkpoints and what they keep; forks and merges. +* **The attacks marked unit**, each by a scenario, its expectation the row's. +* **The store** with a fold made for its tests, smaller than the federation's, for what + `store.md` checks (Tests): order, history, refusal, checkpoints. + +## Properties, over generated histories + +Histories are generated: a few parties (3 to 7), their keys, versions passing, honest +writes and votes, and an adversary that signs anything its own keys or stolen ones can, +on any dependencies, and puts out events no party signs. Each property is checked for +every order of every history small enough (up to some 8 events, every order that puts +each after its dependencies), and for seeded histories and orders beyond that. + +1. **Order.** The same events give the same state, in every order, on every node. +2. **History.** Judging at a history gives what the model gives. +3. **Refusal.** What is refused is refused with everything built on it. +4. **What counts.** Every value that counts is signed by a key among its party's keys, + at a place the current version gives its party. +5. **The policy.** Every version taken has two thirds of the parties of the version it + changes voting `true` in its history. Without a party voting twice, at most one + version changes a version, and nodes holding the same events read the same current + version. +6. **Voting twice.** Wherever two versions change one, the tool over the votes names a + party with `true` and `false` on one proposal, or `true` on two of one version + neither dead. +7. **Checkpoints.** Judging any event above a checkpoint's heads gives the verdict + judging it with the whole history gives; reading gives what the whole history reads + but for what counted no more; nodes moving at different times read the same once they + hold the same; moving refuses nothing that decided it. +8. **Forks and merges.** A fork takes nothing of the stores it came from after its + heads, nor they of it; a merge's state is the values that count on each side at + places its version gives their party, and a key dropped on one side brings back + nothing until its party lists it again. +9. **Votes a node casts by itself.** By its rules a node casts one yes at a time, never + `true` and `false` on one proposal, and, by a rule for checkpoints, backs nothing + that changes more. + +A failing history is cut down before it is printed: events are taken out, one at a time +and with what is built on them, for as long as it still fails. + +## The store on Automerge + +* **The same as in memory.** The same events through the store on Automerge and the + store in memory give the same state, for seeded runs of changes, refusals, drops, + events put again, checkpoints, remakes, rejoins and writers forked. +* **Changes that stay sound.** What a node of a swarm holding a store commits passes + screening on every other node, and what screening takes leaves Automerge sound: the + generated changes of `what_passes_leaves_automerge_sound` with the store's among them. +* **The attacks marked unit** of `store.md`, each by crafted changes. + +## Simulations + +In [`src/simtest/`](../src/simtest/), whole nodes on the simulated network: swarms of 3 +to 7 parties, honest nodes and an adversary node the test drives. It sends different +events and changes to different peers, withholds, crafts changes, decides two remakes +for one epoch. The network partitions, delays and restarts nodes, by seed. Once it is +quiet, the test checks that honest nodes holding the same events read the same, and what +each row marked sim expects. + +## Fixed bytes + +Vectors for: an event and its ID, a signature, a version and its hash, a checkpoint and +its ID, the genesis change of a federation's root, of a fork's and of a merge's, and a +snapshot after a checkpoint. A vector that changes is a change of the federation, which +takes its next number ([`federation.md`](federation.md), Changing the federation). + +## Fuzzing and mutants + +* **Fuzzing**, with `cargo fuzz` (a nightly compiler), outside `cargo quick`: the event + decoder and the fold's judging given any bytes, and screening given any change of a + swarm holding a store, refuse what isn't theirs and never panic. The vectors and + generated scenarios seed it; what it finds becomes a fixed case. +* **Mutants**, with `cargo mutants`, now and then over the store and the fold: a change + to the code that no test notices is a test missing, or code that can go. + +## What runs where + +* `cargo quick`: the rules and attacks by example, the properties at small sizes and a + few hundred seeds, the store on Automerge by crafted changes and seeded runs, the + vectors, and the check that every row has its test. +* `cargo sim`: the simulations. +* Longer runs, by hand or on a schedule: the properties and the store on Automerge with + many more seeds (a count from the environment), fuzzing, mutants. + +## By stage + +1. **The store**: the harness, the store's own fold, its properties (order, history, + refusal, checkpoints). +2. **The federation's fold**: the model, the rules and attacks marked unit, the + properties, the vectors of events, versions and checkpoints. +3. **The store on Automerge**: the same as in memory, changes that stay sound, the + store's attacks marked unit, the simulations of a federation without forks or + remakes, the vectors of genesis changes. +4. **Forks**, merges among them: their rows, properties and vectors. +5. **Remakes**: their rows and simulations, and the vector of a snapshot after a + checkpoint. +6. **The registry**: its rules by example, and the tools reading and writing kartei. diff --git a/docs/federation.md b/docs/federation.md index ad42dd0..d2a0602 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -742,7 +742,7 @@ continuum builds and behaves as it does, and its tests pass untouched. members, checkpoints: what one keeps, and moving to one; the byte formats, and the sizes each may have. Its tests are its rows of Attacks, each with events made for it, and the promises checked over histories generated small enough to try every order, - and larger by seed. + and larger by seed ([`federation-tests.md`](federation-tests.md)). 3. **The store on Automerge**: a swarm started from its root, events in its document, what a change writes, every event put again whichever change carried it, what a checkpoint forgot read no more, a change carrying an event a move refuses dropped, diff --git a/docs/store.md b/docs/store.md index c51b9ca..952953c 100644 --- a/docs/store.md +++ b/docs/store.md @@ -349,7 +349,8 @@ crafted changes. *Sim*: a simulation. *Bench*: measured, not judged. ## Tests -What the tests check of the store, with a fold made for them: +What the tests check of the store, with a fold made for them +([`federation-tests.md`](federation-tests.md) says how they are built): * **Order.** For every order of a set of events that puts each after its dependencies (all of them for small sets, seeded ones for larger), the state is the same, and so |
