From 6c6f978189eafa15add0df865f713dc946dfc5cb Mon Sep 17 00:00:00 2001 From: tv Date: Thu, 19 Nov 2026 03:52:49 +0000 Subject: federation: merge events, the first revision What builds on many heads merges them, but only an event a party writes: in a quiet federation, heads beside each other stay so, and past 64 no event is above them all. Revision 1 (`merge-events`) adds merge events: `{"merge": true}`, signed with a node's own key, the `key` its Ed25519 key, for the party whose node list names it. One counts for nothing, and only gathers what it builds on into the history of what builds on it. Under the base revision, signed by a node its party doesn't list, or by a party's key, it is refused; the model alike. Generated federations begin at either revision, and their nodes merge. A node voting by itself backs no version changing the revision, on any version neither: its party's operators vote on that one, once their nodes run a continuum that knows it. `federation.md` lists the revisions, says what a merge event is, and row 71 is tested (`federation_attack_71`). --- src/federation/attacks.rs | 42 ++++++++++++++++++++++++++++++++++++++++++ src/federation/client.rs | 4 ++-- src/federation/event.rs | 16 +++++++++++++++- src/federation/fold.rs | 20 ++++++++++++++++++++ src/federation/harness.rs | 27 +++++++++++++++++++++------ src/federation/keys.rs | 8 ++++++++ src/federation/model.rs | 40 ++++++++++++++++++++++++++++------------ src/federation/party.rs | 2 +- src/federation/properties.rs | 14 +++++++++++--- src/federation/revision.rs | 37 +++++++++++++++++++++++++++++++++---- src/federation/vote.rs | 37 ++++++++++++++++++++++++++++++++++++- 11 files changed, 217 insertions(+), 30 deletions(-) (limited to 'src') 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 = 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 { 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 { + 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, pub(crate) parties: Vec, + /// 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>, @@ -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 { + 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, party: &str, version: &Version) -> Vec { + 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 = 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