tlog.rs 92.4%

1138 of 1231 lines run, 172 of 273 functions · run #427 on main · run missed
//! The transparency log (spec §14.8, oxygenhub#238, oxygenhub
//! docs/transparency.md): an append-only Merkle tree of what a hub
//! accepts, served as C2SP tlog-tiles with C2SP signed-note checkpoints,
//! so a hub cannot show one history to some and another to others.
//!
//! The tree is RFC 6962's, with BLAKE3 for its hashes, domain-separated
//! for leaves and nodes. Hashes are kept in *stored order*: every hash of
//! the tree, each written as soon as it is known, so the store is
//! append-only (the arithmetic is that of Go's `sumdb/tlog`). Tiles are
//! views of it: level L tile N holds the hashes of tree level 8·L for
//! leaves N·256 onwards.
//!
//! A checkpoint is a signed note: the origin, the tree size and the root,
//! signed with the hub's Ed25519 key (what note tools read) and with its
//! composite key in an extra line, so the log stays post-quantum.

use crate::cbor::{self, Value};
use crate::hash::{KeyId, ObjectRef};
use crate::identity::{verify, Domain, Identity, SecretKey, Signature};
use crate::objects::{array, bytes, check_version, field, map, oref, text, uint, ObjectError};
use sha2::{Digest, Sha256};

/// A hash in the tree.
pub type Hash = [u8; 32];

/// Tile height: a tile holds up to 2⁸ hashes (C2SP tlog-tiles).
pub const TILE_HEIGHT: u32 = 8;
/// Hashes in a full tile.
pub const TILE_WIDTH: u64 = 1 << TILE_HEIGHT;

#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
pub enum TlogError {
    #[error("the proof does not verify")]
    ProofFailed,
    #[error("{0}")]
    BadIndex(String),
    #[error("reading the log's hashes: {0}")]
    Read(String),
    #[error("not a valid note: {0}")]
    BadNote(String),
    #[error("{0}")]
    BadSignature(String),
    #[error("{0}")]
    Schema(String),
}

impl From<ObjectError> for TlogError {
    fn from(e: ObjectError) -> Self {
        TlogError::Schema(e.to_string())
    }
}

type Result<T> = std::result::Result<T, TlogError>;

// ------------------------------------------------------------- hashing

/// A leaf's hash: `BLAKE3("oxygen-tlog-leaf\0" || entry bytes)`.
pub fn leaf_hash(entry: &[u8]) -> Hash {
    let mut h = blake3::Hasher::new();
    h.update(b"oxygen-tlog-leaf\0");
    h.update(entry);
    *h.finalize().as_bytes()
}

/// An interior node's hash: `BLAKE3("oxygen-tlog-node\0" || left || right)`.
pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
    let mut h = blake3::Hasher::new();
    h.update(b"oxygen-tlog-node\0");
    h.update(left);
    h.update(right);
    *h.finalize().as_bytes()
}

/// The root of the empty tree: the hash of nothing, as RFC 6962 has it.
pub fn empty_root() -> Hash {
    *blake3::hash(b"").as_bytes()
}

// --------------------------------------------------------------- entries

/// One accepted object (spec §14.8): small and fixed-shape, never the
/// object itself, so a private repository's entries reveal only ids and
/// hashes.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Entry {
    /// `ref`, `seal`, `tag`, `rotate`, `revoke`, `receipt`, `approval`,
    /// `policy`, `identity`, `certificate`, `accepted`.
    pub kind: String,
    /// The repository's id; zero for identities.
    pub repo: [u8; 16],
    /// The attestation, policy, identity or certificate.
    pub object: ObjectRef,
    /// The keys whose signatures were checked.
    pub signers: Vec<KeyId>,
    /// The hub's clock when it accepted it, in milliseconds (its claim).
    pub received: u64,
}

impl Entry {
    pub fn to_value(&self) -> Value {
        Value::map([
            (0, Value::Uint(1)),
            (1, Value::Text(self.kind.clone())),
            (2, Value::Bytes(self.repo.to_vec())),
            (3, Value::Bytes(self.object.0.to_vec())),
            (
                4,
                Value::Array(
                    self.signers
                        .iter()
                        .map(|k| Value::Bytes(k.0.to_vec()))
                        .collect(),
                ),
            ),
            (5, Value::Uint(self.received)),
        ])
    }

    pub fn encode(&self) -> Vec<u8> {
        cbor::encode(&self.to_value())
    }

    pub fn decode(b: &[u8]) -> Result<Entry> {
        let v = cbor::decode(b).map_err(ObjectError::from)?;
        let m = map(&v, "log entry")?;
        check_version(m)?;
        let repo = bytes(field(m, 2, "repo")?, "repo")?;
        let repo: [u8; 16] = repo
            .try_into()
            .map_err(|_| TlogError::Schema("log entry: repo is not 16 bytes".into()))?;
        let mut signers = Vec::new();
        for s in array(field(m, 4, "signers")?, "signers")? {
            signers.push(oref(s, "signer")?);
        }
        Ok(Entry {
            kind: text(field(m, 1, "kind")?, "kind")?.to_owned(),
            repo,
            object: oref(field(m, 3, "object")?, "object")?,
            signers,
            received: uint(field(m, 5, "received")?, "received")?,
        })
    }

    /// Its leaf hash in the tree.
    pub fn leaf_hash(&self) -> Hash {
        leaf_hash(&self.encode())
    }
}

/// An entry bundle (C2SP tlog-tiles): each entry as a big-endian u16
/// length and its bytes.
pub fn encode_bundle(entries: &[Vec<u8>]) -> Result<Vec<u8>> {
    let mut out = Vec::new();
    for e in entries {
        let n = u16::try_from(e.len())
            .map_err(|_| TlogError::Schema("a log entry over 65535 bytes".into()))?;
        out.extend_from_slice(&n.to_be_bytes());
        out.extend_from_slice(e);
    }
    Ok(out)
}

/// The entries of a bundle.
pub fn decode_bundle(mut b: &[u8]) -> Result<Vec<Vec<u8>>> {
    let mut out = Vec::new();
    while !b.is_empty() {
        if b.len() < 2 {
            return Err(TlogError::Schema("entry bundle: a truncated length".into()));
        }
        let n = u16::from_be_bytes([b[0], b[1]]) as usize;
        if b.len() < 2 + n {
            return Err(TlogError::Schema("entry bundle: a truncated entry".into()));
        }
        out.push(b[2..2 + n].to_vec());
        b = &b[2 + n..];
    }
    Ok(out)
}

// -------------------------------------------------- the tree's arithmetic

/// Reads stored hashes by their stored index.
pub trait HashReader {
    /// The hashes at `indexes`, in that order.
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>>;
}

/// Every stored hash in order, as a log in memory holds them.
impl HashReader for [Hash] {
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>> {
        indexes
            .iter()
            .map(|&i| {
                self.get(i as usize)
                    .copied()
                    .ok_or_else(|| TlogError::Read(format!("no stored hash {i}")))
            })
            .collect()
    }
}

impl HashReader for Vec<Hash> {
    fn read_hashes(&self, indexes: &[u64]) -> Result<Vec<Hash>> {
        self.as_slice().read_hashes(indexes)
    }
}

