From 438d4f06103ba7ae17a80f48aa589219c7d8dd61 Mon Sep 17 00:00:00 2001 From: tv Date: Tue, 17 Nov 2026 00:25:41 +0000 Subject: federation: a fork's root made, and checked by a node holding its history `federation::fork`: a node holding a federation's history makes the root of a fork at heads it holds by a version, with the events the root keeps, as the file the fork's founders start its swarm from (`make`, `root_file`, which `--store-root` reads); and checks a fork's root it is given (`check`): whether it builds that root at its heads, byte for byte, what it holds that those heads lack, and, party by party, the keys the fork's version gives where they aren't those the party had there. The attack rows 35 and 36 have their tests. --- src/federation/attacks.rs | 48 +++++++++++++- src/federation/fork.rs | 162 ++++++++++++++++++++++++++++++++++++++++++++++ src/federation/mod.rs | 4 +- src/swarm/bootstrap.rs | 17 +---- 4 files changed, 213 insertions(+), 18 deletions(-) create mode 100644 src/federation/fork.rs (limited to 'src') diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs index 531dca7..e1d2936 100644 --- a/src/federation/attacks.rs +++ b/src/federation/attacks.rs @@ -5,15 +5,16 @@ use super::event::Checkpoint; use super::fold::Federation; +use super::fork; use super::harness::{self, Party, Spec}; use super::jcs::Json; use super::store::memory::{Offered, Refusal, Store}; use super::store::{Fold, Id}; use super::version::Version; -/// Rows whose tests wait: what a node, a party's client or a tool does (stage 3), forks -/// (stage 4), and flooding. -const LATER: &[u32] = &[30, 33, 35, 36, 39, 45, 51, 58, 63, 65, 68]; +/// Rows whose tests wait: what a node, a party's client or a tool does (stage 3), a fork +/// whose root differs, simulated (stage 4), and flooding. +const LATER: &[u32] = &[30, 33, 39, 45, 51, 58, 63, 65, 68]; fn tv() -> Party { Party::new("tv", 1) @@ -688,6 +689,47 @@ fn federation_attack_34() { assert!(fed.store.fork(&[here], &elsewhere.json().bytes()).is_err()); } +/// A fork at heads of its founder's choosing, leaving out a write of lass's: a node +/// holding the federation builds its root, and is told what those heads lack. +#[test] +fn federation_attack_35() { + let mut fed = three(); + let root = fed.root(); + let here = fed.take(tv().write(&[root], "home/tv/a", s("1"))); + let beside = fed.take(lass().write(&[root], "home/lass/b", s("1"))); + let mut forking = fed.first.after(fed.first.hash()); + forking.parties[0].nodes_since = 1; + let file = fork::make(&fed.store, &[here], &forking.json()).expect("a fork"); + let (fork_root, _) = fork::read_root_file(&file); + let check = fork::check(&fed.store, &fork_root).expect("checked"); + assert!(check.builds); + assert_eq!(check.lacking, vec![beside]); +} + +/// A fork's version giving lass, who didn't go, a key of its founder's: a node holding +/// the federation is told, party by party. +#[test] +fn federation_attack_36() { + let mut fed = three(); + let root = fed.root(); + let here = fed.take(tv().write(&[root], "home/tv/a", s("1"))); + let mut forking = fed.first.after(fed.first.hash()); + forking.parties[1].keys = vec![harness::key_line(9)]; + forking.parties[1].keys_since = 1; + let file = fork::make(&fed.store, &[here], &forking.json()).expect("a fork"); + let (fork_root, _) = fork::read_root_file(&file); + let check = fork::check(&fed.store, &fork_root).expect("checked"); + assert!(check.builds); + assert_eq!( + check.keys, + vec![( + "lass".to_owned(), + vec![lass().key_line()], + vec![harness::key_line(9)] + )] + ); +} + #[test] fn federation_attack_37() { let mut fed = three(); diff --git a/src/federation/fork.rs b/src/federation/fork.rs new file mode 100644 index 0000000..59b744f --- /dev/null +++ b/src/federation/fork.rs @@ -0,0 +1,162 @@ +//! Forks (`docs/federation.md`, Forks): a node holding a federation's history makes the +//! root of a fork at heads it holds, by a version (`make`), and checks one it is given +//! (`check`): whether it builds that root at its heads, what it holds that those heads +//! lack, and, party by party, the keys the fork's version gives where they aren't the +//! keys the party had there. A node that doesn't hold that history takes a fork's root on +//! its operator's word, who names the fork by its root's ID (`--store-id`). +//! +//! A fork's founders start its swarm from a file holding its root on the first line, and +//! the events the root keeps, each on a line of its own (`--store-root`): JCS writes no +//! line break. + +use std::collections::BTreeSet; + +use super::event::Checkpoint; +use super::fold::Federation; +use super::jcs::Json; +use super::store::Id; +use super::store::memory::Store; + +/// The file a store's swarm starts from: its `root` on the first line, and each event of +/// `kept`, the events it keeps, on a line of its own. +pub(crate) fn root_file(root: &[u8], kept: &[Vec]) -> Vec { + let mut file = root.to_vec(); + file.push(b'\n'); + for event in kept { + file.extend_from_slice(event); + file.push(b'\n'); + } + file +} + +/// The root a file holds (`root_file`), and the events it keeps. +pub(crate) fn read_root_file(file: &[u8]) -> (Vec, Vec>) { + let mut lines = file + .split(|byte| *byte == b'\n') + .filter(|line| !line.is_empty()) + .map(<[u8]>::to_vec); + let root = lines.next().unwrap_or_default(); + (root, lines.collect()) +} + +/// The root of the fork at `heads` by `version`, as `store` builds it, with the events it +/// keeps: the file the fork's founders start its swarm from (`root_file`). +pub(crate) fn make( + store: &Store, + heads: &[Id], + version: &Json, +) -> Result, String> { + let (root, kept) = store.fork(heads, &version.bytes()).map_err(|why| why.0)?; + Ok(root_file(&root, &kept)) +} + +/// What a node holding a federation's history finds of a fork's root. +#[derive(Debug, PartialEq, Eq)] +pub(crate) struct Check { + /// Whether it builds the root at its heads by its version, byte for byte; and why it + /// builds none, where it doesn't: heads it doesn't hold, or a version that is no fork. + pub(crate) builds: bool, + pub(crate) why: Option, + /// What it holds that those heads lack: events it took that are neither among them, + /// nor in their history, nor above them. + pub(crate) lacking: Vec, + /// Each party whose keys the fork's version gives otherwise than the party had at + /// those heads, with its keys there and in the fork. + pub(crate) keys: Vec<(String, Vec, Vec)>, +} + +/// What `store` finds of the fork whose root is `root`: as a node holding the history up +/// to its heads builds it, says what it holds that those heads lack, and, party by party, +/// whether the fork's version gives it the keys it had there. +pub(crate) fn check(store: &Store, root: &[u8]) -> Result { + let checkpoint = Checkpoint::read(root).ok_or("no checkpoint, so no fork's root")?; + if checkpoint.at.is_empty() { + return Err("a federation's root, at no heads: no fork's".to_owned()); + } + let heads = &checkpoint.at; + let version = &checkpoint.version; + let (builds, why) = match store.fork(heads, &version.json.bytes()) { + Ok((built, _)) => (built == root, None), + Err(why) => (false, Some(why.0)), + }; + if !heads.iter().all(|head| store.holds(head)) { + return Ok(Check { + builds, + why, + lacking: Vec::new(), + keys: Vec::new(), + }); + } + let lacking = store.left_out(heads, store.taken()); + let at = store.state_at(heads); + let current = at.current(); + let sorted = |mut keys: Vec| { + keys.sort(); + keys + }; + let parties: BTreeSet<&String> = current + .parties + .keys() + .chain(version.parties.keys()) + .collect(); + let keys = parties + .into_iter() + .filter_map(|party| { + let there = if current.parties.contains_key(party) { + sorted(at.keys_of(party, current)) + } else { + Vec::new() + }; + let forked = sorted( + version + .parties + .get(party) + .map(|given| given.keys.clone()) + .unwrap_or_default(), + ); + (there != forked).then(|| (party.clone(), there, forked)) + }) + .collect(); + Ok(Check { + builds, + why, + lacking, + keys, + }) +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::federation::harness::{self, Party, Spec}; + + #[test] + fn a_fork_is_made_into_the_file_its_swarm_starts_from() { + let tv = Party::new("tv", 1); + let first = Spec::first(&[&tv], &[]); + let mut store = Store::::new(first.root(), Vec::new()).unwrap(); + let write = tv.write(&[store.id()], "home/tv/x", harness::str("1")); + let head = Id::of(&write); + store.offer(write.clone()); + let mut spec = first.after(first.hash()); + spec.parties[0].nodes_since = 1; + let file = make(&store, &[head], &spec.json()).unwrap(); + let (root, kept) = read_root_file(&file); + assert_eq!(kept, vec![write]); + assert_eq!(root_file(&root, &kept), file); + assert!(store.checks_fork(&[head], &spec.json().bytes(), &root)); + assert_eq!(read_root_file(&first.root()), (first.root(), Vec::new())); + assert!(make(&store, &[Id::of(b"not held")], &spec.json()).is_err()); + let check = check(&store, &root).unwrap(); + assert_eq!( + check, + Check { + builds: true, + why: None, + lacking: Vec::new(), + keys: Vec::new(), + } + ); + assert!(super::check(&store, &first.root()).is_err()); + } +} diff --git a/src/federation/mod.rs b/src/federation/mod.rs index 61949fd..f7853e7 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -1,6 +1,7 @@ //! A federation of parties that don't trust each other (`docs/federation.md`), on a store //! of events generic over what they read as (`docs/store.md`): what a node of a swarm -//! holding one reads from its document (`held`), and a party's client (`client`, `party`). +//! holding one reads from its document (`held`), forks made and checked (`fork`), and a +//! party's client (`client`, `party`). //! Built stage by stage behind the `federation` feature. // Built stage by stage: parts of it are used by nothing yet, or by tests alone. @@ -11,6 +12,7 @@ mod attacks; pub(crate) mod client; pub(crate) mod event; pub(crate) mod fold; +pub(crate) mod fork; #[cfg(test)] pub(crate) mod harness; pub(crate) mod held; diff --git a/src/swarm/bootstrap.rs b/src/swarm/bootstrap.rs index 594db8f..b280b38 100644 --- a/src/swarm/bootstrap.rs +++ b/src/swarm/bootstrap.rs @@ -280,7 +280,7 @@ impl StoreStart { /// The store `root` or `id` names, if either does: a root the federation takes as one, /// with the events it keeps, which a store's root must be. The file `root` holds the /// root on its first line, and, for a fork, the events it keeps, each on a line of its - /// own: JCS, which writes no line break. + /// own (`federation::fork::root_file`). pub(crate) fn of(root: Option<&Path>, id: Option<&str>, files: &Files) -> Result> { use crate::federation::fold::Federation; use crate::federation::store::{Id, memory::Store}; @@ -293,12 +293,7 @@ impl StoreStart { .read(FileKind::Store, path) .with_context(|| format!("Reading the store's root {}", path.display()))? .with_context(|| format!("The store's root {} doesn't exist", path.display()))?; - let mut lines = file - .split(|byte| *byte == b'\n') - .filter(|line| !line.is_empty()) - .map(<[u8]>::to_vec); - let root = lines.next().unwrap_or_default(); - let kept: Vec> = lines.collect(); + let (root, kept) = crate::federation::fork::read_root_file(&file); if let Err(refused) = Store::::new(root.clone(), kept.clone()) { bail!("The store's root {} is none: {}", path.display(), refused.0); } @@ -619,13 +614,7 @@ mod tests { let dir = crate::files::scratch_dir("fork-root"); let (path, alone) = (dir.join("fork"), dir.join("alone")); let files = Files::default(); - let mut file = root.clone(); - for event in &kept { - file.push(b'\n'); - file.extend_from_slice(event); - } - file.push(b'\n'); - std::fs::write(&path, file).unwrap(); + std::fs::write(&path, crate::federation::fork::root_file(&root, &kept)).unwrap(); std::fs::write(&alone, &root).unwrap(); let fork = StoreStart::of(Some(&path), None, &files).unwrap().unwrap(); assert_eq!(fork.id, Id::of(&root)); -- cgit v1.3.1