diff options
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/attacks.rs | 2 | ||||
| -rw-r--r-- | src/federation/fold.rs | 10 | ||||
| -rw-r--r-- | src/federation/held.rs | 83 | ||||
| -rw-r--r-- | src/federation/store/memory.rs | 114 | ||||
| -rw-r--r-- | src/federation/store/mod.rs | 6 | ||||
| -rw-r--r-- | src/federation/store/testfold.rs | 10 |
6 files changed, 203 insertions, 22 deletions
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(¤t, 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 { |
