//! What a change of a swarm holding a store writes (`docs/store.md`, What a change writes), //! judged by every node by the change and its history alone, in place of rules by path //! (`rules::judge`). It writes nothing but: //! //! * events: at `_continuum/events/` the bytes whose ID (SHA-256) it is, no more than //! the fold allows, at a key held nowhere at the change's history; //! * its node's entry (`_continuum/members/`), and the member list's map where //! there is none. //! //! Everything else is closed: whatever isn't under `_continuum`, the policy, the swarm's //! ID, users, bans, the swarm's topology, remakes and their acks. Nothing deletes or //! replaces an event. A change names its node, as signed (signatures are required), but //! for the changes founding the swarm, which every node builds and nobody signs: the //! genesis change, which the epoch's root is, and those of its writer putting the events //! a fork's root keeps (`document::events`), taken only as built byte for byte. Which //! events the store takes is the store's (`federation::held`); this judges none. //! //! In a swarm not holding a store, no change writes a policy naming one (`turns_store`): //! a swarm holds a store from its genesis change, or not at all. use sha2::{Digest, Sha256}; use super::rules::{Change, Refusal}; use crate::document::at::At; use crate::document::inspect::{Action, Op, Path}; use crate::document::{events, meta, store}; use crate::federation::store::Id; /// The most bytes an event of the fold `fold` may have. fn largest(fold: &str) -> usize { use crate::federation::store::Fold; match fold { crate::federation::fold::Federation::NAME => crate::federation::fold::Federation::LARGEST, _ => 0, } } /// The events the store's root `root` keeps, by the fold `fold`: those of a fork's. fn keeps(fold: &str, root: &[u8]) -> Option> { use crate::federation::store::Fold; match fold { crate::federation::fold::Federation::NAME => { crate::federation::fold::Federation::parts(root).map(|(_, keeps)| keeps) } _ => None, } } /// Whether `change`, naming no node, is one of those founding the swarm, which every node /// builds from the store's root and the events it keeps (`events::is_founding`). fn founding(at: &At<'_>, change: &Change<'_>, fold: &str) -> bool { let Some(root) = events::swarm(at).and_then(|swarm| events::bytes(at, &swarm)) else { return false; }; let Some(keeps) = keeps(fold, &root) else { return false; }; let written: Vec> = change .ops .iter() .filter_map(|op| match &op.action { Action::PutBytes(bytes) => Some(bytes.clone()), _ => None, }) .collect(); events::is_founding(at, fold, (&root, &keeps), &change.hash, &written) } /// Judges `change`, of a swarm holding a store of the fold `fold`, at its history `at`. pub(crate) fn judge(at: &At<'_>, change: &Change<'_>, fold: &str) -> Result<(), Refusal> { let refuse = |why: String| Err(Refusal::Rule(why)); let Some(node) = change.committer else { if founding(at, change, fold) { return Ok(()); } return refuse("it names no node".to_owned()); }; let events = meta::path(&[meta::EVENTS]); let members = meta::path(&[meta::MEMBERS]); let entry = meta::path(&[meta::MEMBERS, node]); for op in change.ops { let allowed = if op.path.starts_with(&events) { event(at, op, fold) } else if op.path.starts_with(&entry) { Ok(()) } else if op.path == members { // The member list's map, made where there is none. if op.action == Action::MakeMap && !store::held_anywhere(at, &members) { Ok(()) } else { Err("it writes the member list".to_owned()) } } else { Err(format!("it writes {}, closed", shown(&op.path))) }; allowed.or_else(|why| refuse(format!("{node}: {why}")))?; } Ok(()) } /// Whether `op`, under `_continuum/events`, puts an event at its ID, held nowhere at `at`, /// no larger than the fold `fold` allows. fn event(at: &At<'_>, op: &Op, fold: &str) -> Result<(), String> { let [_, _, key] = op.path.as_slice() else { return Err(format!("it writes {}, no event's place", shown(&op.path))); }; let Action::PutBytes(bytes) = &op.action else { return Err(format!("it writes {}, no event's bytes", shown(&op.path))); }; if bytes.len() > largest(fold) { return Err(format!( "an event of {} bytes, more than {} allows", bytes.len(), fold )); } if hex(&Sha256::digest(bytes)) != *key { return Err(format!("an event at {key}, which isn't its ID")); } if store::held_anywhere(at, &op.path) { return Err(format!("an event at {key}, held there already")); } Ok(()) } fn hex(bytes: &[u8]) -> String { bytes.iter().map(|byte| format!("{byte:02x}")).collect() } fn shown(path: &Path) -> String { format!("/{}", path.join("/")) } /// Whether `ops` write a policy naming a store: anything at its `store`, or an envelope /// at its place naming one. pub(crate) fn turns_store(ops: &[Op]) -> bool { let policy = super::policy::path(); let mut store = policy.clone(); store.push("store".to_owned()); ops.iter().any(|op| match &op.action { _ if op.path.starts_with(&store) => true, Action::PutString(text) if op.path == policy => crate::document::signed::read(text) .is_some_and(|payload| payload.value.get("store").is_some()), _ => false, }) } #[cfg(test)] mod tests { use super::*; use crate::clock::UnixMillis; use crate::document::replica::{Epoch, Writer, transact}; use crate::document::store::StoreError; use crate::document::typed::{TimestampFormat, Val}; use crate::document::{Document, ScalarValue, Transaction, events}; use crate::federation::store::Id; use serde_json::json; const ROOT: &[u8] = b"{\"a root\":true}"; /// A swarm holding a store, from its genesis change. fn swarm() -> Document { events::started("federation", ROOT, &[]).unwrap() } /// The change `node` writes to `doc` with `f`, judged as every node judges it. fn judged( doc: &mut Document, node: &str, f: impl FnOnce(&mut Transaction<'_>) -> Result<(), StoreError>, ) -> Result<(), String> { let before = doc.get_heads(); transact(doc, UnixMillis(1), &Writer { node, user: None }, f).unwrap(); let after = doc.get_heads(); assert_ne!(after, before, "no change written"); super::super::rules::judge_held(doc, Epoch::GENESIS, &after[0]).unwrap() } fn put(doc: &mut Transaction<'_>, key: &str, bytes: &[u8]) -> Result<(), StoreError> { store::write_val_path( doc, &meta::path(&[meta::EVENTS, key]), &Val::Scalar(ScalarValue::Bytes(bytes.to_vec())), store::Writing::sticky(TimestampFormat::default()), ) .map(|_| ()) } #[test] fn a_change_puts_events_at_their_ids() { let event = b"an event".to_vec(); let id = Id::of(&event); let key = id.to_string(); let mut doc = swarm(); let mut beside = doc.fork(); assert_eq!( judged(&mut doc, "node-a", |doc| put(doc, &key, &event)), Ok(()) ); // The same, by another at once: one event. assert_eq!( judged(&mut beside, "node-b", |doc| put(doc, &key, &event)), Ok(()) ); // Again, at a key held already: refused. Automerge writes no put of the value a // key holds, so the change is one made by hand. let heads = doc.get_heads(); let at = At::new(&doc, &heads).unwrap(); let path = meta::path(&[meta::EVENTS, &key]); let again = Change { hash: crate::document::ChangeHash([0; 32]), deps: &heads, seen: &heads, committer: Some("node-b"), user: None, paths: &std::collections::BTreeSet::from([path.clone()]), ops: &[Op { path, action: Action::PutBytes(event.clone()), }], }; assert!(judge(&at, &again, "federation").is_err()); // A string, not bytes: refused. let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| { store::write_path(doc, &meta::path(&[meta::EVENTS, &key]), &json!("an event")) }) .is_err() ); } /// An event deleted, or replaced: refused. #[test] fn store_attack_4() { let root = Id::of(ROOT).to_string(); let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| { store::delete_path(doc, &meta::path(&[meta::EVENTS, &root]), false) }) .is_err() ); let mut doc = swarm(); assert!(judged(&mut doc, "node-a", |doc| put(doc, &root, b"other bytes")).is_err()); } /// A node writing another node's entry, or under `_continuum` where it may not: /// refused; its own entry it writes. #[test] fn store_attack_18() { let entry = |node: &str| meta::path(&[meta::MEMBERS, node]); let mut doc = swarm(); assert_eq!( judged(&mut doc, "node-a", |doc| { store::write_path(doc, &entry("node-a"), &json!({"alias": "a"})) }), Ok(()) ); assert!( judged(&mut doc, "node-a", |doc| { store::write_path(doc, &entry("node-b"), &json!({})) }) .is_err() ); for closed in [ meta::path(&["else"]), meta::path(&[meta::USERS, "alice"]), meta::path(&[meta::SWARM]), meta::path(&[meta::NEIGHBOURS]), meta::path(&[meta::VOTES, "node-a"]), crate::access::policy::path(), ] { let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| store::write_path( doc, &closed, &json!(1) )) .is_err(), "{closed:?}" ); } } #[test] fn a_swarm_turns_into_no_store() { let mut doc = Document::new(); transact( &mut doc, UnixMillis(1), &Writer { node: "node-a", user: None, }, |doc| store::write_path(doc, &meta::path(&[meta::SWARM]), &json!("s")), ) .unwrap(); assert!( judged(&mut doc, "node-a", |doc| { store::write_path( doc, &crate::access::policy::path(), &events::policy("federation"), ) }) .is_err() ); } // The store's attack rows (`docs/store.md`, Attacks) judged here. /// A change writing outside `_continuum/events` and the protocol data listed: refused. #[test] fn store_attack_1() { let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| store::write_path( doc, &["config".to_owned()], &json!(1) )) .is_err() ); } /// An event at a key its bytes don't hash to: refused. #[test] fn store_attack_2() { let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| put( doc, &Id::of(b"else").to_string(), b"an event" )) .is_err() ); } /// A change by a node that isn't a member, brought by one that is: taken, as nothing /// here asks who is a member. #[test] fn store_attack_7() { let event = b"an event".to_vec(); let mut doc = swarm(); assert_eq!( judged(&mut doc, "a-node-no-party-lists", |doc| put( doc, &Id::of(&event).to_string(), &event )), Ok(()) ); } /// A decision or abort written by a node not its coordinator: refused, as a swarm /// holding a store takes no remake records. #[test] fn store_attack_14() { for part in ["decision", "abortRequested"] { let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| { store::write_path(doc, &meta::path(&[meta::REMAKES, "r", part]), &json!({})) }) .is_err() ); } } /// An event larger than the fold allows, put by a change: refused, by the change's own /// bytes. #[test] fn store_attack_32() { let large = vec![b' '; crate::federation::event::LARGEST + 1]; let mut doc = swarm(); assert!( judged(&mut doc, "node-a", |doc| put( doc, &Id::of(&large).to_string(), &large )) .is_err() ); } /// One to three writes `node` makes at random: events at their IDs, larger than the /// fold allows or not, again, or at other keys; strings and maps under the events; /// deletions; its entry or another's; and what is closed. `written` holds the events /// put so far, by any node. fn written_at_random( doc: &mut Transaction<'_>, rng: &mut crate::testrand::Rng, node: &str, written: &mut Vec>, ) -> Result<(), StoreError> { let largest = crate::federation::event::LARGEST; for _ in 0..rng.between(1, 3) { let fresh = |rng: &mut crate::testrand::Rng| { let mut bytes = rng.bytes32().to_vec(); bytes.resize( if rng.chance(0.1) { largest + 1 } else { rng.between(32, 200) }, b' ', ); bytes }; let some = rng.pick(written.as_slice()).clone(); let key = Id::of(&some).to_string(); let entry = |node: &str| meta::path(&[meta::MEMBERS, node]); match rng.below(10) { 0 | 1 => { let bytes = fresh(rng); put(doc, &Id::of(&bytes).to_string(), &bytes)?; written.push(bytes); } 2 => put(doc, &key, &some)?, 3 => put(doc, &key, &fresh(rng))?, 4 => store::write_path(doc, &meta::path(&[meta::EVENTS, &key]), &json!("text"))?, 5 => store::write_path(doc, &meta::path(&[meta::EVENTS, &key]), &json!({"x": 1}))?, 6 => store::delete_path(doc, &meta::path(&[meta::EVENTS, &key]), false)?, 7 => store::write_path(doc, &entry(node), &json!({"alias": node}))?, 8 => store::write_path(doc, &entry("node-elsewhere"), &json!({}))?, _ => { let closed: [Vec; 3] = [ vec!["config".to_owned()], meta::path(&[meta::SWARM]), crate::access::policy::path(), ]; let path = rng.pick(&closed); store::write_path(doc, path, &json!(1))? } } } Ok(()) } /// Changes generated: three nodes write at random (`written_at_random`), each now and /// then catching up with a node that takes their changes as it receives them /// (`screen::apply_bytes`). What it takes leaves at every key under /// `_continuum/events` the bytes whose ID it is, the root's among them; its document /// saves and loads; and another node, given all it took, takes it all. #[test] fn what_a_node_takes_leaves_its_events_sound() { use crate::access::screen::{Screening, apply_bytes}; use crate::document::Change; use std::cell::Cell; let id = Id::of(ROOT); let (taken, refused) = (Cell::new(0), Cell::new(0)); let offer = |doc: &mut Document, changes: &[Change], screening: &std::sync::Mutex| { let bytes: Vec = changes .iter() .flat_map(|change| change.raw_bytes().to_vec()) .collect(); apply_bytes( doc, Epoch::GENESIS, 0, &bytes, screening, None, &mut crate::document::PatchLog::inactive(), ) .unwrap(); }; crate::testrand::for_seeds(24, |rng| { let screening = std::sync::Mutex::new(Screening::default().holding(Some(id))); let mut ours = Document::new(); offer( &mut ours, &[events::genesis("federation", ROOT)], &screening, ); let nodes = ["node-a", "node-b", "node-c"]; let mut writers: Vec = nodes.iter().map(|_| ours.fork()).collect(); let mut written = vec![ROOT.to_vec()]; for _ in 0..40 { let at = rng.below(nodes.len()); let writer = &mut writers[at]; let before = writer.get_heads(); let _ = transact( writer, UnixMillis(1), &Writer { node: nodes[at], user: None, }, |doc| written_at_random(doc, rng, nodes[at], &mut written), ); let changes = writer.get_changes(&before); for change in &changes { let heads = ours.get_heads(); offer(&mut ours, std::slice::from_ref(change), &screening); let counted = if ours.get_heads() == heads { &refused } else { &taken }; counted.set(counted.get() + 1); } if rng.chance(0.3) { *writer = ours.fork(); } } assert_eq!(events::bytes(&ours, &id).as_deref(), Some(ROOT)); for event in events::ids(&ours) { let bytes = events::bytes(&ours, &event).expect("bytes at an event's key"); assert_eq!(Id::of(&bytes), event); assert!(bytes.len() <= crate::federation::event::LARGEST); } let loaded = Document::load(&ours.save()).expect("it loads"); assert_eq!(loaded.get_heads(), ours.get_heads()); let mut other = Document::new(); let screening = std::sync::Mutex::new(Screening::default().holding(Some(id))); offer(&mut other, &ours.get_changes(&[]), &screening); assert_eq!(other.get_heads(), ours.get_heads()); }); assert!( taken.get() > 0 && refused.get() > 0, "{} taken, {} refused", taken.get(), refused.get() ); } }