/// The largest power of two below `n` (n ≥ 2), and its log.
fn maxpow2(n: u64) -> (u64, u32) {
    let mut l = 0;
    while (1u64 << (l + 1)) < n {
        l += 1;
    }
    (1 << l, l)
}

/// Where the `n`th hash of tree level `level` is stored: level L's nth
/// hash is written right after level L+1's (2n+1)th, and level 0's nth
/// at n + n/2 + n/4 + ….
pub fn stored_hash_index(level: u32, mut n: u64) -> u64 {
    for _ in 0..level {
        n = 2 * n + 1;
    }
    let mut i = 0;
    let mut m = n;
    while m > 0 {
        i += m;
        m >>= 1;
    }
    i + level as u64
}

/// The level and position of the hash at a stored index.
pub fn split_stored_hash_index(index: u64) -> (u32, u64) {
    let mut n = index / 2;
    let mut index_n = stored_hash_index(0, n);
    debug_assert!(index_n <= index);
    loop {
        // Each new leaf n adds 1 + trailing_zeros(n+1) hashes.
        let x = index_n + 1 + (n + 1).trailing_zeros() as u64;
        if x > index {
            break;
        }
        n += 1;
        index_n = x;
    }
    let level = (index - index_n) as u32;
    (level, n >> level)
}

/// How many hashes a tree of `n` leaves stores.
pub fn stored_hash_count(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let mut count = stored_hash_index(0, n - 1) + 1;
    let mut i = n - 1;
    while i & 1 != 0 {
        count += 1;
        i >>= 1;
    }
    count
}

/// The hashes to append when leaf `n` (with hash `leaf`) joins a tree of
/// `n` leaves: the leaf's, then those of the subtrees it completes.
pub fn stored_hashes_for_leaf(
    n: u64,
    leaf: Hash,
    r: &(impl HashReader + ?Sized),
) -> Result<Vec<Hash>> {
    let m = (n + 1).trailing_zeros();
    let indexes: Vec<u64> = (0..m)
        .rev()
        .map(|i| stored_hash_index(i, (n >> i) - 1))
        .collect();
    let old = r.read_hashes(&indexes)?;
    let mut h = leaf;
    let mut out = vec![h];
    for i in 0..m as usize {
        h = node_hash(&old[m as usize - 1 - i], &h);
        out.push(h);
    }
    Ok(out)
}

fn sub_tree_index(mut lo: u64, hi: u64, need: &mut Vec<u64>) {
    while lo < hi {
        let (k, level) = maxpow2(hi - lo + 1);
        debug_assert_eq!(lo & (k - 1), 0);
        need.push(stored_hash_index(level, lo >> level));
        lo += k;
    }
}

fn sub_tree_hash(mut lo: u64, hi: u64, hashes: &[Hash]) -> (Hash, &[Hash]) {
    let mut count = 0;
    while lo < hi {
        let (k, _) = maxpow2(hi - lo + 1);
        count += 1;
        lo += k;
    }
    let mut h = hashes[count - 1];
    for i in (0..count - 1).rev() {
        h = node_hash(&hashes[i], &h);
    }
    (h, &hashes[count..])
}

/// The root of the first `n` leaves.
pub fn tree_hash(n: u64, r: &(impl HashReader + ?Sized)) -> Result<Hash> {
    if n == 0 {
        return Ok(empty_root());
    }
    let mut need = Vec::new();
    sub_tree_index(0, n, &mut need);
    let hashes = r.read_hashes(&need)?;
    Ok(sub_tree_hash(0, n, &hashes).0)
}

fn leaf_proof_index(lo: u64, hi: u64, n: u64, need: &mut Vec<u64>) {
    if lo + 1 == hi {
        return;
    }
    let (k, _) = maxpow2(hi - lo);
    if n < lo + k {
        leaf_proof_index(lo, lo + k, n, need);
        sub_tree_index(lo + k, hi, need);
    } else {
        sub_tree_index(lo, lo + k, need);
        leaf_proof_index(lo + k, hi, n, need);
    }
}

fn leaf_proof(lo: u64, hi: u64, n: u64, hashes: &[Hash]) -> (Vec<Hash>, &[Hash]) {
    if lo + 1 == hi {
        // The verifier has the leaf's hash.
        return (Vec::new(), hashes);
    }
    let (k, _) = maxpow2(hi - lo);
    let (mut p, th, rest);
    if n < lo + k {
        let (pp, h1) = leaf_proof(lo, lo + k, n, hashes);
        let (t, h2) = sub_tree_hash(lo + k, hi, h1);
        (p, th, rest) = (pp, t, h2);
    } else {
        let (t, h1) = sub_tree_hash(lo, lo + k, hashes);
        let (pp, h2) = leaf_proof(lo + k, hi, n, h1);
        (p, th, rest) = (pp, t, h2);
    }
    p.push(th);
    (p, rest)
}

/// The inclusion proof of leaf `n` in the tree of the first `t` leaves.
pub fn prove_inclusion(t: u64, n: u64, r: &(impl HashReader + ?Sized)) -> Result<Vec<Hash>> {
    if n >= t {
        return Err(TlogError::BadIndex(format!(
            "leaf {n} is not in a tree of {t}"
        )));
    }
    let mut need = Vec::new();
    leaf_proof_index(0, t, n, &mut need);
    if need.is_empty() {
        return Ok(Vec::new());
    }
    let hashes = r.read_hashes(&need)?;
    Ok(leaf_proof(0, t, n, &hashes).0)
}

fn run_inclusion(p: &[Hash], lo: u64, hi: u64, n: u64, leaf: Hash) -> Result<Hash> {
    if lo + 1 == hi {
        return if p.is_empty() {
            Ok(leaf)
        } else {
            Err(TlogError::ProofFailed)
        };
    }
    let Some((last, rest)) = p.split_last() else {
        return Err(TlogError::ProofFailed);
    };
    let (k, _) = maxpow2(hi - lo);
    if n < lo + k {
        Ok(node_hash(&run_inclusion(rest, lo, lo + k, n, leaf)?, last))
    } else {
        Ok(node_hash(last, &run_inclusion(rest, lo + k, hi, n, leaf)?))
    }
}

/// Check that leaf `n`, with hash `leaf`, is in the tree of `t` leaves
/// whose root is `root`.
pub fn check_inclusion(proof: &[Hash], t: u64, root: &Hash, n: u64, leaf: &Hash) -> Result<()> {
    if n >= t {
        return Err(TlogError::ProofFailed);
    }
    if run_inclusion(proof, 0, t, n, *leaf)? == *root {
        Ok(())
    } else {
        Err(TlogError::ProofFailed)
    }
}

fn tree_proof_index(lo: u64, hi: u64, n: u64, need: &mut Vec<u64>) {
    if n == hi {
        if lo != 0 {
            sub_tree_index(lo, hi, need);
        }
        return;
    }
    let (k, _) = maxpow2(hi - lo);
    if n <= lo + k {
        tree_proof_index(lo, lo + k, n, need);
        sub_tree_index(lo + k, hi, need);
    } else {
        sub_tree_index(lo, lo + k, need);
        tree_proof_index(lo + k, hi, n, need);
    }
}

