The transparency log as a library (tlog, spec §14.8) e5f8eb2a2006

//! 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());

    }

}

 "const-oid",

 "sha2",

sha2 = "0.11"

    /// A transparency log's checkpoint note (§14.8).

    Checkpoint,

            Domain::Checkpoint => "checkpoint",

pub mod tlog;

domain  = "change" | "attest" | "policy" | "certificate" | "grant" | "checkpoint"

### 14.8 The transparency log

A host keeps an append-only log of what it accepts, so it cannot show one history to some readers and another to others (oxygenhub#238, oxygenhub docs/transparency.md). Each accepted signed object (a reference or tag attestation, a seal, a rotation or revocation, a receipt, an approval, a policy, an identity, a certificate, an acceptance) becomes one entry, in the order the host accepted it:

```

Entry {

  version   [0]: 1

  kind      [1]: text           // "ref", "seal", "tag", "rotate", "revoke", "receipt", "approval",

                                //  "policy", "identity", "certificate", "accepted"

  repo      [2]: bytes(16)      // the repository's id; zero for identities

  object    [3]: ObjectRef      // the attestation, policy, identity or certificate

  signers   [4]: [KeyId]        // the keys whose signatures the host checked

  received  [5]: u64            // the host's clock, milliseconds (its claim)

}

```

**The tree** is RFC 6962's Merkle tree over the entries, with BLAKE3: a leaf's hash is `BLAKE3("oxygen-tlog-leaf\0" || cbor(Entry))`, an interior node's `BLAKE3("oxygen-tlog-node\0" || left || right)`, and the empty tree's root `BLAKE3("")`. A tree of n > 1 leaves splits at k, the largest power of two below n. Inclusion and consistency proofs are RFC 6962's (§2.1.1, §2.1.2), their hashes listed from the leaf upwards.

**Stored order.** Every hash of the tree is stored once, as soon as it is known: adding leaf n stores its hash and then the hash of each subtree it completes (one per trailing 1 bit of n). The hash of tree level L at position n is therefore at stored index `i(L, n)`, where n is first replaced L times by 2n+1, then i = n + ⌊n/2⌋ + ⌊n/4⌋ + … + L. The store is append-only.

**Tiles** (C2SP tlog-tiles, height 8). Level-L tile N holds the hashes of tree level 8L for leaves from N·256 on, 32 bytes each: 256 of them when full, fewer in a partial tile. Its path is `tile/<L>/<N>`, with `.p/<W>` appended for a partial tile of W hashes; N is written in groups of three digits, every group but the last prefixed `x` (1234067 is `x001/x234/067`). The entries of level-0 tile N are at `tile/entries/<N>[.p/<W>]`, each as a big-endian u16 length and its bytes. Full tiles never change.

**Checkpoints** (C2SP tlog-checkpoint) are C2SP signed notes. The text is the origin (the host's name and `/log`), the tree size in decimal and the root in base64, each line ending in a newline. It is signed twice under the origin's name:

- with the host key's Ed25519 half, as a standard note signature (type 0x01: key hash = SHA-256(name ‖ "\n" ‖ 0x01 ‖ public key)[:4], signature over the text), which note tools read;

- with the composite key, as type 0x4f (key hash over the identity object's bytes): the CBOR of a composite Signature in domain `checkpoint` over `BLAKE3("oxygen-tlog-note\0" || text)`.

A reader accepts a checkpoint only when both verify, so the log stays post-quantum. Which witnesses must cosign it, and how a client uses inclusion proofs, are §16's and oxygenhub docs/transparency.md's.