OXYGENHUB
◆ v0.9.0 oxygen / crates / oxy-core / src / tlog.rs
55.0 KiB · Rust · last changed Trusted time: judge a fetched attestation at its integrated time 17 days ago source blame history raw
1 
//! The transparency log (spec §14.8, oxygenhub#238, oxygenhub
2 
//! docs/transparency.md): an append-only Merkle tree of what a hub
3 
//! accepts, served as C2SP tlog-tiles with C2SP signed-note checkpoints,
4 
//! so a hub cannot show one history to some and another to others.
5 
//!
6 
//! The tree is RFC 6962's, with BLAKE3 for its hashes, domain-separated
7 
//! for leaves and nodes. Hashes are kept in *stored order*: every hash of
8 
//! the tree, each written as soon as it is known, so the store is
9 
//! append-only (the arithmetic is that of Go's `sumdb/tlog`). Tiles are
10 
//! views of it: level L tile N holds the hashes of tree level 8·L for
11 
//! leaves N·256 onwards.
12 
//!
13 
//! A checkpoint is a signed note: the origin, the tree size and the root,
14 
//! signed with the hub's Ed25519 key (what note tools read) and with its
15 
//! composite key in an extra line, so the log stays post-quantum.
16
17 
use crate::cbor::{self, Value};
18 
use crate::hash::{KeyId, ObjectRef};
19 
use crate::identity::{verify, Domain, Identity, SecretKey, Signature};
20 
use crate::objects::{array, bytes, check_version, field, map, oref, text, uint, ObjectError};
21 
use sha2::{Digest, Sha256};
22
23 
/// A hash in the tree.
24 
pub type Hash = [u8; 32];
25
26 
/// Tile height: a tile holds up to 2⁸ hashes (C2SP tlog-tiles).
27 
pub const TILE_HEIGHT: u32 = 8;
28 
/// Hashes in a full tile.
29 
pub const TILE_WIDTH: u64 = 1 << TILE_HEIGHT;
30
31 
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
32 
pub enum TlogError {
33 
    #[error("the proof does not verify")]
34 
    ProofFailed,
35 
    #[error("{0}")]
36 
    BadIndex(String),
37 
    #[error("reading the log's hashes: {0}")]
38 
    Read(String),
39 
    #[error("not a valid note: {0}")]
40 
    BadNote(String),
41 
    #[error("{0}")]
42 
    BadSignature(String),
43 
    #[error("{0}")]
44 
    Schema(String),
45 
}
46
47 
impl From<ObjectError> for TlogError {
48 
    fn from(e: ObjectError) -> Self {
49 
        TlogError::Schema(e.to_string())
50 
    }
51 
}
52
53 
type Result<T> = std::result::Result<T, TlogError>;
54
55 
// ------------------------------------------------------------- hashing
56
57 
/// A leaf's hash: `BLAKE3("oxygen-tlog-leaf\0" || entry bytes)`.
58 
pub fn leaf_hash(entry: &[u8]) -> Hash {
59 
    let mut h = blake3::Hasher::new();
60 
    h.update(b"oxygen-tlog-leaf\0");
61 
    h.update(entry);
62 
    *h.finalize().as_bytes()
63 
}
64
65 
/// An interior node's hash: `BLAKE3("oxygen-tlog-node\0" || left || right)`.
66 
pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
67 
    let mut h = blake3::Hasher::new();
68 
    h.update(b"oxygen-tlog-node\0");
69 
    h.update(left);
70 
    h.update(right);
71 
    *h.finalize().as_bytes()
