diff options
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/attacks.rs | 48 | ||||
| -rw-r--r-- | src/federation/fork.rs | 162 | ||||
| -rw-r--r-- | src/federation/mod.rs | 4 |
3 files changed, 210 insertions, 4 deletions
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<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()); + } +} 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; |
