codync-network 0.3.0

Agent Tailscale: the agents on your computers find and message each other, peer to peer
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
//! Who is in the network: a log of signed changes that every member keeps a copy of.
//!
//! Copies merge (a union of entries), and every computer works out the same members from them,
//! whatever order the entries arrived in. Each entry is signed by the computer that made it, and
//! it counts only if that computer could make it:
//!
//! - the network's **root key** (the recovery code, kept on no computer) names the owner;
//! - the **owner** promotes admins, and admits and removes anyone;
//! - **admins** admit computers and remove plain members;
//! - every computer writes only where it is reachable.
//!
//! A removed computer stays removed: coming back means joining again with a new key.
//!
//! Every copy keeps only the entries that can count, so the whole log fits in the one frame a
//! hello carries it in, whatever a stolen computer signs.

use crate::wire;
use anyhow::{Context, Result, anyhow, bail};
use iroh::{EndpointAddr, EndpointId, SecretKey, Signature};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet};
use std::path::Path;

const FILE: &str = "network.json";
/// Entries one computer may have in the log: far more changes than a network of computers makes,
/// and few enough that the log stays well inside a frame.
const MAX_PER_SIGNER: usize = 256;
/// What one entry may hold, so no member can grow the log past what a hello carries.
const MAX_ENTRY: usize = 8 * 1024;
/// The addresses a location keeps: the relay first (`TransportAddr` orders relays before IP
/// addresses), then the direct ones.
const MAX_ADDRS: usize = 64;
/// A computer's name (`node::check_name`'s 40) with the number `free_name` adds.
const MAX_NAME: usize = 48;
/// What a computer's name never holds: they'd break `agent@computer.network`.
pub(crate) const NOT_IN_NAMES: [char; 4] = ['/', ' ', '@', '.'];

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub enum Role {
    Member,
    Admin,
    Owner,
}

impl Role {
    /// Whether a computer with this role may invite computers: the owner and admins.
    pub fn invites(self) -> bool {
        self >= Role::Admin
    }

    /// Whether a computer with this role may remove one with `other`: the owner removes anyone,
    /// admins remove plain members.
    pub fn removes(self, other: Role) -> bool {
        self == Role::Owner || (self == Role::Admin && other == Role::Member)
    }

    /// Whether a computer with this role may make one with `other` an admin: only the owner, and
    /// only a plain member.
    pub fn promotes(self, other: Role) -> bool {
        self == Role::Owner && other == Role::Member
    }
}

/// One computer in the network, as the log has it now.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Member {
    pub name: String,
    pub role: Role,
    /// Where it last said it was reachable.
    pub addr: EndpointAddr,
}

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(tag = "kind", rename_all = "camelCase")]
pub enum Change {
    /// The root key names the owner (again, to move it to another computer).
    Owner {
        id: EndpointId,
        name: String,
    },
    Admit {
        id: EndpointId,
        name: String,
    },
    Promote {
        id: EndpointId,
    },
    /// `cascade` also voids everything the removed computer signed (a stolen one).
    Remove {
        id: EndpointId,
        cascade: bool,
    },
    /// Where the signing computer is reachable.
    Locate {
        addr: EndpointAddr,
    },
}

/// `addr` cut to the addresses a location may hold: what this computer signs, and compares with
/// the location it signed before.
pub fn bounded_addr(addr: EndpointAddr) -> EndpointAddr {
    EndpointAddr::from_parts(addr.id, addr.addrs.into_iter().take(MAX_ADDRS))
}

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct Signed {
    /// When it was signed (Unix ms), as its signer says.
    pub at: u64,
    pub by: EndpointId,
    pub change: Change,
    /// Hex ed25519 signature over the network, signer, time and change.
    pub sig: String,
}

impl Signed {
    pub fn new(network: &EndpointId, key: &SecretKey, at: u64, change: Change) -> Self {
        let by = key.public();
        let sig = wire::hex(&key.sign(&body(network, &by, at, &change)).to_bytes());
        Self { at, by, change, sig }
    }