72 
}
73
74 
/// The root of the empty tree: the hash of nothing, as RFC 6962 has it.
75 
pub fn empty_root() -> Hash {
76 
    *blake3::hash(b"").as_bytes()
77 
}
78
79 
// --------------------------------------------------------------- entries
80
81 
/// One accepted object (spec §14.8): small and fixed-shape, never the
82 
/// object itself, so a private repository's entries reveal only ids and
83 
/// hashes.
84 
#[derive(Clone, Debug, PartialEq, Eq)]
85 
pub struct Entry {
86 
    /// `ref`, `seal`, `tag`, `rotate`, `revoke`, `receipt`, `approval`,
87 
    /// `policy`, `identity`, `certificate`, `accepted`.
88 
    pub kind: String,
89 
    /// The repository's id; zero for identities.
90 
    pub repo: [u8; 16],
91 
    /// The attestation, policy, identity or certificate.
92 
    pub object: ObjectRef,
93 
    /// The keys whose signatures were checked.
94 
    pub signers: Vec<KeyId>,
95 
    /// The hub's clock when it accepted it, in milliseconds (its claim).
96 
    pub received: u64,
97 
}
98
99 
impl Entry {
100 
    pub fn to_value(&self) -> Value {
101 
        Value::map([
102 
            (0, Value::Uint(1)),
103 
            (1, Value::Text(self.kind.clone())),
104 
            (2, Value::Bytes(self.repo.to_vec())),
105 
            (3, Value::Bytes(self.object.0.to_vec())),
106 
            (
107 
                4,
108 
                Value::Array(
109 
                    self.signers
110 
                        .iter()
111 
                        .map(|k| Value::Bytes(k.0.to_vec()))
112 
                        .collect(),
113 
                ),
114 
            ),
115 
            (5, Value::Uint(self.received)),
116 
        ])
117 
    }
118
119 
    pub fn encode(&self) -> Vec<u8> {
120 
        cbor::encode(&self.to_value())
121 
    }
122
123 
    pub fn decode(b: &[u8]) -> Result<Entry> {
124 
        let v = cbor::decode(b).map_err(ObjectError::from)?;
125 
        let m = map(&v, "log entry")?;
126 
        check_version(m)?;
127 
        let repo = bytes(field(m, 2, "repo")?, "repo")?;
128 
        let repo: [u8; 16] = repo
129 
            .try_into()
130 
            .map_err(|_| TlogError::Schema("log entry: repo is not 16 bytes".into()))?;
131 
        let mut signers = Vec::new();
132 
        for s in array(field(m, 4, "signers")?, "signers")? {
133 
            signers.push(oref(s, "signer")?);
134 
        }
135 
        Ok(Entry {
136 
            kind: text(field(m, 1, "kind")?, "kind")?.to_owned(),
137 
            repo,
138 
            object: oref(field(m, 3, "object")?, "object")?,
139 
            signers,
140 
            received: uint(field(m, 5, "received")?, "received")?,
141 
        })
142 
    }
143
144 
    /// Its leaf hash in the tree.
145 
    pub fn leaf_hash(&self) -> Hash {
146 
        leaf_hash(&self.encode())
147 
    }
148 
}
149
150 
/// An entry bundle (C2SP tlog-tiles): each entry as a big-endian u16
151 
/// length and its bytes.
152 
pub fn encode_bundle(entries: &[Vec<u8>]) -> Result<Vec<u8>> {
153 
    let mut out = Vec::new();
154 
    for e in entries {
155 
        let n = u16::try_from(e.len())
156 
            .map_err(|_| TlogError::Schema("a log entry over 65535 bytes".into()))?;
157 
        out.extend_from_slice(&n.to_be_bytes());
158 
        out.extend_from_slice(e);
159 
    }
160 
    Ok(out)
161 
}
162
163 
/// The entries of a bundle.
164 
pub fn decode_bundle(mut b: &[u8]) -> Result<Vec<Vec<u8>>> {
165 
    let mut out = Vec::new();
166 
    while !b.is_empty() {
167 
        if b.len() < 2 {
168 
            return Err(TlogError::Schema("entry bundle: a truncated length".into()));
169 
        }
170 
        let n = u16::from_be_bytes([b[0], b[1]]) as usize;
171 
        if b.len() < 2 + n {
172 
            return Err(TlogError::Schema("entry bundle: a truncated entry".into()));
173 
        }
174 
        out.push(b[2..2 + n].to_vec());
175 
        b = &b[2 + n..];
176 
    }
177 
    Ok(out)
178 
}
179
180 
// -------------------------------------------------- the tree's arithmetic
181
182 
/// Reads stored hashes by their stored index.
183 
pub trait HashReader {
184 
    /// The hashes at `indexes`, in that order.
185 
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>>;
186 
}
187
188 
/// Every stored hash in order, as a log in memory holds them.
189 
impl HashReader for [Hash] {
190 
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>> {
191 
        indexes
192 
            .iter()
193 
            .map(|&i| {
194 
                self.get(i as usize)
195 
                    .copied()
196 
                    .ok_or_else(|| TlogError::Read(format!("no stored hash {i}")))
197 
            })
198 
            .collect()
199 
    }
200 
}
201
202 
impl HashReader for Vec<Hash> {
203 
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>> {
204 
        self.as_slice().read_hashes(indexes)
205 
    }
206 
}
207
208 
/// The largest power of two below `n` (n ≥ 2), and its log.
209 
fn maxpow2(n: u64) -> (u64, u32) {
210 
    let mut l = 0;
211 
    while (1u64 << (l + 1)) < n {
212 
        l += 1;
213 
    }
214 
    (1 << l, l)
215 
}
216
217 
/// Where the `n`th hash of tree level `level` is stored: level L's nth
218 
/// hash is written right after level L+1's (2n+1)th, and level 0's nth
219 
/// at n + n/2 + n/4 + ….
220 
pub fn stored_hash_index(level: u32, mut n: u64) -> u64 {
221 
    for _ in 0..level {
222 
        n = 2 * n + 1;
223 
    }
224 
    let mut i = 0;
225 
    let mut m = n;
226 
    while m > 0 {
227 
        i += m;
228 
        m >>= 1;
229 
    }
230 
    i + level as u64
231 
}
232
233 
/// The level and position of the hash at a stored index.
234 
pub fn split_stored_hash_index(index: u64) -> (u32, u64) {
235 
    let mut n = index / 2;
236 
    let mut index_n = stored_hash_index(0, n);
237 
    debug_assert!(index_n <= index);
238 
    loop {
239 
        // Each new leaf n adds 1 + trailing_zeros(n+1) hashes.
240 
        let x = index_n + 1 + (n + 1).trailing_zeros() as u64;
241 
        if x > index {
242 
            break;
243 
        }
244 
        n += 1;
245 
        index_n = x;
246 
    }
247 
    let level = (index - index_n) as u32;
248 
    (level, n >> level)
249 
}
250
251 
/// How many hashes a tree of `n` leaves stores.
252 
pub fn stored_hash_count(n: u64) -> u64 {
253 
    if n == 0 {
254 
        return 0;
255 
    }
256 
    let mut count = stored_hash_index(0, n - 1) + 1;
257 
    let mut i = n - 1;
258 
    while i & 1 != 0 {
259 
        count += 1;
260 
        i >>= 1;
261 
    }
262 
    count
263 
}
264
265 
/// The hashes to append when leaf `n` (with hash `leaf`) joins a tree of
266 
/// `n` leaves: the leaf's, then those of the subtrees it completes.
267 
pub fn stored_hashes_for_leaf(
268 
    n: u64,
269 
    leaf: Hash,
270 
    r: &(impl HashReader + ?Sized),
271 
) -> Result<Vec<Hash>> {
272 
    let m = (n + 1).trailing_zeros();
273 
    let indexes: Vec<u64> = (0..m)
274 
        .rev()
275 
        .map(|i| stored_hash_index(i, (n >> i) - 1))
276 
        .collect();
277 
    let old = r.read_hashes(&indexes)?;
278 
    let mut h = leaf;
279 
    let mut out = vec![h];
280 
    for i in 0..m as usize {
281 
        h = node_hash(&old[m as usize - 1 - i], &h);
282 
        out.push(h);
283 
    }
284 
    Ok(out)
285 
}
286
287 
fn sub_tree_index(mut lo: u64, hi: u64, need: &mut Vec<u64>) {
288 
    while lo < hi {
289 
        let (k, level) = maxpow2(hi - lo + 1);
290 
        debug_assert_eq!(lo & (k - 1), 0);
291 
        need.push(stored_hash_index(level, lo >> level));
292 
        lo += k;
293 
    }
294 
}
295
296 
fn sub_tree_hash(mut lo: u64, hi: u64, hashes: &[Hash]) -> (Hash, &[Hash]) {
297 
    let mut count = 0;
298 
    while lo < hi {
299 
        let (k, _) = maxpow2(hi - lo + 1);
300 
        count += 1;
301 
        lo += k;
302 
    }
303 
    let mut h = hashes[count - 1];
304 
    for i in (0..count - 1).rev() {
305 
        h = node_hash(&hashes[i], &h);
306 
    }
307 
    (h, &hashes[count..])
308 
}
309
310 
/// The root of the first `n` leaves.
311 
pub fn tree_hash(n: u64, r: &(impl HashReader + ?Sized)) -> Result<Hash> {
312 
    if n == 0 {
313 
        return Ok(empty_root());
314 
    }
315 
    let mut need = Vec::new();
316 
    sub_tree_index(0, n, &mut need);
317 
    let hashes = r.read_hashes(&need)?;
318 
    Ok(sub_tree_hash(0, n, &hashes).0)
319 
}
320
321 
fn leaf_proof_index(lo: u64, hi: u64, n: u64, need: &mut Vec<u64>) {
322 
    if lo + 1 == hi {
323 
        return;
324 
    }
325 
    let (k, _) = maxpow2(hi - lo);
326 
    if n < lo + k {
327 
        leaf_proof_index(lo, lo + k, n, need);
328 
        sub_tree_index(lo + k, hi, need);
329 
    } else {
330 
        sub_tree_index(lo, lo + k, need);
331 
        leaf_proof_index(lo + k, hi, n, need);
332 
    }
333 
}
334
335 
fn leaf_proof(lo: u64, hi: u64, n: u64, hashes: &[Hash]) -> (Vec<Hash>, &[Hash]) {
336 
    if lo + 1 == hi {
337 
        // The verifier has the leaf's hash.
338 
        return (Vec::new(), hashes);
339 
    }
340 
    let (k, _) = maxpow2(hi - lo);
341 
    let (mut p, th, rest);
342 
    if n < lo + k {
343 
        let (pp, h1) = leaf_proof(lo, lo + k, n, hashes);
344 
        let (t, h2) = sub_tree_hash(lo + k, hi, h1);
345 
        (p, th, rest) = (pp, t, h2);
346 
    } else {
347 
        let (t, h1) = sub_tree_hash(lo, lo + k, hashes);
348 
        let (pp, h2) = leaf_proof(lo + k, hi, n, h1);
349 
        (p, th, rest) = (pp, t, h2);
350 
    }
351 
    p.push(th);
352 
    (p, rest)
353 
}
354
355 
/// The inclusion proof of leaf `n` in the tree of the first `t` leaves.
356 
pub fn prove_inclusion(t: u64, n: u64, r: &(impl HashReader + ?Sized)) -> Result<Vec<Hash>> {
357 
    if n >= t {
358 
        return Err(TlogError::BadIndex(format!(
359 
            "leaf {n} is not in a tree of {t}"
360 
        )));
361 
    }
362 
    let mut need = Vec::new();
363 
    leaf_proof_index(0, t, n, &mut need);
364 
    if need.is_empty() {
365 
        return Ok(Vec::new());
366 
    }
367 
    let hashes = r.read_hashes(&need)?;
368 
    Ok(leaf_proof(0, t, n, &hashes).0)
369 
}
370
371 
fn run_inclusion(p: &[Hash], lo: u64, hi: u64, n: u64, leaf: Hash) -> Result<Hash> {
372 
    if lo + 1 == hi {
373 
        return if p.is_empty() {
374 
            Ok(leaf)
375 
        } else {
376 
            Err(TlogError::ProofFailed)
377 
        };
378 
    }
379 
    let Some((last, rest)) = p.split_last() else {
380 
        return Err(TlogError::ProofFailed);
381 
    };
382 
    let (k, _) = maxpow2(hi - lo);
383 
    if n < lo + k {
384 
        Ok(node_hash(&run_inclusion(rest, lo, lo + k, n, leaf)?, last))
385 
    } else {
386 
        Ok(node_hash(last, &run_inclusion(rest, lo + k, hi, n, leaf)?))
387 
    }
388 
}
389
390 
/// Check that leaf `n`, with hash `leaf`, is in the tree of `t` leaves
391 
/// whose root is `root`.
392 
pub fn check_inclusion(proof: &[Hash], t: u64, root: &Hash, n: u64, leaf: &Hash) -> Result<()> {
393 
    if n >= t {
394 
        return Err(TlogError::ProofFailed);
395 
    }
396 
    if run_inclusion(proof, 0, t, n, *leaf)? == *root {
397 
        Ok(())
398 
    } else {
399 
        Err(TlogError::ProofFailed)
400 
    }
401 
}
402
403 
fn tree_proof_index(lo: u64, hi: u64, n: u64, need: &mut Vec<u64>) {
404 
    if n == hi {
405 
        if lo != 0 {
406 
            sub_tree_index(lo, hi, need);
407 
        }
408 
        return;
409 
    }
410 
    let (k, _) = maxpow2(hi - lo);
411 
    if n <= lo + k {
412 
        tree_proof_index(lo, lo + k, n, need);
413 
        sub_tree_index(lo + k, hi, need);
414 
    } else {
415 
        sub_tree_index(lo, lo + k, need);
416 
        tree_proof_index(lo + k, hi, n, need);
417 
    }
418 
}
419
420 
fn tree_proof(lo: u64, hi: u64, n: u64, hashes: &[Hash]) -> (Vec<Hash>, &[Hash]) {
421 
    if n == hi {
422 
        if lo == 0 {
423 
            // Exactly the old tree, whose root the verifier has.
424 
            return (Vec::new(), hashes);
425 
        }
426 
        let (th, rest) = sub_tree_hash(lo, hi, hashes);
427 
        return (vec![th], rest);
428 
    }
429 
    let (k, _) = maxpow2(hi - lo);
430 
    let (mut p, th, rest);
431 
    if n <= lo + k {
432 
        let (pp, h1) = tree_proof(lo, lo + k, n, hashes);
433 
        let (t, h2) = sub_tree_hash(lo + k, hi, h1);
434 
        (p, th, rest) = (pp, t, h2);
435 
    } else {
436 
        let (t, h1) = sub_tree_hash(lo, lo + k, hashes);
437 
        let (pp, h2) = tree_proof(lo + k, hi, n, h1);
438 
        (p, th, rest) = (pp, t, h2);
439 
    }
440 
    p.push(th);
441 
    (p, rest)
442 
}
443
444 
/// The consistency proof that the tree of `n` leaves is a prefix of the
445 
/// tree of `t`.
446 
pub fn prove_consistency(t: u64, n: u64, r: &(impl HashReader + ?Sized)) -> Result<Vec<Hash>> {
447 
    if n < 1 || n > t {
448 
        return Err(TlogError::BadIndex(format!(
449 
            "no consistency proof from {n} to {t}"
450 
        )));
451 
    }
452 
    let mut need = Vec::new();
453 
    tree_proof_index(0, t, n, &mut need);
454 
    if need.is_empty() {
455 
        return Ok(Vec::new());
456 
    }
457 
    let hashes = r.read_hashes(&need)?;
458 
    Ok(tree_proof(0, t, n, &hashes).0)
459 
}
460
461 
fn run_consistency(p: &[Hash], lo: u64, hi: u64, n: u64, old: Hash) -> Result<(Hash, Hash)> {
462 
    if n == hi {
463 
        if lo == 0 {
464 
            return if p.is_empty() {
465 
                Ok((old, old))
466 
            } else {
467 
                Err(TlogError::ProofFailed)
468 
            };
469 
        }
470 
        return match p {
471 
            [h] => Ok((*h, *h)),
472 
            _ => Err(TlogError::ProofFailed),
473 
        };
474 
    }
475 
    let Some((last, rest)) = p.split_last() else {
476 
        return Err(TlogError::ProofFailed);
477 
    };
478 
    let (k, _) = maxpow2(hi - lo);
479 
    if n <= lo + k {
480 
        let (oh, th) = run_consistency(rest, lo, lo + k, n, old)?;
481 
        Ok((oh, node_hash(&th, last)))
482 
    } else {
483 
        let (oh, th) = run_consistency(rest, lo + k, hi, n, old)?;
484 
        Ok((node_hash(last, &oh), node_hash(last, &th)))
485 
    }
486 
}
487
488 
/// Check that the tree of `n` leaves with root `old_root` is a prefix of
489 
/// the tree of `t` leaves with root `root`.
490 
pub fn check_consistency(
491 
    proof: &[Hash],
492 
    t: u64,
493 
    root: &Hash,
494 
    n: u64,
495 
    old_root: &Hash,
496 
) -> Result<()> {
497 
    if n < 1 || n > t {
498 
        return Err(TlogError::ProofFailed);
499 
    }
500 
    let (oh, th) = run_consistency(proof, 0, t, n, *old_root)?;
501 
    if oh == *old_root && th == *root {
502 
        Ok(())
503 
    } else {
504 
        Err(TlogError::ProofFailed)
505 
    }
506 
}
507
508 
// ----------------------------------------------------------------- tiles
509
510 
/// A tile (C2SP tlog-tiles, height 8): level `level`'s hashes for leaves
511 
/// from `n`·256, `width` of them (256 when full).
512 
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
513 
pub struct Tile {
514 
    pub level: u32,
515 
    pub n: u64,
516 
    pub width: u32,
517 
}
518
519 
/// A tile index as a path: three-digit groups, all but the last with an
520 
/// `x`, as `x001/x234/067` for 1234067.
521 
pub fn index_path(n: u64) -> String {
522 
    let mut groups = Vec::new();
523 
    let mut m = n;
524 
    loop {
525 
        groups.push(m % 1000);
526 
        m /= 1000;
527 
        if m == 0 {
528 
            break;
529 
        }
530 
    }
531 
    groups.reverse();
532 
    let last = groups.len() - 1;
533 
    groups
534 
        .iter()
535 
        .enumerate()
536 
        .map(|(i, g)| {
537 
            if i < last {
538 
                format!("x{g:03}")
539 
            } else {
540 
                format!("{g:03}")
541 
            }
542 
        })
543 
        .collect::<Vec<_>>()
544 
        .join("/")
545 
}
546
547 
/// The index a path names (the inverse of [`index_path`]).
548 
pub fn parse_index_path(path: &str) -> Option<u64> {
549 
    let parts: Vec<&str> = path.split('/').collect();
550 
    let mut n: u64 = 0;
551 
    for (i, p) in parts.iter().enumerate() {
552 
        let digits = if i + 1 < parts.len() {
553 
            p.strip_prefix('x')?
554 
        } else {
555 
            p
556 
        };
557 
        if digits.len() != 3 || !digits.bytes().all(|c| c.is_ascii_digit()) {
558 
            return None;
559 
        }
560 
        n = n.checked_mul(1000)?.checked_add(digits.parse().ok()?)?;
561 
    }
562 
    Some(n)
563 
}
564
565 
impl Tile {
566 
    /// `tile/<L>/<N>[.p/<W>]`.
567 
    pub fn path(&self) -> String {
568 
        format!(
569 
            "tile/{}/{}{}",
570 
            self.level,
571 
            index_path(self.n),
572 
            self.partial()
573 
        )
574 
    }
575
576 
    /// The entry bundle beside a level-0 tile: `tile/entries/<N>[.p/<W>]`.
577 
    pub fn entries_path(&self) -> String {
578 
        format!("tile/entries/{}{}", index_path(self.n), self.partial())
579 
    }
580
581 
    fn partial(&self) -> String {
582 
        if (self.width as u64) < TILE_WIDTH {
583 
            format!(".p/{}", self.width)
584 
        } else {
585 
            String::new()
586 
        }
587 
    }
588
589 
    /// The tile a path names (`<L>/<N>[.p/<W>]` after `tile/`).
590 
    pub fn parse(path: &str) -> Option<Tile> {
591 
        let (level, rest) = path.split_once('/')?;
592 
        let level: u32 = level.parse().ok()?;
593 
        let (index, width) = match rest.split_once(".p/") {
594 
            Some((i, w)) => {
595 
                let w: u32 = w.parse().ok()?;
596 
                if w == 0 || w as u64 >= TILE_WIDTH {
597 
                    return None;
598 
                }
599 
                (i, w)
600 
            }
601 
            None => (rest, TILE_WIDTH as u32),
602 
        };
603 
        Some(Tile {
604 
            level,
605 
            n: parse_index_path(index)?,
606 
            width,
607 
        })
608 
    }
609
610 
    /// The tile holding the stored hash at `index`, and the byte range its
611 
    /// hash comes from in the tile's data.
612 
    pub fn for_index(index: u64) -> (Tile, usize, usize) {
613 
        let (level, mut n) = split_stored_hash_index(index);
614 
        let tl = level / TILE_HEIGHT;
615 
        let within = level - tl * TILE_HEIGHT;
616 
        let tn = (n << within) >> TILE_HEIGHT;
617 
        n -= (tn << TILE_HEIGHT) >> within;
618 
        let width = ((n + 1) << within) as u32;
619 
        let tile = Tile {
620 
            level: tl,
621 
            n: tn,
622 
            width,
623 
        };
624 
        (
625 
            tile,
626 
            ((n << within) * 32) as usize,
627 
            (((n + 1) << within) * 32) as usize,
628 
        )
629 
    }
630
631 
    /// The tile's data: its hashes, read from stored order.
632 
    pub fn read_data(&self, r: &(impl HashReader + ?Sized)) -> Result<Vec<u8>> {
633 
        let start = self.n << TILE_HEIGHT;
634 
        let indexes: Vec<u64> = (0..self.width as u64)
635 
            .map(|i| stored_hash_index(TILE_HEIGHT * self.level, start + i))
636 
            .collect();
637 
        Ok(r.read_hashes(&indexes)?.concat())
638 
    }
639
640 
    /// The stored hash at `index` from this tile's data.
641 
    pub fn hash_at(&self, data: &[u8], index: u64) -> Result<Hash> {
642 
        if self.width == 0
643 
            || self.width as u64 > TILE_WIDTH
644 
            || data.len() < self.width as usize * 32
645 
        {
646 
            return Err(TlogError::Read(format!("tile {} is short", self.path())));
647 
        }
648 
        let (t, start, end) = Tile::for_index(index);
649 
        if t.level != self.level || t.n != self.n || t.width > self.width {
650 
            return Err(TlogError::Read(format!(
651 
                "stored hash {index} is not in tile {}",
652 
                self.path()
653 
            )));
654 
        }
655 
        Ok(tile_hash(&data[start..end]))
656 
    }
657
658 
    /// The tiles a tree that grows from `old` to `new` leaves writes, full
659 
    /// ones and the new partial ones.
660 
    pub fn new_tiles(old: u64, new: u64) -> Vec<Tile> {
661 
        let mut tiles = Vec::new();
662 
        let mut level = 0u32;
663 
        while level < 8 && (new >> (TILE_HEIGHT * level)) > 0 {
664 
            let old_n = old >> (TILE_HEIGHT * level);
665 
            let new_n = new >> (TILE_HEIGHT * level);
666 
            if old_n != new_n {
667 
                for n in (old_n >> TILE_HEIGHT)..(new_n >> TILE_HEIGHT) {
668 
                    tiles.push(Tile {
669 
                        level,
670 
                        n,
671 
                        width: TILE_WIDTH as u32,
672 
                    });
673 
                }
674 
                let n = new_n >> TILE_HEIGHT;
675 
                let w = new_n - (n << TILE_HEIGHT);
676 
                if w > 0 {
677 
                    tiles.push(Tile {
678 
                        level,
679 
                        n,
680 
                        width: w as u32,
681 
                    });
682 
                }
683 
            }
684 
            level += 1;
685 
        }
686 
        tiles
687 
    }
688 
}
689
690 
fn tile_hash(data: &[u8]) -> Hash {
691 
    if data.len() == 32 {
692 
        let mut h = [0u8; 32];
693 
        h.copy_from_slice(data);
694 
        return h;
695 
    }
696 
    let half = data.len() / 2;
697 
    node_hash(&tile_hash(&data[..half]), &tile_hash(&data[half..]))
698 
}
699
700 
// ----------------------------------------------------- notes, checkpoints
701
702 
/// One signature line of a note: `— <name> <base64(key hash || sig)>`.
703 
#[derive(Clone, Debug, PartialEq, Eq)]
704 
pub struct NoteSignature {
705 
    pub name: String,
706 
    pub key_hash: [u8; 4],
707 
    pub sig: Vec<u8>,
708 
}
709
710 
/// A C2SP signed note: its text and its signature lines.
711 
#[derive(Clone, Debug, PartialEq, Eq)]
712 
pub struct Note {
713 
    /// The text, ending with a newline.
714 
    pub text: String,
715 
    pub sigs: Vec<NoteSignature>,
716 
}
717
718 
/// Signature types in a note's key hash (C2SP signed-note).
719 
const SIG_ED25519: u8 = 0x01;
720 
/// Oxygen's composite Ed25519 + ML-DSA-65 signature (spec §14.8).
721 
const SIG_COMPOSITE: u8 = 0x4f;
722
723 
fn key_hash(name: &str, sig_type: u8, key: &[u8]) -> [u8; 4] {
724 
    let mut h = Sha256::new();
725 
    h.update(name.as_bytes());
726 
    h.update(b"\n");
727 
    h.update([sig_type]);
728 
    h.update(key);
729 
    let d = h.finalize();
730 
    [d[0], d[1], d[2], d[3]]
731 
}
732
733 
/// What a composite signature of a note signs (domain `checkpoint`).
734 
fn note_target(text: &str) -> ObjectRef {
735 
    let mut h = blake3::Hasher::new();
736 
    h.update(b"oxygen-tlog-note\0");
737 
    h.update(text.as_bytes());
738 
    ObjectRef(*h.finalize().as_bytes())
739 
}
740
741 
fn valid_name(name: &str) -> bool {
742 
    !name.is_empty() && !name.contains(|c: char| c.is_whitespace() || c == '+')
743 
}
744
745 
impl Note {
746 
    /// The note as served: the text, a blank line, the signature lines.
747 
    pub fn encode(&self) -> String {
748 
        let mut out = self.text.clone();
749 
        out.push('\n');
750 
        for s in &self.sigs {
751 
            let mut b = s.key_hash.to_vec();
752 
            b.extend_from_slice(&s.sig);
753 
            out.push_str(&format!(
754 
                "\u{2014} {} {}\n",
755 
                s.name,
756 
                crate::dsse::base64(&b)
757 
            ));
758 
        }
759 
        out
760 
    }
761
762 
    pub fn parse(s: &str) -> Result<Note> {
763 
        let bad = |w: &str| TlogError::BadNote(w.to_string());
764 
        let split = s
765 
            .rfind("\n\n")
766 
            .ok_or_else(|| bad("no blank line before the signatures"))?;
767 
        let text = &s[..split + 1];
768 
        if text.chars().any(|c| c.is_control() && c != '\n') {
769 
            return Err(bad("control characters in the text"));
770 
        }
771 
        let mut sigs = Vec::new();
772 
        for line in s[split + 2..].lines() {
773 
            let rest = line
774 
                .strip_prefix("\u{2014} ")
775 
                .ok_or_else(|| bad("a signature line without its dash"))?;
776 
            let (name, b64) = rest
777 
                .split_once(' ')
778 
                .ok_or_else(|| bad("a signature line without a key"))?;
779 
            let b =
780 
                crate::dsse::base64_decode(b64).ok_or_else(|| bad("a signature is not base64"))?;
781 
            if b.len() < 5 || !valid_name(name) {
782 
                return Err(bad("a malformed signature line"));
783 
            }
784 
            sigs.push(NoteSignature {
785 
                name: name.to_string(),
786 
                key_hash: [b[0], b[1], b[2], b[3]],
787 
                sig: b[4..].to_vec(),
788 
            });
789 
        }
790 
        if sigs.is_empty() {
791 
            return Err(bad("no signatures"));
792 
        }
793 
        Ok(Note {
794 
            text: text.to_string(),
795 
            sigs,
796 
        })
797 
    }
798
799 
    /// Sign as `name` with `identity`'s key: the Ed25519 line note tools
800 
    /// read, and the composite line that keeps it post-quantum.
801 
    pub fn sign(text: &str, name: &str, identity: &Identity, sk: &SecretKey) -> Result<Note> {
802 
        if !valid_name(name) {
803 
            return Err(TlogError::BadNote(format!(
804 
                "{name:?} cannot name a note's key"
805 
            )));
806 
        }
807 
        if !text.ends_with('\n') || text.contains("\n\n") {
808 
            return Err(TlogError::BadNote(
809 
                "the text must end with one newline and hold no blank line".into(),
810 
            ));
811 
        }
812 
        let ed = NoteSignature {
813 
            name: name.to_string(),
814 
            key_hash: key_hash(name, SIG_ED25519, &identity.ed25519_pk),
815 
            sig: sk.sign_ed25519(text.as_bytes()).to_vec(),
816 
        };
817 
        let composite = NoteSignature {
818 
            name: name.to_string(),
819 
            key_hash: key_hash(name, SIG_COMPOSITE, &identity.encode()),
820 
            sig: cbor::encode(
821 
                &sk.sign(Domain::Checkpoint, &identity.hash(), &note_target(text))
822 
                    .to_value(),
823 
            ),
824 
        };
825 
        Ok(Note {
826 
            text: text.to_string(),
827 
            sigs: vec![ed, composite],
828 
        })
829 
    }
830
831 
    /// Both of `name`'s signatures by `identity` verify (a note signed
832 
    /// with Ed25519 only is not enough).
833 
    pub fn verify(&self, name: &str, identity: &Identity) -> Result<()> {
834 
        let find = |t: u8, key: &[u8]| {
835 
            let h = key_hash(name, t, key);
836 
            self.sigs.iter().find(|s| s.name == name && s.key_hash == h)
837 
        };
838 
        let ed = find(SIG_ED25519, &identity.ed25519_pk)
839 
            .ok_or_else(|| TlogError::BadSignature(format!("no Ed25519 signature by {name}")))?;
840 
        identity
841 
            .verify_ed25519(self.text.as_bytes(), &ed.sig)
842 
            .map_err(|_| {
843 
                TlogError::BadSignature(format!("{name}'s Ed25519 signature does not verify"))
844 
            })?;
845 
        let c = find(SIG_COMPOSITE, &identity.encode())
846 
            .ok_or_else(|| TlogError::BadSignature(format!("no composite signature by {name}")))?;
847 
        let sig = cbor::decode(&c.sig)
848 
            .map_err(|e| e.to_string())
849 
            .and_then(|v| Signature::from_value(&v).map_err(|e| e.to_string()))
850 
            .map_err(|e| TlogError::BadSignature(format!("{name}'s composite signature: {e}")))?;
851 
        verify(identity, &sig, Domain::Checkpoint, &note_target(&self.text)).map_err(|e| {
852 
            TlogError::BadSignature(format!("{name}'s composite signature does not verify: {e}"))
853 
        })
854 
    }
855 
}
856
857 
/// A checkpoint (C2SP tlog-checkpoint): the log's origin, size and root.
858 
#[derive(Clone, Debug, PartialEq, Eq)]
859 
pub struct Checkpoint {
860 
    /// The log's name: the hub's host and `/log`.
861 
    pub origin: String,
862 
    pub size: u64,
863 
    pub root: Hash,
864 
    /// Further lines, each without its newline.
865 
    pub extensions: Vec<String>,
866 
}
867
868 
impl Checkpoint {
869 
    pub fn text(&self) -> String {
870 
        let mut t = format!(
871 
            "{}\n{}\n{}\n",
872 
            self.origin,
873 
            self.size,
874 
            crate::dsse::base64(&self.root)
875 
        );
876 
        for e in &self.extensions {
877 
            t.push_str(e);
878 
            t.push('\n');
879 
        }
880 
        t
881 
    }
882
883 
    pub fn parse(text: &str) -> Result<Checkpoint> {
884 
        let bad = |w: &str| TlogError::BadNote(format!("checkpoint: {w}"));
885 
        if !text.ends_with('\n') {
886 
            return Err(bad("no final newline"));
887 
        }
888 
        let mut lines = text[..text.len() - 1].split('\n');
889 
        let origin = lines
890 
            .next()
891 
            .filter(|o| !o.is_empty())
892 
            .ok_or_else(|| bad("no origin"))?;
893 
        let size = lines
894 
            .next()
895 
            .and_then(|s| {
896 
                (s == "0" || !s.starts_with('0'))
897 
                    .then(|| s.parse().ok())
898 
                    .flatten()
899 
            })
900 
            .ok_or_else(|| bad("no tree size"))?;
901 
        let root = lines
902 
            .next()
903 
            .and_then(crate::dsse::base64_decode)
904 
            .and_then(|b| <Hash>::try_from(b).ok())
905 
            .ok_or_else(|| bad("no root hash"))?;
906 
        Ok(Checkpoint {
907 
            origin: origin.to_string(),
908 
            size,
909 
            root,
910 
            extensions: lines.map(String::from).collect(),
911 
        })
912 
    }
913
914 
    /// Signed by the log's key, named by its origin.
915 
    pub fn sign(&self, identity: &Identity, sk: &SecretKey) -> Result<Note> {
916 
        Note::sign(&self.text(), &self.origin, identity, sk)
917 
    }
918
919 
    /// The checkpoint a note carries, once the log's key (`identity`)
920 
    /// signed it for `origin`.
921 
    pub fn verify(note: &Note, origin: &str, identity: &Identity) -> Result<Checkpoint> {
922 
        note.verify(origin, identity)?;
923 
        let c = Checkpoint::parse(&note.text)?;
924 
        if c.origin != origin {
925 
            return Err(TlogError::BadNote(format!(
926 
                "checkpoint of {}, not of {origin}",
927 
                c.origin
928 
            )));
929 
        }
930 
        Ok(c)
931 
    }
932 
}
933
934 
// ------------------------------------------------------------- witnesses
935
936 
/// C2SP tlog-cosignature: a witness's Ed25519 cosignature.
937 
const SIG_COSIGNATURE: u8 = 0x04;
938 
/// Oxygen's composite cosignature beside it (spec §14.8).
939 
const SIG_COSIG_COMPOSITE: u8 = 0x4e;
940
941 
/// What a cosignature signs: `cosignature/v1`, the witness's time in
942 
/// seconds, then the checkpoint's text.
943 
fn cosigned_message(text: &str, time: u64) -> String {
944 
    format!("cosignature/v1\ntime {time}\n{text}")
945 
}
946
947 
fn cosig_target(message: &str) -> ObjectRef {
948 
    let mut h = blake3::Hasher::new();
949 
    h.update(b"oxygen-tlog-cosig\0");
950 
    h.update(message.as_bytes());
951 
    ObjectRef(*h.finalize().as_bytes())
952 
}
953
954 
/// A witness's cosignature of a checkpoint's text at `time` (seconds):
955 
/// the C2SP cosignature/v1 line, and a composite line that keeps it
956 
/// post-quantum. Each carries the time before the signature.
957 
pub fn cosign(
958 
    text: &str,
959 
    name: &str,
960 
    witness: &Identity,
961 
    sk: &SecretKey,
962 
    time: u64,
963 
) -> Result<Vec<NoteSignature>> {
964 
    if !valid_name(name) {
965 
        return Err(TlogError::BadNote(format!(
966 
            "{name:?} cannot name a witness"
967 
        )));
968 
    }
969 
    let message = cosigned_message(text, time);
970 
    let mut ed = time.to_be_bytes().to_vec();
971 
    ed.extend_from_slice(&sk.sign_ed25519(message.as_bytes()));
972 
    let mut composite = time.to_be_bytes().to_vec();
973 
    composite.extend_from_slice(&cbor::encode(
974 
        &sk.sign(Domain::Checkpoint, &witness.hash(), &cosig_target(&message))
975 
            .to_value(),
976 
    ));
977 
    Ok(vec![
978 
        NoteSignature {
979 
            name: name.to_string(),
980 
            key_hash: key_hash(name, SIG_COSIGNATURE, &witness.ed25519_pk),
981 
            sig: ed,
982 
        },
983 
        NoteSignature {
984 
            name: name.to_string(),
985 
            key_hash: key_hash(name, SIG_COSIG_COMPOSITE, &witness.encode()),
986 
            sig: composite,
987 
        },
988 
    ])
989 
}
990
991 
impl Note {
992 
    /// The time `witness` (named `name`) cosigned this note, once both its
993 
    /// lines verify and agree on the time.
994 
    pub fn cosigned_by(&self, name: &str, witness: &Identity) -> Result<u64> {
995 
        let find = |t: u8, key: &[u8]| {
996 
            let h = key_hash(name, t, key);
997 
            self.sigs.iter().find(|s| s.name == name && s.key_hash == h)
998 
        };
999 
        let time_of = |sig: &[u8]| -> Result<(u64, Vec<u8>)> {
1000 
            if sig.len() < 9 {
1001 
                return Err(TlogError::BadSignature(format!(
1002 
                    "{name}'s cosignature is short"
1003 
                )));
1004 
            }
1005 
            let mut t = [0u8; 8];
1006 
            t.copy_from_slice(&sig[..8]);
1007 
            Ok((u64::from_be_bytes(t), sig[8..].to_vec()))
1008 
        };
1009 
        let ed = find(SIG_COSIGNATURE, &witness.ed25519_pk)
1010 
            .ok_or_else(|| TlogError::BadSignature(format!("no cosignature by {name}")))?;
1011 
        let (time, sig) = time_of(&ed.sig)?;
1012 
        let message = cosigned_message(&self.text, time);
1013 
        witness
1014 
            .verify_ed25519(message.as_bytes(), &sig)
1015 
            .map_err(|_| {
1016 
                TlogError::BadSignature(format!("{name}'s cosignature does not verify"))
1017 
            })?;
1018 
        let c = find(SIG_COSIG_COMPOSITE, &witness.encode()).ok_or_else(|| {
1019 
            TlogError::BadSignature(format!("no composite cosignature by {name}"))
1020 
        })?;
1021 
        let (ctime, csig) = time_of(&c.sig)?;
1022 
        if ctime != time {
1023 
            return Err(TlogError::BadSignature(format!(
1024 
                "{name}'s two cosignatures disagree on the time"
1025 
            )));
1026 
        }
1027 
        let sig = cbor::decode(&csig)
1028 
            .map_err(|e| e.to_string())
1029 
            .and_then(|v| Signature::from_value(&v).map_err(|e| e.to_string()))
1030 
            .map_err(|e| TlogError::BadSignature(format!("{name}'s composite cosignature: {e}")))?;
1031 
        verify(witness, &sig, Domain::Checkpoint, &cosig_target(&message)).map_err(|e| {
1032 
            TlogError::BadSignature(format!(
1033 
                "{name}'s composite cosignature does not verify: {e}"
1034 
            ))
1035 
        })?;
1036 
        Ok(time)
1037 
    }
1038 
}
1039
1040 
/// A C2SP tlog-witness `add-checkpoint` request: the size of the last
1041 
/// checkpoint the witness cosigned for this log, the consistency proof
1042 
/// from it, and the new checkpoint note.
1043 
#[derive(Clone, Debug, PartialEq, Eq)]
1044 
pub struct AddCheckpoint {
1045 
    pub old_size: u64,
1046 
    pub proof: Vec<Hash>,
1047 
    pub note: String,
1048 
}
1049
1050 
impl AddCheckpoint {
1051 
    pub fn encode(&self) -> String {
1052 
        let mut out = format!("old {}\n", self.old_size);
1053 
        for h in &self.proof {
1054 
            out.push_str(&crate::dsse::base64(h));
1055 
            out.push('\n');
1056 
        }
1057 
        out.push('\n');
1058 
        out.push_str(&self.note);
1059 
        out
1060 
    }
1061
1062 
    pub fn parse(body: &str) -> Result<AddCheckpoint> {
1063 
        let bad = |w: &str| TlogError::BadNote(format!("add-checkpoint: {w}"));
1064 
        let (head, note) = body
1065 
            .split_once("\n\n")
1066 
            .ok_or_else(|| bad("no blank line before the checkpoint"))?;
1067 
        let mut lines = head.split('\n');
1068 
        let old_size = lines
1069 
            .next()
1070 
            .and_then(|l| l.strip_prefix("old "))
1071 
            .and_then(|n| n.parse().ok())
1072 
            .ok_or_else(|| bad("no old size"))?;
1073 
        let mut proof = Vec::new();
1074 
        for l in lines {
1075 
            let h = crate::dsse::base64_decode(l)
1076 
                .and_then(|b| <Hash>::try_from(b).ok())
1077 
                .ok_or_else(|| bad("a proof line is not a hash"))?;
1078 
            proof.push(h);
1079 
        }
1080 
        Ok(AddCheckpoint {
1081 
            old_size,
1082 
            proof,
1083 
            note: note.to_string(),
1084 
        })
1085 
    }
1086 
}
1087
1088 
/// What a witness answers.
1089 
#[derive(Clone, Debug, PartialEq, Eq)]
1090 
pub enum Witnessed {
1091 
    /// Cosigned: the checkpoint, and the cosignature lines to return.
1092 
    Cosigned {
1093 
        checkpoint: Checkpoint,
1094 
        lines: Vec<NoteSignature>,
1095 
    },
1096 
    /// The request's old size is not the witness's: it answers with its own
1097 
    /// (409, so the log retries with a proof from there).
1098 
    Conflict(u64),
1099 
}
1100
1101 
/// Why a witness refused.
1102 
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
1103 
pub enum WitnessError {
1104 
    /// Not signed by the log's key (403).
1105 
    #[error("{0}")]
1106 
    Unsigned(String),
1107 
    /// The checkpoint does not extend what the witness cosigned (422).
1108 
    #[error("{0}")]
1109 
    Inconsistent(String),
1110 
    /// Malformed (400).
1111 
    #[error("{0}")]
1112 
    Bad(String),
1113 
}
1114
1115 
/// A witness: its name in cosignatures, and its key.
1116 
pub struct WitnessKey<'a> {
1117 
    pub name: &'a str,