fn tree_proof(lo: u64, hi: u64, n: u64, hashes: &[Hash]) -> (Vec<Hash>, &[Hash]) {
    if n == hi {
        if lo == 0 {
            // Exactly the old tree, whose root the verifier has.
            return (Vec::new(), hashes);
        }
        let (th, rest) = sub_tree_hash(lo, hi, hashes);
        return (vec![th], rest);
    }
    let (k, _) = maxpow2(hi - lo);
    let (mut p, th, rest);
    if n <= lo + k {
        let (pp, h1) = tree_proof(lo, lo + k, n, hashes);
        let (t, h2) = sub_tree_hash(lo + k, hi, h1);
        (p, th, rest) = (pp, t, h2);
    } else {
        let (t, h1) = sub_tree_hash(lo, lo + k, hashes);
        let (pp, h2) = tree_proof(lo + k, hi, n, h1);
        (p, th, rest) = (pp, t, h2);
    }
    p.push(th);
    (p, rest)
}

/// The consistency proof that the tree of `n` leaves is a prefix of the
/// tree of `t`.
pub fn prove_consistency(t: u64, n: u64, r: &(impl HashReader + ?Sized)) -> Result<Vec<Hash>> {
    if n < 1 || n > t {
        return Err(TlogError::BadIndex(format!(
            "no consistency proof from {n} to {t}"
        )));
    }
    let mut need = Vec::new();
    tree_proof_index(0, t, n, &mut need);
    if need.is_empty() {
        return Ok(Vec::new());
    }
    let hashes = r.read_hashes(&need)?;
    Ok(tree_proof(0, t, n, &hashes).0)
}

fn run_consistency(p: &[Hash], lo: u64, hi: u64, n: u64, old: Hash) -> Result<(Hash, Hash)> {
    if n == hi {
        if lo == 0 {
            return if p.is_empty() {
                Ok((old, old))
            } else {
                Err(TlogError::ProofFailed)
            };
        }
        return match p {
            [h] => Ok((*h, *h)),
            _ => Err(TlogError::ProofFailed),
        };
    }
    let Some((last, rest)) = p.split_last() else {
        return Err(TlogError::ProofFailed);
    };
    let (k, _) = maxpow2(hi - lo);
    if n <= lo + k {
        let (oh, th) = run_consistency(rest, lo, lo + k, n, old)?;
        Ok((oh, node_hash(&th, last)))
    } else {
        let (oh, th) = run_consistency(rest, lo + k, hi, n, old)?;
        Ok((node_hash(last, &oh), node_hash(last, &th)))
    }
}

/// Check that the tree of `n` leaves with root `old_root` is a prefix of
/// the tree of `t` leaves with root `root`.
pub fn check_consistency(
    proof: &[Hash],
    t: u64,
    root: &Hash,
    n: u64,
    old_root: &Hash,
) -> Result<()> {
    if n < 1 || n > t {
        return Err(TlogError::ProofFailed);
    }
    let (oh, th) = run_consistency(proof, 0, t, n, *old_root)?;
    if oh == *old_root && th == *root {
        Ok(())
    } else {
        Err(TlogError::ProofFailed)
    }
}

// ----------------------------------------------------------------- tiles

/// A tile (C2SP tlog-tiles, height 8): level `level`'s hashes for leaves
/// from `n`·256, `width` of them (256 when full).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Tile {
    pub level: u32,
    pub n: u64,
    pub width: u32,
}

/// A tile index as a path: three-digit groups, all but the last with an
/// `x`, as `x001/x234/067` for 1234067.
pub fn index_path(n: u64) -> String {
    let mut groups = Vec::new();
    let mut m = n;
    loop {
        groups.push(m % 1000);
        m /= 1000;
        if m == 0 {
            break;
        }
    }
    groups.reverse();
    let last = groups.len() - 1;
    groups
        .iter()
        .enumerate()
        .map(|(i, g)| {
            if i < last {
                format!("x{g:03}")
            } else {
                format!("{g:03}")
            }
        })
        .collect::<Vec<_>>()
        .join("/")
}

/// The index a path names (the inverse of [`index_path`]).
pub fn parse_index_path(path: &str) -> Option<u64> {
    let parts: Vec<&str> = path.split('/').collect();
    let mut n: u64 = 0;
    for (i, p) in parts.iter().enumerate() {
        let digits = if i + 1 < parts.len() {
            p.strip_prefix('x')?
        } else {
            p
        };
        if digits.len() != 3 || !digits.bytes().all(|c| c.is_ascii_digit()) {
            return None;
        }
        n = n.checked_mul(1000)?.checked_add(digits.parse().ok()?)?;
    }
    Some(n)
}

impl Tile {
    /// `tile/<L>/<N>[.p/<W>]`.
    pub fn path(&self) -> String {
        format!(
            "tile/{}/{}{}",
            self.level,
            index_path(self.n),
            self.partial()
        )
    }

    /// The entry bundle beside a level-0 tile: `tile/entries/<N>[.p/<W>]`.
    pub fn entries_path(&self) -> String {
        format!("tile/entries/{}{}", index_path(self.n), self.partial())
    }

    fn partial(&self) -> String {
        if (self.width as u64) < TILE_WIDTH {
            format!(".p/{}", self.width)
        } else {
            String::new()
        }
    }

    /// The tile a path names (`<L>/<N>[.p/<W>]` after `tile/`).
    pub fn parse(path: &str) -> Option<Tile> {
        let (level, rest) = path.split_once('/')?;
        let level: u32 = level.parse().ok()?;
        let (index, width) = match rest.split_once(".p/") {
            Some((i, w)) => {
                let w: u32 = w.parse().ok()?;
                if w == 0 || w as u64 >= TILE_WIDTH {
                    return None;
                }
                (i, w)
            }
            None => (rest, TILE_WIDTH as u32),
        };
        Some(Tile {
            level,
            n: parse_index_path(index)?,
            width,
        })
    }

    /// The tile holding the stored hash at `index`, and the byte range its
    /// hash comes from in the tile's data.
    pub fn for_index(index: u64) -> (Tile, usize, usize) {
        let (level, mut n) = split_stored_hash_index(index);
        let tl = level / TILE_HEIGHT;
        let within = level - tl * TILE_HEIGHT;
        let tn = (n << within) >> TILE_HEIGHT;
        n -= (tn << TILE_HEIGHT) >> within;
        let width = ((n + 1) << within) as u32;
        let tile = Tile {
            level: tl,
            n: tn,
            width,
        };
        (
            tile,
            ((n << within) * 32) as usize,
            (((n + 1) << within) * 32) as usize,
        )
    }

    /// The tile's data: its hashes, read from stored order.
    pub fn read_data(&self, r: &(impl HashReader + ?Sized)) -> Result<Vec<u8>> {
        let start = self.n << TILE_HEIGHT;
        let indexes: Vec<u64> = (0..self.width as u64)
            .map(|i| stored_hash_index(TILE_HEIGHT * self.level, start + i))
            .collect();
        Ok(r.read_hashes(&indexes)?.concat())
    }

    /// The stored hash at `index` from this tile's data.
    pub fn hash_at(&self, data: &[u8], index: u64) -> Result<Hash> {
        if self.width == 0
            || self.width as u64 > TILE_WIDTH
            || data.len() < self.width as usize * 32
        {
            return Err(TlogError::Read(format!("tile {} is short", self.path())));
        }
        let (t, start, end) = Tile::for_index(index);
        if t.level != self.level || t.n != self.n || t.width > self.width {
            return Err(TlogError::Read(format!(
                "stored hash {index} is not in tile {}",
                self.path()
            )));
        }
        Ok(tile_hash(&data[start..end]))
    }

