diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/federation/attacks.rs | 42 | ||||
| -rw-r--r-- | src/federation/client.rs | 4 | ||||
| -rw-r--r-- | src/federation/event.rs | 16 | ||||
| -rw-r--r-- | src/federation/fold.rs | 20 | ||||
| -rw-r--r-- | src/federation/harness.rs | 27 | ||||
| -rw-r--r-- | src/federation/keys.rs | 8 | ||||
| -rw-r--r-- | src/federation/model.rs | 40 | ||||
| -rw-r--r-- | src/federation/party.rs | 2 | ||||
| -rw-r--r-- | src/federation/properties.rs | 14 | ||||
| -rw-r--r-- | src/federation/revision.rs | 37 | ||||
| -rw-r--r-- | src/federation/vote.rs | 37 |
11 files changed, 217 insertions, 30 deletions
diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs index 2043c19..215a860 100644 --- a/src/federation/attacks.rs +++ b/src/federation/attacks.rs @@ -1359,3 +1359,45 @@ fn federation_attack_64() { fed.take(lass.vote(&[no], on, bad.hash(), false)); } } + +/// Merge events: under the base revision, signed by a node its party doesn't list, by a +/// party's key, or spelled otherwise. Taken only under a revision with merge events, +/// signed by a node its party lists; and they count for nothing. +#[test] +fn federation_attack_71() { + use super::event; + use super::revision::Feature; + let (tv, lass, makefu) = (tv(), lass(), makefu()); + let mut fed = three(); + let root = fed.root(); + let on = fed.first.hash(); + let write = fed.take(tv.write(&[root], "home/tv/a", s("1"))); + // tv lists node 0 (`Spec::first`). + fed.judged(harness::merge("tv", 0, &[write])); + let mut revised = fed.first.after(on); + revised.revision = Feature::MergeEvents.revision(); + let (_, written) = fed.pass(&[write], &lass, &revised, on, &[&lass, &makefu]); + let before = (fed.store.state().values(), fed.store.state().members()); + let merged = fed.take(harness::merge("tv", 0, &[written])); + fed.judged(harness::merge("tv", 5, &[merged])); + fed.judged(harness::merge("lass", 0, &[merged])); + fed.judged(tv.sign(&[merged], event::merge())); + let otherwise = harness::node_key(0); + let line = crate::access::sshsig::PublicKey(otherwise.verifying_key().to_bytes()).line(); + assert_eq!( + fed.refused(event::signed( + &otherwise, + "tv", + &line, + &[merged], + ("merge", Json::Bool(false)) + )), + Refusal::None + ); + // Nothing it builds on counts otherwise. + assert_eq!( + (fed.store.state().values(), fed.store.state().members()), + before + ); + assert_eq!(fed.store.heads(), vec![merged]); +} diff --git a/src/federation/client.rs b/src/federation/client.rs index da64923..4d61944 100644 --- a/src/federation/client.rs +++ b/src/federation/client.rs @@ -342,7 +342,7 @@ impl Record { /// What its party signs again, as a move refused it: of the latest event it signed at /// each place, its key set and its node list, those `refused` names, each with what it /// does. Not what a later one replaced, nor votes and proposals, whose version a move - /// leaves behind. + /// leaves behind, nor merges, which a node signs. pub(crate) fn again(&self, refused: impl Fn(&Id) -> bool) -> Vec<(Id, Does)> { let mut latest: BTreeMap<String, (Id, Does)> = BTreeMap::new(); for text in &self.signed { @@ -353,7 +353,7 @@ impl Record { Does::Write { path, .. } => format!("write {}", path.join("/")), Does::Keys(_) => "keys".to_owned(), Does::Nodes(_) => "nodes".to_owned(), - Does::Proposal { .. } | Does::Vote { .. } => continue, + Does::Proposal { .. } | Does::Vote { .. } | Does::Merge => continue, }; latest.insert(what, (Id::of(text.as_bytes()), signed.does)); } diff --git a/src/federation/event.rs b/src/federation/event.rs index 864bedb..ec4493f 100644 --- a/src/federation/event.rs +++ b/src/federation/event.rs @@ -81,6 +81,11 @@ pub(crate) fn vote(on: Id, proposal: Id, yes: bool) -> (&'static str, Json) { ("vote", does.expect("names once each")) } +/// What a node writing a merge event does: nothing but build on its dependencies. +pub(crate) fn merge() -> (&'static str, Json) { + ("merge", Json::Bool(true)) +} + /// A version event, which nobody signs: its bytes. pub(crate) fn version_event(deps: &[Id], version: Id) -> Vec<u8> { Json::object(vec![ @@ -135,6 +140,9 @@ pub(crate) enum Does { Proposal { hash: Id, version: Json }, /// A vote on a proposal (`proposal`) on a version (`on`). Vote { on: Id, proposal: Id, yes: bool }, + /// Nothing but building on its dependencies, signed by a node its party lists, with + /// its node key (`revision::Feature::MergeEvents`). + Merge, } impl Event { @@ -166,7 +174,7 @@ impl Event { let version = Id::from_hex(json.get("version")?.as_str()?)?; return Some(Event::Version { deps, version }); } - let does = ["write", "keys", "nodes", "proposal", "vote"] + let does = ["write", "keys", "nodes", "proposal", "vote", "merge"] .into_iter() .find(|name| names.contains(name))?; let mut expected = vec!["deps", "key", "party", "sig", does]; @@ -213,6 +221,12 @@ impl Event { hash: Id::of(&what.bytes()), version: what.clone(), }, + "merge" => { + if what.as_bool() != Some(true) { + return None; + } + Does::Merge + } _ => { if what.names() != ["on", "proposal", "yes"] { return None; diff --git a/src/federation/fold.rs b/src/federation/fold.rs index 3670051..d832976 100644 --- a/src/federation/fold.rs +++ b/src/federation/fold.rs @@ -10,6 +10,8 @@ use std::collections::{BTreeMap, BTreeSet}; use super::event::{self, Checkpoint, Does, Event, Signed}; use super::jcs::{self, Json}; +use super::keys; +use super::revision::Feature; use super::store::{Fold, Id, Refused}; use super::version::Version; @@ -490,6 +492,24 @@ impl State { Ok(()) } Does::Keys(_) | Does::Nodes(_) | Does::Proposal { .. } => by_version(), + Does::Merge => { + let merging = Feature::MergeEvents; + if !current.revision.has(merging) { + return Err(Refused::new(format!( + "a merge event under {}: taken from {} on", + current.revision, + merging.revision() + ))); + } + let node = keys::node_of(&Event::public(signed)); + if !node.is_some_and(|node| self.nodes_of(&signed.party, current).contains(&node)) { + return Err(Refused::new(format!( + "a merge event signed by no node {} lists", + signed.party + ))); + } + Ok(()) + } Does::Vote { on, proposal, yes } => { by_version()?; if *on != current.hash { diff --git a/src/federation/harness.rs b/src/federation/harness.rs index 4baf049..f14736d 100644 --- a/src/federation/harness.rs +++ b/src/federation/harness.rs @@ -5,6 +5,7 @@ use ed25519_dalek::SigningKey; use super::event; use super::jcs::Json; +use super::revision::Revision; use super::store::Id; use crate::access::sshsig::PublicKey; @@ -25,13 +26,21 @@ pub(crate) fn key_line(seed: u8) -> String { .line() } -/// A node ID made from a seed. +/// A node's key made from a seed. +pub(crate) fn node_key(seed: u8) -> SigningKey { + SigningKey::from_bytes(&[seed.wrapping_add(128); 32]) +} + +/// A node ID made from a seed: `node_key`'s. 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(), - ) + crate::identity::node_id_of(&node_key(seed).verifying_key().to_bytes()) +} + +/// A merge event the node of `seed` signs for `party`, on `deps`. +pub(crate) fn merge(party: &str, seed: u8, deps: &[Id]) -> Vec<u8> { + let key = node_key(seed); + let line = PublicKey(key.verifying_key().to_bytes()).line(); + event::signed(&key, party, &line, deps, event::merge()) } pub(crate) fn str(text: &str) -> Json { @@ -127,6 +136,8 @@ pub(crate) struct Spec { pub(crate) number: u64, pub(crate) changes: Option<Id>, pub(crate) parties: Vec<SpecParty>, + /// The revision it follows: named where it isn't the base revision. + pub(crate) revision: Revision, /// Each rule: its path and its writer. pub(crate) rules: Vec<(String, Json)>, pub(crate) checkpoint: Option<Vec<Id>>, @@ -139,6 +150,7 @@ impl Spec { Spec { number: 0, changes: None, + revision: Revision::default(), parties: parties .iter() .enumerate() @@ -241,6 +253,9 @@ impl Spec { if let Some(heads) = &self.checkpoint { members.push(("checkpoint", ids(heads))); } + if self.revision != Revision::default() { + members.push(("revision", str(&self.revision.id().to_string()))); + } object(members) } diff --git a/src/federation/keys.rs b/src/federation/keys.rs index 0dbe5f7..aff7792 100644 --- a/src/federation/keys.rs +++ b/src/federation/keys.rs @@ -125,6 +125,14 @@ pub(crate) fn node_id(text: &str) -> bool { identity::public_of(text).is_some_and(|key| VerifyingKey::from_bytes(&key).is_ok()) } +/// The ID of the node whose key `key` is, where it is an Ed25519 key, as a node's are. +pub(crate) fn node_of(key: &Key) -> Option<String> { + match key { + Key::Ed25519(PublicKey(public)) => Some(identity::node_id_of(public)), + Key::P256(_) => None, + } +} + /// Whether `sig` is `key`'s signature of `message`, spelled as the federation spells one. pub(crate) fn verifies(key: &Key, sig: &str, message: &[u8]) -> bool { let Ok(blob) = BASE64.decode(sig) else { diff --git a/src/federation/model.rs b/src/federation/model.rs index 8cd189b..cfe787d 100644 --- a/src/federation/model.rs +++ b/src/federation/model.rs @@ -7,6 +7,8 @@ use std::collections::{BTreeMap, BTreeSet}; use super::event::{Checkpoint, Does, Event, Signed}; use super::jcs::Json; +use super::keys; +use super::revision::Feature; use super::store::Id; use super::version::Version; @@ -259,6 +261,23 @@ impl Model { } } + /// The node list of `party` in a history by `version`. + fn nodes(&self, history: &BTreeSet<Id>, party: &str, version: &Version) -> Vec<String> { + let Some(given) = version.parties.get(party) else { + return Vec::new(); + }; + match self + .list(history, party, version, false) + .map(|id| &self.taken[&id]) + { + Some(Event::Signed(Signed { + does: Does::Nodes(nodes), + .. + })) => nodes.clone(), + _ => given.nodes.clone(), + } + } + /// The parties voting `true`, and `false`, on a proposal on `on` in a history. fn votes( &self, @@ -328,6 +347,13 @@ impl Model { && current.writer(path) == Some(signed.party.as_str()) } Does::Keys(_) | Does::Nodes(_) | Does::Proposal { .. } => by_version, + // Signed by a node its party lists, under a revision taking them. + Does::Merge => { + current.revision.has(Feature::MergeEvents) + && keys::node_of(&Event::public(signed)).is_some_and(|node| { + self.nodes(history, &signed.party, ¤t).contains(&node) + }) + } Does::Vote { on, proposal, yes } => { by_version && *on == current.hash @@ -501,18 +527,8 @@ impl Model { let all = self.taken(); let current = self.version(); let mut members = BTreeSet::new(); - for (party, given) in ¤t.parties { - let nodes = match self - .list(&all, party, ¤t, false) - .map(|id| &self.taken[&id]) - { - Some(Event::Signed(Signed { - does: Does::Nodes(nodes), - .. - })) => nodes.clone(), - _ => given.nodes.clone(), - }; - for node in nodes { + for party in current.parties.keys() { + for node in self.nodes(&all, party, ¤t) { members.insert((node, party.clone())); } } diff --git a/src/federation/party.rs b/src/federation/party.rs index 655d4c2..cfcc569 100644 --- a/src/federation/party.rs +++ b/src/federation/party.rs @@ -777,7 +777,7 @@ async fn again(node: &Node, signer: &Signer, record: &mut Record, path: &Path) - Does::Write { path, value } => event::write(&path.join("/"), value), Does::Keys(keys) => event::keys(&keys), Does::Nodes(nodes) => event::nodes(&nodes), - Does::Proposal { .. } | Does::Vote { .. } => continue, + Does::Proposal { .. } | Does::Vote { .. } | Does::Merge => continue, }; println!("signing again {refused}"); sign(node, signer, record, path, does).await?; diff --git a/src/federation/properties.rs b/src/federation/properties.rs index 02c7799..214bb27 100644 --- a/src/federation/properties.rs +++ b/src/federation/properties.rs @@ -1,7 +1,7 @@ //! The federation's properties over generated histories (`docs/federation-tests.md`, //! Properties): three to five parties write, change their key sets and node lists, propose //! versions and checkpoints, vote, and write the versions that pass, each on what it last -//! caught up with; an adversary signs with its keys or stolen ones whatever it likes. The +//! caught up with, and their nodes merge; an adversary signs with its keys or stolen ones whatever it likes. The //! store is checked against the model, which reads every history anew, against itself in //! other orders, and read from a document against itself given the events alone. A //! failing history is cut down, events taken out with what builds on them for as long as @@ -17,6 +17,7 @@ use super::harness::{self, Party, Spec}; use super::held::Holding; use super::jcs::Json; use super::model::{Model, Verdict}; +use super::revision::Feature; use super::store::memory::{Offered, Refusal, Store}; use super::store::{Fold, Id}; use super::version::Version; @@ -109,7 +110,11 @@ fn generate(rng: &mut Rng, kind: Kind) -> History { .collect(); let adversary = count - 1; let refs: Vec<&Party> = parties.iter().collect(); - let first = Spec::first(&refs, &[("names/{party}", harness::str("{party}"))]); + let mut first = Spec::first(&refs, &[("names/{party}", harness::str("{party}"))]); + // Half the federations begin at a revision with merge events, which nodes then sign. + if rng.chance(0.5) { + first.revision = Feature::MergeEvents.revision(); + } let root = first.root(); let root_id = Id::of(&root); let mut world: Store<Federation> = Store::new(root.clone(), Vec::new()).expect("a root"); @@ -146,7 +151,10 @@ fn generate(rng: &mut Rng, kind: Kind) -> History { .filter(|(id, ..)| known[w].contains(id)) .collect(); let roll = rng.below(100); - let event = if roll < 35 || (roll >= 60 && mine.is_empty()) { + let event = if roll < 4 { + // A node merges, its party's or not. + harness::merge(&party.name, rng.below(10) as u8, &deps) + } else if roll < 35 || (roll >= 60 && mine.is_empty()) { let path = format!("home/{}/k{}", party.name, rng.below(3)); writer.write(&deps, &path, harness::str(&step.to_string())) } else if roll < 43 { diff --git a/src/federation/revision.rs b/src/federation/revision.rs index 876ec15..3c6261b 100644 --- a/src/federation/revision.rs +++ b/src/federation/revision.rs @@ -12,24 +12,44 @@ use super::store::Id; /// A feature a revision adds. #[derive(Clone, Copy, Debug, PartialEq, Eq)] -pub(crate) enum Feature {} +pub(crate) enum Feature { + /// Merge events: a node its party lists, with its own key, builds on events it holds, + /// writing nothing (`Does::Merge`). + MergeEvents, +} impl Feature { /// Its name, in the IDs of the revisions that have it: never changed once released, /// and specific, so that a feature another build names alike is one it adds alike. pub(crate) fn name(self) -> &'static str { - match self {} + match self { + Feature::MergeEvents => "merge-events", + } } /// What it adds, in a line. pub(crate) fn what(self) -> &'static str { - match self {} + match self { + Feature::MergeEvents => { + "merge events, which a node its party lists signs with its own key, building \ + on events it holds and writing nothing" + } + } + } + + /// The revision that adds it. + pub(crate) fn revision(self) -> Revision { + let at = FEATURES + .iter() + .position(|feature| *feature == self) + .expect("every feature is in FEATURES"); + Revision(at + 1) } } /// The features, in the order revisions add them: revision n has the first n, the base /// revision none. Only ever appended to. -pub(crate) const FEATURES: &[Feature] = &[]; +pub(crate) const FEATURES: &[Feature] = &[Feature::MergeEvents]; /// A revision: how many of `FEATURES` it has. #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)] @@ -113,6 +133,15 @@ mod tests { assert_eq!(Revision::of(&Id::of(b"[]")), Some(Revision(0))); assert_eq!(Revision::of(&Id::of(b"[\"elsewhere\"]")), None); assert_eq!(Revision::default().to_string(), "the base revision"); + assert_eq!( + Feature::MergeEvents.revision().to_string(), + "revision 1 (merge-events)" + ); + assert_eq!( + Revision(1).id(), + Id::of(br#"["merge-events"]"#), + "a released revision's ID changes never" + ); let names: Vec<&str> = FEATURES.iter().map(|feature| feature.name()).collect(); let distinct: std::collections::BTreeSet<&str> = names.iter().copied().collect(); assert_eq!(distinct.len(), names.len(), "a feature named twice"); diff --git a/src/federation/vote.rs b/src/federation/vote.rs index 2e5ce15..c274849 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -5,7 +5,8 @@ //! * **Following**: it votes `true` on a proposal on the current version where a party it //! follows voted `true`, never `false`; by default only on a version that only moves to a //! checkpoint (`Version::only_moves_on`), and then only where no proposal that changes -//! more holds it back (`holds_back`), as such a version lapses it. +//! more holds it back (`holds_back`), as such a version lapses it; never on one changing +//! the revision. //! * **Proposing a checkpoint**: once so many events are held beyond its checkpoint, so //! many versions were written since, or so long after it moved there by its own clock, it //! proposes a version that only moves to a checkpoint, at the heads of what it held for a @@ -268,6 +269,15 @@ pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec<Act if !own_one && !rules.follow_any && !moves_on { continue; } + // A revision its operators move to by hand: its party's nodes run a continuum + // that knows it first. + let revised = proposed + .version + .as_ref() + .is_some_and(|version| version.revision != current.revision); + if !own_one && revised { + continue; + } // A checkpoint lapses what else is proposed: the party it follows may not end so // a proposal that changes more. let lapses = all.iter().any(|other| { @@ -622,6 +632,31 @@ mod tests { )); } + /// A party the node follows backs a version moving to a later revision: a node + /// following on any version backs it not, as its operators move to a revision by hand. + #[test] + fn a_follower_backs_no_change_of_the_revision() { + let (tv, _, _, first, mut store) = three(); + let root = store.id(); + let mut revised = first.after(first.hash()); + revised.revision = crate::federation::revision::Feature::MergeEvents.revision(); + let proposal = taken(&mut store, tv.propose(&[root], &revised.json())); + taken( + &mut store, + tv.vote(&[proposal], first.hash(), revised.hash(), true), + ); + let any = Rules { + follow: vec!["tv".to_owned()], + follow_any: true, + ..Rules::default() + }; + let long = |_: &Id| Some(Duration::from_secs(3600)); + let record = record(&store, "makefu"); + assert!(decide(&seen(&store, &long), &any, &record).is_empty()); + // By hand, it does. + assert!(by_hand(&seen(&store, &long), &any, &record, revised.hash(), true).is_ok()); + } + /// A party the node follows backs a checkpoint while a proposal that changes more, /// which another party backs, can still pass: the node backs it not, as it would lapse /// that one; while nobody but its proposer backs that one, it does. |
