aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/federation/attacks.rs42
-rw-r--r--src/federation/client.rs4
-rw-r--r--src/federation/event.rs16
-rw-r--r--src/federation/fold.rs20
-rw-r--r--src/federation/harness.rs27
-rw-r--r--src/federation/keys.rs8
-rw-r--r--src/federation/model.rs40
-rw-r--r--src/federation/party.rs2
-rw-r--r--src/federation/properties.rs14
-rw-r--r--src/federation/revision.rs37
-rw-r--r--src/federation/vote.rs37
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, &current).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 &current.parties {
- let nodes = match self
- .list(&all, party, &current, 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, &current) {
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.