    /// The tiles a tree that grows from `old` to `new` leaves writes, full
    /// ones and the new partial ones.
    pub fn new_tiles(old: u64, new: u64) -> Vec<Tile> {
        let mut tiles = Vec::new();
        let mut level = 0u32;
        while level < 8 && (new >> (TILE_HEIGHT * level)) > 0 {
            let old_n = old >> (TILE_HEIGHT * level);
            let new_n = new >> (TILE_HEIGHT * level);
            if old_n != new_n {
                for n in (old_n >> TILE_HEIGHT)..(new_n >> TILE_HEIGHT) {
                    tiles.push(Tile {
                        level,
                        n,
                        width: TILE_WIDTH as u32,
                    });
                }
                let n = new_n >> TILE_HEIGHT;
                let w = new_n - (n << TILE_HEIGHT);
                if w > 0 {
                    tiles.push(Tile {
                        level,
                        n,
                        width: w as u32,
                    });
                }
            }
            level += 1;
        }
        tiles
    }
}

fn tile_hash(data: &[u8]) -> Hash {
    if data.len() == 32 {
        let mut h = [0u8; 32];
        h.copy_from_slice(data);
        return h;
    }
    let half = data.len() / 2;
    node_hash(&tile_hash(&data[..half]), &tile_hash(&data[half..]))
}

// ----------------------------------------------------- notes, checkpoints

/// One signature line of a note: `— <name> <base64(key hash || sig)>`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NoteSignature {
    pub name: String,
    pub key_hash: [u8; 4],
    pub sig: Vec<u8>,
}

/// A C2SP signed note: its text and its signature lines.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Note {
    /// The text, ending with a newline.
    pub text: String,
    pub sigs: Vec<NoteSignature>,
}

/// Signature types in a note's key hash (C2SP signed-note).
const SIG_ED25519: u8 = 0x01;
/// Oxygen's composite Ed25519 + ML-DSA-65 signature (spec §14.8).
const SIG_COMPOSITE: u8 = 0x4f;

fn key_hash(name: &str, sig_type: u8, key: &[u8]) -> [u8; 4] {
    let mut h = Sha256::new();
    h.update(name.as_bytes());
    h.update(b"\n");
    h.update([sig_type]);
    h.update(key);
    let d = h.finalize();
    [d[0], d[1], d[2], d[3]]
}

/// What a composite signature of a note signs (domain `checkpoint`).
fn note_target(text: &str) -> ObjectRef {
    let mut h = blake3::Hasher::new();
    h.update(b"oxygen-tlog-note\0");
    h.update(text.as_bytes());
    ObjectRef(*h.finalize().as_bytes())
}

fn valid_name(name: &str) -> bool {
    !name.is_empty() && !name.contains(|c: char| c.is_whitespace() || c == '+')
}

impl Note {
    /// The note as served: the text, a blank line, the signature lines.
    pub fn encode(&self) -> String {
        let mut out = self.text.clone();
        out.push('\n');
        for s in &self.sigs {
            let mut b = s.key_hash.to_vec();
            b.extend_from_slice(&s.sig);
            out.push_str(&format!(
                "\u{2014} {} {}\n",
                s.name,
                crate::dsse::base64(&b)
            ));
        }
        out
    }

    pub fn parse(s: &str) -> Result<Note> {
        let bad = |w: &str| TlogError::BadNote(w.to_string());
        let split = s
            .rfind("\n\n")
            .ok_or_else(|| bad("no blank line before the signatures"))?;
        let text = &s[..split + 1];
        if text.chars().any(|c| c.is_control() && c != '\n') {
            return Err(bad("control characters in the text"));
        }
        let mut sigs = Vec::new();
        for line in s[split + 2..].lines() {
            let rest = line
                .strip_prefix("\u{2014} ")
                .ok_or_else(|| bad("a signature line without its dash"))?;
            let (name, b64) = rest
                .split_once(' ')
                .ok_or_else(|| bad("a signature line without a key"))?;
            let b =
                crate::dsse::base64_decode(b64).ok_or_else(|| bad("a signature is not base64"))?;
            if b.len() < 5 || !valid_name(name) {
                return Err(bad("a malformed signature line"));
            }
            sigs.push(NoteSignature {
                name: name.to_string(),
                key_hash: [b[0], b[1], b[2], b[3]],
                sig: b[4..].to_vec(),
            });
        }
        if sigs.is_empty() {
            return Err(bad("no signatures"));
        }
        Ok(Note {
            text: text.to_string(),
            sigs,
        })
    }

    /// Sign as `name` with `identity`'s key: the Ed25519 line note tools
    /// read, and the composite line that keeps it post-quantum.
    pub fn sign(text: &str, name: &str, identity: &Identity, sk: &SecretKey) -> Result<Note> {
        if !valid_name(name) {
            return Err(TlogError::BadNote(format!(
                "{name:?} cannot name a note's key"
            )));
        }
        if !text.ends_with('\n') || text.contains("\n\n") {
            return Err(TlogError::BadNote(
                "the text must end with one newline and hold no blank line".into(),
            ));
        }
        let ed = NoteSignature {
            name: name.to_string(),
            key_hash: key_hash(name, SIG_ED25519, &identity.ed25519_pk),
            sig: sk.sign_ed25519(text.as_bytes()).to_vec(),
        };
        let composite = NoteSignature {
            name: name.to_string(),
            key_hash: key_hash(name, SIG_COMPOSITE, &identity.encode()),
            sig: cbor::encode(
                &sk.sign(Domain::Checkpoint, &identity.hash(), &note_target(text))
                    .to_value(),
            ),
        };
        Ok(Note {
            text: text.to_string(),
            sigs: vec![ed, composite],
        })
    }

    /// Both of `name`'s signatures by `identity` verify (a note signed
    /// with Ed25519 only is not enough).
    pub fn verify(&self, name: &str, identity: &Identity) -> Result<()> {
        let find = |t: u8, key: &[u8]| {
            let h = key_hash(name, t, key);
            self.sigs.iter().find(|s| s.name == name && s.key_hash == h)
        };
        let ed = find(SIG_ED25519, &identity.ed25519_pk)
            .ok_or_else(|| TlogError::BadSignature(format!("no Ed25519 signature by {name}")))?;
        identity
            .verify_ed25519(self.text.as_bytes(), &ed.sig)
            .map_err(|_| {
                TlogError::BadSignature(format!("{name}'s Ed25519 signature does not verify"))
            })?;
        let c = find(SIG_COMPOSITE, &identity.encode())
            .ok_or_else(|| TlogError::BadSignature(format!("no composite signature by {name}")))?;
        let sig = cbor::decode(&c.sig)
            .map_err(|e| e.to_string())
            .and_then(|v| Signature::from_value(&v).map_err(|e| e.to_string()))
            .map_err(|e| TlogError::BadSignature(format!("{name}'s composite signature: {e}")))?;
        verify(identity, &sig, Domain::Checkpoint, &note_target(&self.text)).map_err(|e| {
            TlogError::BadSignature(format!("{name}'s composite signature does not verify: {e}"))
        })
    }
}

