crates/oxy-core/src/tlog.rs at e5f8eb2a2006 · andymccall/oxygen

# e5f8eb2a2006 oxygen / crates / oxy-core / src / tlog.rs
36.1 KiB · Rust · last changed The transparency log as a library (tlog, spec §14.8) 18 days ago source blame history raw
//! 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)
    }
}

#[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 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());
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