    fn verifies(&self, network: &EndpointId) -> bool {
        let Some(Ok(bytes)) = wire::unhex(&self.sig).map(<[u8; Signature::LENGTH]>::try_from) else { return false };
        self.by.verify(&body(network, &self.by, self.at, &self.change), &Signature::from_bytes(&bytes)).is_ok()
    }
}

fn body(network: &EndpointId, by: &EndpointId, at: u64, change: &Change) -> Vec<u8> {
    serde_json::to_vec(&(network, by, at, change)).expect("a change always serializes")
}

/// The network as this computer knows it.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct Roster {
    /// The network's id: its root key.
    pub network: EndpointId,
    log: BTreeSet<Signed>,
    #[serde(skip)]
    members: BTreeMap<EndpointId, Member>,
    #[serde(skip)]
    removed: BTreeSet<EndpointId>,
}

impl PartialEq for Roster {
    fn eq(&self, other: &Self) -> bool {
        self.network == other.network && self.log == other.log
    }
}

impl Roster {
    /// A new network with `me` as its owner. Returns it with the root key, which the caller
    /// shows once as the recovery code and keeps nowhere.
    pub fn create(me: &SecretKey, name: String, addr: EndpointAddr, at: u64) -> (Self, SecretKey) {
        let root = SecretKey::generate();
        let network = root.public();
        let mut roster = Self { network, log: BTreeSet::new(), members: BTreeMap::new(), removed: BTreeSet::new() };
        roster.log.insert(Signed::new(&network, &root, at, Change::Owner { id: me.public(), name }));
        roster.log.insert(Signed::new(&network, me, at, Change::Locate { addr: bounded_addr(addr) }));
        roster.rebuild();
        (roster, root)
    }

    /// Signs `change` as `key` and adds it, if `key` may make it.
    pub fn sign(&mut self, key: &SecretKey, at: u64, change: Change) -> Result<()> {
        let entry = Signed::new(&self.network, key, at, change);
        let before = self.clone();
        self.log.insert(entry);
        self.rebuild();
        if self.members == before.members && self.removed == before.removed {
            *self = before;
            bail!("this computer isn't allowed to make that change");
        }
        Ok(())
    }

    pub fn members(&self) -> &BTreeMap<EndpointId, Member> {
        &self.members
    }

    pub fn is_member(&self, id: &EndpointId) -> bool {
        self.members.contains_key(id)
    }

    pub fn is_removed(&self, id: &EndpointId) -> bool {
        self.removed.contains(id)
    }

    pub fn role(&self, id: &EndpointId) -> Option<Role> {
        self.members.get(id).map(|m| m.role)
    }

    /// The member called `name`, or whose id starts with it.
    pub fn find(&self, name: &str) -> Option<EndpointId> {
        let name = name.trim();
        self.members
            .iter()
            .find(|(_, m)| m.name.eq_ignore_ascii_case(name))
            .or_else(|| self.members.iter().find(|(id, _)| name.len() >= 6 && id.to_string().starts_with(name)))
            .map(|(id, _)| *id)
    }

    pub fn name(&self, id: &EndpointId) -> String {
        self.members.get(id).map_or_else(|| id.fmt_short().to_string(), |m| m.name.clone())
    }

    /// `name`, or the first of `name-2`, `name-3`… no other computer has.
    pub fn free_name(&self, name: &str, for_id: &EndpointId) -> String {
        let taken = |n: &str| self.find(n).is_some_and(|id| id != *for_id);
        if !taken(name) {
            return name.into();
        }
        // One more number than there are members: one of them is free.
        (2..=self.members.len() + 2).map(|n| format!("{name}-{n}")).find(|n| !taken(n)).expect("a number is free")
    }