/// A checkpoint (C2SP tlog-checkpoint): the log's origin, size and root.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Checkpoint {
    /// The log's name: the hub's host and `/log`.
    pub origin: String,
    pub size: u64,
    pub root: Hash,
    /// Further lines, each without its newline.
    pub extensions: Vec<String>,
}

impl Checkpoint {
    pub fn text(&self) -> String {
        let mut t = format!(
            "{}\n{}\n{}\n",
            self.origin,
            self.size,
            crate::dsse::base64(&self.root)
        );
        for e in &self.extensions {
            t.push_str(e);
            t.push('\n');
        }
        t
    }

    pub fn parse(text: &str) -> Result<Checkpoint> {
        let bad = |w: &str| TlogError::BadNote(format!("checkpoint: {w}"));
        if !text.ends_with('\n') {
            return Err(bad("no final newline"));
        }
        let mut lines = text[..text.len() - 1].split('\n');
        let origin = lines
            .next()
            .filter(|o| !o.is_empty())
            .ok_or_else(|| bad("no origin"))?;
        let size = lines
            .next()
            .and_then(|s| {
                (s == "0" || !s.starts_with('0'))
                    .then(|| s.parse().ok())
                    .flatten()
            })
            .ok_or_else(|| bad("no tree size"))?;
        let root = lines
            .next()
            .and_then(crate::dsse::base64_decode)
            .and_then(|b| <Hash>::try_from(b).ok())
            .ok_or_else(|| bad("no root hash"))?;
        Ok(Checkpoint {
            origin: origin.to_string(),
            size,
            root,
            extensions: lines.map(String::from).collect(),
        })
    }

    /// Signed by the log's key, named by its origin.
    pub fn sign(&self, identity: &Identity, sk: &SecretKey) -> Result<Note> {
        Note::sign(&self.text(), &self.origin, identity, sk)
    }

    /// The checkpoint a note carries, once the log's key (`identity`)
    /// signed it for `origin`.
    pub fn verify(note: &Note, origin: &str, identity: &Identity) -> Result<Checkpoint> {
        note.verify(origin, identity)?;
        let c = Checkpoint::parse(&note.text)?;
        if c.origin != origin {
            return Err(TlogError::BadNote(format!(
                "checkpoint of {}, not of {origin}",
                c.origin
            )));
        }
        Ok(c)
    }
}

// ------------------------------------------------------------- witnesses

/// C2SP tlog-cosignature: a witness's Ed25519 cosignature.
const SIG_COSIGNATURE: u8 = 0x04;
/// Oxygen's composite cosignature beside it (spec §14.8).
const SIG_COSIG_COMPOSITE: u8 = 0x4e;

/// What a cosignature signs: `cosignature/v1`, the witness's time in
/// seconds, then the checkpoint's text.
fn cosigned_message(text: &str, time: u64) -> String {
    format!("cosignature/v1\ntime {time}\n{text}")
}

fn cosig_target(message: &str) -> ObjectRef {
    let mut h = blake3::Hasher::new();
    h.update(b"oxygen-tlog-cosig\0");
    h.update(message.as_bytes());
    ObjectRef(*h.finalize().as_bytes())
}

/// A witness's cosignature of a checkpoint's text at `time` (seconds):
/// the C2SP cosignature/v1 line, and a composite line that keeps it
/// post-quantum. Each carries the time before the signature.
pub fn cosign(
    text: &str,
    name: &str,
    witness: &Identity,
    sk: &SecretKey,
    time: u64,
) -> Result<Vec<NoteSignature>> {
    if !valid_name(name) {
        return Err(TlogError::BadNote(format!(
            "{name:?} cannot name a witness"
        )));
    }
    let message = cosigned_message(text, time);
    let mut ed = time.to_be_bytes().to_vec();
    ed.extend_from_slice(&sk.sign_ed25519(message.as_bytes()));
    let mut composite = time.to_be_bytes().to_vec();
    composite.extend_from_slice(&cbor::encode(
        &sk.sign(Domain::Checkpoint, &witness.hash(), &cosig_target(&message))
            .to_value(),
    ));
    Ok(vec![
        NoteSignature {
            name: name.to_string(),
            key_hash: key_hash(name, SIG_COSIGNATURE, &witness.ed25519_pk),
            sig: ed,
        },
        NoteSignature {
            name: name.to_string(),
            key_hash: key_hash(name, SIG_COSIG_COMPOSITE, &witness.encode()),
            sig: composite,
        },
    ])
}

impl Note {
    /// The time `witness` (named `name`) cosigned this note, once both its
    /// lines verify and agree on the time.
    pub fn cosigned_by(&self, name: &str, witness: &Identity) -> Result<u64> {
        let find = |t: u8, key: &[u8]| {
            let h = key_hash(name, t, key);
            self.sigs.iter().find(|s| s.name == name && s.key_hash == h)
        };
        let time_of = |sig: &[u8]| -> Result<(u64, Vec<u8>)> {
            if sig.len() < 9 {
                return Err(TlogError::BadSignature(format!(
                    "{name}'s cosignature is short"
                )));
            }
            let mut t = [0u8; 8];
            t.copy_from_slice(&sig[..8]);
            Ok((u64::from_be_bytes(t), sig[8..].to_vec()))
        };
        let ed = find(SIG_COSIGNATURE, &witness.ed25519_pk)
            .ok_or_else(|| TlogError::BadSignature(format!("no cosignature by {name}")))?;
        let (time, sig) = time_of(&ed.sig)?;
        let message = cosigned_message(&self.text, time);
        witness
            .verify_ed25519(message.as_bytes(), &sig)
            .map_err(|_| {
                TlogError::BadSignature(format!("{name}'s cosignature does not verify"))
            })?;
        let c = find(SIG_COSIG_COMPOSITE, &witness.encode()).ok_or_else(|| {
            TlogError::BadSignature(format!("no composite cosignature by {name}"))
        })?;
        let (ctime, csig) = time_of(&c.sig)?;
        if ctime != time {
            return Err(TlogError::BadSignature(format!(
                "{name}'s two cosignatures disagree on the time"
            )));
        }
        let sig = cbor::decode(&csig)
            .map_err(|e| e.to_string())
            .and_then(|v| Signature::from_value(&v).map_err(|e| e.to_string()))
            .map_err(|e| TlogError::BadSignature(format!("{name}'s composite cosignature: {e}")))?;
        verify(witness, &sig, Domain::Checkpoint, &cosig_target(&message)).map_err(|e| {
            TlogError::BadSignature(format!(
                "{name}'s composite cosignature does not verify: {e}"
            ))
        })?;
        Ok(time)
    }
}

/// A C2SP tlog-witness `add-checkpoint` request: the size of the last
/// checkpoint the witness cosigned for this log, the consistency proof
/// from it, and the new checkpoint note.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AddCheckpoint {
    pub old_size: u64,
    pub proof: Vec<Hash>,
    pub note: String,
}

impl AddCheckpoint {
    pub fn encode(&self) -> String {
        let mut out = format!("old {}\n", self.old_size);
        for h in &self.proof {
            out.push_str(&crate::dsse::base64(h));
            out.push('\n');
        }
        out.push('\n');
        out.push_str(&self.note);
        out
    }

