aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/federation/event.rs316
-rw-r--r--src/federation/harness.rs291
-rw-r--r--src/federation/mod.rs3
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;