aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/federation/attacks.rs48
-rw-r--r--src/federation/fork.rs162
-rw-r--r--src/federation/mod.rs4
-rw-r--r--src/swarm/bootstrap.rs17
4 files changed, 213 insertions, 18 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;
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<Option<Self>> {
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<Vec<u8>> = lines.collect();
+ let (root, kept) = crate::federation::fork::read_root_file(&file);
if let Err(refused) = Store::<Federation>::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));