diff options
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/event.rs | 316 | ||||
| -rw-r--r-- | src/federation/harness.rs | 291 | ||||
| -rw-r--r-- | src/federation/mod.rs | 3 |
3 files changed, 610 insertions, 0 deletions
diff --git a/src/federation/event.rs b/src/federation/event.rs new file mode 100644 index 0000000..b8e89f1 --- /dev/null +++ b/src/federation/event.rs @@ -0,0 +1,316 @@ +//! The federation's events, and its checkpoints, as bytes (`docs/federation.md`, Events, +//! Checkpoints): what each holds, and what makes one none. + +use super::jcs::{self, Json}; +use super::keys; +use super::store::Id; +use super::version::{self, Version}; +use crate::access::sshsig::PublicKey; + +/// The most bytes an event may have. +pub(crate) const LARGEST: usize = 256 * 1024; + +/// Dependencies an event may name. +pub(crate) const DEPENDENCIES: usize = 64; + +/// An event, read from its bytes. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Event { + /// What a party signs. + Signed(Signed), + /// A version event: a version written once its proposal passed, signed by nobody. + Version { deps: Vec<Id>, version: Id }, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Signed { + pub(crate) deps: Vec<Id>, + pub(crate) party: String, + /// The key it is signed with, as the event spells it. + pub(crate) key: String, + pub(crate) does: Does, +} + +/// What a signed event does. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Does { + /// A value at a place: `null` empties it. + Write { path: Vec<String>, value: Json }, + /// The party's key set. + Keys(Vec<String>), + /// The party's node list. + Nodes(Vec<String>), + /// A version proposed, taken whatever it holds: whether it is one is asked where a + /// version event names it. Its hash is the version's. + Proposal { hash: Id, version: Json }, + /// A vote on a proposal (`proposal`) on a version (`on`). + Vote { on: Id, proposal: Id, yes: bool }, +} + +impl Event { + /// The event `bytes` are, where they are one: none where they aren't the JCS encoding + /// of the JSON they read as, a field is missing or more, `key` or `sig` doesn't read + /// back to itself, the signature doesn't hold, or it is larger than federation 1 + /// allows. + pub(crate) fn read(bytes: &[u8]) -> Option<Event> { + if bytes.len() > LARGEST { + return None; + } + let json = jcs::read(bytes)?; + let deps = version::ascending_ids(json.get("deps")?)?; + if deps.is_empty() || deps.len() > DEPENDENCIES { + return None; + } + let names = json.names(); + if names == ["deps", "version"] { + let version = Id::from_hex(json.get("version")?.as_str()?)?; + return Some(Event::Version { deps, version }); + } + let does = ["write", "keys", "nodes", "proposal", "vote"] + .into_iter() + .find(|name| names.contains(name))?; + let mut expected = vec!["deps", "key", "party", "sig", does]; + expected.sort_by(|a, b| jcs::names_order(a, b)); + if names != expected { + return None; + } + let party = json.get("party")?.as_str()?; + let key = json.get("key")?.as_str()?; + let public = keys::key(key)?; + if !version::is_party(party) { + return None; + } + let sig = json.get("sig")?.as_str()?; + if !keys::verifies(&public, sig, &json.without("sig").bytes()) { + return None; + } + let what = json.get(does)?; + let does = match does { + "write" => { + if what.names() != ["path", "value"] { + return None; + } + Does::Write { + path: version::path(what.get("path")?.as_str()?)?, + value: what.get("value")?.clone(), + } + } + "keys" => { + let set = strings(what)?; + if set.len() > version::KEYS || !set.iter().all(|key| keys::key(key).is_some()) { + return None; + } + Does::Keys(set) + } + "nodes" => { + let list = strings(what)?; + if list.len() > version::NODES || !list.iter().all(|id| keys::node_id(id)) { + return None; + } + Does::Nodes(list) + } + "proposal" => Does::Proposal { + hash: Id::of(&what.bytes()), + version: what.clone(), + }, + _ => { + if what.names() != ["on", "proposal", "yes"] { + return None; + } + Does::Vote { + on: Id::from_hex(what.get("on")?.as_str()?)?, + proposal: Id::from_hex(what.get("proposal")?.as_str()?)?, + yes: what.get("yes")?.as_bool()?, + } + } + }; + Some(Event::Signed(Signed { + deps, + party: party.to_owned(), + key: key.to_owned(), + does, + })) + } + + pub(crate) fn deps(&self) -> &[Id] { + match self { + Event::Signed(signed) => &signed.deps, + Event::Version { deps, .. } => deps, + } + } + + /// The key a signed event is signed with. + pub(crate) fn public(signed: &Signed) -> PublicKey { + keys::key(&signed.key).expect("an event's key was read as one") + } +} + +/// Strings a JSON array holds, where it holds strings only, none twice. +fn strings(json: &Json) -> Option<Vec<String>> { + let items = json + .as_array()? + .iter() + .map(|item| item.as_str().map(str::to_owned)) + .collect::<Option<Vec<String>>>()?; + let mut sorted = items.clone(); + sorted.sort(); + sorted.dedup(); + (sorted.len() == items.len()).then_some(items) +} + +/// A checkpoint, a federation's root and a fork's among them: the heads it is at, the +/// events it keeps, and its version. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Checkpoint { + pub(crate) at: Vec<Id>, + pub(crate) keeps: Vec<Id>, + pub(crate) version: Version, +} + +impl Checkpoint { + /// The checkpoint `bytes` are, where they are one: the JCS encoding of + /// `{"at": [<IDs>], "keeps": [<IDs>], "version": <version>}`, its IDs ascending, its + /// version one by itself. + pub(crate) fn read(bytes: &[u8]) -> Option<Checkpoint> { + let json = jcs::read(bytes)?; + if json.names() != ["at", "keeps", "version"] { + return None; + } + Some(Checkpoint { + at: version::ascending_ids(json.get("at")?)?, + keeps: version::ascending_ids(json.get("keeps")?)?, + version: Version::read(json.get("version")?).ok()?, + }) + } + + /// Its bytes. + pub(crate) fn bytes(&self) -> Vec<u8> { + let ids = + |ids: &[Id]| Json::Array(ids.iter().map(|id| Json::Str(id.to_string())).collect()); + Json::object(vec![ + ("at".to_owned(), ids(&self.at)), + ("keeps".to_owned(), ids(&self.keeps)), + ("version".to_owned(), self.version.json.clone()), + ]) + .expect("three names") + .bytes() + } +} + +#[cfg(test)] +mod tests { + use super::super::harness::{self, Party, Spec}; + use super::*; + + fn tv() -> Party { + Party::new("tv", 1) + } + + fn dep() -> Id { + Id::of(b"a dependency") + } + + #[test] + fn every_kind_of_event_reads_back() { + let tv = tv(); + let read = |bytes: Vec<u8>| match Event::read(&bytes) { + Some(Event::Signed(signed)) => signed.does, + other => panic!("not a signed event: {other:?}"), + }; + assert!(matches!( + read(tv.write(&[dep()], "home/tv/x", harness::str("1"))), + Does::Write { .. } + )); + assert_eq!( + read(tv.keys(&[dep()], &[tv.key_line()])), + Does::Keys(vec![tv.key_line()]) + ); + assert_eq!( + read(tv.nodes(&[dep()], &[harness::node_id(1)])), + Does::Nodes(vec![harness::node_id(1)]) + ); + let spec = Spec::first(&[&tv], &[]); + assert!(matches!( + read(tv.propose(&[dep()], &spec.json())), + Does::Proposal { hash, .. } if hash == spec.hash() + )); + assert_eq!( + read(tv.vote(&[dep()], dep(), spec.hash(), true)), + Does::Vote { + on: dep(), + proposal: spec.hash(), + yes: true + } + ); + assert_eq!( + Event::read(&harness::version_event(&[dep()], spec.hash())), + Some(Event::Version { + deps: vec![dep()], + version: spec.hash() + }) + ); + } + + #[test] + fn an_event_spelled_otherwise_is_none() { + let tv = tv(); + let value = || { + ( + "write", + harness::object(vec![("path", harness::str("a")), ("value", Json::Null)]), + ) + }; + let none = |bytes: Vec<u8>| assert_eq!(Event::read(&bytes), None); + // Signed by another key, or its key with a comment. + none(tv.signed_as(&Party::new("x", 2).key, &tv.key_line(), &[dep()], value())); + none(tv.signed_as(&tv.key, &format!("{} tv", tv.key_line()), &[dep()], value())); + // Dependencies: none, or more than federation 1 allows. + none(tv.sign(&[], value())); + let many: Vec<Id> = (0..=DEPENDENCIES) + .map(|i| Id::of(&i.to_be_bytes())) + .collect(); + none(tv.sign(&many, value())); + assert!(Event::read(&tv.sign(&many[1..], value())).is_some()); + // A party that is no party's name. + none(Party::new("t v", 1).sign(&[dep()], value())); + // A field more. + let unsigned = harness::object(vec![ + ("deps", harness::ids(&[dep()])), + ("party", harness::str("tv")), + ("key", harness::str(&tv.key_line())), + value(), + ("more", Json::Null), + ]); + let sig = keys::sign(&tv.key, &unsigned.bytes()); + let Json::Object(mut members) = unsigned else { + unreachable!() + }; + members.push(("sig".to_owned(), Json::Str(sig))); + none(Json::object(members).expect("an object").bytes()); + // Larger than federation 1 allows. + none(tv.write(&[dep()], "a", Json::Str("x".repeat(LARGEST)))); + // A node ID or key spelled otherwise, or more keys than a set may hold. + none(tv.nodes(&[dep()], &[harness::node_id(1).to_uppercase()])); + let keys: Vec<String> = (1..=17).map(harness::key_line).collect(); + none(tv.keys(&[dep()], &keys)); + assert!(Event::read(&tv.keys(&[dep()], &keys[1..])).is_some()); + // Its bytes changed after it was signed. + let signed = String::from_utf8(tv.write(&[dep()], "a", harness::str("1"))).expect("UTF-8"); + none(signed.replace(r#""1""#, r#""2""#).into_bytes()); + } + + #[test] + fn a_checkpoint_reads_back_and_is_no_event() { + let spec = Spec::first(&[&tv()], &[]); + let checkpoint = Checkpoint { + at: Vec::new(), + keeps: Vec::new(), + version: Version::read(&spec.json()).expect("a version"), + }; + assert_eq!( + Checkpoint::read(&checkpoint.bytes()), + Some(checkpoint.clone()) + ); + assert_eq!(Event::read(&checkpoint.bytes()), None); + } +} diff --git a/src/federation/harness.rs b/src/federation/harness.rs new file mode 100644 index 0000000..6d1b214 --- /dev/null +++ b/src/federation/harness.rs @@ -0,0 +1,291 @@ +//! What the federation's tests build with (`docs/federation-tests.md`, The harness): +//! parties with keys made from seeds, signing events as the design says, and versions. + +use ed25519_dalek::SigningKey; + +use super::jcs::Json; +use super::keys; +use super::store::Id; +use crate::access::sshsig::PublicKey; + +/// A party of the tests: a name and a key, made from a seed. +#[derive(Clone)] +pub(crate) struct Party { + pub(crate) name: String, + pub(crate) key: SigningKey, +} + +/// A key made from a seed, spelled as the federation spells one. +pub(crate) fn key_line(seed: u8) -> String { + PublicKey( + SigningKey::from_bytes(&[seed; 32]) + .verifying_key() + .to_bytes(), + ) + .line() +} + +/// A node ID made from a seed. +pub(crate) fn node_id(seed: u8) -> String { + crate::identity::node_id_of( + &SigningKey::from_bytes(&[seed.wrapping_add(128); 32]) + .verifying_key() + .to_bytes(), + ) +} + +pub(crate) fn str(text: &str) -> Json { + Json::Str(text.to_owned()) +} + +/// The JSON of IDs, as an event or a version names them. +pub(crate) fn ids(ids: &[Id]) -> Json { + let mut ids = ids.to_vec(); + ids.sort(); + ids.dedup(); + Json::Array(ids.iter().map(|id| Json::Str(id.to_string())).collect()) +} + +pub(crate) fn object(members: Vec<(&str, Json)>) -> Json { + Json::object( + members + .into_iter() + .map(|(name, value)| (name.to_owned(), value)) + .collect(), + ) + .expect("names once each") +} + +impl Party { + pub(crate) fn new(name: &str, seed: u8) -> Party { + Party { + name: name.to_owned(), + key: SigningKey::from_bytes(&[seed; 32]), + } + } + + /// Its key, spelled as the federation spells one. + pub(crate) fn key_line(&self) -> String { + PublicKey(self.key.verifying_key().to_bytes()).line() + } + + /// An event it signs, on `deps`, doing `does` (a field's name, and what it holds), with + /// `key` its key, signed with `signer`: the two differ only where a test wants them to. + pub(crate) fn signed_as( + &self, + signer: &SigningKey, + key: &str, + deps: &[Id], + does: (&str, Json), + ) -> Vec<u8> { + let unsigned = object(vec![ + ("deps", ids(deps)), + ("party", str(&self.name)), + ("key", str(key)), + (does.0, does.1), + ]); + let sig = keys::sign(signer, &unsigned.bytes()); + let Json::Object(mut members) = unsigned else { + unreachable!("an object") + }; + members.push(("sig".to_owned(), Json::Str(sig))); + Json::object(members).expect("names once each").bytes() + } + + pub(crate) fn sign(&self, deps: &[Id], does: (&str, Json)) -> Vec<u8> { + self.signed_as(&self.key, &self.key_line(), deps, does) + } + + pub(crate) fn write(&self, deps: &[Id], path: &str, value: Json) -> Vec<u8> { + self.sign( + deps, + ("write", object(vec![("path", str(path)), ("value", value)])), + ) + } + + pub(crate) fn keys(&self, deps: &[Id], keys: &[String]) -> Vec<u8> { + self.sign( + deps, + ( + "keys", + Json::Array(keys.iter().map(|key| str(key)).collect()), + ), + ) + } + + pub(crate) fn nodes(&self, deps: &[Id], nodes: &[String]) -> Vec<u8> { + self.sign( + deps, + ( + "nodes", + Json::Array(nodes.iter().map(|id| str(id)).collect()), + ), + ) + } + + pub(crate) fn propose(&self, deps: &[Id], version: &Json) -> Vec<u8> { + self.sign(deps, ("proposal", version.clone())) + } + + pub(crate) fn vote(&self, deps: &[Id], on: Id, proposal: Id, yes: bool) -> Vec<u8> { + self.sign( + deps, + ( + "vote", + object(vec![ + ("on", str(&on.to_string())), + ("proposal", str(&proposal.to_string())), + ("yes", Json::Bool(yes)), + ]), + ), + ) + } +} + +/// A version event, which nobody signs. +pub(crate) fn version_event(deps: &[Id], version: Id) -> Vec<u8> { + object(vec![ + ("deps", ids(deps)), + ("version", str(&version.to_string())), + ]) + .bytes() +} + +/// What a version gives a party, as a test spells it out. +#[derive(Clone)] +pub(crate) struct SpecParty { + pub(crate) name: String, + pub(crate) keys_since: u64, + pub(crate) keys: Vec<String>, + pub(crate) nodes_since: u64, + pub(crate) nodes: Vec<String>, +} + +/// A version, as a test spells it out. +#[derive(Clone)] +pub(crate) struct Spec { + pub(crate) number: u64, + pub(crate) changes: Option<Id>, + pub(crate) parties: Vec<SpecParty>, + /// Each rule: its path and its writer. + pub(crate) rules: Vec<(String, Json)>, + pub(crate) checkpoint: Option<Vec<Id>>, +} + +impl Spec { + /// A first version naming these parties, each with its key and no nodes but the + /// first's, with a namespace each (`home/{party}/**`) and the rules given after. + pub(crate) fn first(parties: &[&Party], rules: &[(&str, Json)]) -> Spec { + Spec { + number: 0, + changes: None, + parties: parties + .iter() + .enumerate() + .map(|(i, party)| { + let nodes = if i == 0 { vec![node_id(0)] } else { Vec::new() }; + SpecParty { + name: party.name.clone(), + keys_since: 0, + keys: vec![party.key_line()], + nodes_since: 0, + nodes, + } + }) + .collect(), + rules: std::iter::once(("home/{party}/**".to_owned(), str("{party}"))) + .chain( + rules + .iter() + .map(|(path, writer)| ((*path).to_owned(), writer.clone())), + ) + .collect(), + checkpoint: None, + } + } + + /// The version after `before`, which this spells: one past its number, changing its + /// hash, nothing named anew. + pub(crate) fn after(&self, before: Id) -> Spec { + Spec { + number: self.number + 1, + changes: Some(before), + checkpoint: None, + ..self.clone() + } + } + + pub(crate) fn json(&self) -> Json { + let mut members = vec![ + ("federation", Json::Int(1)), + ("number", Json::Int(self.number as i64)), + ( + "changes", + self.changes + .map_or(Json::Null, |hash| Json::Str(hash.to_string())), + ), + ( + "keys", + object( + self.parties + .iter() + .map(|party| { + ( + party.name.as_str(), + object(vec![ + ("since", Json::Int(party.keys_since as i64)), + ( + "keys", + Json::Array( + party.keys.iter().map(|key| str(key)).collect(), + ), + ), + ]), + ) + }) + .collect(), + ), + ), + ( + "nodes", + object( + self.parties + .iter() + .map(|party| { + ( + party.name.as_str(), + object(vec![ + ("since", Json::Int(party.nodes_since as i64)), + ( + "nodes", + Json::Array(party.nodes.iter().map(|id| str(id)).collect()), + ), + ]), + ) + }) + .collect(), + ), + ), + ( + "rules", + Json::Array( + self.rules + .iter() + .map(|(path, writer)| { + object(vec![("path", str(path)), ("writer", writer.clone())]) + }) + .collect(), + ), + ), + ]; + if let Some(heads) = &self.checkpoint { + members.push(("checkpoint", ids(heads))); + } + object(members) + } + + /// The version's hash. + pub(crate) fn hash(&self) -> Id { + Id::of(&self.json().bytes()) + } +} diff --git a/src/federation/mod.rs b/src/federation/mod.rs index ddd4c4a..43f683a 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -5,6 +5,9 @@ // Until a node runs it (stage 3), parts of it are used by nothing, or by tests alone. #![allow(dead_code)] +pub(crate) mod event; +#[cfg(test)] +pub(crate) mod harness; pub(crate) mod jcs; pub(crate) mod keys; pub(crate) mod store; |
