//! 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, against itself in //! other orders, and read from a document against itself given the events alone. 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::held::Holding; 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::document::events; 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, events: Vec>, } impl History { fn root_id(&self) -> Id { Id::of(&self.root) } fn store(&self, order: &[usize]) -> (Store, Vec) { 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 { (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::>() .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 generate(rng: &mut Rng, kind: Kind) -> History { let count = rng.between(3, 5); let parties: Vec = (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 = first.root(); let root_id = Id::of(&root); let mut world: Store = Store::new(root.clone(), Vec::new()).expect("a root"); let mut specs: BTreeMap = BTreeMap::from([(first.hash(), first)]); // The key each party signs its writes with: its version's, or its set's. let mut signing: Vec = parties.iter().map(|party| party.key.clone()).collect(); let mut known: Vec> = 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> = vec![BTreeSet::new(); count]; let mut events: Vec> = 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 = 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); } } /// The current version's hash, the values at places, and the members. type Reads = ( Id, BTreeMap, BTreeSet<(String, String)>, ); /// What a store reads, to compare with the model or another store. fn reads(store: &Store) -> Reads { let state = store.state(); ( state.current().hash, state.values(), state.members().into_iter().collect(), ) } fn model_reads(model: &Model) -> Reads { (model.version().hash, model.values(), model.members()) } /// What a store holds, to compare with another store: its checkpoint, the events it took /// after it, and what it reads. fn holds(store: &Store) -> (Vec, BTreeSet, Reads) { ( store.checkpoint().to_vec(), store.taken().iter().copied().collect(), reads(store), ) } /// 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 = 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 held = holds(&history.store(&history.written()).0); let mut rng = Rng::new(history.events.len() as u64); let mut orders = vec![history.written().into_iter().rev().collect::>()]; for _ in 0..3 { let mut order = history.written(); rng.shuffle(&mut order); orders.push(order); } for order in orders { if holds(&history.store(&order).0) != held { return Err(format!( "offered in the order {order:?}, a store holds otherwise" )); } } Ok(()) }, ); } /// The events of a history put into a document by two writers, in batches of a shuffled /// order, some by both at once, the writers merging now and then; a node reads its store /// from each writer's document as it grows, and once more after both merged. #[test] fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds() { check( 24, Kind { adversary: false, checkpoints: true, }, |history| { let alone = holds(&history.store(&history.written()).0); let mut rng = Rng::new(history.events.len() as u64); let started = events::started(Federation::NAME, &history.root, &[]).expect("a root"); let mut docs = [started.fork(), started.fork()]; let holdings = [Holding::default(), Holding::default()]; let read = |holdings: &[Holding; 2], docs: &[_; 2]| { for (holding, doc) in holdings.iter().zip(docs) { holding.read(holding.unread(doc, 0).expect("a store")); } }; let mut order = history.written(); rng.shuffle(&mut order); let mut rest = order.as_slice(); while !rest.is_empty() { let (batch, after) = rest.split_at(rng.between(1, 4).min(rest.len())); rest = after; let batch: Vec<&[u8]> = batch.iter().map(|&i| &history.events[i][..]).collect(); let at = usize::from(rng.chance(0.5)); events::put(&mut docs[at], &batch); if rng.chance(0.2) { events::put(&mut docs[1 - at], &batch); } if rng.chance(0.3) { let [one, other] = &mut docs; one.merge(other).expect("merged"); other.merge(one).expect("merged"); } read(&holdings, &docs); } let [one, other] = &mut docs; one.merge(other).expect("merged"); other.merge(one).expect("merged"); read(&holdings, &docs); for (n, holding) in holdings.iter().enumerate() { if holding.with(holds).as_ref() != Some(&alone) { return Err(format!( "the store read from writer {n}'s document holds otherwise than one \ given the events alone" )); } } 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 = store .taken() .iter() .filter_map(|id| store.get(id).and_then(Event::read_taken)) .collect(); let written: BTreeSet = 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(()) }, ); } /// A fork at the heads of a history's first half, by the version current there, numbered /// one past it and changing it: its root keeps what counts at those heads, with its /// version current; it takes nothing else of the history; and the store it came from /// takes nothing built on the fork's root. #[test] fn a_fork_keeps_what_counts_at_its_heads_and_takes_nothing_of_the_other() { check( 32, Kind { adversary: false, checkpoints: false, }, |history| { let (mut whole, _) = history.store(&history.written()); let half: Vec = (0..history.events.len() / 2).collect(); let (at, _) = history.store(&half); let heads = at.heads(); let current = at.state().current(); let super::jcs::Json::Object(mut members) = current .json .without("number") .without("changes") .without("checkpoint") else { return Err("a version that is no object".to_owned()); }; members.push(( "number".to_owned(), super::jcs::Json::Int(current.number as i64 + 1), )); members.push(( "changes".to_owned(), super::jcs::Json::Str(current.hash.to_string()), )); let spec = super::jcs::Json::object(members).expect("names once each"); let (root, kept) = whole .fork(&heads, &spec.bytes()) .map_err(|why| format!("no fork at {heads:?}: {}", why.0))?; let mut fork: Store = Store::new(root.clone(), kept).map_err(|why| format!("no root: {}", why.0))?; if fork.state().current().hash != Id::of(&spec.bytes()) { return Err("the fork's version isn't current at its root".to_owned()); } if fork.state().values() != at.state().values() || fork.state().members() != at.state().members() { return Err("the fork's root doesn't keep what counts at its heads".to_owned()); } for event in &history.events { if let Offered::Taken(ids) = fork.offer(event.clone()) { return Err(format!("the fork takes {ids:?} of the history")); } } let on_the_fork = harness::version_event(&[Id::of(&root)], Id::of(b"a version")); if matches!(whole.offer(on_the_fork), Offered::Taken(_)) { return Err("the store it came from takes what builds on the fork".to_owned()); } Ok(()) }, ); }