//! 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 { 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 { 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 { fn convert(value: &serde_json::Value) -> Result { 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::>()?) } serde_json::Value::Object(members) => Json::object( members .iter() .map(|(name, value)| Ok((name.clone(), convert(value)?))) .collect::>()?, ) .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, /// The votes it cast, each as signed. #[serde(default)] pub(crate) votes: Vec, /// 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, /// The events it signed but votes, each as signed, oldest first. #[serde(default)] pub(crate) signed: Vec, } /// 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 { 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]) -> bool { let no: BTreeSet = 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 { 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 { 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], ) -> Result>, 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>) { 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 = 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 = 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 = 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> = 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 = 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>| { 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 = [&first, &later, &keys] .into_iter() .map(|event| Id::of(event)) .collect(); let again: Vec = 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))); } }