Skip to main content

codync_network/
roster.rs

1//! Who is in the network: a log of signed changes that every member keeps a copy of.
2//!
3//! Copies merge (a union of entries), and every computer works out the same members from them,
4//! whatever order the entries arrived in. Each entry is signed by the computer that made it, and
5//! it counts only if that computer could make it:
6//!
7//! - the network's **root key** (the recovery code, kept on no computer) names the owner;
8//! - the **owner** promotes admins, and admits and removes anyone;
9//! - **admins** admit computers and remove plain members;
10//! - every computer writes only where it is reachable.
11//!
12//! A removed computer stays removed: coming back means joining again with a new key.
13//!
14//! Every copy keeps only the entries that can count, so the whole log fits in the one frame a
15//! hello carries it in, whatever a stolen computer signs.
16
17use crate::wire;
18use anyhow::{Context, Result, anyhow, bail};
19use iroh::{EndpointAddr, EndpointId, SecretKey, Signature};
20use serde::{Deserialize, Serialize};
21use std::collections::{BTreeMap, BTreeSet};
22use std::path::Path;
23
24const FILE: &str = "network.json";
25/// Entries one computer may have in the log: far more changes than a network of computers makes,
26/// and few enough that the log stays well inside a frame.
27const MAX_PER_SIGNER: usize = 256;
28/// What one entry may hold, so no member can grow the log past what a hello carries.
29const MAX_ENTRY: usize = 8 * 1024;
30/// The addresses a location keeps: the relay first (`TransportAddr` orders relays before IP
31/// addresses), then the direct ones.
32const MAX_ADDRS: usize = 64;
33/// A computer's name (`node::check_name`'s 40) with the number `free_name` adds.
34const MAX_NAME: usize = 48;
35/// What a computer's name never holds: they'd break `agent@computer.network`.
36pub(crate) const NOT_IN_NAMES: [char; 4] = ['/', ' ', '@', '.'];
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
39#[serde(rename_all = "camelCase")]
40pub enum Role {
41    Member,
42    Admin,
43    Owner,
44}
45
46impl Role {
47    /// Whether a computer with this role may invite computers: the owner and admins.
48    pub fn invites(self) -> bool {
49        self >= Role::Admin
50    }
51
52    /// Whether a computer with this role may remove one with `other`: the owner removes anyone,
53    /// admins remove plain members.
54    pub fn removes(self, other: Role) -> bool {
55        self == Role::Owner || (self == Role::Admin && other == Role::Member)
56    }
57
58    /// Whether a computer with this role may make one with `other` an admin: only the owner, and
59    /// only a plain member.
60    pub fn promotes(self, other: Role) -> bool {
61        self == Role::Owner && other == Role::Member
62    }
63}
64
65/// One computer in the network, as the log has it now.
66#[derive(Clone, Debug, PartialEq, Eq)]
67pub struct Member {
68    pub name: String,
69    pub role: Role,
70    /// Where it last said it was reachable.
71    pub addr: EndpointAddr,
72}
73
74#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
75#[serde(tag = "kind", rename_all = "camelCase")]
76pub enum Change {
77    /// The root key names the owner (again, to move it to another computer).
78    Owner {
79        id: EndpointId,
80        name: String,
81    },
82    Admit {
83        id: EndpointId,
84        name: String,
85    },
86    Promote {
87        id: EndpointId,
88    },
89    /// `cascade` also voids everything the removed computer signed (a stolen one).
90    Remove {
91        id: EndpointId,
92        cascade: bool,
93    },
94    /// Where the signing computer is reachable.
95    Locate {
96        addr: EndpointAddr,
97    },
98}
99
100/// `addr` cut to the addresses a location may hold: what this computer signs, and compares with
101/// the location it signed before.
102pub fn bounded_addr(addr: EndpointAddr) -> EndpointAddr {
103    EndpointAddr::from_parts(addr.id, addr.addrs.into_iter().take(MAX_ADDRS))
104}
105
106#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
107pub struct Signed {
108    /// When it was signed (Unix ms), as its signer says.
109    pub at: u64,
110    pub by: EndpointId,
111    pub change: Change,
112    /// Hex ed25519 signature over the network, signer, time and change.
113    pub sig: String,
114}
115
116impl Signed {
117    pub fn new(network: &EndpointId, key: &SecretKey, at: u64, change: Change) -> Self {
118        let by = key.public();
119        let sig = wire::hex(&key.sign(&body(network, &by, at, &change)).to_bytes());
120        Self { at, by, change, sig }
121    }
122
123    fn verifies(&self, network: &EndpointId) -> bool {
124        let Some(Ok(bytes)) = wire::unhex(&self.sig).map(<[u8; Signature::LENGTH]>::try_from) else { return false };
125        self.by.verify(&body(network, &self.by, self.at, &self.change), &Signature::from_bytes(&bytes)).is_ok()
126    }
127}
128
129fn body(network: &EndpointId, by: &EndpointId, at: u64, change: &Change) -> Vec<u8> {
130    serde_json::to_vec(&(network, by, at, change)).expect("a change always serializes")
131}
132
133/// The network as this computer knows it.
134#[derive(Clone, Debug, Serialize, Deserialize)]
135pub struct Roster {
136    /// The network's id: its root key.
137    pub network: EndpointId,
138    log: BTreeSet<Signed>,
139    #[serde(skip)]
140    members: BTreeMap<EndpointId, Member>,
141    #[serde(skip)]
142    removed: BTreeSet<EndpointId>,
143}
144
145impl PartialEq for Roster {
146    fn eq(&self, other: &Self) -> bool {
147        self.network == other.network && self.log == other.log
148    }
149}
150
151impl Roster {
152    /// A new network with `me` as its owner. Returns it with the root key, which the caller
153    /// shows once as the recovery code and keeps nowhere.
154    pub fn create(me: &SecretKey, name: String, addr: EndpointAddr, at: u64) -> (Self, SecretKey) {
155        let root = SecretKey::generate();
156        let network = root.public();
157        let mut roster = Self { network, log: BTreeSet::new(), members: BTreeMap::new(), removed: BTreeSet::new() };
158        roster.log.insert(Signed::new(&network, &root, at, Change::Owner { id: me.public(), name }));
159        roster.log.insert(Signed::new(&network, me, at, Change::Locate { addr: bounded_addr(addr) }));
160        roster.rebuild();
161        (roster, root)
162    }
163
164    /// Signs `change` as `key` and adds it, if `key` may make it.
165    pub fn sign(&mut self, key: &SecretKey, at: u64, change: Change) -> Result<()> {
166        let entry = Signed::new(&self.network, key, at, change);
167        let before = self.clone();
168        self.log.insert(entry);
169        self.rebuild();
170        if self.members == before.members && self.removed == before.removed {
171            *self = before;
172            bail!("this computer isn't allowed to make that change");
173        }
174        Ok(())
175    }
176
177    pub fn members(&self) -> &BTreeMap<EndpointId, Member> {
178        &self.members
179    }
180
181    pub fn is_member(&self, id: &EndpointId) -> bool {
182        self.members.contains_key(id)
183    }
184
185    pub fn is_removed(&self, id: &EndpointId) -> bool {
186        self.removed.contains(id)
187    }
188
189    pub fn role(&self, id: &EndpointId) -> Option<Role> {
190        self.members.get(id).map(|m| m.role)
191    }
192
193    /// The member called `name`, or whose id starts with it.
194    pub fn find(&self, name: &str) -> Option<EndpointId> {
195        let name = name.trim();
196        self.members
197            .iter()
198            .find(|(_, m)| m.name.eq_ignore_ascii_case(name))
199            .or_else(|| self.members.iter().find(|(id, _)| name.len() >= 6 && id.to_string().starts_with(name)))
200            .map(|(id, _)| *id)
201    }
202
203    pub fn name(&self, id: &EndpointId) -> String {
204        self.members.get(id).map_or_else(|| id.fmt_short().to_string(), |m| m.name.clone())
205    }
206
207    /// `name`, or the first of `name-2`, `name-3`… no other computer has.
208    pub fn free_name(&self, name: &str, for_id: &EndpointId) -> String {
209        let taken = |n: &str| self.find(n).is_some_and(|id| id != *for_id);
210        if !taken(name) {
211            return name.into();
212        }
213        // One more number than there are members: one of them is free.
214        (2..=self.members.len() + 2).map(|n| format!("{name}-{n}")).find(|n| !taken(n)).expect("a number is free")
215    }
216
217    /// Takes in another member's copy: the entries that verify. Returns whether anything changed.
218    pub fn merge(&mut self, other: &Roster) -> bool {
219        if other.network != self.network {
220            return false;
221        }
222        let new: Vec<Signed> =
223            other.log.iter().filter(|e| !self.log.contains(e) && e.verifies(&self.network)).cloned().collect();
224        if new.is_empty() {
225            return false;
226        }
227        let before = self.log.clone();
228        self.log.extend(new);
229        self.rebuild();
230        self.log != before
231    }
232
233    /// Works out the members from the log, then drops the entries that can't count.
234    fn rebuild(&mut self) {
235        let known = self.count();
236        if self.compact(&known) {
237            self.count();
238        }
239    }
240
241    /// Drops what can't count, so the log stays small enough to send whole: entries out of bounds,
242    /// entries by computers the log never let in, changes to who is in by computers that may not
243    /// make them, all but each computer's newest location (and none of a removed one's), and
244    /// whatever a computer signed past its share. Returns whether anything went.
245    fn compact(&mut self, known: &Known) -> bool {
246        let before = self.log.len();
247        self.log.retain(bounded);
248        let newest = newest_locations(&self.log);
249        let mut share: BTreeMap<EndpointId, usize> = BTreeMap::new();
250        let kept: BTreeSet<Signed> = self
251            .log
252            .iter()
253            .filter(|s| {
254                let counts = known.signers.contains(&s.by)
255                    && match &s.change {
256                        Change::Owner { .. } => s.by == self.network,
257                        Change::Locate { .. } => {
258                            !self.removed.contains(&s.by) && newest.get(&s.by).is_some_and(|(n, _)| *n == *s)
259                        }
260                        _ => known.deciders.contains(&s.by),
261                    };
262                let n = share.entry(s.by).or_default();
263                *n += usize::from(counts);
264                counts && *n <= MAX_PER_SIGNER
265            })
266            .cloned()
267            .collect();
268        let changed = kept.len() != before;
269        self.log = kept;
270        changed
271    }
272
273    /// Works out the members from the log. Who may sign what depends only on entries from above
274    /// (the root, then the owners, latest first, then admins), so the result doesn't depend on
275    /// arrival order. Returns who may have entries in the log.
276    fn count(&mut self) -> Known {
277        let root = self.network;
278        let log: Vec<&Signed> = self.log.iter().collect();
279        // Owners in turn, each from the time the root named it.
280        let mut owners: Vec<(u64, EndpointId, String)> = log
281            .iter()
282            .filter(|s| s.by == root)
283            .filter_map(|s| match &s.change {
284                Change::Owner { id, name } => Some((s.at, *id, name.clone())),
285                _ => None,
286            })
287            .collect();
288        owners.sort();
289        let owner_at = |at: u64| owners.iter().rev().find(|(from, ..)| *from <= at).map(|(_, id, _)| *id);
290        let top = |by: &EndpointId, at: u64| *by == root || owner_at(at) == Some(*by);
291        let owner = owners.last().map(|(_, id, _)| *id);
292
293        // Removals by the top: the root's, then each owner's from the latest named back. An owner
294        // that one above it removed with `cascade` (a stolen one) removes nobody, whatever time it
295        // signs with, and only the root removes the current owner.
296        let mut above = vec![root];
297        for (_, id, _) in owners.iter().rev() {
298            if !above.contains(id) {
299                above.push(*id);
300            }
301        }
302        let mut top_removed: BTreeMap<EndpointId, (u64, bool)> = BTreeMap::new();
303        for by in &above {
304            if top_removed.get(by).is_some_and(|&(_, cascade)| cascade) {
305                continue;
306            }
307            for s in log.iter().filter(|s| s.by == *by && top(&s.by, s.at)) {
308                if let Change::Remove { id, cascade } = &s.change
309                    && (s.by == root || (Some(*id) != owner_at(s.at) && Some(*id) != owner))
310                {
311                    note_removal(&mut top_removed, *id, s.at, *cascade);
312                }
313            }
314        }
315        let top_voided = |by: &EndpointId| top_removed.get(by).is_some_and(|&(_, cascade)| cascade);
316        let mut promoted: BTreeMap<EndpointId, u64> = BTreeMap::new();
317        for s in &log {
318            if let Change::Promote { id } = &s.change
319                && top(&s.by, s.at)
320                && !top_voided(&s.by)
321            {
322                let at = promoted.entry(*id).or_insert(s.at);
323                *at = (*at).min(s.at);
324            }
325        }
326        // Admins, within the time span they could sign in.
327        let admin_at = |id: &EndpointId, at: u64| {
328            promoted.get(id).is_some_and(|&from| {
329                from <= at && top_removed.get(id).is_none_or(|&(until, cascade)| !cascade && at < until)
330            })
331        };
332        let mut removed = top_removed.clone();
333        for s in &log {
334            if let Change::Remove { id, cascade } = &s.change
335                && admin_at(&s.by, s.at)
336                && Some(*id) != owner_at(s.at)
337                && !promoted.contains_key(id)
338                && !top_removed.contains_key(id)
339            {
340                note_removal(&mut removed, *id, s.at, *cascade);
341            }
342        }
343        // A cascade-removed computer voids what it admitted, too.
344        let voided = |by: &EndpointId| removed.get(by).is_some_and(|&(_, cascade)| cascade);
345        let may_admit = |s: &Signed| !voided(&s.by) && (top(&s.by, s.at) || admin_at(&s.by, s.at));
346
347        // Each computer with the time it got in and the name it got in with.
348        let mut admitted: BTreeMap<EndpointId, (u64, String)> = BTreeMap::new();
349        for (at, id, name) in &owners {
350            admitted.entry(*id).or_insert_with(|| (*at, name.clone()));
351        }
352        for s in &log {
353            if let Change::Admit { id, name } = &s.change
354                && may_admit(s)
355            {
356                let first = admitted.entry(*id).or_insert_with(|| (s.at, name.clone()));
357                if s.at < first.0 {
358                    *first = (s.at, name.clone());
359                }
360            }
361        }
362        let addrs = newest_locations(&self.log);
363        let tops = std::iter::once(root).chain(owners.iter().map(|(_, id, _)| *id));
364        let known = Known {
365            signers: tops.clone().chain(admitted.keys().copied()).collect(),
366            deciders: tops.chain(promoted.keys().copied()).collect(),
367        };
368        self.removed = removed.keys().copied().collect();
369        let removed_at: BTreeMap<EndpointId, u64> = removed.iter().map(|(id, &(at, _))| (*id, at)).collect();
370        self.members = distinct_names(admitted, &removed_at)
371            .into_iter()
372            .filter(|(id, _)| !self.removed.contains(id))
373            .map(|(id, name)| {
374                let role = if Some(id) == owner {
375                    Role::Owner
376                } else if admin_at(&id, u64::MAX) {
377                    Role::Admin
378                } else {
379                    Role::Member
380                };
381                let addr = addrs.get(&id).map_or_else(|| EndpointAddr::new(id), |(_, a)| (*a).clone());
382                (id, Member { name, role, addr })
383            })
384            .collect();
385        known
386    }
387
388    /// A copy that came from disk or another computer: only the entries that verify count.
389    #[must_use]
390    pub fn verified(mut self) -> Self {
391        let network = self.network;
392        self.log.retain(|s| s.verifies(&network));
393        self.rebuild();
394        self
395    }
396
397    pub fn load(dir: &Path) -> Result<Option<Self>> {
398        match std::fs::read(dir.join(FILE)) {
399            Ok(bytes) => {
400                let roster: Self = serde_json::from_slice(&bytes).context("network.json is damaged")?;
401                Ok(Some(roster.verified()))
402            }
403            Err(e) if e.kind() == std::io::ErrorKind::NotFound => Ok(None),
404            Err(e) => Err(e).context("couldn't read network.json"),
405        }
406    }
407
408    pub fn save(&self, dir: &Path) -> Result<()> {
409        let tmp = dir.join(format!("{FILE}.tmp"));
410        std::fs::write(&tmp, serde_json::to_vec_pretty(self)?)?;
411        std::fs::rename(&tmp, dir.join(FILE)).context("couldn't save network.json")
412    }
413}
414
415/// Who may have entries in the log.
416struct Known {
417    /// The root, the owners and every computer the log let in (removed ones too).
418    signers: BTreeSet<EndpointId>,
419    /// Those that may change who is in: the root, the owners and the admins.
420    deciders: BTreeSet<EndpointId>,
421}
422
423/// Whether an entry is within bounds: a name a computer may have, a location's few addresses, and
424/// a few KiB in all. Anything past them can't count, whoever signed it.
425fn bounded(s: &Signed) -> bool {
426    let fits = match &s.change {
427        Change::Owner { name, .. } | Change::Admit { name, .. } => {
428            !name.is_empty() && name.len() <= MAX_NAME && !name.contains(NOT_IN_NAMES)
429        }
430        Change::Locate { addr } => addr.addrs.len() <= MAX_ADDRS,
431        Change::Promote { .. } | Change::Remove { .. } => true,
432    };
433    fits && serde_json::to_vec(s).is_ok_and(|bytes| bytes.len() <= MAX_ENTRY)
434}
435
436/// Where each computer last said it is reachable: the entry and the address. Only that one counts.
437fn newest_locations(log: &BTreeSet<Signed>) -> BTreeMap<EndpointId, (&Signed, &EndpointAddr)> {
438    let mut newest: BTreeMap<EndpointId, (&Signed, &EndpointAddr)> = BTreeMap::new();
439    for s in log {
440        if let Change::Locate { addr } = &s.change
441            && addr.id == s.by
442            && newest.get(&s.by).is_none_or(|(n, _)| s.at > n.at)
443        {
444            newest.insert(s.by, (s, addr));
445        }
446    }
447    newest
448}
449
450/// Names every computer uniquely. Two admins can admit a `laptop` each before their copies meet:
451/// the one admitted later (by time, then id) gets the first free number, the same on every copy. A
452/// removed computer keeps its name from the computers admitted while it was in, so no one's name
453/// moves when it goes (letters on their way still name them); one admitted after can take it.
454fn distinct_names(
455    admitted: BTreeMap<EndpointId, (u64, String)>,
456    removed_at: &BTreeMap<EndpointId, u64>,
457) -> BTreeMap<EndpointId, String> {
458    let mut order: Vec<(u64, EndpointId, String)> =
459        admitted.into_iter().map(|(id, (at, name))| (at, id, name)).collect();
460    order.sort();
461    // Each name given, and until when it is held: for good, or until its computer was removed.
462    let mut held: BTreeMap<String, Option<u64>> = BTreeMap::new();
463    let mut names = BTreeMap::new();
464    for (at, id, name) in order {
465        let free = |n: &str| held.get(&n.to_lowercase()).is_none_or(|until| until.is_some_and(|t| t < at));
466        let unique = std::iter::once(name.clone())
467            // One more number than there are names: one of them is free.
468            .chain((2..=held.len() + 2).map(|n| format!("{name}-{n}")))
469            .find(|n| free(n))
470            .expect("a number is free");
471        held.insert(unique.to_lowercase(), removed_at.get(&id).copied());
472        names.insert(id, unique);
473    }
474    names
475}
476
477/// Notes that `id` was removed at `at`: the earliest removal counts, and a cascade from any.
478fn note_removal(removed: &mut BTreeMap<EndpointId, (u64, bool)>, id: EndpointId, at: u64, cascade: bool) {
479    let e = removed.entry(id).or_insert((at, cascade));
480    *e = (e.0.min(at), e.1 || cascade);
481}
482
483/// The recovery code for a root key, and back.
484pub fn recovery_code(root: &SecretKey) -> String {
485    let hex = wire::hex(&root.to_bytes());
486    hex.as_bytes().chunks(8).map(|c| String::from_utf8_lossy(c).into_owned()).collect::<Vec<_>>().join("-")
487}
488
489pub fn root_from_code(code: &str) -> Result<SecretKey> {
490    let hex: String = code.chars().filter(char::is_ascii_hexdigit).collect();
491    let bytes: [u8; 32] = wire::unhex(&hex)
492        .and_then(|b| b.try_into().ok())
493        .ok_or_else(|| anyhow!("a recovery code is 64 hex characters"))?;
494    Ok(SecretKey::from_bytes(&bytes))
495}
496
497#[cfg(test)]
498mod tests;