diff options
| author | tv <tv@krebsco.de> | 2026-11-16 22:50:39 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-17 00:09:39 +0100 |
| commit | ef392f4f52529bef1042e6fb0d2bea33e9bbab87 (patch) | |
| tree | 342b956f6814af16fa1e1d13ff95fc94b4fcb760 | |
| parent | 65e9d86e48e3fd182882ceb54b9b8b1ff475369d (diff) | |
federation: a store read from its document holds what one given the events alone holds
A property over generated federations, honest ones with checkpoints: their events are
put into a document by two writers, in batches of a shuffled order, some by both at
once, the writers merging now and then; a node reads its store from each writer's
document as it grows, and once more after both merged. Each holds what a store given
the events alone holds: its checkpoint, the events it took after it, and what it reads.
| -rw-r--r-- | src/federation/properties.rs | 111 |
1 files changed, 83 insertions, 28 deletions
diff --git a/src/federation/properties.rs b/src/federation/properties.rs index 7200703..082fcac 100644 --- a/src/federation/properties.rs +++ b/src/federation/properties.rs @@ -2,9 +2,10 @@ //! 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 -//! store is checked against the model, which reads every history anew, and against itself -//! in other orders. A failing history is cut down, events taken out with what builds on -//! them for as long as it still fails, and printed. +//! 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 +//! it still fails, and printed. use std::collections::{BTreeMap, BTreeSet}; @@ -13,11 +14,13 @@ use ed25519_dalek::SigningKey; use super::event::{Checkpoint, Does, Event}; use super::fold::Federation; use super::harness::{self, Party, Spec}; +use super::held::Holding; use super::model::{Model, Verdict}; use super::store::memory::{Offered, Refusal, Store}; use super::store::{Fold, Id}; use super::version::Version; use crate::access::sshsig::PublicKey; +use crate::document::events; use crate::testrand::{Rng, for_seeds}; /// The most events a history has. @@ -265,14 +268,15 @@ fn cut_down( } } -/// What a store reads, to compare with the model or another store. -fn reads( - store: &Store<Federation>, -) -> ( +/// The current version's hash, the values at places, and the members. +type Reads = ( Id, BTreeMap<String, super::jcs::Json>, BTreeSet<(String, String)>, -) { +); + +/// What a store reads, to compare with the model or another store. +fn reads(store: &Store<Federation>) -> Reads { let state = store.state(); ( state.current().hash, @@ -281,16 +285,20 @@ fn reads( ) } -fn model_reads( - model: &Model, -) -> ( - Id, - BTreeMap<String, super::jcs::Json>, - BTreeSet<(String, String)>, -) { +fn model_reads(model: &Model) -> Reads { (model.version().hash, model.values(), model.members()) } +/// What a store holds, to compare with another store: its checkpoint, the events it took +/// after it, and what it reads. +fn holds(store: &Store<Federation>) -> (Vec<u8>, BTreeSet<Id>, Reads) { + ( + store.checkpoint().to_vec(), + store.taken().iter().copied().collect(), + reads(store), + ) +} + /// The verdict a store's answer stands for. fn verdict(offered: &Offered) -> Verdict { match offered { @@ -370,12 +378,7 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() { checkpoints: true, }, |history| { - let (store, _) = history.store(&history.written()); - let held = ( - store.checkpoint().to_vec(), - store.taken().iter().copied().collect::<BTreeSet<Id>>(), - reads(&store), - ); + let held = holds(&history.store(&history.written()).0); let mut rng = Rng::new(history.events.len() as u64); let mut orders = vec![history.written().into_iter().rev().collect::<Vec<usize>>()]; for _ in 0..3 { @@ -384,13 +387,7 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() { orders.push(order); } for order in orders { - let (other, _) = history.store(&order); - let other_held = ( - other.checkpoint().to_vec(), - other.taken().iter().copied().collect::<BTreeSet<Id>>(), - reads(&other), - ); - if other_held != held { + if holds(&history.store(&order).0) != held { return Err(format!( "offered in the order {order:?}, a store holds otherwise" )); @@ -401,6 +398,64 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() { ); } +/// The events of a history put into a document by two writers, in batches of a shuffled +/// order, some by both at once, the writers merging now and then; a node reads its store +/// from each writer's document as it grows, and once more after both merged. +#[test] +fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds() { + check( + 24, + Kind { + adversary: false, + checkpoints: true, + }, + |history| { + let alone = holds(&history.store(&history.written()).0); + let mut rng = Rng::new(history.events.len() as u64); + let started = events::started(Federation::NAME, &history.root).expect("a root"); + let mut docs = [started.fork(), started.fork()]; + let holdings = [Holding::default(), Holding::default()]; + let read = |holdings: &[Holding; 2], docs: &[_; 2]| { + for (holding, doc) in holdings.iter().zip(docs) { + holding.read(holding.unread(doc, 0).expect("a store")); + } + }; + let mut order = history.written(); + rng.shuffle(&mut order); + let mut rest = order.as_slice(); + while !rest.is_empty() { + let (batch, after) = rest.split_at(rng.between(1, 4).min(rest.len())); + rest = after; + let batch: Vec<&[u8]> = batch.iter().map(|&i| &history.events[i][..]).collect(); + let at = usize::from(rng.chance(0.5)); + events::put(&mut docs[at], &batch); + if rng.chance(0.2) { + events::put(&mut docs[1 - at], &batch); + } + if rng.chance(0.3) { + let [one, other] = &mut docs; + one.merge(other).expect("merged"); + other.merge(one).expect("merged"); + } + read(&holdings, &docs); + } + let [one, other] = &mut docs; + one.merge(other).expect("merged"); + other.merge(one).expect("merged"); + read(&holdings, &docs); + for (n, holding) in holdings.iter().enumerate() { + if holding.with(holds).as_ref() != Some(&alone) { + return Err(format!( + "the store read from writer {n}'s document holds otherwise than one \ + given the events alone" + )); + } + } + Ok(()) + }, + ); +} + #[test] fn after_a_checkpoint_the_store_judges_and_reads_as_the_whole_history() { check( |
