diff options
| author | tv <tv@krebsco.de> | 2026-11-16 18:43:42 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 20:08:49 +0100 |
| commit | 526f727ec1a5ff6c9d11c754966cf1ae472f21b3 (patch) | |
| tree | febfabb0de3103636b8f09637ad6151882e4a039 /src | |
| parent | 01a11cb403af0351411fe79deb49269b667bf881 (diff) | |
federation: properties over generated federations
Three to five parties write in their namespaces, change their key sets and node lists,
propose versions and checkpoints on what they last caught up with, vote, and write the
versions that pass; honest ones back one proposal on a version, an adversary votes as it
likes and signs as another party with its own key, or where it may not write. Over such
histories:
* the store judges every event, and reads, as the model does, offered the same events in
the same order, with an adversary and without;
* what builds on a refused event is refused;
* honest parties read the same whatever order the events come in, checkpoints and all;
* after a checkpoint, what the store took the model takes, reading the whole history but
for what the store refused as not above it, and the two read the same; the version
naming the checkpoint is taken;
* every version a store takes was backed by two thirds of the parties of the version it
changes, in its history;
* without a party voting twice, no two versions change one.
A failing history is cut down and printed.
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/mod.rs | 2 | ||||
| -rw-r--r-- | src/federation/properties.rs | 574 |
2 files changed, 576 insertions, 0 deletions
diff --git a/src/federation/mod.rs b/src/federation/mod.rs index aaa8225..8f6f351 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -15,5 +15,7 @@ pub(crate) mod jcs; pub(crate) mod keys; #[cfg(test)] mod model; +#[cfg(test)] +mod properties; pub(crate) mod store; pub(crate) mod version; diff --git a/src/federation/properties.rs b/src/federation/properties.rs new file mode 100644 index 0000000..7200703 --- /dev/null +++ b/src/federation/properties.rs @@ -0,0 +1,574 @@ +//! The federation's properties over generated histories (`docs/federation-tests.md`, +//! Properties): three to five parties write, change their key sets and node lists, propose +//! versions and checkpoints, vote, and write the versions that pass, each on what it last +//! caught up with; an adversary signs with its keys or stolen ones whatever it likes. The +//! store is checked against the model, which reads every history anew, and against itself +//! in other orders. A failing history is cut down, events taken out with what builds on +//! them for as long as it still fails, and printed. + +use std::collections::{BTreeMap, BTreeSet}; + +use ed25519_dalek::SigningKey; + +use super::event::{Checkpoint, Does, Event}; +use super::fold::Federation; +use super::harness::{self, Party, Spec}; +use super::model::{Model, Verdict}; +use super::store::memory::{Offered, Refusal, Store}; +use super::store::{Fold, Id}; +use super::version::Version; +use crate::access::sshsig::PublicKey; +use crate::testrand::{Rng, for_seeds}; + +/// The most events a history has. +const MOST: usize = 30; + +/// A root, and events in the order written. +#[derive(Clone)] +struct History { + root: Vec<u8>, + events: Vec<Vec<u8>>, +} + +impl History { + fn root_id(&self) -> Id { + Id::of(&self.root) + } + + fn store(&self, order: &[usize]) -> (Store<Federation>, Vec<Offered>) { + let mut store = Store::new(self.root.clone(), Vec::new()).expect("a root"); + let offered = order + .iter() + .map(|&i| store.offer(self.events[i].clone())) + .collect(); + (store, offered) + } + + fn written(&self) -> Vec<usize> { + (0..self.events.len()).collect() + } + + /// The history without the event at `i`, and what builds on it. + fn without(&self, i: usize) -> History { + let mut gone = BTreeSet::from([Id::of(&self.events[i])]); + let mut events = Vec::new(); + for event in &self.events { + let id = Id::of(event); + let deps = Federation::dependencies(event).unwrap_or_default(); + if gone.contains(&id) || deps.iter().any(|dep| gone.contains(dep)) { + gone.insert(id); + } else { + events.push(event.clone()); + } + } + History { + root: self.root.clone(), + events, + } + } + + fn show(&self) -> String { + std::iter::once(format!("root {}", String::from_utf8_lossy(&self.root))) + .chain( + self.events + .iter() + .map(|event| format!("{} {}", Id::of(event), String::from_utf8_lossy(event))), + ) + .collect::<Vec<_>>() + .join("\n") + } +} + +/// How a history is written: whether an adversary takes part, and whether versions name +/// checkpoints. +#[derive(Clone, Copy)] +struct Kind { + adversary: bool, + checkpoints: bool, +} + +/// One of `ids`, of the latest five more often than not. +fn pick(rng: &mut Rng, ids: &[Id]) -> Id { + if rng.chance(0.6) { + *rng.pick(&ids[ids.len().saturating_sub(5)..]) + } else { + *rng.pick(ids) + } +} + +fn root_of(spec: &Spec) -> Vec<u8> { + Checkpoint { + at: Vec::new(), + keeps: Vec::new(), + version: Version::read(&spec.json()).expect("a version"), + } + .bytes() +} + +fn generate(rng: &mut Rng, kind: Kind) -> History { + let count = rng.between(3, 5); + let parties: Vec<Party> = (0..count) + .map(|i| Party::new(&format!("p{i}"), i as u8 + 1)) + .collect(); + let adversary = count - 1; + let refs: Vec<&Party> = parties.iter().collect(); + let first = Spec::first(&refs, &[("names/{party}", harness::str("{party}"))]); + let root = root_of(&first); + let root_id = Id::of(&root); + let mut world: Store<Federation> = Store::new(root.clone(), Vec::new()).expect("a root"); + let mut specs: BTreeMap<Id, Spec> = BTreeMap::from([(first.hash(), first)]); + // The key each party signs its writes with: its version's, or its set's. + let mut signing: Vec<SigningKey> = parties.iter().map(|party| party.key.clone()).collect(); + let mut known: Vec<Vec<Id>> = vec![vec![root_id]; count]; + // Each proposal: its event, the version it proposes, the version it is on, and + // whether it names a checkpoint. + let mut proposals: Vec<(Id, Id, Id, bool)> = Vec::new(); + let mut votes: Vec<(Id, Id)> = Vec::new(); + let mut backed: Vec<BTreeSet<Id>> = vec![BTreeSet::new(); count]; + let mut events: Vec<Vec<u8>> = Vec::new(); + for step in 0..rng.between(1, MOST) { + let w = rng.below(count); + let party = &parties[w]; + if rng.chance(0.25) { + known[w] = std::iter::once(root_id) + .chain(events.iter().map(|event| Id::of(event))) + .collect(); + } + let mut deps = vec![pick(rng, &known[w])]; + let other = pick(rng, &known[w]); + if rng.chance(0.3) && !deps.contains(&other) { + deps.push(other); + } + let current = world.state_at(&deps).current().clone(); + let writer = Party { + name: party.name.clone(), + key: signing[w].clone(), + }; + let mine: Vec<&(Id, Id, Id, bool)> = proposals + .iter() + .filter(|(id, ..)| known[w].contains(id)) + .collect(); + let roll = rng.below(100); + let event = if roll < 35 || (roll >= 60 && mine.is_empty()) { + let path = format!("home/{}/k{}", party.name, rng.below(3)); + writer.write(&deps, &path, harness::str(&step.to_string())) + } else if roll < 43 { + let new = SigningKey::from_bytes(&[(100 + step as u8).wrapping_add(w as u8 * 31); 32]); + let line = PublicKey(new.verifying_key().to_bytes()).line(); + signing[w] = new; + party.keys(&deps, &[line]) + } else if roll < 48 { + party.nodes(&deps, &[harness::node_id(rng.below(10) as u8)]) + } else if roll < 60 { + match specs.get(¤t.hash) { + None => writer.write(&deps, &format!("home/{}/x", party.name), harness::str("x")), + Some(base) => { + let mut next = base.after(current.hash); + let named = kind.checkpoints + && rng.chance(0.5) + && deps.iter().any(|dep| *dep != root_id); + if named { + let head = *deps.iter().find(|dep| **dep != root_id).expect("one"); + next.checkpoint = Some(vec![head]); + deps = vec![head]; + } else { + next.rules + .push((format!("names/x{step}"), harness::str(&party.name))); + } + let bytes = party.propose(&deps, &next.json()); + proposals.push((Id::of(&bytes), next.hash(), current.hash, named)); + specs.insert(next.hash(), next); + bytes + } + } + } else if roll < 85 { + let &&(proposal, hash, on, named) = rng.pick(&mine); + let yes = if kind.adversary && w == adversary { + rng.chance(0.7) + } else { + backed[w].insert(on) + }; + if !named && rng.chance(0.3) { + deps.push(proposal); + } else { + deps = vec![proposal]; + } + let bytes = party.vote(&deps, on, hash, yes); + votes.push((Id::of(&bytes), proposal)); + bytes + } else if roll < 96 || !kind.adversary { + let &&(proposal, hash, ..) = rng.pick(&mine); + let on_it: Vec<Id> = votes + .iter() + .filter(|(vote, voted)| *voted == proposal && known[w].contains(vote)) + .map(|(vote, _)| *vote) + .collect(); + let deps = if on_it.is_empty() { + vec![proposal] + } else { + on_it + }; + harness::version_event(&deps, hash) + } else { + // The adversary signs as another party with its own key, or writes elsewhere. + let victim = &parties[rng.below(count)]; + let thief = Party { + name: victim.name.clone(), + key: parties[adversary].key.clone(), + }; + if rng.chance(0.5) { + thief.write( + &deps, + &format!("home/{}/k0", victim.name), + harness::str("stolen"), + ) + } else { + parties[adversary].write( + &deps, + &format!("names/{}", victim.name), + harness::str("x"), + ) + } + }; + let id = Id::of(&event); + world.offer(event.clone()); + known[w].push(id); + events.push(event); + } + History { root, events } +} + +fn check(cases: u64, kind: Kind, property: impl Fn(&History) -> Result<(), String>) { + for_seeds(cases, |rng| { + let history = generate(rng, kind); + if let Err(why) = property(&history) { + let (history, why) = cut_down(history, why, &property); + panic!("{why}, in the history\n{}", history.show()); + } + }); +} + +fn cut_down( + mut history: History, + mut why: String, + property: &impl Fn(&History) -> Result<(), String>, +) -> (History, String) { + 'shorter: loop { + for i in (0..history.events.len()).rev() { + let shorter = history.without(i); + if let Err(still) = property(&shorter) { + (history, why) = (shorter, still); + continue 'shorter; + } + } + return (history, why); + } +} + +/// What a store reads, to compare with the model or another store. +fn reads( + store: &Store<Federation>, +) -> ( + Id, + BTreeMap<String, super::jcs::Json>, + BTreeSet<(String, String)>, +) { + let state = store.state(); + ( + state.current().hash, + state.values(), + state.members().into_iter().collect(), + ) +} + +fn model_reads( + model: &Model, +) -> ( + Id, + BTreeMap<String, super::jcs::Json>, + BTreeSet<(String, String)>, +) { + (model.version().hash, model.values(), model.members()) +} + +/// The verdict a store's answer stands for. +fn verdict(offered: &Offered) -> Verdict { + match offered { + Offered::Taken(_) => Verdict::Taken, + Offered::Held => Verdict::Held, + Offered::Waiting => Verdict::Waiting, + Offered::Refused(_) => Verdict::Refused, + } +} + +#[test] +fn the_store_judges_and_reads_as_the_model() { + for adversary in [false, true] { + check( + 48, + Kind { + adversary, + checkpoints: false, + }, + |history| { + let mut model = Model::new(&history.root); + let mut store: Store<Federation> = + Store::new(history.root.clone(), Vec::new()).expect("a root"); + for event in &history.events { + let id = Id::of(event); + let stored = verdict(&store.offer(event.clone())); + let modelled = model.offer(event); + if stored != modelled { + return Err(format!( + "{id}: the store says {stored:?}, the model {modelled:?}" + )); + } + } + if reads(&store) != model_reads(&model) { + return Err(format!( + "the store reads {:?}, the model {:?}", + reads(&store), + model_reads(&model) + )); + } + Ok(()) + }, + ); + } +} + +#[test] +fn what_builds_on_a_refused_event_is_refused() { + check( + 48, + Kind { + adversary: true, + checkpoints: true, + }, + |history| { + let (store, _) = history.store(&history.written()); + for event in &history.events { + let id = Id::of(event); + let deps = Federation::dependencies(event).unwrap_or_default(); + if let Some(dep) = deps.iter().find(|dep| store.refusal(dep).is_some()) + && store.refusal(&id).is_none() + { + return Err(format!("{id} is taken, built on {dep}, which is refused")); + } + } + Ok(()) + }, + ); +} + +#[test] +fn honest_parties_read_the_same_whatever_order_events_come_in() { + check( + 32, + Kind { + adversary: false, + checkpoints: true, + }, + |history| { + let (store, _) = history.store(&history.written()); + let held = ( + store.checkpoint().to_vec(), + store.taken().iter().copied().collect::<BTreeSet<Id>>(), + reads(&store), + ); + let mut rng = Rng::new(history.events.len() as u64); + let mut orders = vec![history.written().into_iter().rev().collect::<Vec<usize>>()]; + for _ in 0..3 { + let mut order = history.written(); + rng.shuffle(&mut order); + orders.push(order); + } + for order in orders { + let (other, _) = history.store(&order); + let other_held = ( + other.checkpoint().to_vec(), + other.taken().iter().copied().collect::<BTreeSet<Id>>(), + reads(&other), + ); + if other_held != held { + return Err(format!( + "offered in the order {order:?}, a store holds otherwise" + )); + } + } + Ok(()) + }, + ); +} + +#[test] +fn after_a_checkpoint_the_store_judges_and_reads_as_the_whole_history() { + check( + 48, + Kind { + adversary: false, + checkpoints: true, + }, + |history| { + let (store, _) = history.store(&history.written()); + // What the store refused as not above a checkpoint, and what builds on it, the + // model is never given: it reads every history from the root, never moving. + let mut beside = BTreeSet::new(); + let mut model = Model::new(&history.root); + for event in &history.events { + let id = Id::of(event); + let deps = Federation::dependencies(event).unwrap_or_default(); + if store.refusal(&id) == Some(&Refusal::NotAbove) + || deps.iter().any(|dep| beside.contains(dep)) + { + beside.insert(id); + continue; + } + model.offer(event); + } + let taken = model.taken(); + for id in store.taken() { + if !taken.contains(id) { + return Err(format!( + "{id} is taken after the checkpoint, not by the model" + )); + } + } + if reads(&store) != model_reads(&model) { + return Err(format!( + "the store reads {:?}, the whole history {:?}", + reads(&store), + model_reads(&model) + )); + } + // Moving refused nothing that decided it: the version naming the checkpoint is + // written there, its proposal held. + let (at, _) = Federation::parts(store.checkpoint()).expect("a checkpoint"); + if !at.is_empty() { + let held: Vec<Event> = store + .taken() + .iter() + .filter_map(|id| store.get(id).and_then(Event::read_taken)) + .collect(); + let written: BTreeSet<Id> = held + .iter() + .filter_map(|event| match event { + Event::Version { version, .. } => Some(*version), + Event::Signed(_) => None, + }) + .collect(); + let named = held.iter().any(|event| match event { + Event::Signed(signed) => match &signed.does { + Does::Proposal { hash, version } => { + written.contains(hash) + && Version::read(version).is_ok_and(|version| { + version.checkpoint.as_deref() == Some(&at[..]) + }) + } + _ => false, + }, + Event::Version { .. } => false, + }); + if !named { + return Err("the version naming the checkpoint isn't taken".to_owned()); + } + } + Ok(()) + }, + ); +} + +#[test] +fn every_version_a_store_takes_was_passed_by_two_thirds_in_its_history() { + check( + 48, + Kind { + adversary: true, + checkpoints: false, + }, + |history| { + let (store, _) = history.store(&history.written()); + let first = Checkpoint::read(&history.root).expect("a root").version; + for id in store.taken() { + let Some(Event::Version { deps, version }) = + store.get(id).and_then(Event::read_taken) + else { + continue; + }; + // Its history, read from what the store holds. + let mut seen = BTreeSet::new(); + let mut todo = deps.clone(); + let mut events = Vec::new(); + while let Some(dep) = todo.pop() { + if let Some(bytes) = store.get(&dep) + && seen.insert(dep) + { + let event = Event::read_taken(bytes).expect("an event"); + todo.extend_from_slice(event.deps()); + events.push(event); + } + } + let proposed = |hash: &Id| { + events.iter().find_map(|event| match event { + Event::Signed(signed) => match &signed.does { + Does::Proposal { + hash: proposed, + version, + } if proposed == hash => Version::read(version).ok(), + _ => None, + }, + Event::Version { .. } => None, + }) + }; + let next = proposed(&version).ok_or(format!("{id}: no proposal in its history"))?; + let changed = match next.changes { + Some(hash) if hash == first.hash => first.clone(), + Some(hash) => proposed(&hash).ok_or(format!("{id}: no version it changes"))?, + None => return Err(format!("{id}: a first version written")), + }; + let yes: BTreeSet<&str> = events + .iter() + .filter_map(|event| match event { + Event::Signed(signed) => match signed.does { + Does::Vote { + on, + proposal, + yes: true, + } if on == changed.hash && proposal == version => { + Some(signed.party.as_str()) + } + _ => None, + }, + Event::Version { .. } => None, + }) + .collect(); + if 3 * yes.len() < 2 * changed.parties.len() { + return Err(format!( + "{id}: written with {} of {} parties", + yes.len(), + changed.parties.len() + )); + } + } + Ok(()) + }, + ); +} + +#[test] +fn without_a_party_voting_twice_no_two_versions_change_one() { + check( + 48, + Kind { + adversary: false, + checkpoints: true, + }, + |history| { + let (store, _) = history.store(&history.written()); + if let Some((id, _)) = store.refused().find(|(_, why)| **why == Refusal::Own) { + return Err(format!("{id}: a version changing one another changes")); + } + Ok(()) + }, + ); +} |
