//! Swarms holding a store (`docs/store.md`, Members), the federation its fold: nodes //! started from its root, or joining by its ID, sync with the members its store names; //! the events put on any of them reach all of them, and none reaches a node its party //! doesn't list; and the attack rows marked sim, each by its test. use std::collections::{BTreeMap, BTreeSet}; use std::sync::Arc; use std::time::Duration; use super::{SOON, Sim, sim_key}; use crate::document::events; use crate::federation::event::Event; use crate::federation::fold::Federation; use crate::federation::harness::{self, Party, Spec}; use crate::federation::held::{self, Holding}; use crate::federation::jcs::Json; use crate::federation::store::memory::Store; use crate::federation::store::{Fold, Id}; use crate::files::Files; use crate::node::NodeConfig; use crate::state::AppState; use crate::swarm::bootstrap::{Origin, Start}; /// How long a test waits for what takes a few rounds of syncs, writes and reads. const LONG: Duration = Duration::from_secs(30); /// A federation of `parties`, each listing the simulated nodes named with it: its first /// version, its root, and its ID. fn federation(parties: &[(&Party, &[&str])]) -> (Spec, Vec, Id) { let named: Vec<&Party> = parties.iter().map(|(party, _)| *party).collect(); let mut first = Spec::first(&named, &[]); for (spec, (_, nodes)) in first.parties.iter_mut().zip(parties) { spec.nodes = nodes.iter().map(|node| sim_key(node).id()).collect(); } let root = first.root(); let id = Id::of(&root); (first, root, id) } /// tv, lass and makefu. fn three() -> (Party, Party, Party) { ( Party::new("tv", 1), Party::new("lass", 2), Party::new("makefu", 3), ) } fn s(text: &str) -> Json { harness::str(text) } /// What a node of `party` keeps of its store, without a file (`--store-party`). fn holding(party: &str) -> Holding { Holding::open( None, Arc::new(Files::default()), None, Some(party.to_owned()), ) .expect("no file to read") } /// What a node of `party` keeps of its store, starting from the checkpoint `pin`, found in /// the document (`--store-checkpoint`). fn pinned(party: &str, pin: Id) -> Holding { Holding::open( None, Arc::new(Files::default()), Some(pin), Some(party.to_owned()), ) .expect("no file to read") } /// `config`, of a node of the swarm holding the store `id`, keeping `holding`: started /// from the store's `root` where given (`--store-root`), else joining by its ID /// (`--store-id`). fn of_the_store(config: &mut NodeConfig, id: Id, root: Option<&[u8]>, holding: Holding) { config.store = Some(id); config.holding = holding; if let Some(root) = root { config.initial_doc = events::started(Federation::NAME, root).expect("a root"); } } /// Starts `nodes`, each by its name with what it keeps of its store, from the store's /// `root`, the first one the others' seed, and waits until each holds the store. async fn started(sim: &Sim, root: &[u8], nodes: Vec<(&str, Holding)>) -> Vec { let id = Id::of(root); let first = nodes[0].0.to_owned(); let states: Vec = nodes .into_iter() .map(|(name, holding)| { let seeds: Vec<&str> = if name == first { Vec::new() } else { vec![first.as_str()] }; let root = root.to_vec(); sim.start_with( name, &seeds, Start::FromDocument(Origin::Root), move |config| of_the_store(config, id, Some(&root), holding), ) }) .collect(); let all: Vec<&AppState> = states.iter().collect(); sim.wait_ready(&all, SOON).await; let all = &all; sim.wait_until("every node holds the store", SOON, move || async move { all.iter().all(|node| node.holding.tells_members()) }) .await; states } /// Puts `events` on `node`, each in a change of its own. async fn put(node: &AppState, events: &[&[u8]]) { for event in events { held::write(node, None, event.to_vec()) .await .expect("an event put"); } } /// What `f` reads of `node`'s store, while it holds one. fn read(node: &AppState, f: impl FnOnce(&Store) -> T) -> Option { node.holding.with(f) } /// Whether `node` holds every event of `ids`. fn holds(node: &AppState, ids: &[Id]) -> bool { read(node, |store| ids.iter().all(|id| store.holds(id))) == Some(true) } /// The version current, as `node`'s store reads, by its hash. fn current(node: &AppState) -> Option { read(node, |store| store.state().current().hash) } /// The ID of the checkpoint `node`'s store holds. fn checkpoint(node: &AppState) -> Option { read(node, |store| Id::of(store.checkpoint())) } /// The version event writing `version` that `node`'s store took after its checkpoint. fn written(node: &AppState, version: Id) -> Option { read(node, |store| { store.taken().iter().copied().find(|id| { matches!( store.get(id).and_then(Event::read_taken), Some(Event::Version { version: writes, .. }) if writes == version ) }) }) .flatten() } /// What counts, as `node`'s store reads: the current version, the values at places, and /// the members; and the events it took after its checkpoint. type Counts = ( Id, BTreeMap, Vec<(String, String)>, BTreeSet, ); fn counts(node: &AppState) -> Option { read(node, |store| { let state = store.state(); ( state.current().hash, state.values(), state.members(), store.taken().iter().copied().collect(), ) }) } /// tv lists a and b, which start from the root; lass lists c, which joins by the store's /// ID; d is of lass too, which doesn't list it. Events put on a and on c reach a, b and /// c; d, which no member syncs with, gets nothing. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn the_events_put_on_a_member_reach_every_member_alone() { let sim = Sim::with_identity(81); let (tv, lass, _) = three(); let (_, root, id) = federation(&[(&tv, &["a", "b"]), (&lass, &["c"])]); let mut nodes = started( &sim, &root, vec![("a", holding("tv")), ("b", holding("tv"))], ) .await; nodes.push(sim.start_with("c", &["a"], Start::Join, |config| { of_the_store(config, id, None, holding("lass")) })); let [a, b, c] = [&nodes[0], &nodes[1], &nodes[2]]; let members = [a, b, c]; sim.wait_ready(&members, SOON).await; sim.wait_until("a, b and c hold the store", SOON, move || async move { members.iter().all(|node| node.holding.tells_members()) }) .await; let d = sim.start_with("d", &["a"], Start::Join, |config| { of_the_store(config, id, None, holding("lass")) }); let on_a = tv.write(&[id], "home/tv/x", s("1")); let on_c = lass.write(&[id], "home/lass/y", s("2")); let ids = [Id::of(&on_a), Id::of(&on_c)]; put(a, &[&on_a]).await; put(c, &[&on_c]).await; sim.wait_until("a, b and c hold both events", SOON, move || async move { members.iter().all(|node| holds(node, &ids)) }) .await; sim.wait_converged(&members, SOON).await; for node in members { assert_eq!(read(node, |store| store.state().values().len()), Some(2)); } // Long enough for d to have joined, were it let in. tokio::time::sleep(Duration::from_secs(3)).await; assert!(!d.is_ready().await); assert!(!d.holding.tells_members()); assert!(events::ids(&d.doc.read().await.doc).is_empty()); } /// Different events to different peers: tv, lass and makefu, a node each, apart while /// each is given its own: two writes of tv's at one place, a write of lass's, and a /// proposal and the votes that pass it, each on another node. Together, they read the /// same, the version that passed current, written by whichever held it passed. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn federation_attack_28() { let sim = Sim::with_identity(82); let (tv, lass, makefu) = three(); let (first, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); let nodes = started( &sim, &root, vec![ ("a", holding("tv")), ("b", holding("lass")), ("c", holding("makefu")), ], ) .await; for name in ["a", "b", "c"] { sim.net.take_down(name); } let on = first.hash(); let mut next = first.after(on); next.rules.push(("names/x".to_owned(), s("tv"))); let proposal = makefu.propose(&[id], &next.json()); let given = [ [tv.write(&[id], "home/tv/x", s("a")), proposal.clone()], [ tv.write(&[id], "home/tv/x", s("b")), tv.vote(&[Id::of(&proposal)], on, next.hash(), true), ], [ lass.write(&[id], "home/lass/y", s("c")), lass.vote(&[Id::of(&proposal)], on, next.hash(), true), ], ]; for (node, events) in nodes.iter().zip(&given) { put(node, &[&events[0], &events[1]]).await; } let (all, writes) = (&nodes, [0, 1, 2].map(|i| Id::of(&given[i][0]))); sim.wait_until( "each holds the write it was given", SOON, move || async move { all.iter() .zip(writes) .all(|(node, write)| holds(node, &[write])) }, ) .await; // Apart, a and b read their own write at one place. let at = |node: &AppState| read(node, |store| store.state().value("home/tv/x").cloned()); assert_eq!(at(&nodes[0]), Some(Some(s("a")))); assert_eq!(at(&nodes[1]), Some(Some(s("b")))); for name in ["a", "b", "c"] { sim.net.bring_up(name); } let passed = next.hash(); sim.wait_until("every node reads the same", LONG, move || async move { let first = counts(&all[0]); first.as_ref().is_some_and(|counts| counts.0 == passed) && all.iter().all(|node| counts(node) == first) }) .await; let counts = counts(&nodes[0]).expect("a store"); assert!(writes.iter().all(|write| counts.3.contains(write))); } /// The version passing on the first version of tv, lass and makefu that only moves to a /// checkpoint at `heads`, proposed by tv, and backed by tv and lass: its spec, and the /// proposal and votes. fn checkpoint_at( (tv, lass, _): &(Party, Party, Party), first: &Spec, heads: &[Id], ) -> (Spec, [Vec; 3]) { let on = first.hash(); let mut next = first.after(on); next.checkpoint = Some(heads.to_vec()); let proposal = tv.propose(heads, &next.json()); let votes = [tv, lass].map(|party| party.vote(&[Id::of(&proposal)], on, next.hash(), true)); let [tv_yes, lass_yes] = votes; (next, [proposal, tv_yes, lass_yes]) } /// A node away while the others moved to a checkpoint and forgot what came before: c, /// back, builds the checkpoint from the document, which holds what came before, and /// reads what a and b read, what came after it too. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn store_attack_24() { let sim = Sim::with_identity(83); let parties = three(); let (tv, lass, makefu) = &parties; let (first, root, id) = federation(&[(tv, &["a"]), (lass, &["b"]), (makefu, &["c"])]); let nodes = started( &sim, &root, vec![ ("a", holding("tv")), ("b", holding("lass")), ("c", holding("makefu")), ], ) .await; sim.net.take_down("c"); let gone = tv.write(&[id], "home/tv/a", s("0")); let head = tv.write(&[Id::of(&gone)], "home/tv/a", s("1")); let (next, [proposal, tv_yes, lass_yes]) = checkpoint_at(&parties, &first, &[Id::of(&head)]); put(&nodes[0], &[&gone, &head, &proposal, &tv_yes]).await; put(&nodes[1], &[&lass_yes]).await; let (all, passed) = (&nodes, next.hash()); sim.wait_until( "a and b moved to the checkpoint", LONG, move || async move { all[..2] .iter() .all(|node| current(node) == Some(passed) && checkpoint(node) != Some(id)) }, ) .await; let after = tv.write(&[Id::of(&head)], "home/tv/b", s("2")); put(&nodes[0], &[&after]).await; let moved = checkpoint(&nodes[0]).expect("a store"); assert_eq!(checkpoint(&nodes[1]), Some(moved)); assert_eq!( read(&nodes[0], |store| store.holds(&Id::of(&gone))), Some(false) ); sim.net.bring_up("c"); let after = Id::of(&after); sim.wait_until( "c moved there, and holds what came after", LONG, move || async move { checkpoint(&all[2]) == Some(moved) && holds(&all[2], &[after]) && holds(&all[0], &[after]) }, ) .await; assert_eq!(counts(&nodes[2]), counts(&nodes[0])); assert!(events::ids(&nodes[2].doc.read().await.doc).contains(&Id::of(&gone))); } /// Keys voting twice part honest nodes: tv backs a proposal of its own with lass, and one /// of lass's with makefu; b, apart, takes the other version than a and c. Together, they /// stay parted, and b's operator has it drop what it took and take the other side's; or, /// where the versions named checkpoints, starts it again from the checkpoint the others /// moved to, pinned. No fork. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn federation_attack_49() { for (seed, checkpoints) in [(84, false), (85, true)] { parted(seed, checkpoints).await; } } async fn parted(seed: u64, checkpoints: bool) { let sim = Sim::with_identity(seed); let (tv, lass, makefu) = three(); let (first, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); let nodes = started( &sim, &root, vec![ ("a", holding("tv")), ("b", holding("lass")), ("c", holding("makefu")), ], ) .await; sim.net.take_down("b"); let on = first.hash(); let (mut one, mut two) = (first.after(on), first.after(on)); two.rules.push(("names/x".to_owned(), s("tv"))); let heads = [ tv.write(&[id], "home/tv/a", s("1")), lass.write(&[id], "home/lass/b", s("2")), ]; if checkpoints { one.checkpoint = Some(vec![Id::of(&heads[0])]); two.checkpoint = Some(vec![Id::of(&heads[1])]); } let p1 = tv.propose(&[Id::of(&heads[0])], &one.json()); let p2 = lass.propose(&[Id::of(&heads[1])], &two.json()); let ones = [&tv, &lass].map(|party| party.vote(&[Id::of(&p1)], on, one.hash(), true)); let twos = [&tv, &makefu].map(|party| party.vote(&[Id::of(&p2)], on, two.hash(), true)); put(&nodes[0], &[&heads[0], &p1, &ones[0], &ones[1]]).await; put(&nodes[1], &[&heads[1], &p2, &twos[0], &twos[1]]).await; let (all, one_hash, two_hash) = (&nodes, one.hash(), two.hash()); sim.wait_until( "a and c take one version, b the other", LONG, move || async move { current(&all[0]) == Some(one_hash) && current(&all[2]) == Some(one_hash) && current(&all[1]) == Some(two_hash) }, ) .await; sim.net.bring_up("b"); let members: Vec<&AppState> = nodes.iter().collect(); sim.wait_converged(&members, LONG).await; // Parted: each keeps the version it took. assert_eq!(current(&nodes[0]), Some(one_hash)); assert_eq!(current(&nodes[1]), Some(two_hash)); assert_eq!(current(&nodes[2]), Some(one_hash)); let b = if checkpoints { let pin = checkpoint(&nodes[0]).expect("a store"); sim.restart_with("b", &["a"], Start::Join, move |config| { of_the_store(config, id, None, pinned("lass", pin)) }) } else { let took = written(&nodes[1], two_hash).expect("b wrote what it took"); let other = written(&nodes[0], one_hash).expect("a wrote what it took"); let dropped = nodes[1].holding.drop_taken(&[took]); assert!(matches!(dropped, Some(Ok(_))), "{dropped:?}"); assert!(nodes[1].holding.allow(&[other])); nodes[1].clone() }; let b = &b; sim.wait_until("b takes the others' version", LONG, move || async move { current(b) == Some(one_hash) }) .await; assert_eq!(checkpoint(b), checkpoint(&nodes[0])); }