1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
# Testing the store and the federation: a plan
A plan, built stage by stage (By stage): so far, the store's tests. 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 and forks), 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.
* **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.** A fork takes nothing of the store it came from after its heads, nor that
store of it; and its root keeps what counts at its heads with its version current.
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, nor heads that leave out what it held for a while.
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; and honest nodes
hold one document, whatever each takes from it.
* **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; an event whose value holds names JCS sorts by their
UTF-16 units otherwise than by their bytes (one from U+E000 to U+FFFF beside one beyond
U+FFFF); events at federation 1's sizes and just past them; a signature, a version and
its hash, a checkpoint and its ID, the genesis change of a federation's root and of a
fork'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**: 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.
|