1118 
    pub identity: &'a Identity,
1119 
    pub sk: &'a SecretKey,
1120 
}
1121
1122 
/// A witness's decision (C2SP tlog-witness) on `req` for the log named
1123 
/// `origin` with key `log_key`, whose last cosigned checkpoint was
1124 
/// `latest` (size and root): cosign when the new checkpoint verifies and
1125 
/// extends it, as `me` at `now` (seconds).
1126 
pub fn witness(
1127 
    req: &AddCheckpoint,
1128 
    origin: &str,
1129 
    log_key: &Identity,
1130 
    latest: Option<(u64, Hash)>,
1131 
    me: &WitnessKey,
1132 
    now: u64,
1133 
) -> std::result::Result<Witnessed, WitnessError> {
1134 
    let note = Note::parse(&req.note).map_err(|e| WitnessError::Bad(e.to_string()))?;
1135 
    let cp = Checkpoint::verify(&note, origin, log_key)
1136 
        .map_err(|e| WitnessError::Unsigned(e.to_string()))?;
1137 
    let (old, old_root) = latest.unwrap_or((0, empty_root()));
1138 
    if req.old_size != old {
1139 
        return Ok(Witnessed::Conflict(old));
1140 
    }
1141 
    if cp.size < old {
1142 
        return Err(WitnessError::Bad(format!(
1143 
            "a checkpoint of {} entries is older than the {old} cosigned",
1144 
            cp.size
1145 
        )));
1146 
    }
1147 
    let consistent = match (old, cp.size == old) {
1148 
        (0, _) => req.proof.is_empty(),
1149 
        (_, true) => req.proof.is_empty() && cp.root == old_root,
1150 
        _ => check_consistency(&req.proof, cp.size, &cp.root, old, &old_root).is_ok(),
1151 
    };
1152 
    if !consistent {
1153 
        return Err(WitnessError::Inconsistent(format!(
1154 
            "the checkpoint of {} entries does not extend the one of {old} cosigned",
1155 
            cp.size
1156 
        )));
1157 
    }
1158 
    let lines = cosign(&note.text, me.name, me.identity, me.sk, now)
1159 
        .map_err(|e| WitnessError::Bad(e.to_string()))?;
1160 
    Ok(Witnessed::Cosigned {
1161 
        checkpoint: cp,
1162 
        lines,
1163 
    })
1164 
}
1165
1166 
// -------------------------------------------------------- integrated time
1167
1168 
/// How far a claimed time may stray from an integrated time before it is
1169 
/// noted (spec §14.8, *Integrated time*): ten minutes, in milliseconds.
1170 
pub const TIME_TOLERANCE_MS: u64 = 10 * 60 * 1000;
1171
1172 
impl Note {
1173 
    /// The witnesses among `trusted` (name and identity) whose
1174 
    /// cosignatures of this note verify, with their times in seconds.
1175 
    /// Lines by anyone else are ignored.
1176 
    pub fn cosignatures(&self, trusted: &[(String, Identity)]) -> Vec<(String, u64)> {
1177 
        trusted
1178 
            .iter()
1179 
            .filter_map(|(n, id)| self.cosigned_by(n, id).ok().map(|t| (n.clone(), t)))
1180 
            .collect()
1181 
    }
1182 
}
1183
1184 
/// When witnesses first saw a log entry (spec §14.8): an upper bound on
1185 
/// when what it logs was signed, by a clock neither its signer nor the
1186 
/// log chose.
1187 
#[derive(Clone, Debug, PartialEq, Eq)]
1188 
pub struct Integrated {
1189 
    /// The earliest trusted cosignature's time, in seconds.
1190 
    pub time: u64,
1191 
    /// The witness that made it.
1192 
    pub witness: String,
1193 
    /// The size of the checkpoint it cosigned.
1194 
    pub size: u64,
1195 
}
1196
1197 
impl Integrated {
1198 
    /// The time in milliseconds, as Oxygen's other times are.
1199 
    pub fn ms(&self) -> u64 {
1200 
        self.time.saturating_mul(1000)
1201 
    }
1202 
}
1203
1204 
/// Entry `index` (`entry`, its bytes)'s integrated time: the earliest time
1205 
/// a witness in `trusted` cosigned one of `cosigned` (checkpoint notes,
1206 
/// each with the entry's inclusion proof against it) that `log_key`
1207 
/// signed for `origin` and that includes the entry. A note that does not
1208 
/// verify, or does not include the entry, counts for nothing; `Err` says
1209 
/// why no time could be read.
1210 
pub fn integrated_time(
1211 
    entry: &[u8],
1212 
    index: u64,
1213 
    cosigned: &[(&str, &[Hash])],
1214 
    origin: &str,
1215 
    log_key: &Identity,
1216 
    trusted: &[(String, Identity)],
1217 
) -> std::result::Result<Integrated, String> {
1218 
    if cosigned.is_empty() {
1219 
        return Err("no witness has cosigned a checkpoint holding it yet".into());
1220 
    }
1221 
    let leaf = leaf_hash(entry);
1222 
    let mut best: Option<Integrated> = None;
1223 
    let mut why = String::new();
1224 
    for (text, proof) in cosigned {
1225 
        let checked = Note::parse(text)
1226 
            .and_then(|n| Checkpoint::verify(&n, origin, log_key).map(|c| (n, c)))
1227 
            .and_then(|(n, c)| {
1228 
                check_inclusion(proof, c.size, &c.root, index, &leaf)?;
1229 
                Ok((n, c))
1230 
            });
1231 
        let (note, cp) = match checked {
1232 
            Ok(x) => x,
1233 
            Err(e) => {
1234 
                why = format!("a cosigned checkpoint served for it does not hold it ({e})");
1235 
                continue;
1236 
            }
1237 
        };
1238 
        let times = note.cosignatures(trusted);
1239 
        if times.is_empty() {
1240 
            why = format!(
1241 
                "the checkpoint of {} entries holding it is cosigned by no witness this user trusts",
1242 
                cp.size
1243 
            );
1244 
            continue;
1245 
        }
1246 
        for (witness, time) in times {
1247 
            if best.as_ref().is_none_or(|b| time < b.time) {
1248 
                best = Some(Integrated {
1249 
                    time,
1250 
                    witness,
1251 
                    size: cp.size,
1252 
                });
1253 
            }
1254 
        }
1255 
    }
1256 
    best.ok_or(why)
1257 
}
1258
1259 
#[cfg(test)]
1260 
mod tests {
1261 
    use super::*;
1262
1263 
    /// A log in memory: its stored hashes, grown leaf by leaf.
1264 
    fn grow(leaves: u64) -> (Vec<Hash>, Vec<Hash>) {
1265 
        let mut stored: Vec<Hash> = Vec::new();
1266 
        let mut leaf_hashes = Vec::new();
1267 
        for n in 0..leaves {
1268 
            let h = leaf_hash(format!("entry {n}").as_bytes());
1269 
            leaf_hashes.push(h);
1270 
            let add = stored_hashes_for_leaf(n, h, &stored).unwrap();
1271 
            assert_eq!(stored.len() as u64, stored_hash_index(0, n));
1272 
            stored.extend(add);
1273 
            assert_eq!(stored.len() as u64, stored_hash_count(n + 1));
1274 
        }
1275 
        (stored, leaf_hashes)
1276 
    }
1277
1278 
    /// RFC 6962's MTH, straight from its definition.
1279 
    fn mth(leaves: &[Hash]) -> Hash {
1280 
        match leaves.len() {
1281 
            0 => empty_root(),
1282 
            1 => leaves[0],
1283 
            n => {
1284 
                let (k, _) = maxpow2(n as u64);
1285 
                node_hash(&mth(&leaves[..k as usize]), &mth(&leaves[k as usize..]))
1286 
            }
1287 
        }
1288 
    }
1289
1290 
    #[test]
1291 
    fn stored_indexes_round_trip() {
1292 
        for level in 0..6 {
1293 
            for n in 0..300 {
1294 
                let i = stored_hash_index(level, n);
1295 
                assert_eq!(split_stored_hash_index(i), (level, n));
1296 
            }
1297 
        }
1298 
    }
1299
1300 
    #[test]
1301 
    fn roots_match_rfc_6962_and_every_proof_verifies() {
1302 
        let (stored, leaves) = grow(140);
1303 
        for t in 1..=140u64 {
1304 
            let root = tree_hash(t, &stored).unwrap();
1305 
            assert_eq!(root, mth(&leaves[..t as usize]), "root of {t}");
1306 
            for n in 0..t {
1307 
                let p = prove_inclusion(t, n, &stored).unwrap();
1308 
                check_inclusion(&p, t, &root, n, &leaves[n as usize]).unwrap();
1309 
                // Another leaf, another tree, a tampered path: refused.
1310 
                let other = (n + 1) % t;
1311 
                if other != n {
1312 
                    assert!(check_inclusion(&p, t, &root, n, &leaves[other as usize]).is_err());
1313 
                }
1314 
                if let Some(first) = p.first() {
1315 
                    let mut bad = p.clone();
1316 
                    bad[0] = node_hash(first, first);
1317 
                    assert!(check_inclusion(&bad, t, &root, n, &leaves[n as usize]).is_err());
1318 
                }
1319 
                let old = n + 1;
1320 
                let old_root = tree_hash(old, &stored).unwrap();
1321 
                let c = prove_consistency(t, old, &stored).unwrap();
1322 
                check_consistency(&c, t, &root, old, &old_root).unwrap();
1323 
                if old < t {
1324 
                    let fork = node_hash(&old_root, &old_root);
1325 
                    assert!(
1326 
                        check_consistency(&c, t, &root, old, &fork).is_err(),
1327 
                        "a forked history"
1328 
                    );
1329 
                }
1330 
            }
1331 
        }
1332 
        assert_eq!(tree_hash(0, &stored).unwrap(), empty_root());
1333 
    }
1334
1335 
    #[test]
1336 
    fn tiles_hold_the_stored_hashes() {
1337 
        let n = 70_000u64;
1338 
        let (stored, _) = grow(n);
1339 
        let tiles = Tile::new_tiles(0, n);
1340 
        // 273 full tiles of level 0 and a partial one, one full and one
1341 
        // partial at level 1, a partial at level 2.
1342 
        assert_eq!(tiles.iter().filter(|t| t.level == 0).count(), 274);
1343 
        assert_eq!(tiles.iter().filter(|t| t.level == 2).count(), 1);
1344 
        let datas: Vec<(Tile, Vec<u8>)> = tiles
1345 
            .iter()
1346 
            .map(|t| (*t, t.read_data(&stored).unwrap()))
1347 
            .collect();
1348 
        for (i, want) in stored.iter().enumerate().step_by(7) {
1349 
            let (t, ..) = Tile::for_index(i as u64);
1350 
            let (tile, data) = datas
1351 
                .iter()
1352 
                .find(|(d, _)| d.level == t.level && d.n == t.n && d.width >= t.width)
1353 
                .expect("the tile holding it was written");
1354 
            assert_eq!(
1355 
                tile.hash_at(data, i as u64).unwrap(),
1356 
                *want,
1357 
                "stored hash {i}"
1358 
            );
1359 
        }
1360 
        // Growing writes only what changed.
1361 
        let grown = Tile::new_tiles(n, n + 300);
1362 
        assert!(grown.iter().all(|t| t.level > 0 || t.n >= n / 256));
1363 
    }
1364
1365 
    #[test]
1366 
    fn tile_paths() {
1367 
        assert_eq!(index_path(1_234_067), "x001/x234/067");
1368 
        assert_eq!(index_path(5), "005");
1369 
        assert_eq!(index_path(1000), "x001/000");
1370 
        assert_eq!(parse_index_path("x001/x234/067"), Some(1_234_067));
1371 
        assert_eq!(parse_index_path("x001/234/067"), None);
1372 
        let t = Tile {
1373 
            level: 1,
1374 
            n: 1234,
1375 
            width: 17,
1376 
        };
1377 
        assert_eq!(t.path(), "tile/1/x001/234.p/17");
1378 
        assert_eq!(Tile::parse("1/x001/234.p/17"), Some(t));
1379 
        assert_eq!(
1380 
            Tile {
1381 
                level: 0,
1382 
                n: 3,
1383 
                width: 256
1384 
            }
1385 
            .entries_path(),
1386 
            "tile/entries/003"
1387 
        );
1388 
        assert_eq!(Tile::parse("0/003.p/256"), None, "a full tile has no .p");
1389 
    }
1390
1391 
    #[test]
1392 
    fn entries_and_bundles_round_trip() {
1393 
        let e = Entry {
1394 
            kind: "ref".into(),
1395 
            repo: [7; 16],
1396 
            object: ObjectRef([1; 32]),
1397 
            signers: vec![ObjectRef([2; 32])],
1398 
            received: 1_792_000_000_000,
1399 
        };
1400 
        assert_eq!(Entry::decode(&e.encode()).unwrap(), e);
1401 
        let b = encode_bundle(&[e.encode(), b"x".to_vec()]).unwrap();
1402 
        assert_eq!(decode_bundle(&b).unwrap(), vec![e.encode(), b"x".to_vec()]);
1403 
        assert!(decode_bundle(&b[..b.len() - 1]).is_err());
1404 
        assert_eq!(e.leaf_hash(), leaf_hash(&e.encode()));
1405 
    }
1406
1407 
    #[test]
1408 
    fn a_witness_cosigns_what_extends_what_it_saw_and_nothing_else() {
1409 
        let log_sk = SecretKey::generate();
1410 
        let log = log_sk.identity("log", "[email protected]", 1);
1411 
        let w_sk = SecretKey::generate();
1412 
        let w = w_sk.identity("witness", "[email protected]", 1);
1413 
        let origin = "hub.example/log";
1414 
        let (stored, _) = grow(40);
1415 
        let note_of = |n: u64| {
1416 
            Checkpoint {
1417 
                origin: origin.into(),
1418 
                size: n,
1419 
                root: tree_hash(n, &stored).unwrap(),
1420 
                extensions: vec![],
1421 
            }
1422 
            .sign(&log, &log_sk)
1423 
            .unwrap()
1424 
            .encode()
1425 
        };
1426 
        let ask = |old: u64, n: u64, latest: Option<(u64, Hash)>| {
1427 
            let proof = if old == 0 || old == n {
1428 
                vec![]
1429 
            } else {
1430 
                prove_consistency(n, old, &stored).unwrap()
1431 
            };
1432 
            let req = AddCheckpoint {
1433 
                old_size: old,
1434 
                proof,
1435 
                note: note_of(n),
1436 
            };
1437 
            let req = AddCheckpoint::parse(&req.encode()).unwrap();
1438 
            let me = WitnessKey {
1439 
                name: "w.example",
1440 
                identity: &w,
1441 
                sk: &w_sk,
1442 
            };
1443 
            witness(&req, origin, &log, latest, &me, 1_792_300_000)
1444 
        };
1445 
        // First sight, then a later checkpoint with its proof.
1446 
        let Ok(Witnessed::Cosigned { checkpoint, lines }) = ask(0, 10, None) else {
1447 
            panic!()
1448 
        };
1449 
        let mut note = Note::parse(&note_of(10)).unwrap();
1450 
        note.sigs.extend(lines);
1451 
        let back = Note::parse(&note.encode()).unwrap();
1452 
        assert_eq!(back.cosigned_by("w.example", &w).unwrap(), 1_792_300_000);
1453 
        assert!(
1454 
            back.cosigned_by("w.example", &log).is_err(),
1455 
            "another witness's key"
1456 
        );
1457 
        let latest = Some((10, checkpoint.root));
1458 
        assert!(matches!(
1459 
            ask(10, 40, latest),
1460 
            Ok(Witnessed::Cosigned { .. })
1461 
        ));
1462 
        // The log's idea of what the witness saw is wrong: told the size.
1463 
        assert_eq!(ask(5, 40, latest), Ok(Witnessed::Conflict(10)));
1464 
        // A fork: what the witness saw is not a prefix.
1465 
        let forked = Some((10, [9; 32]));
1466 
        assert!(matches!(
1467 
            ask(10, 40, forked),
1468 
            Err(WitnessError::Inconsistent(_))
1469 
        ));
1470 
        // Signed by someone else.
1471 
        let req = AddCheckpoint {
1472 
            old_size: 0,
1473 
            proof: vec![],
1474 
            note: note_of(10),
1475 
        };
1476 
        assert!(matches!(
1477 
            witness(
1478 
                &req,
1479 
                origin,
1480 
                &w,
1481 
                None,
1482 
                &WitnessKey {
1483 
                    name: "w.example",
1484 
                    identity: &w,
1485 
                    sk: &w_sk
1486 
                },
1487 
                1
1488 
            ),
1489 
            Err(WitnessError::Unsigned(_))
1490 
        ));
1491 
    }
1492
1493 
    #[test]
1494 
    fn checkpoints_are_signed_twice_and_checked() {
1495 
        let sk = SecretKey::generate();
1496 
        let hub = sk.identity("oxygenhub.io", "[email protected]", 1);
1497 
        let (stored, _) = grow(10);
1498 
        let c = Checkpoint {
1499 
            origin: "oxygenhub.io/log".into(),
1500 
            size: 10,
1501 
            root: tree_hash(10, &stored).unwrap(),
1502 
            extensions: vec![],
1503 
        };
1504 
        let note = c.sign(&hub, &sk).unwrap();
1505 
        let served = note.encode();
1506 
        assert!(served.starts_with("oxygenhub.io/log\n10\n"));
1507 
        assert_eq!(served.matches("\n\u{2014} oxygenhub.io/log ").count(), 2);
1508 
        let back = Note::parse(&served).unwrap();
1509 
        assert_eq!(
1510 
            Checkpoint::verify(&back, "oxygenhub.io/log", &hub).unwrap(),
1511 
            c
1512 
        );
1513 
        // Another key, another origin, a changed size, a lost line: refused.
1514 
        let other_sk = SecretKey::generate();
1515 
        let other = other_sk.identity("x", "x@x", 1);
1516 
        assert!(Checkpoint::verify(&back, "oxygenhub.io/log", &other).is_err());
1517 
        assert!(Checkpoint::verify(&back, "elsewhere/log", &hub).is_err());
1518 
        let forged = Note {
1519 
            text: back.text.replace("\n10\n", "\n11\n"),
1520 
            ..back.clone()
1521 
        };
1522 
        assert!(Checkpoint::verify(&forged, "oxygenhub.io/log", &hub).is_err());
1523 
        let ed_only = Note {
1524 
            sigs: vec![back.sigs[0].clone()],
1525 
            ..back.clone()
1526 
        };
1527 
        assert!(
1528 
            matches!(Checkpoint::verify(&ed_only, "oxygenhub.io/log", &hub), Err(TlogError::BadSignature(m)) if m.contains("composite")),
1529 
            "the post-quantum line is required"
1530 
        );
1531 
        // The Ed25519 line is a standard note signature over the text.
1532 
        let h = key_hash("oxygenhub.io/log", SIG_ED25519, &hub.ed25519_pk);
1533 
        assert_eq!(back.sigs[0].key_hash, h);
1534 
        assert!(hub
1535 
            .verify_ed25519(back.text.as_bytes(), &back.sigs[0].sig)
1536 
            .is_ok());
1537 
    }
1538
1539 
    #[test]
1540 
    fn an_entry_is_integrated_when_a_trusted_witness_first_cosigned_it() {
1541 
        let log_sk = SecretKey::generate();
1542 
        let log = log_sk.identity("log", "[email protected]", 1);
1543 
        let origin = "hub.example/log";
1544 
        let witness = |name: &str| {
1545 
            let sk = SecretKey::generate();
1546 
            (name.to_string(), sk.identity(name, "[email protected]", 1), sk)
1547 
        };
1548 
        let (a, b, c) = (
1549 
            witness("a.example"),
1550 
            witness("b.example"),
1551 
            witness("c.example"),
1552 
        );
1553 
        let trusted = vec![(a.0.clone(), a.1.clone()), (b.0.clone(), b.1.clone())];
1554 
        // A log of 40 real entries, so `integrated_time` hashes the leaf.
1555 
        let leaf_bytes = |n: u64| {
1556 
            Entry {
1557 
                kind: "ref".into(),
1558 
                repo: [n as u8; 16],
1559 
                object: ObjectRef([n as u8; 32]),
1560 
                signers: vec![],
1561 
                received: n,
1562 
            }
1563 
            .encode()
1564 
        };
1565 
        let mut stored: Vec<Hash> = Vec::new();
1566 
        for n in 0..40 {
1567 
            let add = stored_hashes_for_leaf(n, leaf_hash(&leaf_bytes(n)), &stored).unwrap();
1568 
            stored.extend(add);
1569 
        }
1570 
        // Checkpoint `n`, cosigned by each of `by` at its time.
1571 
        type W = (String, Identity, SecretKey);
1572 
        let cosigned = |n: u64, by: &[(&W, u64)]| {
1573 
            let cp = Checkpoint {
1574 
                origin: origin.into(),
1575 
                size: n,
1576 
                root: tree_hash(n, &stored).unwrap(),
1577 
                extensions: vec![],
1578 
            };
1579 
            let mut note = cp.sign(&log, &log_sk).unwrap();
1580 
            for ((name, id, sk), t) in by {
1581 
                note.sigs
1582 
                    .extend(cosign(&note.text, name, id, sk, *t).unwrap());
1583 
            }
1584 
            note.encode()
1585 
        };
1586 
        let proof = |n: u64| prove_inclusion(n, 7, &stored).unwrap();
1587 
        let entry = leaf_bytes(7);
1588 
        let time = |served: &[(String, Vec<Hash>)]| {
1589 
            let s: Vec<(&str, &[Hash])> = served
1590 
                .iter()
1591 
                .map(|(n, p)| (n.as_str(), p.as_slice()))
1592 
                .collect();
1593 
            integrated_time(&entry, 7, &s, origin, &log, &trusted)
1594 
        };
1595
1596 
        // One checkpoint, two witnesses: the earlier cosignature.
1597 
        let one = cosigned(10, &[(&a, 1_792_300_050), (&b, 1_792_300_020)]);
1598 
        let got = time(&[(one.clone(), proof(10))]).unwrap();
1599 
        assert_eq!(
1600 
            (got.time, got.witness.as_str(), got.size),
1601 
            (1_792_300_020, "b.example", 10)
1602 
        );
1603 
        assert_eq!(got.ms(), 1_792_300_020_000);
1604 
        // Witnesses that first cosigned different checkpoints: the
1605 
        // earliest of all.
1606 
        let later = cosigned(20, &[(&a, 1_792_300_010)]);
1607 
        let got = time(&[(later.clone(), proof(20)), (one.clone(), proof(10))]).unwrap();
1608 
        assert_eq!(
1609 
            (got.time, got.witness.as_str()),
1610 
            (1_792_300_010, "a.example")
1611 
        );
1612
1613 
        // A witness this user does not trust is no witness, however early.
1614 
        let stranger = cosigned(10, &[(&c, 1)]);
1615 
        let err = time(&[(stranger, proof(10))]).unwrap_err();
1616 
        assert!(err.contains("no witness this user trusts"), "{err}");
1617 
        // A forged cosignature under a trusted name: c's key signed it.
1618 
        let forged = cosigned(10, &[(&(a.0.clone(), c.1.clone(), c.2.clone()), 1)]);
1619 
        assert!(time(&[(forged.clone(), proof(10))]).is_err());
1620 
        // Beside a real one, it changes nothing.
1621 
        let got = time(&[(forged, proof(10)), (one.clone(), proof(10))]).unwrap();
1622 
        assert_eq!(got.time, 1_792_300_020);
1623 
        // A time moved after cosigning no longer verifies.
1624 
        let mut moved = Note::parse(&one).unwrap();
1625 
        for s in moved.sigs.iter_mut().filter(|s| s.name == "b.example") {
1626 
            s.sig[..8].copy_from_slice(&1u64.to_be_bytes());
1627 
        }
1628 
        let got = time(&[(moved.encode(), proof(10))]).unwrap();
1629 
        assert_eq!(got.witness, "a.example", "b's lines no longer verify");
1630
1631 
        // A checkpoint that does not hold the entry, a proof for another
1632 
        // size, another log's key: no time.
1633 
        let early = cosigned(5, &[(&a, 1)]);
1634 
        assert!(time(&[(early, proof(10))]).is_err());
1635 
        assert!(time(&[(one.clone(), proof(20))]).is_err());
1636 
        let other_sk = SecretKey::generate();
1637 
        let other = other_sk.identity("x", "x@x", 1);
1638 
        let s = [(one.as_str(), proof(10))];
1639 
        let s: Vec<(&str, &[Hash])> = s.iter().map(|(n, p)| (*n, p.as_slice())).collect();
1640 
        assert!(integrated_time(&entry, 7, &s, origin, &other, &trusted).is_err());
1641 
        assert!(integrated_time(&entry, 7, &s, "elsewhere/log", &log, &trusted).is_err());
1642 
        assert!(integrated_time(&leaf_bytes(8), 7, &s, origin, &log, &trusted).is_err());
1643 
        // Nothing served.
1644 
        assert!(time(&[]).unwrap_err().contains("no witness has cosigned"));
1645 
    }
1646 
}