    /// Takes in another member's copy: the entries that verify. Returns whether anything changed.
    pub fn merge(&mut self, other: &Roster) -> bool {
        if other.network != self.network {
            return false;
        }
        let new: Vec<Signed> =
            other.log.iter().filter(|e| !self.log.contains(e) && e.verifies(&self.network)).cloned().collect();
        if new.is_empty() {
            return false;
        }
        let before = self.log.clone();
        self.log.extend(new);
        self.rebuild();
        self.log != before
    }

    /// Works out the members from the log, then drops the entries that can't count.
    fn rebuild(&mut self) {
        let known = self.count();
        if self.compact(&known) {
            self.count();
        }
    }

    /// Drops what can't count, so the log stays small enough to send whole: entries out of bounds,
    /// entries by computers the log never let in, changes to who is in by computers that may not
    /// make them, all but each computer's newest location (and none of a removed one's), and
    /// whatever a computer signed past its share. Returns whether anything went.
    fn compact(&mut self, known: &Known) -> bool {
        let before = self.log.len();
        self.log.retain(bounded);
        let newest = newest_locations(&self.log);
        let mut share: BTreeMap<EndpointId, usize> = BTreeMap::new();
        let kept: BTreeSet<Signed> = self
            .log
            .iter()
            .filter(|s| {
                let counts = known.signers.contains(&s.by)
                    && match &s.change {
                        Change::Owner { .. } => s.by == self.network,
                        Change::Locate { .. } => {
                            !self.removed.contains(&s.by) && newest.get(&s.by).is_some_and(|(n, _)| *n == *s)
                        }
                        _ => known.deciders.contains(&s.by),
                    };
                let n = share.entry(s.by).or_default();
                *n += usize::from(counts);
                counts && *n <= MAX_PER_SIGNER
            })
            .cloned()
            .collect();
        let changed = kept.len() != before;
        self.log = kept;
        changed
    }

