diff options
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(()) + }, + ); +} |
