summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-18 17:26:53 +0000
committertv <tv@krebsco.de>2026-11-18 18:31:11 +0100
commit598366b03679eac9d04f32d9194f3ba4ba9c3da8 (patch)
tree91620955243fa081fdd0365fb76c8aca0ba4288c /src
parentf261a80b88c1fb640f4c892934809e15a7e05a95 (diff)
store: a drop refuses whatever writes what a dropped event writes
A fold may say what an event writes that others may write alike (`Fold::writes`): of the federation, a version event's version. A node whose operator has it drop such an event drops the taken events writing the same with it, and refuses any writing it from then on, whoever wrote it anew: of a version, it takes no other version event naming it and writes none itself, though it holds the votes that passed it. The node keeps what each dropped event writes in its store file, across restarts; allowing one of them takes them all back. Row 51 of the federation's attacks has its test, and waits no more.
Diffstat (limited to 'src')
-rw-r--r--src/api/events.rs5
-rw-r--r--src/federation/attacks.rs2
-rw-r--r--src/federation/fold.rs10
-rw-r--r--src/federation/held.rs83
-rw-r--r--src/federation/store/memory.rs114
-rw-r--r--src/federation/store/mod.rs6
-rw-r--r--src/federation/store/testfold.rs10
7 files changed, 207 insertions, 23 deletions
diff --git a/src/api/events.rs b/src/api/events.rs
index 3017c25..04dc77e 100644
--- a/src/api/events.rs
+++ b/src/api/events.rs
@@ -73,7 +73,10 @@ fn why(refusal: &Refusal) -> String {
Refusal::Own => {
"its history takes it, but this node doesn't, by what it took before".to_owned()
}
- Refusal::Dropped => "this node's operator had it drop it".to_owned(),
+ Refusal::Dropped => {
+ "this node's operator had it drop it, or a version event naming the version it names"
+ .to_owned()
+ }
}
}
diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs
index d3dc660..316f5eb 100644
--- a/src/federation/attacks.rs
+++ b/src/federation/attacks.rs
@@ -14,7 +14,7 @@ use super::store::{Fold, Id};
use super::version::Version;
/// Rows whose tests wait: what a node or a party's client doesn't do yet, and flooding.
-const LATER: &[u32] = &[30, 39, 51, 63, 68];
+const LATER: &[u32] = &[30, 39, 63, 68];
fn tv() -> Party {
Party::new("tv", 1)
diff --git a/src/federation/fold.rs b/src/federation/fold.rs
index 89ce12c..f37c213 100644
--- a/src/federation/fold.rs
+++ b/src/federation/fold.rs
@@ -642,6 +642,16 @@ impl Fold for Federation {
}
}
+ /// A version event's version: an operator having its node drop one has it refuse every
+ /// version event naming that version, whoever wrote it anew (`docs/federation.md`,
+ /// Changing the policy).
+ fn writes(bytes: &[u8]) -> Option<Id> {
+ match Event::read_taken(bytes) {
+ Some(Event::Version { version, .. }) => Some(version),
+ _ => None,
+ }
+ }
+
fn checkpoint(at: &State, heads: &[Id]) -> (Vec<u8>, Vec<Id>) {
let current = at.current().clone();
let keeps = at.counting(&current, true);
diff --git a/src/federation/held.rs b/src/federation/held.rs
index c29dd0a..200323e 100644
--- a/src/federation/held.rs
+++ b/src/federation/held.rs
@@ -50,7 +50,8 @@ const LOOK: Duration = Duration::from_secs(5);
const PUT_BYTES: usize = 1024 * 1024;
/// What a node keeps of its own of its store across restarts, as its file holds it: the
-/// events it refused by what it took before, and those its operator had it drop, by ID.
+/// events it refused by what it took before, and those its operator had it drop, by ID;
+/// and of the dropped version events, the version each writes.
#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", deny_unknown_fields)]
struct Kept {
@@ -58,24 +59,38 @@ struct Kept {
refused: BTreeSet<String>,
#[serde(default)]
dropped: BTreeSet<String>,
+ #[serde(default)]
+ writes: BTreeMap<String, String>,
}
+/// What the store refused of its own, what it dropped, and of the dropped what each writes.
+type KeptIds = (Vec<Id>, Vec<Id>, Vec<(Id, Id)>);
+
impl Kept {
- fn of(own: &[Id], dropped: &[Id]) -> Self {
+ fn of(own: &[Id], dropped: &[Id], writes: &[(Id, Id)]) -> Self {
Kept {
refused: own.iter().map(Id::to_string).collect(),
dropped: dropped.iter().map(Id::to_string).collect(),
+ writes: writes
+ .iter()
+ .map(|(id, writes)| (id.to_string(), writes.to_string()))
+ .collect(),
}
}
- /// The IDs it holds: what was refused, and what dropped.
- fn ids(&self) -> Option<(Vec<Id>, Vec<Id>)> {
+ /// The IDs it holds: what was refused, what dropped, and what of that writes what.
+ fn ids(&self) -> Option<KeptIds> {
let ids = |set: &BTreeSet<String>| {
set.iter()
.map(|id| Id::from_hex(id))
.collect::<Option<Vec<Id>>>()
};
- Some((ids(&self.refused)?, ids(&self.dropped)?))
+ let writes = self
+ .writes
+ .iter()
+ .map(|(id, writes)| Some((Id::from_hex(id)?, Id::from_hex(writes)?)))
+ .collect::<Option<Vec<(Id, Id)>>>()?;
+ Some((ids(&self.refused)?, ids(&self.dropped)?, writes))
}
}
@@ -248,7 +263,7 @@ impl Holding {
return;
};
let id = Id::of(&root);
- let (own, dropped) = inner.kept.ids().unwrap_or_default();
+ let (own, dropped, writes) = inner.kept.ids().unwrap_or_default();
// What a checkpoint keeps follows it in the document: a fork's root's too.
let kept = |checkpoint: &[u8]| -> Option<Vec<Vec<u8>>> {
Federation::parts(checkpoint)
@@ -296,7 +311,7 @@ impl Holding {
match started {
Ok(store) => {
info!(store = %id, refused = own.len(), dropped = dropped.len(), "Reading the store from the document");
- inner.store = Some(store.refusing(&own, &dropped));
+ inner.store = Some(store.refusing(&own, &dropped, &writes));
}
Err(why) => {
if inner.none.replace(id) != Some(id) {
@@ -342,7 +357,7 @@ impl Holding {
inner.taken_at.entry(*id).or_insert(now);
}
let (own, dropped) = store.own();
- let kept = Kept::of(&own, &dropped);
+ let kept = Kept::of(&own, &dropped, &store.dropped_writes());
if kept != inner.kept {
for id in kept.refused.difference(&inner.kept.refused) {
warn!(event = %id, "Refused an event its history takes, by what this node took before: kept so");
@@ -1609,6 +1624,58 @@ mod tests {
);
}
+ /// Row 51 (`docs/federation.md`): a node whose operator had it drop a version is sent
+ /// it again, written anew by another node, and holds the votes that passed it: it takes
+ /// no event writing that version and writes it no more, before or after a restart,
+ /// until its operator allows it again.
+ #[test]
+ fn federation_attack_51() {
+ let (tv, lass, makefu) = (
+ Party::new("tv", 1),
+ Party::new("lass", 2),
+ Party::new("makefu", 3),
+ );
+ let first = Spec::first(&[&tv, &lass, &makefu], &[]);
+ let root = first.root();
+ let on = first.hash();
+ let one = first.after(on);
+ let proposal = tv.propose(&[Id::of(&root)], &one.json());
+ let votes = [&tv, &lass, &makefu]
+ .map(|party| party.vote(&[Id::of(&proposal)], on, one.hash(), true));
+ let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], one.hash());
+ let anew = harness::version_event(&[Id::of(&votes[1]), Id::of(&votes[2])], one.hash());
+ let current = |holding: &Holding| holding.with(|store| store.state().current().hash);
+ let started = || {
+ let mut doc = events::started(Federation::NAME, &root, &[]).unwrap();
+ for event in [&proposal].into_iter().chain(&votes).chain([&written]) {
+ put(&mut doc, event);
+ }
+ doc
+ };
+ let dir = crate::files::scratch_dir("held-attack-51");
+ let path = dir.join("store.json");
+ let files = Arc::new(Files::default());
+ let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap();
+ read(&holding, &started(), 0);
+ assert_eq!(current(&holding), Some(one.hash()));
+ holding.drop_taken(&[Id::of(&written)]).unwrap().unwrap();
+ assert_eq!(current(&holding), Some(on));
+ // Sent again, in another document, beside the same version written anew.
+ let mut again = started();
+ assert_eq!(put_by(&mut again, "node-b", &anew), Ok(()));
+ read(&holding, &again, 1);
+ assert_eq!(current(&holding), Some(on));
+ assert_eq!(holding.passed(), Vec::<Vec<u8>>::new());
+ let restarted = Holding::open(Some(path), files, None, None).unwrap();
+ read(&restarted, &again, 0);
+ assert_eq!(current(&restarted), Some(on));
+ assert_eq!(restarted.passed(), Vec::<Vec<u8>>::new());
+ // Allowed again: taken.
+ assert!(restarted.allow(&[Id::of(&written)]));
+ read(&restarted, &again, 0);
+ assert_eq!(current(&restarted), Some(one.hash()));
+ }
+
// The store's attack rows (`docs/store.md`, Attacks) read from a document.
/// tv's federation, its root, and a document started from it.
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index bc0c672..7527a44 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -19,7 +19,7 @@ pub(crate) enum Refusal {
NotAbove,
/// Its history takes it, but the node doesn't, by what it took before.
Own,
- /// Its operator had the node drop it.
+ /// Its operator had the node drop it, or one writing what it writes (`Fold::writes`).
Dropped,
}
@@ -68,6 +68,9 @@ pub(crate) struct Store<F: Fold> {
waits_for: HashMap<Id, BTreeSet<Id>>,
/// The events refused, and why.
refused: HashMap<Id, Refusal>,
+ /// Of the events refused as dropped, those writing what other events may write alike,
+ /// and what each writes (`Fold::writes`): an event writing that is refused as dropped.
+ writes: HashMap<Id, Id>,
/// What a move to a checkpoint forgot that came before its heads: held as accounted
/// for, and nothing after the checkpoint builds on it.
forgotten: HashSet<Id>,
@@ -112,6 +115,7 @@ impl<F: Fold> Store<F> {
waiting: HashMap::new(),
waits_for: HashMap::new(),
refused: HashMap::new(),
+ writes: HashMap::new(),
forgotten: HashSet::new(),
})
}
@@ -443,6 +447,12 @@ impl<F: Fold> Store<F> {
}
fn judged(&mut self, id: Id, event: Event, taken: &mut Vec<Id>) -> Offered {
+ if let Some(writes) = F::writes(&event.bytes)
+ && self.writes.values().any(|dropped| *dropped == writes)
+ {
+ self.writes.insert(id, writes);
+ return self.refuse(id, Refusal::Dropped);
+ }
if let Some(refused) = event
.dependencies
.iter()
@@ -503,22 +513,31 @@ impl<F: Fold> Store<F> {
self.refused.iter()
}
- /// Drops events taken after the checkpoint, with everything built on them, as their
- /// operator has the node do: it refuses them from then on, until its operator allows
- /// them again. What the checkpoint keeps, or holds by ID, it drops not: every event
- /// after it builds on that. Returns what it dropped, in the order taken.
+ /// Drops events taken after the checkpoint, those writing what they write alike
+ /// (`Fold::writes`), and everything built on them, as their operator has the node do:
+ /// it refuses them from then on, and whatever writes what they write, until its
+ /// operator allows them again. What the checkpoint keeps, or holds by ID, it drops not:
+ /// every event after it builds on that. Returns what it dropped, in the order taken.
pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result<Vec<Id>, Refused> {
if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) {
return Err(Refused::new(format!(
"{id} isn't an event taken after the checkpoint"
)));
}
+ let named: HashSet<Id> = ids
+ .iter()
+ .filter_map(|id| F::writes(&self.events[id].bytes))
+ .collect();
let mut dropped: HashMap<Id, Refusal> =
ids.iter().map(|id| (*id, Refusal::Dropped)).collect();
for id in &self.order {
if dropped.contains_key(id) {
continue;
}
+ if F::writes(&self.events[id].bytes).is_some_and(|writes| named.contains(&writes)) {
+ dropped.insert(*id, Refusal::Dropped);
+ continue;
+ }
if let Some(on) = self.events[id]
.dependencies
.iter()
@@ -536,7 +555,11 @@ impl<F: Fold> Store<F> {
.collect();
self.order.retain(|id| !dropped.contains_key(id));
for id in &order {
- self.events.remove(id);
+ if let Some(event) = self.events.remove(id)
+ && let Some(writes) = F::writes(&event.bytes)
+ {
+ self.writes.insert(*id, writes);
+ }
}
self.refused.extend(dropped);
let mut state = self.start.clone();
@@ -548,14 +571,27 @@ impl<F: Fold> Store<F> {
}
/// Takes back what the node refused of its own, or dropped, as its operator says
- /// otherwise: `ids`, and what was refused for being built on them. They are taken when
- /// offered again, where the store takes them then.
+ /// otherwise: `ids`, what was dropped for writing what a dropped one among them writes,
+ /// and what was refused for being built on them. They are taken when offered again,
+ /// where the store takes them then.
pub(crate) fn allow(&mut self, ids: &[Id]) {
let mut todo: Vec<Id> = ids
.iter()
.filter(|id| matches!(self.refused.get(id), Some(Refusal::Own | Refusal::Dropped)))
.copied()
.collect();
+ let lifted: HashSet<Id> = todo
+ .iter()
+ .filter_map(|id| self.writes.get(id))
+ .copied()
+ .collect();
+ todo.extend(
+ self.writes
+ .iter()
+ .filter(|(_, writes)| lifted.contains(writes))
+ .map(|(id, _)| *id),
+ );
+ self.writes.retain(|_, writes| !lifted.contains(writes));
while let Some(id) = todo.pop() {
self.refused.remove(&id);
todo.extend(
@@ -568,17 +604,31 @@ impl<F: Fold> Store<F> {
}
/// Itself, refusing `own` as its node refused them of its own and `dropped` as its
- /// operator had it drop them: a store read anew, before anything is offered to it,
- /// refuses what its node refused so before, whatever order the events come in
+ /// operator had it drop them, and whatever writes what one of `writes`, each a dropped
+ /// event and what it writes, does: a store read anew, before anything is offered to
+ /// it, refuses what its node refused so before, whatever order the events come in
/// (`docs/store.md`, A node's own).
- pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id]) -> Self {
+ pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id], writes: &[(Id, Id)]) -> Self {
self.refused
.extend(own.iter().map(|id| (*id, Refusal::Own)));
self.refused
.extend(dropped.iter().map(|id| (*id, Refusal::Dropped)));
+ self.writes.extend(writes.iter().copied());
self
}
+ /// Of what its operator had it drop, the events writing what others may write alike,
+ /// each with what it writes, in the order of their IDs.
+ pub(crate) fn dropped_writes(&self) -> Vec<(Id, Id)> {
+ let mut writes: Vec<(Id, Id)> = self
+ .writes
+ .iter()
+ .map(|(id, writes)| (*id, *writes))
+ .collect();
+ writes.sort_unstable();
+ writes
+ }
+
/// What its node refused of its own, and what its operator had it drop.
pub(crate) fn own(&self) -> (Vec<Id>, Vec<Id>) {
let of = |refusal: Refusal| {
@@ -778,6 +828,46 @@ mod tests {
assert!(store.drop_taken(&[root]).is_err());
}
+ /// An event its operator had the node drop writing what others write alike: they are
+ /// dropped with it, taken or offered later, and whatever writes it, before or after a
+ /// store is read anew, until its operator allows one.
+ #[test]
+ fn a_drop_refuses_whatever_writes_what_the_dropped_write() {
+ let mut store = store();
+ let root = store.id();
+ let mark = taken(store.offer(testfold::put(&[root], "mark", "1")));
+ let one = testfold::era(&[root], 1, "one");
+ let again = testfold::era(&[mark], 1, "one");
+ let anew = testfold::era(&[root, mark], 1, "one");
+ let one_id = taken(store.offer(one.clone()));
+ let again_id = taken(store.offer(again));
+ assert_eq!(store.drop_taken(&[one_id]).unwrap(), vec![one_id, again_id]);
+ assert_eq!(store.state().era().0, 0);
+ assert_eq!(
+ store.offer(anew.clone()),
+ Offered::Refused(Refusal::Dropped)
+ );
+ assert_eq!(store.dropped_writes().len(), 3);
+ // Read anew: one writing the same, never offered before, is refused as dropped.
+ let (own, drops) = store.own();
+ let mut read = self::store().refusing(&own, &drops, &store.dropped_writes());
+ taken(read.offer(testfold::put(&[root], "mark", "1")));
+ let later = taken(read.offer(testfold::put(&[mark], "later", "1")));
+ assert_eq!(
+ read.offer(testfold::era(&[later], 1, "one")),
+ Offered::Refused(Refusal::Dropped)
+ );
+ assert!(matches!(
+ read.offer(testfold::era(&[root], 1, "two")),
+ Offered::Taken(_)
+ ));
+ // Allowed again: all of them.
+ store.allow(&[one_id]);
+ assert!(store.dropped_writes().is_empty());
+ assert!(matches!(store.offer(one), Offered::Taken(_)));
+ assert!(matches!(store.offer(anew), Offered::Taken(_)));
+ }
+
#[test]
fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() {
let mut store = store();
@@ -794,7 +884,7 @@ mod tests {
(&[Id::of(&other)][..], &[dropped][..])
);
// Read anew, the other era first: refused as before.
- let mut anew = self::store().refusing(&own, &drops);
+ let mut anew = self::store().refusing(&own, &drops, &store.dropped_writes());
assert_eq!(anew.offer(other), Offered::Refused(Refusal::Own));
assert_eq!(
anew.offer(testfold::put(&[root], "b", "1")),
diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs
index ec3fb56..4027fb9 100644
--- a/src/federation/store/mod.rs
+++ b/src/federation/store/mod.rs
@@ -94,6 +94,12 @@ pub(crate) trait Fold {
true
}
+ /// What the event writes that other events may write alike, where it writes such: a
+ /// node refuses whatever writes what an event its operator had it drop writes.
+ fn writes(_event: &[u8]) -> Option<Id> {
+ None
+ }
+
/// The checkpoint at `heads`, read as `at`: its bytes, and the events it keeps.
fn checkpoint(at: &Self::State, heads: &[Id]) -> (Vec<u8>, Vec<Id>);
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs
index bf23321..2478c0a 100644
--- a/src/federation/store/testfold.rs
+++ b/src/federation/store/testfold.rs
@@ -6,7 +6,8 @@
//! holds is its latest put, none other having it in its history, then the lowest ID.
//! * `lock`: a key locked for good.
//! * `era`: era `n`, taken only where `n` is one past the era at its history; of two of one
-//! number, a node keeps the first it takes (as the federation's versions).
+//! number, a node keeps the first it takes (as the federation's versions). Eras of one
+//! number and tag write the same: a drop of one refuses them all.
//! * `cut`: cut `n`, naming heads to move the store to, as `era`: above the heads the latest
//! cut of its history names, and holding that cut (or after the checkpoint the state
//! starts from, where it holds none); none of them in another's history. It must be above
@@ -362,6 +363,13 @@ impl Fold for TestFold {
}
}
+ fn writes(event: &[u8]) -> Option<Id> {
+ match decode(event)? {
+ (_, Kind::Era { n, tag }) => Some(Id::of(format!("era {n} {tag}").as_bytes())),
+ _ => None,
+ }
+ }
+
fn checkpoint(at: &State, heads: &[Id]) -> (Vec<u8>, Vec<Id>) {
let keeps: Vec<Id> = at.counting().into_values().collect();
let checkpoint = Checkpoint {