    /// Works out the members from the log. Who may sign what depends only on entries from above
    /// (the root, then the owners, latest first, then admins), so the result doesn't depend on
    /// arrival order. Returns who may have entries in the log.
    fn count(&mut self) -> Known {
        let root = self.network;
        let log: Vec<&Signed> = self.log.iter().collect();
        // Owners in turn, each from the time the root named it.
        let mut owners: Vec<(u64, EndpointId, String)> = log
            .iter()
            .filter(|s| s.by == root)
            .filter_map(|s| match &s.change {
                Change::Owner { id, name } => Some((s.at, *id, name.clone())),
                _ => None,
            })
            .collect();
        owners.sort();
        let owner_at = |at: u64| owners.iter().rev().find(|(from, ..)| *from <= at).map(|(_, id, _)| *id);
        let top = |by: &EndpointId, at: u64| *by == root || owner_at(at) == Some(*by);
        let owner = owners.last().map(|(_, id, _)| *id);

        // Removals by the top: the root's, then each owner's from the latest named back. An owner
        // that one above it removed with `cascade` (a stolen one) removes nobody, whatever time it
        // signs with, and only the root removes the current owner.
        let mut above = vec![root];
        for (_, id, _) in owners.iter().rev() {
            if !above.contains(id) {
                above.push(*id);
            }
        }
        let mut top_removed: BTreeMap<EndpointId, (u64, bool)> = BTreeMap::new();
        for by in &above {
            if top_removed.get(by).is_some_and(|&(_, cascade)| cascade) {
                continue;
            }
            for s in log.iter().filter(|s| s.by == *by && top(&s.by, s.at)) {
                if let Change::Remove { id, cascade } = &s.change
                    && (s.by == root || (Some(*id) != owner_at(s.at) && Some(*id) != owner))
                {
                    note_removal(&mut top_removed, *id, s.at, *cascade);
                }
            }
        }
        let top_voided = |by: &EndpointId| top_removed.get(by).is_some_and(|&(_, cascade)| cascade);
        let mut promoted: BTreeMap<EndpointId, u64> = BTreeMap::new();
        for s in &log {
            if let Change::Promote { id } = &s.change
                && top(&s.by, s.at)
                && !top_voided(&s.by)
            {
                let at = promoted.entry(*id).or_insert(s.at);
                *at = (*at).min(s.at);
            }
        }
        // Admins, within the time span they could sign in.
        let admin_at = |id: &EndpointId, at: u64| {
            promoted.get(id).is_some_and(|&from| {
                from <= at && top_removed.get(id).is_none_or(|&(until, cascade)| !cascade && at < until)
            })
        };
        let mut removed = top_removed.clone();
        for s in &log {
            if let Change::Remove { id, cascade } = &s.change
                && admin_at(&s.by, s.at)
                && Some(*id) != owner_at(s.at)
                && !promoted.contains_key(id)
                && !top_removed.contains_key(id)
            {
                note_removal(&mut removed, *id, s.at, *cascade);
            }
        }
        // A cascade-removed computer voids what it admitted, too.
        let voided = |by: &EndpointId| removed.get(by).is_some_and(|&(_, cascade)| cascade);
        let may_admit = |s: &Signed| !voided(&s.by) && (top(&s.by, s.at) || admin_at(&s.by, s.at));

        // Each computer with the time it got in and the name it got in with.
        let mut admitted: BTreeMap<EndpointId, (u64, String)> = BTreeMap::new();
        for (at, id, name) in &owners {
            admitted.entry(*id).or_insert_with(|| (*at, name.clone()));
        }
        for s in &log {
            if let Change::Admit { id, name } = &s.change
                && may_admit(s)
            {
                let first = admitted.entry(*id).or_insert_with(|| (s.at, name.clone()));
                if s.at < first.0 {
                    *first = (s.at, name.clone());
                }
            }
        }
        let addrs = newest_locations(&self.log);
        let tops = std::iter::once(root).chain(owners.iter().map(|(_, id, _)| *id));
        let known = Known {
            signers: tops.clone().chain(admitted.keys().copied()).collect(),
            deciders: tops.chain(promoted.keys().copied()).collect(),
        };
        self.removed = removed.keys().copied().collect();
        let removed_at: BTreeMap<EndpointId, u64> = removed.iter().map(|(id, &(at, _))| (*id, at)).collect();
        self.members = distinct_names(admitted, &removed_at)
            .into_iter()
            .filter(|(id, _)| !self.removed.contains(id))
            .map(|(id, name)| {
                let role = if Some(id) == owner {
                    Role::Owner
                } else if admin_at(&id, u64::MAX) {
                    Role::Admin
                } else {
                    Role::Member
                };
                let addr = addrs.get(&id).map_or_else(|| EndpointAddr::new(id), |(_, a)| (*a).clone());
                (id, Member { name, role, addr })
            })
            .collect();
        known
    }

    /// A copy that came from disk or another computer: only the entries that verify count.
    #[must_use]
    pub fn verified(mut self) -> Self {
        let network = self.network;
        self.log.retain(|s| s.verifies(&network));
        self.rebuild();
        self
    }

    pub fn load(dir: &Path) -> Result<Option<Self>> {
        match std::fs::read(dir.join(FILE)) {
            Ok(bytes) => {
                let roster: Self = serde_json::from_slice(&bytes).context("network.json is damaged")?;
                Ok(Some(roster.verified()))
            }
            Err(e) if e.kind() == std::io::ErrorKind::NotFound => Ok(None),
            Err(e) => Err(e).context("couldn't read network.json"),
        }
    }

    pub fn save(&self, dir: &Path) -> Result<()> {
        let tmp = dir.join(format!("{FILE}.tmp"));
        std::fs::write(&tmp, serde_json::to_vec_pretty(self)?)?;
        std::fs::rename(&tmp, dir.join(FILE)).context("couldn't save network.json")
    }
}

/// Who may have entries in the log.
struct Known {
    /// The root, the owners and every computer the log let in (removed ones too).
    signers: BTreeSet<EndpointId>,
    /// Those that may change who is in: the root, the owners and the admins.
    deciders: BTreeSet<EndpointId>,
}

