diff options
| author | tv <tv@krebsco.de> | 2026-11-16 21:48:27 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 23:07:39 +0100 |
| commit | 9d9292ae5570cc4be6b68cd3eda92e80893bc679 (patch) | |
| tree | 4ff203cebbf6d723af678f5b60e6cfb39a0143aa /src/federation | |
| parent | 491751e51a554d991d5066dbe968aa44f3d66f30 (diff) | |
federation: what a party's client decides by
A party's client signs its party's events with one of its keys, read from an OpenSSH
private key file, unencrypted (`client::signing_key`), and keeps its party's record
(`client::Record`): the votes it cast, each as signed, with the versions they are on;
with each `true`, the votes that made its party's earlier proposal on that version dead,
as signed; and the events it signed besides. The record begins on the version current
then, and casts nothing on it; it is written whole or not at all.
It votes by its record, never by what a node shows (`docs/federation.md`, Changing the
policy): never `true` and `false` on one proposal, nor the same twice; a `true` only for
a version changing the current one, and one at a time, its earlier `true` on a proposal
the votes given make dead, each checked from itself and its version, which it keeps. It
signs again, of the latest event it signed at each place, its key set and its node list,
what a move refused (`Record::again`). And over the records parties' clients keep, it
names a party that voted twice (`client::voted_twice`): its `true` and `false` on one
proposal, or its `true` on two of one version, neither dead by all the votes.
JSON is taken as the federation takes it (`client::json`).
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/client.rs | 638 | ||||
| -rw-r--r-- | src/federation/mod.rs | 1 |
2 files changed, 639 insertions, 0 deletions
diff --git a/src/federation/client.rs b/src/federation/client.rs new file mode 100644 index 0000000..ef6e116 --- /dev/null +++ b/src/federation/client.rs @@ -0,0 +1,638 @@ +//! A party's client (`docs/federation.md`, Changing the policy, Checkpoints): what signs +//! its party's events with one of its keys, and keeps its party's record of its votes, +//! votes by that record, never by what a node shows, and signs again what a move refused. +//! The client itself (`continuum-party`) puts events through a node's API; this is what it +//! decides by. +//! +//! The record holds the votes the party cast, each as signed, with the versions they are +//! on; with each `true`, the votes that made its party's earlier proposal on that version +//! dead, as signed, so that once a checkpoint left them out nothing names its party as +//! voting twice; and the events it signed besides, to sign again what a move refused. It +//! is written before a vote is sent. A record begins on the version current then, and +//! casts nothing on it, as a `true` sent before it began may be held back somewhere. + +use std::collections::{BTreeMap, BTreeSet}; +use std::path::Path; + +use base64::{Engine, engine::general_purpose::STANDARD as BASE64}; +use ed25519_dalek::SigningKey; +use serde::{Deserialize, Serialize}; + +use super::event::{Does, Event, Signed}; +use super::jcs::{self, Json}; +use super::store::Id; +use super::version::Version; + +/// The Ed25519 key an OpenSSH private key file holds, unencrypted, as `ssh-keygen -t +/// ed25519 -N ''` writes one. +pub(crate) fn signing_key(text: &str) -> Result<SigningKey, String> { + const BEGIN: &str = "-----BEGIN OPENSSH PRIVATE KEY-----"; + const END: &str = "-----END OPENSSH PRIVATE KEY-----"; + let inner = text + .trim() + .strip_prefix(BEGIN) + .and_then(|rest| rest.strip_suffix(END)) + .ok_or("not an OpenSSH private key")?; + let blob: String = inner.split_whitespace().collect(); + let blob = BASE64 + .decode(blob) + .map_err(|_| "an OpenSSH private key that isn't base64")?; + let mut reader = Reader(&blob); + if reader.take(15) != Some(b"openssh-key-v1\0".as_slice()) { + return Err("not an OpenSSH private key".to_owned()); + } + let cipher = reader.string().ok_or("a truncated key")?; + let kdf = reader.string().ok_or("a truncated key")?; + if cipher != b"none" || kdf != b"none" { + return Err( + "an encrypted key: the client reads only unencrypted ones (ssh-keygen -p -N '')" + .to_owned(), + ); + } + reader.string().ok_or("a truncated key")?; + if reader.u32() != Some(1) { + return Err("a file holding other than one key".to_owned()); + } + reader.string().ok_or("a truncated key")?; + let mut private = Reader(reader.string().ok_or("a truncated key")?); + let check = private.u32(); + if check.is_none() || check != private.u32() { + return Err("a key whose check doesn't hold".to_owned()); + } + if private.string() != Some(b"ssh-ed25519".as_slice()) { + return Err("not an Ed25519 key".to_owned()); + } + let public = private.string().ok_or("a truncated key")?; + let secret = private.string().ok_or("a truncated key")?; + let (Ok(seed), Ok(public)) = ( + <[u8; 32]>::try_from(secret.get(..32).unwrap_or_default()), + <[u8; 32]>::try_from(public), + ) else { + return Err("an Ed25519 key of another length".to_owned()); + }; + let key = SigningKey::from_bytes(&seed); + if key.verifying_key().to_bytes() != public { + return Err("a key whose public half isn't its own".to_owned()); + } + Ok(key) +} + +/// SSH's wire encoding, read. +struct Reader<'a>(&'a [u8]); + +impl<'a> Reader<'a> { + fn take(&mut self, count: usize) -> Option<&'a [u8]> { + let (taken, rest) = self.0.split_at_checked(count)?; + self.0 = rest; + Some(taken) + } + + fn u32(&mut self) -> Option<u32> { + Some(u32::from_be_bytes(self.take(4)?.try_into().ok()?)) + } + + fn string(&mut self) -> Option<&'a [u8]> { + let length = self.u32()? as usize; + self.take(length) + } +} + +/// `value` as the federation takes JSON (`jcs`): integers of up to 2^53, no fractions, a +/// depth of at most 32. +pub(crate) fn json(value: &serde_json::Value) -> Result<Json, String> { + fn convert(value: &serde_json::Value) -> Result<Json, String> { + Ok(match value { + serde_json::Value::Null => Json::Null, + serde_json::Value::Bool(value) => Json::Bool(*value), + serde_json::Value::Number(number) => Json::Int( + number + .as_i64() + .ok_or_else(|| format!("{number}: the federation takes integers only"))?, + ), + serde_json::Value::String(text) => Json::Str(text.clone()), + serde_json::Value::Array(items) => { + Json::Array(items.iter().map(convert).collect::<Result<_, _>>()?) + } + serde_json::Value::Object(members) => Json::object( + members + .iter() + .map(|(name, value)| Ok((name.clone(), convert(value)?))) + .collect::<Result<_, String>>()?, + ) + .ok_or("a name twice")?, + }) + } + let json = convert(value)?; + jcs::read(&json.bytes()).ok_or_else(|| "JSON the federation doesn't take".to_owned()) +} + +/// A party's record, as its client keeps it in a file. +#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)] +#[serde(rename_all = "camelCase", deny_unknown_fields)] +pub(crate) struct Record { + /// The store it is of, by ID. + pub(crate) store: String, + pub(crate) party: String, + /// The version current when it began, by hash: it casts nothing on it. + pub(crate) began: String, + /// The versions it voted on, by hash, each as its JCS text. + #[serde(default)] + pub(crate) versions: BTreeMap<String, String>, + /// The votes it cast, each as signed. + #[serde(default)] + pub(crate) votes: Vec<String>, + /// With each `true`, the votes that made its party's earlier proposal on that version + /// dead, each as signed. + #[serde(default)] + pub(crate) nays: Vec<String>, + /// The events it signed but votes, each as signed, oldest first. + #[serde(default)] + pub(crate) signed: Vec<String>, +} + +/// A vote, read from its bytes: who cast it, on what, how. +struct Vote { + party: String, + key: String, + on: Id, + proposal: Id, + yes: bool, +} + +impl Vote { + /// The vote `bytes` are, where they are one; with `verify`, only where its signature + /// holds. + fn read(bytes: &[u8], verify: bool) -> Option<Vote> { + let event = if verify { + Event::read(bytes) + } else { + Event::read_taken(bytes) + }; + match event? { + Event::Signed(Signed { + party, + key, + does: Does::Vote { on, proposal, yes }, + .. + }) => Some(Vote { + party, + key, + on, + proposal, + yes, + }), + _ => None, + } + } + + /// Whether it counts as cast on `version`: on it, signed with a key it names for its + /// party. + fn counts_on(&self, version: &Version) -> bool { + self.on == version.hash + && version + .parties + .get(&self.party) + .is_some_and(|party| party.keys.contains(&self.key)) + } +} + +/// Whether `nays`, each checked from itself and `on`, make the proposal `proposal` on `on` +/// dead: so many parties voted `false` that the rest can't pass it. +fn dead_by(on: &Version, proposal: &Id, nays: &[Vec<u8>]) -> bool { + let no: BTreeSet<String> = nays + .iter() + .filter_map(|bytes| Vote::read(bytes, true)) + .filter(|vote| vote.counts_on(on) && vote.proposal == *proposal && !vote.yes) + .map(|vote| vote.party) + .collect(); + let parties = on.parties.len(); + 3 * (parties - no.len().min(parties)) < 2 * parties +} + +impl Record { + /// A record of `party` of the store `store`, beginning on `current`. + pub(crate) fn begin(store: Id, party: &str, current: &Version) -> Self { + Record { + store: store.to_string(), + party: party.to_owned(), + began: current.hash.to_string(), + versions: BTreeMap::new(), + votes: Vec::new(), + nays: Vec::new(), + signed: Vec::new(), + } + } + + /// The record the file at `path` holds. + pub(crate) fn load(path: &Path) -> Result<Self, String> { + let bytes = std::fs::read(path).map_err(|error| format!("{}: {error}", path.display()))?; + serde_json::from_slice(&bytes).map_err(|error| format!("{}: {error}", path.display())) + } + + /// Writes it to the file at `path`, whole or not at all. + pub(crate) fn save(&self, path: &Path) -> Result<(), String> { + let mut bytes = serde_json::to_vec_pretty(self).map_err(|error| error.to_string())?; + bytes.push(b'\n'); + let mut temporary = path.as_os_str().to_owned(); + temporary.push(".new"); + let temporary = std::path::PathBuf::from(temporary); + std::fs::write(&temporary, &bytes) + .and_then(|()| std::fs::File::open(&temporary)?.sync_all()) + .and_then(|()| std::fs::rename(&temporary, path)) + .map_err(|error| format!("{}: {error}", path.display())) + } + + /// Its votes on `on`, as it cast them. + fn votes_on(&self, on: &Id) -> Vec<Vote> { + self.votes + .iter() + .filter_map(|text| Vote::read(text.as_bytes(), false)) + .filter(|vote| vote.on == *on) + .collect() + } + + /// Whether its party may vote `yes` on the proposal of hash `proposal`, proposing + /// `proposed`, on `current`, the current version, by this record: the nays among + /// `nays` to keep with it, or why not. Never `true` and `false` on one proposal, nor + /// the same twice; none on the version it began on; a `true` only for a version, and + /// one at a time: its party's earlier `true` on `current` must be on a proposal the + /// `nays` make dead. + pub(crate) fn may_vote( + &self, + current: &Version, + proposal: Id, + proposed: &Json, + yes: bool, + nays: &[Vec<u8>], + ) -> Result<Vec<Vec<u8>>, String> { + if current.hash.to_string() == self.began { + return Err( + "this record began on the current version: it casts nothing on it, as a vote sent before may be held back" + .to_owned(), + ); + } + let cast = self.votes_on(¤t.hash); + if let Some(earlier) = cast.iter().find(|vote| vote.proposal == proposal) { + return Err(if earlier.yes == yes { + "voted so on it already".to_owned() + } else { + "never `true` and `false` on one proposal".to_owned() + }); + } + if !yes { + return Ok(Vec::new()); + } + let version = Version::read(proposed).map_err(|why| format!("no version: {why}"))?; + version + .changes_validly(Some(current)) + .map_err(|why| format!("no version changing the current one: {why}"))?; + let mut kept = Vec::new(); + for earlier in cast.iter().filter(|vote| vote.yes) { + if !dead_by(current, &earlier.proposal, nays) { + return Err(format!( + "one `true` at a time: the party's on {} isn't dead by the votes given", + earlier.proposal + )); + } + kept.extend(nays.iter().cloned()); + } + Ok(kept) + } + + /// Records the vote `cast` on `current`, with the `nays` that freed its party: before it + /// is sent. + pub(crate) fn cast(&mut self, current: &Version, cast: &[u8], nays: Vec<Vec<u8>>) { + self.versions.insert( + current.hash.to_string(), + String::from_utf8_lossy(¤t.json.bytes()).into_owned(), + ); + self.votes.push(String::from_utf8_lossy(cast).into_owned()); + for nay in nays { + let nay = String::from_utf8_lossy(&nay).into_owned(); + if !self.nays.contains(&nay) { + self.nays.push(nay); + } + } + } + + /// Records an event it signed, but a vote. + pub(crate) fn signed(&mut self, event: &[u8]) { + self.signed + .push(String::from_utf8_lossy(event).into_owned()); + } + + /// 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. + 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 { + let Some(Event::Signed(signed)) = Event::read_taken(text.as_bytes()) else { + continue; + }; + let what = match &signed.does { + Does::Write { path, .. } => format!("write {}", path.join("/")), + Does::Keys(_) => "keys".to_owned(), + Does::Nodes(_) => "nodes".to_owned(), + Does::Proposal { .. } | Does::Vote { .. } => continue, + }; + latest.insert(what, (Id::of(text.as_bytes()), signed.does)); + } + latest.into_values().filter(|(id, _)| refused(id)).collect() + } +} + +/// The parties that voted twice, by the votes `records` keep: of each version they name, +/// a party whose `true` and `false` are on one proposal, or whose `true` is on two +/// proposals of which neither is dead by all the votes. Each vote counts as checked from +/// itself and its version; one of a version no record holds counts for nothing. Each +/// party once a version, with why. +pub(crate) fn voted_twice(records: &[Record]) -> Vec<(Id, String, String)> { + let versions: BTreeMap<Id, Version> = records + .iter() + .flat_map(|record| record.versions.values()) + .filter_map(|text| jcs::read(text.as_bytes())) + .filter_map(|json| Version::read(&json).ok()) + .map(|version| (version.hash, version)) + .collect(); + let mut votes: BTreeMap<Id, Vote> = BTreeMap::new(); + for text in records + .iter() + .flat_map(|record| record.votes.iter().chain(&record.nays)) + { + if let Some(vote) = Vote::read(text.as_bytes(), true) + && versions.get(&vote.on).is_some_and(|on| vote.counts_on(on)) + { + votes.insert(Id::of(text.as_bytes()), vote); + } + } + let mut twice = Vec::new(); + for (hash, version) in &versions { + let on: Vec<&Vote> = votes.values().filter(|vote| vote.on == *hash).collect(); + let nays: Vec<Vec<u8>> = votes + .iter() + .filter(|(_, vote)| vote.on == *hash && !vote.yes) + .filter_map(|(id, _)| { + records + .iter() + .flat_map(|record| record.votes.iter().chain(&record.nays)) + .find(|text| Id::of(text.as_bytes()) == *id) + .map(|text| text.as_bytes().to_vec()) + }) + .collect(); + let parties: BTreeSet<&str> = on.iter().map(|vote| vote.party.as_str()).collect(); + for party in parties { + let cast: BTreeSet<(Id, bool)> = on + .iter() + .filter(|vote| vote.party == party) + .map(|vote| (vote.proposal, vote.yes)) + .collect(); + let backed: Vec<Id> = cast + .iter() + .filter(|(_, yes)| *yes) + .map(|(proposal, _)| *proposal) + .collect(); + let why = if let Some((proposal, _)) = cast + .iter() + .find(|(proposal, yes)| *yes && cast.contains(&(*proposal, false))) + { + Some(format!("`true` and `false` on {proposal}")) + } else { + let alive: Vec<&Id> = backed + .iter() + .filter(|proposal| !dead_by(version, proposal, &nays)) + .collect(); + (alive.len() >= 2).then(|| format!("`true` on {} and {}", alive[0], alive[1])) + }; + if let Some(why) = why { + twice.push((*hash, party.to_owned(), why)); + } + } + } + twice +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::federation::harness::{self, Party, Spec}; + + /// tv, lass and makefu; a version after the first, and another beside it. + fn three() -> (Party, Party, Party, Spec, Version, Spec, Spec) { + let (tv, lass, makefu) = ( + Party::new("tv", 1), + Party::new("lass", 2), + Party::new("makefu", 3), + ); + let first = Spec::first(&[&tv, &lass, &makefu], &[]); + let current = Version::read(&first.json()).unwrap(); + let one = first.after(first.hash()); + let mut two = first.after(first.hash()); + two.rules.push(("names/x".to_owned(), harness::str("tv"))); + (tv, lass, makefu, first, current, one, two) + } + + #[test] + fn a_key_reads_from_an_openssh_file() { + // `ssh-keygen -t ed25519 -N '' -C test` of a key made from 32 bytes of 7, spelled + // out by OpenSSH's format. + let key = SigningKey::from_bytes(&[7; 32]); + let public = key.verifying_key().to_bytes(); + let string = |bytes: &[u8]| { + let mut out = (bytes.len() as u32).to_be_bytes().to_vec(); + out.extend_from_slice(bytes); + out + }; + let mut public_blob = string(b"ssh-ed25519"); + public_blob.extend(string(&public)); + let mut private = [9u32.to_be_bytes(), 9u32.to_be_bytes()].concat(); + private.extend(string(b"ssh-ed25519")); + private.extend(string(&public)); + private.extend(string(&[[7u8; 32], public].concat())); + private.extend(string(b"test")); + private.extend([1u8, 2, 3]); + let mut blob = b"openssh-key-v1\0".to_vec(); + blob.extend(string(b"none")); + blob.extend(string(b"none")); + blob.extend(string(b"")); + blob.extend(1u32.to_be_bytes()); + blob.extend(string(&public_blob)); + blob.extend(string(&private)); + let file = format!( + "-----BEGIN OPENSSH PRIVATE KEY-----\n{}\n-----END OPENSSH PRIVATE KEY-----\n", + BASE64.encode(&blob) + ); + assert_eq!(signing_key(&file).unwrap().to_bytes(), key.to_bytes()); + assert!(signing_key("ssh-ed25519 AAAA").is_err()); + let encrypted = file.replace( + &BASE64.encode(&blob), + &BASE64.encode({ + let mut other = b"openssh-key-v1\0".to_vec(); + other.extend(string(b"aes256-ctr")); + other + }), + ); + assert!(signing_key(&encrypted).is_err()); + } + + #[test] + fn json_as_the_federation_takes_it() { + assert_eq!( + json(&serde_json::json!({"b": 1, "a": [true, null, "x"]})) + .unwrap() + .bytes(), + br#"{"a":[true,null,"x"],"b":1}"#.to_vec() + ); + assert!(json(&serde_json::json!(1.5)).is_err()); + assert!(json(&serde_json::json!(1u64 << 60)).is_err()); + } + + #[test] + fn a_record_votes_one_true_at_a_time_and_never_both() { + let (tv, lass, makefu, first, current, one, two) = three(); + let root = Id::of(b"root"); + let mut record = Record::begin(root, "tv", ¤t); + // Begun on the current version: nothing cast on it. + assert!( + record + .may_vote(¤t, one.hash(), &one.json(), true, &[]) + .is_err() + ); + record.began = Id::of(b"earlier").to_string(); + assert_eq!( + record.may_vote(¤t, one.hash(), &one.json(), true, &[]), + Ok(Vec::new()) + ); + let yes = tv.vote(&[root], first.hash(), one.hash(), true); + record.cast(¤t, &yes, Vec::new()); + assert!( + record + .may_vote(¤t, one.hash(), &one.json(), false, &[]) + .is_err() + ); + assert!( + record + .may_vote(¤t, one.hash(), &one.json(), true, &[]) + .is_err() + ); + // Another `true` only once the first is dead: two nays of three parties. + assert!( + record + .may_vote(¤t, two.hash(), &two.json(), true, &[]) + .is_err() + ); + let nays = vec![ + lass.vote(&[root], first.hash(), one.hash(), false), + makefu.vote(&[root], first.hash(), one.hash(), false), + ]; + assert!( + record + .may_vote(¤t, two.hash(), &two.json(), true, &nays[..1]) + .is_err() + ); + assert_eq!( + record.may_vote(¤t, two.hash(), &two.json(), true, &nays), + Ok(nays.clone()) + ); + // A nay signed by a key the version doesn't name counts for nothing. + let forged = Party { + name: "makefu".to_owned(), + key: SigningKey::from_bytes(&[42; 32]), + }; + let unnamed = vec![ + nays[0].clone(), + forged.vote(&[root], first.hash(), one.hash(), false), + ]; + assert!( + record + .may_vote(¤t, two.hash(), &two.json(), true, &unnamed) + .is_err() + ); + // No version: not backed. + assert!( + record + .may_vote(¤t, Id::of(b"x"), &harness::str("x"), true, &nays) + .is_err() + ); + } + + #[test] + fn a_party_voting_twice_shows_in_the_records() { + let (tv, lass, makefu, first, current, one, two) = three(); + let root = Id::of(b"root"); + let record = |party: &Party, votes: Vec<Vec<u8>>| { + let mut record = Record::begin(root, &party.name, ¤t); + for vote in votes { + record.cast(¤t, &vote, Vec::new()); + } + record + }; + let honest = [ + record( + &lass, + vec![lass.vote(&[root], first.hash(), one.hash(), true)], + ), + record( + &makefu, + vec![makefu.vote(&[root], first.hash(), two.hash(), false)], + ), + ]; + assert!(voted_twice(&honest).is_empty()); + // tv's `true` on both, neither dead: twice. + let both = record( + &tv, + vec![ + tv.vote(&[root], first.hash(), one.hash(), true), + tv.vote(&[root], first.hash(), two.hash(), true), + ], + ); + let found = voted_twice(&[both.clone(), honest[0].clone()]); + assert_eq!(found.len(), 1); + assert_eq!((found[0].0, found[0].1.as_str()), (first.hash(), "tv")); + // Once the first is dead by the nays a client kept, it isn't. + let mut freed = both; + freed.nays = vec![ + lass.vote(&[root], first.hash(), one.hash(), false), + makefu.vote(&[root], first.hash(), one.hash(), false), + ] + .into_iter() + .map(|nay| String::from_utf8(nay).unwrap()) + .collect(); + assert!(voted_twice(&[freed]).is_empty()); + // `true` and `false` on one proposal: twice. + let flipped = record( + &tv, + vec![ + tv.vote(&[root], first.hash(), one.hash(), true), + tv.vote(&[Id::of(b"elsewhere")], first.hash(), one.hash(), false), + ], + ); + assert_eq!(voted_twice(&[flipped]).len(), 1); + } + + #[test] + fn a_party_signs_again_the_latest_of_what_a_move_refused() { + let (tv, _, _, _, current, _, _) = three(); + let root = Id::of(b"root"); + let mut record = Record::begin(root, "tv", ¤t); + let first = tv.write(&[root], "home/tv/a", harness::str("1")); + let later = tv.write(&[Id::of(&first)], "home/tv/a", harness::str("2")); + let elsewhere = tv.write(&[root], "home/tv/b", harness::str("1")); + let keys = tv.keys(&[root], &[tv.key_line()]); + for event in [&first, &later, &elsewhere, &keys] { + record.signed(event); + } + let refused: BTreeSet<Id> = [&first, &later, &keys] + .into_iter() + .map(|event| Id::of(event)) + .collect(); + let again: Vec<Id> = record + .again(|id| refused.contains(id)) + .into_iter() + .map(|(id, _)| id) + .collect(); + assert_eq!(again.len(), 2); + assert!(again.contains(&Id::of(&later)) && again.contains(&Id::of(&keys))); + } +} diff --git a/src/federation/mod.rs b/src/federation/mod.rs index f7b3d01..25f4889 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -7,6 +7,7 @@ #[cfg(test)] mod attacks; +pub(crate) mod client; pub(crate) mod event; pub(crate) mod fold; #[cfg(test)] |