    pub fn parse(body: &str) -> Result<AddCheckpoint> {
        let bad = |w: &str| TlogError::BadNote(format!("add-checkpoint: {w}"));
        let (head, note) = body
            .split_once("\n\n")
            .ok_or_else(|| bad("no blank line before the checkpoint"))?;
        let mut lines = head.split('\n');
        let old_size = lines
            .next()
            .and_then(|l| l.strip_prefix("old "))
            .and_then(|n| n.parse().ok())
            .ok_or_else(|| bad("no old size"))?;
        let mut proof = Vec::new();
        for l in lines {
            let h = crate::dsse::base64_decode(l)
                .and_then(|b| <Hash>::try_from(b).ok())
                .ok_or_else(|| bad("a proof line is not a hash"))?;
            proof.push(h);
        }
        Ok(AddCheckpoint {
            old_size,
            proof,
            note: note.to_string(),
        })
    }
}

/// What a witness answers.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Witnessed {
    /// Cosigned: the checkpoint, and the cosignature lines to return.
    Cosigned {
        checkpoint: Checkpoint,
        lines: Vec<NoteSignature>,
    },
    /// The request's old size is not the witness's: it answers with its own
    /// (409, so the log retries with a proof from there).
    Conflict(u64),
}

/// Why a witness refused.
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
pub enum WitnessError {
    /// Not signed by the log's key (403).
    #[error("{0}")]
    Unsigned(String),
    /// The checkpoint does not extend what the witness cosigned (422).
    #[error("{0}")]
    Inconsistent(String),
    /// Malformed (400).
    #[error("{0}")]
    Bad(String),
}

/// A witness: its name in cosignatures, and its key.
pub struct WitnessKey<'a> {
    pub name: &'a str,
    pub identity: &'a Identity,
    pub sk: &'a SecretKey,
}

/// A witness's decision (C2SP tlog-witness) on `req` for the log named
/// `origin` with key `log_key`, whose last cosigned checkpoint was
/// `latest` (size and root): cosign when the new checkpoint verifies and
/// extends it, as `me` at `now` (seconds).
pub fn witness(
    req: &AddCheckpoint,
    origin: &str,
    log_key: &Identity,
    latest: Option<(u64, Hash)>,
    me: &WitnessKey,
    now: u64,
) -> std::result::Result<Witnessed, WitnessError> {
    let note = Note::parse(&req.note).map_err(|e| WitnessError::Bad(e.to_string()))?;
    let cp = Checkpoint::verify(&note, origin, log_key)
        .map_err(|e| WitnessError::Unsigned(e.to_string()))?;
    let (old, old_root) = latest.unwrap_or((0, empty_root()));
    if req.old_size != old {
        return Ok(Witnessed::Conflict(old));
    }
    if cp.size < old {
        return Err(WitnessError::Bad(format!(
            "a checkpoint of {} entries is older than the {old} cosigned",
            cp.size
        )));
    }
    let consistent = match (old, cp.size == old) {
        (0, _) => req.proof.is_empty(),
        (_, true) => req.proof.is_empty() && cp.root == old_root,
        _ => check_consistency(&req.proof, cp.size, &cp.root, old, &old_root).is_ok(),
    };
    if !consistent {
        return Err(WitnessError::Inconsistent(format!(
            "the checkpoint of {} entries does not extend the one of {old} cosigned",
            cp.size
        )));
    }
    let lines = cosign(&note.text, me.name, me.identity, me.sk, now)
        .map_err(|e| WitnessError::Bad(e.to_string()))?;
    Ok(Witnessed::Cosigned {
        checkpoint: cp,
        lines,
    })
}

// -------------------------------------------------------- integrated time

/// How far a claimed time may stray from an integrated time before it is
/// noted (spec §14.8, *Integrated time*): ten minutes, in milliseconds.
pub const TIME_TOLERANCE_MS: u64 = 10 * 60 * 1000;

impl Note {
    /// The witnesses among `trusted` (name and identity) whose
    /// cosignatures of this note verify, with their times in seconds.
    /// Lines by anyone else are ignored.
    pub fn cosignatures(&self, trusted: &[(String, Identity)]) -> Vec<(String, u64)> {
        trusted
            .iter()
            .filter_map(|(n, id)| self.cosigned_by(n, id).ok().map(|t| (n.clone(), t)))
            .collect()
    }
}

/// When witnesses first saw a log entry (spec §14.8): an upper bound on
/// when what it logs was signed, by a clock neither its signer nor the
/// log chose.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Integrated {
    /// The earliest trusted cosignature's time, in seconds.
    pub time: u64,
    /// The witness that made it.
    pub witness: String,
    /// The size of the checkpoint it cosigned.
    pub size: u64,
}

impl Integrated {
    /// The time in milliseconds, as Oxygen's other times are.
    pub fn ms(&self) -> u64 {
        self.time.saturating_mul(1000)
    }
}