/// Whether an entry is within bounds: a name a computer may have, a location's few addresses, and
/// a few KiB in all. Anything past them can't count, whoever signed it.
fn bounded(s: &Signed) -> bool {
    let fits = match &s.change {
        Change::Owner { name, .. } | Change::Admit { name, .. } => {
            !name.is_empty() && name.len() <= MAX_NAME && !name.contains(NOT_IN_NAMES)
        }
        Change::Locate { addr } => addr.addrs.len() <= MAX_ADDRS,
        Change::Promote { .. } | Change::Remove { .. } => true,
    };
    fits && serde_json::to_vec(s).is_ok_and(|bytes| bytes.len() <= MAX_ENTRY)
}

/// Where each computer last said it is reachable: the entry and the address. Only that one counts.
fn newest_locations(log: &BTreeSet<Signed>) -> BTreeMap<EndpointId, (&Signed, &EndpointAddr)> {
    let mut newest: BTreeMap<EndpointId, (&Signed, &EndpointAddr)> = BTreeMap::new();
    for s in log {
        if let Change::Locate { addr } = &s.change
            && addr.id == s.by
            && newest.get(&s.by).is_none_or(|(n, _)| s.at > n.at)
        {
            newest.insert(s.by, (s, addr));
        }
    }
    newest
}

/// Names every computer uniquely. Two admins can admit a `laptop` each before their copies meet:
/// the one admitted later (by time, then id) gets the first free number, the same on every copy. A
/// removed computer keeps its name from the computers admitted while it was in, so no one's name
/// moves when it goes (letters on their way still name them); one admitted after can take it.
fn distinct_names(
    admitted: BTreeMap<EndpointId, (u64, String)>,
    removed_at: &BTreeMap<EndpointId, u64>,
) -> BTreeMap<EndpointId, String> {
    let mut order: Vec<(u64, EndpointId, String)> =
        admitted.into_iter().map(|(id, (at, name))| (at, id, name)).collect();
    order.sort();
    // Each name given, and until when it is held: for good, or until its computer was removed.
    let mut held: BTreeMap<String, Option<u64>> = BTreeMap::new();
    let mut names = BTreeMap::new();
    for (at, id, name) in order {
        let free = |n: &str| held.get(&n.to_lowercase()).is_none_or(|until| until.is_some_and(|t| t < at));
        let unique = std::iter::once(name.clone())
            // One more number than there are names: one of them is free.
            .chain((2..=held.len() + 2).map(|n| format!("{name}-{n}")))
            .find(|n| free(n))
            .expect("a number is free");
        held.insert(unique.to_lowercase(), removed_at.get(&id).copied());
        names.insert(id, unique);
    }
    names
}

/// Notes that `id` was removed at `at`: the earliest removal counts, and a cascade from any.
fn note_removal(removed: &mut BTreeMap<EndpointId, (u64, bool)>, id: EndpointId, at: u64, cascade: bool) {
    let e = removed.entry(id).or_insert((at, cascade));
    *e = (e.0.min(at), e.1 || cascade);
}

/// The recovery code for a root key, and back.
pub fn recovery_code(root: &SecretKey) -> String {
    let hex = wire::hex(&root.to_bytes());
    hex.as_bytes().chunks(8).map(|c| String::from_utf8_lossy(c).into_owned()).collect::<Vec<_>>().join("-")
}

pub fn root_from_code(code: &str) -> Result<SecretKey> {
    let hex: String = code.chars().filter(char::is_ascii_hexdigit).collect();
    let bytes: [u8; 32] = wire::unhex(&hex)
        .and_then(|b| b.try_into().ok())
        .ok_or_else(|| anyhow!("a recovery code is 64 hex characters"))?;
    Ok(SecretKey::from_bytes(&bytes))
}

#[cfg(test)]
mod tests;