aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 12:46:42 +0000
committertv <tv@krebsco.de>2026-11-19 13:52:29 +0100
commit03105d40322dff9c18f0571872ab0f643aded0f7 (patch)
treea96b625f4d57d23ee12a6db72780446530b413cd
parente8f0760a9b08e6b1a7372e79c48744035d1e4e1a (diff)
federation: checked against the release a federation-<F>.<R> tag namesfederation-1.1
A corpus of generated histories, committed, said what this code made of them, right or not, and held hundreds of kilobytes a revision; generated from code that changes, it could only be checked, never written again. Each release that makes a revision is tagged `federation-<F>.<R>`, the federation's number and the revision's (`federation-1.1`, revision 1 of federation 1). `scripts/federation-check` writes histories from this tree (`write_histories`, an ignored test): of each revision it knows and each kind the properties generate, those of a few seeds from a random one it says, and the attack tests' crafted ones, as each test offered them where nothing but offers made them. It judges them with `continuum-party judge` here and with the continuum the latest such tag names (or one given), built in a worktree and kept between runs, leaves out those whose root the tagged one reads as none, and says where the two differ. Run before a release, not by `cargo quick`. The corpus and its test are gone; the test plan and `federation.md` say how a release is checked.
-rw-r--r--docs/federation-tests.md38
-rw-r--r--docs/federation.md11
-rwxr-xr-xscripts/federation-check78
-rw-r--r--src/federation/corpus.rs315
-rw-r--r--src/federation/judge.rs60
-rw-r--r--src/federation/mod.rs2
6 files changed, 167 insertions, 337 deletions
diff --git a/docs/federation-tests.md b/docs/federation-tests.md
index c22f300..eeb90b6 100644
--- a/docs/federation-tests.md
+++ b/docs/federation-tests.md
@@ -124,22 +124,26 @@ and a key set `ssh-keygen` signed with it. A vector that changes is a change to
every node must agree on ([`federation.md`](federation.md),
[Changing the federation](federation.md#changing-the-federation)).
-## The corpus
+## Against released revisions
-What each revision takes, refuses and reads, as fixed bytes: for each revision this
-continuum knows, a file in `src/federation/corpus/` of histories generated at that
-revision (of every kind the properties generate, those of the first two seeds, and of the
-next few hundred those showing what the ones kept don't: of each kind of event, what
-became of one, a version written, a move, a stop; eight at most), each event's bytes with
-what became of it, by kind (taken, refused and why, by kind, waiting, held back, gone with
-a move), and what the store reads after. Together they show a version written, a move to
-a checkpoint, a stop, and a merge event taken where the revision has merge events, else
-refused. A revision's file is written once, as the
-revision is made (`write_the_corpus`, run by hand), and never edited after: every later
-continuum judges it alike (`every_revision_judges_as_its_corpus_says`), so that a change
-to judging that alters an earlier revision's comes as a later revision. Its first line
-names the revision by its ID: a feature renamed fails as a judgment changed does. It holds
-only what its histories exercise.
+A release judges every history under the revisions an earlier release knows as that one
+did, the earlier one's continuum built and asked. Each release that makes a revision is
+tagged `federation-<F>.<R>`, the federation's number and the revision's
+(`federation-1.1`, revision 1 of federation 1); `scripts/federation-check` judges the same
+histories with the continuum the latest such tag names (or one given) and with the tree it
+runs in, and says where they differ. The histories: of each revision this tree knows and
+each kind the properties generate, those of a few seeds (`write_histories`, from a random
+seed it says, `CONTINUUM_TEST_SEED` to rerun them), and the attack tests' crafted ones, as
+each test offered them where nothing but offers made them (`attacks::recording`); those
+whose root the tagged continuum reads as none, of a revision after it, it leaves out. Both
+judge with `continuum-party judge`, whose format no release changes (`federation::judge`):
+what became of each event, by kind and never by a refusal's words, and what the store
+reads after.
+
+So a change to judging that alters what an earlier revision does comes as a later
+revision, and the check, run before a release, says so where one doesn't. It needs the
+tags and a build of the tagged commit, kept between runs; a tree without git's history
+can't run it, nor a release before `judge`.
## Fuzzing and mutants
@@ -154,8 +158,10 @@ only what its histories exercise.
* `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, the corpus, and the check that every row has its test.
+ vectors, and the check that every row has its test.
* `cargo sim`: the simulations.
+* Before a release: `scripts/federation-check`, against the latest `federation-<F>.<R>`
+ tag ([Against released revisions](#against-released-revisions)).
* 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.
diff --git a/docs/federation.md b/docs/federation.md
index 30bff6e..8dc23b3 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -881,10 +881,13 @@ version names: a change there splits the swarm until every node runs it
A version leaves `revision` out for the base revision, and names a revision no earlier
than that of the version it changes. What a revision adds counts at a history only where
the version current there names that revision or a later one: before, every node judges
-as before, so that what a party uses early, every node refuses alike. A version is read by
-the revision it names, so one moving to a revision may already hold what that revision
-adds to a version; its proposal, the votes on it and its version event are judged under
-the version before. A node voting by itself backs no version changing the revision
+as before, so that what a party uses early, every node refuses alike. A release making a
+revision is tagged `federation-<F>.<R>`, and every later one is checked to judge as it
+does under the revisions it knows ([`federation-tests.md`](federation-tests.md),
+[Against released revisions](federation-tests.md#against-released-revisions)). A version
+is read by the revision it names, so one moving to a revision may already hold what that
+revision adds to a version; its proposal, the votes on it and its version event are judged
+under the version before. A node voting by itself backs no version changing the revision
([Votes a node casts by itself](#votes-a-node-casts-by-itself)): its party's operators
vote on it.
diff --git a/scripts/federation-check b/scripts/federation-check
new file mode 100755
index 0000000..e31e002
--- /dev/null
+++ b/scripts/federation-check
@@ -0,0 +1,78 @@
+#!/bin/sh
+# Judges the same histories with continuum as a federation tag names it and with this
+# tree, and says where they differ (docs/federation-tests.md: Against released
+# revisions). Each release that makes a revision of the federation is tagged
+# federation-<F>.<R>, the federation's number and the revision's (federation-1.1 for
+# revision 1 of federation 1); a later one judges every history under the revisions that
+# release knows as it did. Run before a release, from a checkout with its tags.
+#
+# scripts/federation-check [TAG]
+#
+# TAG is the latest federation-<F>.<R> unless given. The histories: of each
+# revision and kind, generated from CONTINUUM_TEST_SEED on (a random one, said, unless
+# given), CONTINUUM_TEST_CASES times as many as `write_histories` writes; and those the
+# attack tests offer. CONTINUUM_FEATURES are the features both are built with, a
+# transport among them (federation,mycelium unless given); the tag's build is kept in
+# CONTINUUM_CHECK_TARGET (~/.cache/continuum/federation-check unless given) for the
+# next run.
+
+set -eu
+
+cd "$(git rev-parse --show-toplevel)"
+
+tag=${1:-$(git tag --list 'federation-[0-9]*.[0-9]*' --sort=-version:refname | head -n 1)}
+if [ -z "$tag" ]; then
+ echo "federation-check: no federation-<F>.<R> tag to check against" >&2
+ exit 2
+fi
+features=${CONTINUUM_FEATURES:-federation,mycelium}
+seed=${CONTINUUM_TEST_SEED:-$(od -An -N4 -tu4 /dev/urandom | tr -d ' ')}
+cache=${XDG_CACHE_HOME:-$HOME/.cache}
+target=${CONTINUUM_CHECK_TARGET:-$cache/continuum/federation-check}
+
+work=$(mktemp -d)
+clean() {
+ git worktree remove --force "$work/tagged" >/dev/null 2>&1 || true
+ rm -rf "$work"
+}
+trap clean EXIT
+trap 'exit 130' INT TERM
+
+echo "federation-check: $tag against this tree, histories from seed $seed" >&2
+echo "federation-check: CONTINUUM_TEST_SEED=$seed reruns them" >&2
+
+CONTINUUM_HISTORIES="$work/histories" CONTINUUM_TEST_SEED=$seed \
+ cargo test -q --features "$features" --lib write_histories -- --ignored >&2
+cargo run -q --features "$features" --bin continuum-party -- judge \
+ <"$work/histories" >"$work/here"
+
+git worktree add -q --detach "$work/tagged" "$tag"
+(cd "$work/tagged" && CARGO_TARGET_DIR=$target \
+ cargo run -q --features "$features" --bin continuum-party -- judge) \
+ <"$work/histories" >"$work/there"
+
+# Histories whose root the tag's continuum reads as none, of a revision after it, it
+# doesn't judge: left out on both sides.
+awk '/^case /{label=substr($0, 6)} $0 == "root none"{print label}' "$work/there" \
+ >"$work/unread"
+keep() {
+ awk -v unread="$work/unread" '
+ BEGIN { while ((getline line < unread) > 0) skip[line] = 1 }
+ /^case / { label = substr($0, 6) }
+ !(label in skip)
+ ' "$1"
+}
+keep "$work/there" >"$work/there.kept"
+keep "$work/here" >"$work/here.kept"
+
+judged=$(grep -c '^case ' "$work/there.kept" || true)
+left=$(wc -l <"$work/unread" | tr -d ' ')
+if diff -u --label "$tag" --label "this tree" "$work/there.kept" "$work/here.kept" \
+ >"$work/differ"; then
+ echo "federation-check: $judged histories judged alike" \
+ "($left of revisions after $tag left out)"
+else
+ head -n 200 "$work/differ"
+ echo "federation-check: this tree judges otherwise than $tag (seed $seed): above" >&2
+ exit 1
+fi
diff --git a/src/federation/corpus.rs b/src/federation/corpus.rs
deleted file mode 100644
index f19e2b1..0000000
--- a/src/federation/corpus.rs
+++ /dev/null
@@ -1,315 +0,0 @@
-//! What each revision of federation 1 takes, refuses and reads, as fixed bytes
-//! (`docs/federation-tests.md`, The corpus): for each revision this continuum knows, a file
-//! in `corpus/` of histories generated at that revision, each with what became of every
-//! event and what the store reads after, written once when the revision is made
-//! (`write_the_corpus`) and never edited after. Every later continuum judges them alike: a
-//! change to judging that alters what an earlier revision's corpus says comes as a later
-//! revision.
-
-use std::collections::{BTreeMap, BTreeSet};
-use std::fmt::Write as _;
-use std::path::PathBuf;
-
-use super::event::{Does, Event};
-use super::fold::Federation;
-use super::properties::{self, History, Kind};
-use super::revision::{Feature, Revision};
-use super::store::Id;
-use super::store::memory::{Refusal, Store};
-use crate::testrand::Rng;
-
-/// Of each kind, the seeds histories are generated from, the first so many kept
-/// whatever they show, and at most how many kept.
-const SCANNED: u64 = 400;
-const FIRST: u64 = 2;
-const MOST: usize = 8;
-
-/// The kinds of history generated: with an adversary or not, versions naming checkpoints
-/// or not, and versions this continuum doesn't read or not.
-fn kinds() -> Vec<Kind> {
- let mut kinds = Vec::new();
- for adversary in [false, true] {
- for checkpoints in [false, true] {
- for unread in [false, true] {
- kinds.push(Kind {
- adversary,
- checkpoints,
- unread,
- });
- }
- }
- }
- kinds
-}
-
-fn dir() -> PathBuf {
- PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("src/federation/corpus")
-}
-
-/// The file of `revision`'s corpus: by its number and the feature it adds, or `base`.
-fn file(revision: Revision) -> PathBuf {
- let name = match revision.features().last() {
- None => "0-base".to_owned(),
- Some(feature) => format!("{}-{}", revision.0, feature.name()),
- };
- dir().join(format!("{name}.txt"))
-}
-
-/// The first line of `revision`'s corpus, naming it by its ID, so that a renamed feature
-/// fails as a changed judgment does.
-fn header(revision: Revision) -> String {
- format!(
- "continuum federation 1, {revision}, ID {}: never edited once released",
- revision.id()
- )
-}
-
-/// What became of `id` in `store`, by kind: never a refusal's words, which may change.
-fn became(store: &Store<Federation>, id: &Id) -> String {
- if store.stopped().is_some_and(|(at, ..)| at == id) {
- return "stopped at".to_owned();
- }
- if store.held_back().iter().any(|(held, _)| held == id) {
- return "held back".to_owned();
- }
- if store.holds(id) {
- return "taken".to_owned();
- }
- if store.get(id).is_some() {
- return "kept".to_owned();
- }
- match store.refusal(id) {
- Some(Refusal::None) => "refused: none".to_owned(),
- Some(Refusal::Judged(_)) => "refused: judged".to_owned(),
- Some(Refusal::BuiltOn(_)) => "refused: built on a refused one".to_owned(),
- Some(Refusal::NotAbove) => "refused: not above the checkpoint".to_owned(),
- Some(Refusal::Own) => "refused: its own".to_owned(),
- Some(Refusal::Dropped) => "refused: dropped".to_owned(),
- None if store.is_waiting(id) => "waiting".to_owned(),
- None => "gone with a move".to_owned(),
- }
-}
-
-/// What `store` reads: its checkpoint, the current version, the values at places, the
-/// members, and the event it stopped at; a line of JSON.
-fn reads(store: &Store<Federation>) -> String {
- let state = store.state();
- let values: BTreeMap<String, String> = state
- .values()
- .into_iter()
- .map(|(path, value)| (path, String::from_utf8_lossy(&value.bytes()).into_owned()))
- .collect();
- serde_json::json!({
- "checkpoint": Id::of(store.checkpoint()).to_string(),
- "current": state.current().hash.to_string(),
- "values": values,
- "members": state.members(),
- "stopped": store.stopped().map(|(id, ..)| id.to_string()),
- })
- .to_string()
-}
-
-/// A store from `root`, offered `events` in their order.
-fn offered(root: &[u8], events: &[Vec<u8>]) -> Store<Federation> {
- let mut store = Store::new(root.to_vec(), Vec::new()).expect("a root");
- for event in events {
- store.offer(event.clone());
- }
- store
-}
-
-/// What a history shows of what a corpus is to hold: of each kind of event, what became
-/// of one; and whether a version was written, the store moved to a checkpoint, or stopped.
-fn shows(history: &History) -> BTreeSet<String> {
- let store = offered(&history.root, &history.events);
- let mut shown = BTreeSet::new();
- if store.state().current().number > 0 {
- shown.insert("a version written".to_owned());
- }
- if Id::of(store.checkpoint()) != store.id() {
- shown.insert("a move to a checkpoint".to_owned());
- }
- if store.stopped().is_some() {
- shown.insert("a stop".to_owned());
- }
- for event in &history.events {
- let kind = match Event::read_taken(event) {
- Some(Event::Signed(signed)) => match signed.does {
- Does::Write { .. } => "a write",
- Does::Keys(_) => "a key set",
- Does::Nodes(_) => "a node list",
- Does::Proposal { .. } => "a proposal",
- Does::Vote { .. } => "a vote",
- Does::Merge => "a merge event",
- },
- Some(Event::Version { .. }) => "a version event",
- None => "no event",
- };
- shown.insert(format!("{kind}: {}", became(&store, &Id::of(event))));
- }
- shown
-}
-
-/// A case: a root, and its events offered in the order written; what each became, and
-/// what the store reads after, as the corpus spells them.
-fn case(label: &str, root: &[u8], events: &[Vec<u8>]) -> String {
- let store = offered(root, events);
- let mut text = format!("case {label}\nroot {}\n", String::from_utf8_lossy(root));
- for event in events {
- let _ = writeln!(text, "event {}", String::from_utf8_lossy(event));
- let _ = writeln!(text, "became {}", became(&store, &Id::of(event)));
- }
- let _ = writeln!(text, "reads {}", reads(&store));
- text
-}
-
-/// `revision`'s corpus, generated: of each kind, histories whose first version follows
-/// `revision`, those of the first seeds, and of the rest those showing what the ones kept
-/// don't (`shows`), up to `MOST`.
-fn generated(revision: Revision) -> String {
- let mut text = header(revision) + "\n";
- for kind in kinds() {
- let mut held = BTreeSet::new();
- let mut kept = 0;
- for seed in 0..SCANNED {
- if kept == MOST {
- break;
- }
- let history = properties::generate_at(&mut Rng::new(seed), kind, Some(revision));
- let shown = shows(&history);
- if seed >= FIRST && shown.is_subset(&held) {
- continue;
- }
- held.extend(shown);
- kept += 1;
- let label = format!("seed {seed}, {kind:?}");
- text += &case(&label, &history.root, &history.events);
- }
- }
- text
-}
-
-/// A corpus's cases, read: each its label, its root, and its events with what each
-/// became, and what the store reads after.
-struct Case {
- label: String,
- root: Vec<u8>,
- events: Vec<(Vec<u8>, String)>,
- reads: String,
-}
-
-fn parse(text: &str) -> Result<(String, Vec<Case>), String> {
- let mut lines = text.lines();
- let header = lines.next().ok_or("an empty corpus")?.to_owned();
- let mut cases: Vec<Case> = Vec::new();
- let mut event: Option<Vec<u8>> = None;
- for line in lines {
- let (word, rest) = line.split_once(' ').ok_or(format!("no line: {line:?}"))?;
- let current = cases.last_mut();
- match (word, current) {
- ("case", _) => cases.push(Case {
- label: rest.to_owned(),
- root: Vec::new(),
- events: Vec::new(),
- reads: String::new(),
- }),
- ("root", Some(case)) => case.root = rest.as_bytes().to_vec(),
- ("event", Some(_)) => event = Some(rest.as_bytes().to_vec()),
- ("became", Some(case)) => {
- let bytes = event.take().ok_or("`became` without its event")?;
- case.events.push((bytes, rest.to_owned()));
- }
- ("reads", Some(case)) => case.reads = rest.to_owned(),
- _ => return Err(format!("no line of a corpus: {line:?}")),
- }
- }
- Ok((header, cases))
-}
-
-/// Writes the corpus of every revision this continuum knows that has none: once, when a
-/// revision is made, its file then committed and never edited. Run by hand:
-/// `cargo test --features federation write_the_corpus -- --ignored`.
-#[test]
-#[ignore = "writes into the source tree: run by hand when a revision is made"]
-fn write_the_corpus() {
- std::fs::create_dir_all(dir()).expect("the corpus's directory");
- for revision in Revision::known() {
- let path = file(revision);
- if !path.exists() {
- std::fs::write(&path, generated(revision)).expect("the corpus written");
- println!("wrote {}", path.display());
- }
- }
-}
-
-/// Every revision this continuum knows has its corpus, which it judges and reads as the
-/// corpus says; and which shows a version written, a move to a checkpoint and a stop, and
-/// what became of a merge event at that revision: taken where it has merge events, else
-/// refused.
-#[test]
-fn every_revision_judges_as_its_corpus_says() {
- for revision in Revision::known() {
- let path = file(revision);
- let text = std::fs::read_to_string(&path).unwrap_or_else(|_| {
- panic!(
- "no corpus of {revision} ({}): write it once, as the revision is made, with \
- `cargo test --features federation write_the_corpus -- --ignored`, and \
- commit it",
- path.display()
- )
- });
- let (named, cases) = parse(&text).unwrap_or_else(|why| panic!("{}: {why}", path.display()));
- assert_eq!(
- named,
- header(revision),
- "{}: another revision",
- path.display()
- );
- assert!(!cases.is_empty(), "{}: no case", path.display());
- let mut shown = BTreeSet::new();
- for case in cases {
- let events: Vec<Vec<u8>> = case.events.iter().map(|(bytes, _)| bytes.clone()).collect();
- let judged = self::case(&case.label, &case.root, &events);
- shown.extend(shows(&History {
- root: case.root.clone(),
- events,
- }));
- let (_, again) = parse(&format!("{named}\n{judged}")).expect("as written");
- let again = &again[0];
- for ((bytes, was), (_, is)) in case.events.iter().zip(&again.events) {
- assert_eq!(
- was,
- is,
- "{}, {}: the event {} became otherwise",
- path.display(),
- case.label,
- Id::of(bytes)
- );
- }
- assert_eq!(
- case.reads,
- again.reads,
- "{}, {}: the store reads otherwise",
- path.display(),
- case.label
- );
- }
- let merged = if revision.has(Feature::MergeEvents) {
- "a merge event: taken"
- } else {
- "a merge event: refused: judged"
- };
- for wanted in [
- "a version written",
- "a move to a checkpoint",
- "a stop",
- merged,
- ] {
- assert!(
- shown.contains(wanted),
- "{}: no case shows {wanted}",
- path.display()
- );
- }
- }
-}
diff --git a/src/federation/judge.rs b/src/federation/judge.rs
index 4fc4ce8..2936bdc 100644
--- a/src/federation/judge.rs
+++ b/src/federation/judge.rs
@@ -142,7 +142,67 @@ fn reads(store: &Store<Federation>) -> String {
#[cfg(test)]
mod tests {
use super::*;
+ use crate::federation::attacks;
use crate::federation::harness::{self, Party, Spec};
+ use crate::federation::properties::{self, Kind};
+ use crate::federation::revision::Revision;
+ use crate::testrand::Rng;
+
+ /// Of each revision and kind, how many seeds' histories are written, times
+ /// `CONTINUUM_TEST_CASES`.
+ const CASES: u64 = 25;
+
+ /// Writes the histories to judge to the file `CONTINUUM_HISTORIES` names
+ /// (`scripts/federation-check`): of each revision this continuum knows and each kind
+ /// the properties generate, the histories of `CASES` seeds from `CONTINUUM_TEST_SEED`
+ /// on; and those the attack tests offer, where nothing but offers made them.
+ #[test]
+ #[ignore = "writes the file CONTINUUM_HISTORIES names: run by scripts/federation-check"]
+ fn write_histories() {
+ let path = std::env::var("CONTINUUM_HISTORIES").expect("CONTINUUM_HISTORIES: a file");
+ let env = |name: &str| {
+ std::env::var(name)
+ .ok()
+ .and_then(|value| value.parse::<u64>().ok())
+ };
+ let first = env("CONTINUUM_TEST_SEED").unwrap_or(0);
+ let cases = CASES.saturating_mul(env("CONTINUUM_TEST_CASES").unwrap_or(1));
+ let mut histories = Vec::new();
+ for revision in Revision::known() {
+ for adversary in [false, true] {
+ for checkpoints in [false, true] {
+ for unread in [false, true] {
+ let kind = Kind {
+ adversary,
+ checkpoints,
+ unread,
+ };
+ for seed in first..first.saturating_add(cases) {
+ let generated =
+ properties::generate_at(&mut Rng::new(seed), kind, Some(revision));
+ histories.push(History {
+ label: format!("{revision}, seed {seed}, {kind:?}"),
+ root: generated.root,
+ events: generated.events,
+ });
+ }
+ }
+ }
+ }
+ }
+ for (name, test) in attacks::TESTS {
+ for (n, recorded) in attacks::recording(*test).into_iter().enumerate() {
+ if recorded.offers_only {
+ histories.push(History {
+ label: format!("{name}, store {n}"),
+ root: recorded.root,
+ events: recorded.events,
+ });
+ }
+ }
+ }
+ std::fs::write(&path, spelled(&histories)).expect("the histories written");
+ }
/// Histories read back as spelled, and judged as the format says: an event taken, one
/// refused, and a root of a revision this continuum doesn't know read as none.
diff --git a/src/federation/mod.rs b/src/federation/mod.rs
index 18fc70d..b86bc53 100644
--- a/src/federation/mod.rs
+++ b/src/federation/mod.rs
@@ -11,8 +11,6 @@ pub(crate) mod agent;
#[cfg(test)]
mod attacks;
pub(crate) mod client;
-#[cfg(test)]
-mod corpus;
pub(crate) mod event;
pub(crate) mod fold;
pub(crate) mod fork;