diff options
| author | tv <tv@krebsco.de> | 2026-11-17 00:25:41 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-17 01:47:45 +0100 |
| commit | 438d4f06103ba7ae17a80f48aa589219c7d8dd61 (patch) | |
| tree | 0191dceb5fa2025276e3d67429375712f8869745 /src/federation/fork.rs | |
| parent | 3a5bf56e644e7334536a7d3dae742a940182f856 (diff) | |
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.
Diffstat (limited to 'src/federation/fork.rs')
| -rw-r--r-- | src/federation/fork.rs | 162 |
1 files changed, 162 insertions, 0 deletions
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<u8>]) -> Vec<u8> { + 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<u8>, Vec<Vec<u8>>) { + 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<Federation>, + heads: &[Id], + version: &Json, +) -> Result<Vec<u8>, 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<String>, + /// 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<Id>, + /// 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<String>, Vec<String>)>, +} + +/// 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<Federation>, root: &[u8]) -> Result<Check, String> { + 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<String>| { + 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::<Federation>::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()); + } +} |
