aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation')
-rw-r--r--src/federation/mod.rs2
-rw-r--r--src/federation/properties.rs574
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(&current.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(())
+ },
+ );
+}