From f2ed3e1e9e9c6199fb0bc3b1e2efb4eeb5f89b05 Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 14:38:16 +0000 Subject: 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. --- docs/federation-tests.md | 149 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 149 insertions(+) create mode 100644 docs/federation-tests.md (limited to 'docs/federation-tests.md') 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. -- cgit v1.3.1