/// Entry `index` (`entry`, its bytes)'s integrated time: the earliest time
/// a witness in `trusted` cosigned one of `cosigned` (checkpoint notes,
/// each with the entry's inclusion proof against it) that `log_key`
/// signed for `origin` and that includes the entry. A note that does not
/// verify, or does not include the entry, counts for nothing; `Err` says
/// why no time could be read.
pub fn integrated_time(
    entry: &[u8],
    index: u64,
    cosigned: &[(&str, &[Hash])],
    origin: &str,
    log_key: &Identity,
    trusted: &[(String, Identity)],
) -> std::result::Result<Integrated, String> {
    if cosigned.is_empty() {
        return Err("no witness has cosigned a checkpoint holding it yet".into());
    }
    let leaf = leaf_hash(entry);
    let mut best: Option<Integrated> = None;
    let mut why = String::new();
    for (text, proof) in cosigned {
        let checked = Note::parse(text)
            .and_then(|n| Checkpoint::verify(&n, origin, log_key).map(|c| (n, c)))
            .and_then(|(n, c)| {
                check_inclusion(proof, c.size, &c.root, index, &leaf)?;
                Ok((n, c))
            });
        let (note, cp) = match checked {
            Ok(x) => x,
            Err(e) => {
                why = format!("a cosigned checkpoint served for it does not hold it ({e})");
                continue;
            }
        };
        let times = note.cosignatures(trusted);
        if times.is_empty() {
            why = format!(
                "the checkpoint of {} entries holding it is cosigned by no witness this user trusts",
                cp.size
            );
            continue;
        }
        for (witness, time) in times {
            if best.as_ref().is_none_or(|b| time < b.time) {
                best = Some(Integrated {
                    time,
                    witness,
                    size: cp.size,
                });
            }
        }
    }
    best.ok_or(why)
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A log in memory: its stored hashes, grown leaf by leaf.
    fn grow(leaves: u64) -> (Vec<Hash>, Vec<Hash>) {
        let mut stored: Vec<Hash> = Vec::new();
        let mut leaf_hashes = Vec::new();
        for n in 0..leaves {
            let h = leaf_hash(format!("entry {n}").as_bytes());
            leaf_hashes.push(h);
            let add = stored_hashes_for_leaf(n, h, &stored).unwrap();
            assert_eq!(stored.len() as u64, stored_hash_index(0, n));
            stored.extend(add);
            assert_eq!(stored.len() as u64, stored_hash_count(n + 1));
        }
        (stored, leaf_hashes)
    }

    /// RFC 6962's MTH, straight from its definition.
    fn mth(leaves: &[Hash]) -> Hash {
        match leaves.len() {
            0 => empty_root(),
            1 => leaves[0],
            n => {
                let (k, _) = maxpow2(n as u64);
                node_hash(&mth(&leaves[..k as usize]), &mth(&leaves[k as usize..]))
            }
        }
    }

    #[test]
    fn stored_indexes_round_trip() {
        for level in 0..6 {
            for n in 0..300 {
                let i = stored_hash_index(level, n);
                assert_eq!(split_stored_hash_index(i), (level, n));
            }
        }
    }

    #[test]
    fn roots_match_rfc_6962_and_every_proof_verifies() {
        let (stored, leaves) = grow(140);
        for t in 1..=140u64 {
            let root = tree_hash(t, &stored).unwrap();
            assert_eq!(root, mth(&leaves[..t as usize]), "root of {t}");
            for n in 0..t {
                let p = prove_inclusion(t, n, &stored).unwrap();
                check_inclusion(&p, t, &root, n, &leaves[n as usize]).unwrap();
                // Another leaf, another tree, a tampered path: refused.
                let other = (n + 1) % t;
                if other != n {
                    assert!(check_inclusion(&p, t, &root, n, &leaves[other as usize]).is_err());
                }
                if let Some(first) = p.first() {
                    let mut bad = p.clone();
                    bad[0] = node_hash(first, first);
                    assert!(check_inclusion(&bad, t, &root, n, &leaves[n as usize]).is_err());
                }
                let old = n + 1;
                let old_root = tree_hash(old, &stored).unwrap();
                let c = prove_consistency(t, old, &stored).unwrap();
                check_consistency(&c, t, &root, old, &old_root).unwrap();
                if old < t {
                    let fork = node_hash(&old_root, &old_root);
                    assert!(
                        check_consistency(&c, t, &root, old, &fork).is_err(),
                        "a forked history"
                    );
                }
            }
        }
        assert_eq!(tree_hash(0, &stored).unwrap(), empty_root());
    }

    #[test]
    fn tiles_hold_the_stored_hashes() {
        let n = 70_000u64;
        let (stored, _) = grow(n);
        let tiles = Tile::new_tiles(0, n);
        // 273 full tiles of level 0 and a partial one, one full and one
        // partial at level 1, a partial at level 2.
        assert_eq!(tiles.iter().filter(|t| t.level == 0).count(), 274);
        assert_eq!(tiles.iter().filter(|t| t.level == 2).count(), 1);
        let datas: Vec<(Tile, Vec<u8>)> = tiles
            .iter()
            .map(|t| (*t, t.read_data(&stored).unwrap()))
            .collect();
        for (i, want) in stored.iter().enumerate().step_by(7) {
            let (t, ..) = Tile::for_index(i as u64);
            let (tile, data) = datas
                .iter()
                .find(|(d, _)| d.level == t.level && d.n == t.n && d.width >= t.width)
                .expect("the tile holding it was written");
            assert_eq!(
                tile.hash_at(data, i as u64).unwrap(),
                *want,
                "stored hash {i}"
            );
        }
        // Growing writes only what changed.
        let grown = Tile::new_tiles(n, n + 300);
        assert!(grown.iter().all(|t| t.level > 0 || t.n >= n / 256));
    }

    #[test]
    fn tile_paths() {
        assert_eq!(index_path(1_234_067), "x001/x234/067");
        assert_eq!(index_path(5), "005");
        assert_eq!(index_path(1000), "x001/000");
        assert_eq!(parse_index_path("x001/x234/067"), Some(1_234_067));
        assert_eq!(parse_index_path("x001/234/067"), None);
        let t = Tile {
            level: 1,
            n: 1234,
            width: 17,
        };
        assert_eq!(t.path(), "tile/1/x001/234.p/17");
        assert_eq!(Tile::parse("1/x001/234.p/17"), Some(t));
        assert_eq!(
            Tile {
                level: 0,
                n: 3,
                width: 256
            }
            .entries_path(),
            "tile/entries/003"
        );
        assert_eq!(Tile::parse("0/003.p/256"), None, "a full tile has no .p");
    }

    #[test]
    fn entries_and_bundles_round_trip() {
        let e = Entry {
            kind: "ref".into(),
            repo: [7; 16],
            object: ObjectRef([1; 32]),
            signers: vec![ObjectRef([2; 32])],
            received: 1_792_000_000_000,
        };
        assert_eq!(Entry::decode(&e.encode()).unwrap(), e);
        let b = encode_bundle(&[e.encode(), b"x".to_vec()]).unwrap();
        assert_eq!(decode_bundle(&b).unwrap(), vec![e.encode(), b"x".to_vec()]);
        assert!(decode_bundle(&b[..b.len() - 1]).is_err());
        assert_eq!(e.leaf_hash(), leaf_hash(&e.encode()));
    }

    #[test]
    fn a_witness_cosigns_what_extends_what_it_saw_and_nothing_else() {
        let log_sk = SecretKey::generate();
        let log = log_sk.identity("log", "[email protected]", 1);
        let w_sk = SecretKey::generate();
        let w = w_sk.identity("witness", "[email protected]", 1);
        let origin = "hub.example/log";
        let (stored, _) = grow(40);
        let note_of = |n: u64| {
            Checkpoint {
                origin: origin.into(),
                size: n,
                root: tree_hash(n, &stored).unwrap(),
                extensions: vec![],
            }
            .sign(&log, &log_sk)
            .unwrap()
            .encode()
        };
        let ask = |old: u64, n: u64, latest: Option<(u64, Hash)>| {
            let proof = if old == 0 || old == n {
                vec![]
            } else {
                prove_consistency(n, old, &stored).unwrap()
            };
            let req = AddCheckpoint {
                old_size: old,
                proof,
                note: note_of(n),
            };
            let req = AddCheckpoint::parse(&req.encode()).unwrap();
            let me = WitnessKey {
                name: "w.example",
                identity: &w,
                sk: &w_sk,
            };
            witness(&req, origin, &log, latest, &me, 1_792_300_000)
        };
        // First sight, then a later checkpoint with its proof.
        let Ok(Witnessed::Cosigned { checkpoint, lines }) = ask(0, 10, None) else {
            panic!()
        };
        let mut note = Note::parse(&note_of(10)).unwrap();
        note.sigs.extend(lines);
        let back = Note::parse(&note.encode()).unwrap();
        assert_eq!(back.cosigned_by("w.example", &w).unwrap(), 1_792_300_000);
        assert!(
            back.cosigned_by("w.example", &log).is_err(),
            "another witness's key"
        );
        let latest = Some((10, checkpoint.root));
        assert!(matches!(
            ask(10, 40, latest),
            Ok(Witnessed::Cosigned { .. })
        ));
        // The log's idea of what the witness saw is wrong: told the size.
        assert_eq!(ask(5, 40, latest), Ok(Witnessed::Conflict(10)));
        // A fork: what the witness saw is not a prefix.
        let forked = Some((10, [9; 32]));
        assert!(matches!(
            ask(10, 40, forked),
            Err(WitnessError::Inconsistent(_))
        ));
        // Signed by someone else.
        let req = AddCheckpoint {
            old_size: 0,
            proof: vec![],
            note: note_of(10),
        };
        assert!(matches!(
            witness(
                &req,
                origin,
                &w,
                None,
                &WitnessKey {
                    name: "w.example",
                    identity: &w,
                    sk: &w_sk
                },
                1
            ),
            Err(WitnessError::Unsigned(_))
        ));
    }

    #[test]
    fn checkpoints_are_signed_twice_and_checked() {
        let sk = SecretKey::generate();
        let hub = sk.identity("oxygenhub.io", "[email protected]", 1);
        let (stored, _) = grow(10);
        let c = Checkpoint {
            origin: "oxygenhub.io/log".into(),
            size: 10,
            root: tree_hash(10, &stored).unwrap(),
            extensions: vec![],
        };
        let note = c.sign(&hub, &sk).unwrap();
        let served = note.encode();
        assert!(served.starts_with("oxygenhub.io/log\n10\n"));
        assert_eq!(served.matches("\n\u{2014} oxygenhub.io/log ").count(), 2);
        let back = Note::parse(&served).unwrap();
        assert_eq!(
            Checkpoint::verify(&back, "oxygenhub.io/log", &hub).unwrap(),
            c
        );
        // Another key, another origin, a changed size, a lost line: refused.
        let other_sk = SecretKey::generate();
        let other = other_sk.identity("x", "x@x", 1);
        assert!(Checkpoint::verify(&back, "oxygenhub.io/log", &other).is_err());
        assert!(Checkpoint::verify(&back, "elsewhere/log", &hub).is_err());
        let forged = Note {
            text: back.text.replace("\n10\n", "\n11\n"),
            ..back.clone()
        };
        assert!(Checkpoint::verify(&forged, "oxygenhub.io/log", &hub).is_err());
        let ed_only = Note {
            sigs: vec![back.sigs[0].clone()],
            ..back.clone()
        };
        assert!(
            matches!(Checkpoint::verify(&ed_only, "oxygenhub.io/log", &hub), Err(TlogError::BadSignature(m)) if m.contains("composite")),
            "the post-quantum line is required"
        );
        // The Ed25519 line is a standard note signature over the text.
        let h = key_hash("oxygenhub.io/log", SIG_ED25519, &hub.ed25519_pk);
        assert_eq!(back.sigs[0].key_hash, h);
        assert!(hub
            .verify_ed25519(back.text.as_bytes(), &back.sigs[0].sig)
            .is_ok());
    }

    #[test]
    fn an_entry_is_integrated_when_a_trusted_witness_first_cosigned_it() {
        let log_sk = SecretKey::generate();
        let log = log_sk.identity("log", "[email protected]", 1);
        let origin = "hub.example/log";
        let witness = |name: &str| {
            let sk = SecretKey::generate();
            (name.to_string(), sk.identity(name, "[email protected]", 1), sk)
        };
        let (a, b, c) = (
            witness("a.example"),
            witness("b.example"),
            witness("c.example"),
        );
        let trusted = vec![(a.0.clone(), a.1.clone()), (b.0.clone(), b.1.clone())];
        // A log of 40 real entries, so `integrated_time` hashes the leaf.
        let leaf_bytes = |n: u64| {
            Entry {
                kind: "ref".into(),
                repo: [n as u8; 16],
                object: ObjectRef([n as u8; 32]),
                signers: vec![],
                received: n,
            }
            .encode()
        };
        let mut stored: Vec<Hash> = Vec::new();
        for n in 0..40 {
            let add = stored_hashes_for_leaf(n, leaf_hash(&leaf_bytes(n)), &stored).unwrap();
            stored.extend(add);
        }
        // Checkpoint `n`, cosigned by each of `by` at its time.
        type W = (String, Identity, SecretKey);
        let cosigned = |n: u64, by: &[(&W, u64)]| {
            let cp = Checkpoint {
                origin: origin.into(),
                size: n,
                root: tree_hash(n, &stored).unwrap(),
                extensions: vec![],
            };
            let mut note = cp.sign(&log, &log_sk).unwrap();
            for ((name, id, sk), t) in by {
                note.sigs
                    .extend(cosign(&note.text, name, id, sk, *t).unwrap());
            }
            note.encode()
        };
        let proof = |n: u64| prove_inclusion(n, 7, &stored).unwrap();
        let entry = leaf_bytes(7);
        let time = |served: &[(String, Vec<Hash>)]| {
            let s: Vec<(&str, &[Hash])> = served
                .iter()
                .map(|(n, p)| (n.as_str(), p.as_slice()))
                .collect();
            integrated_time(&entry, 7, &s, origin, &log, &trusted)
        };

        // One checkpoint, two witnesses: the earlier cosignature.
        let one = cosigned(10, &[(&a, 1_792_300_050), (&b, 1_792_300_020)]);
        let got = time(&[(one.clone(), proof(10))]).unwrap();
        assert_eq!(
            (got.time, got.witness.as_str(), got.size),
            (1_792_300_020, "b.example", 10)
        );
        assert_eq!(got.ms(), 1_792_300_020_000);
        // Witnesses that first cosigned different checkpoints: the
        // earliest of all.
        let later = cosigned(20, &[(&a, 1_792_300_010)]);
        let got = time(&[(later.clone(), proof(20)), (one.clone(), proof(10))]).unwrap();
        assert_eq!(
            (got.time, got.witness.as_str()),
            (1_792_300_010, "a.example")
        );

        // A witness this user does not trust is no witness, however early.
        let stranger = cosigned(10, &[(&c, 1)]);
        let err = time(&[(stranger, proof(10))]).unwrap_err();
        assert!(err.contains("no witness this user trusts"), "{err}");
        // A forged cosignature under a trusted name: c's key signed it.
        let forged = cosigned(10, &[(&(a.0.clone(), c.1.clone(), c.2.clone()), 1)]);
        assert!(time(&[(forged.clone(), proof(10))]).is_err());
        // Beside a real one, it changes nothing.
        let got = time(&[(forged, proof(10)), (one.clone(), proof(10))]).unwrap();
        assert_eq!(got.time, 1_792_300_020);
        // A time moved after cosigning no longer verifies.
        let mut moved = Note::parse(&one).unwrap();
        for s in moved.sigs.iter_mut().filter(|s| s.name == "b.example") {
            s.sig[..8].copy_from_slice(&1u64.to_be_bytes());
        }
        let got = time(&[(moved.encode(), proof(10))]).unwrap();
        assert_eq!(got.witness, "a.example", "b's lines no longer verify");

        // A checkpoint that does not hold the entry, a proof for another
        // size, another log's key: no time.
        let early = cosigned(5, &[(&a, 1)]);
        assert!(time(&[(early, proof(10))]).is_err());
        assert!(time(&[(one.clone(), proof(20))]).is_err());
        let other_sk = SecretKey::generate();
        let other = other_sk.identity("x", "x@x", 1);
        let s = [(one.as_str(), proof(10))];
        let s: Vec<(&str, &[Hash])> = s.iter().map(|(n, p)| (*n, p.as_slice())).collect();
        assert!(integrated_time(&entry, 7, &s, origin, &other, &trusted).is_err());
        assert!(integrated_time(&entry, 7, &s, "elsewhere/log", &log, &trusted).is_err());
        assert!(integrated_time(&leaf_bytes(8), 7, &s, origin, &log, &trusted).is_err());
        // Nothing served.
        assert!(time(&[]).unwrap_err().contains("no witness has cosigned"));
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Coverage / crates/oxy-core/src/tlog.rs 92.4%

Keyboard
