diff options
Diffstat (limited to 'src')
| -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)] |
