Transparency log

Deep dive

How it works

Parts:

• Log — keeps the RFC 6962 tree, signs heads; untrusted.
• Submitter — sends an entry, gets an inclusion promise (SCT) or an index.
• Client — accepts a statement only with an inclusion proof against a trusted head.
• Monitor — reads every new entry, checks heads and consistency.
• Witness — cosigns a head only if it extends the last head it cosigned.

1. Submit. The log appends leaf SHA-256(0x00 || entry) and returns an SCT: a promise to include it within the Maximum Merge Delay (MMD).
2. Head. Sign (size, root, time): an STH, or a checkpoint in tile logs; one head covers many entries.
3. Witness. The log sends old size, consistency proof and new checkpoint; the witness verifies, stores, cosigns.
4. Client. Recompute the root from the entry and its sibling hashes (inclusion proof); compare with a cosigned head.
5. Monitor. Verify the head signature and a consistency proof from the last kept head, read the new entries (RFC 9162 §8.2).

submitter --entry--> LOG --checkpoint + consistency proof--> witnesses
                      |                                          | cosigned
        monitors <----+---- tiles (static files) -----+          v
      (read all, prove prefix)                        +--> client: inclusion proof vs cosigned head

An inclusion proof binds an entry to a root; a consistency proof binds two roots by a prefix relation, so rewritten history cannot prove consistency with the old head. Showing client A one head and monitor B another of the same size (split view) needs two incompatible signatures; a witness signs only successors. Two signed heads with no provable prefix relation are evidence of misbehaviour (§8.3). An SCT is only a promise: a TLS client audits it against a head dated after SCT timestamp plus MMD.

Tiles and checkpoints. A checkpoint is a signed note: origin line, decimal size, base64 root, signature lines. Tile logs serve the tree as static files: a full tile is 256 consecutive hashes (8,192 B) of one level at tile/<L>/<N>, the right edge a partial .p/<W>. Clients fetch tiles and compute proofs; hashing stays RFC 6962.

Code

Log storing every complete subtree; proofs per RFC 9162 §2.1.3.1, §2.1.4.1; verification as inner plus border part.

use sha2::{Digest, Sha256};
pub type H = [u8; 32];

fn hash(prefix: u8, a: &[u8], b: &[u8]) -> H {
    Sha256::new().chain_update([prefix]).chain_update(a).chain_update(b).finalize().into()
}
pub fn leaf(d: &[u8]) -> H { hash(0x00, d, &[]) }
pub fn node(l: &H, r: &H) -> H { hash(0x01, l, r) }
fn split(n: usize) -> usize { n.next_power_of_two() / 2 } // largest power of two < n

#[derive(Default)]
pub struct Log { lv: Vec<Vec<H>> } // lv[l][i] = hash of leaves [i*2^l, (i+1)*2^l)

impl Log {
    pub fn append(&mut self, data: &[u8]) {
        let mut x = leaf(data);
        for l in 0.. {
            if self.lv.len() == l { self.lv.push(vec![]); }
            self.lv[l].push(x);
            let n = self.lv[l].len();
            if n % 2 == 1 { return; } // right sibling not there yet
            x = node(&self.lv[l][n - 2], &self.lv[l][n - 1]);
        }
    }
    fn mth(&self, lo: usize, hi: usize) -> H { // MTH(D[lo:hi]), stored where complete
        let n = hi - lo;
        if n == 0 { return Sha256::digest(b"").into(); }
        if n.is_power_of_two() { return self.lv[n.trailing_zeros() as usize][lo / n]; }
        let k = lo + split(n);
        node(&self.mth(lo, k), &self.mth(k, hi))
    }
    pub fn root(&self, size: usize) -> H { self.mth(0, size) } // any past size
    pub fn inclusion(&self, m: usize, size: usize) -> Vec<H> {
        let (mut lo, mut hi, mut p) = (0, size, vec![]);
        while hi - lo > 1 {
            let k = lo + split(hi - lo);
            if m < k { p.push(self.mth(k, hi)); hi = k } else { p.push(self.mth(lo, k)); lo = k }
        }
        p.reverse(); p
    }
    // 0 < m <= size
    pub fn consistency(&self, m: usize, size: usize) -> Vec<H> {
        let (mut lo, mut hi, mut left_edge, mut p) = (0, size, true, vec![]);
        while hi != m {
            let k = lo + split(hi - lo);
            if m <= k { p.push(self.mth(k, hi)); hi = k } else { p.push(self.mth(lo, k)); lo = k; left_edge = false }
        }
        if !left_edge { p.push(self.mth(lo, hi)); } // a subtree that is not the old root itself
        p.reverse(); p
    }
}

fn decomp(index: u64, size: u64) -> (usize, usize) { // (inner steps, border steps)
    let inner = (64 - (index ^ (size - 1)).leading_zeros()) as usize;
    (inner, index.checked_shr(inner as u32).unwrap_or(0).count_ones() as usize)
}
fn chain_inner(mut r: H, proof: &[H], index: u64, left_only: bool) -> H {
    for (i, p) in proof.iter().enumerate() {
        if (index >> i) & 1 == 1 { r = node(p, &r); } else if !left_only { r = node(&r, p); }
    }
    r
}
fn chain_border(r: H, proof: &[H]) -> H { proof.iter().fold(r, |r, p| node(p, &r)) }

pub fn verify_inclusion(lh: H, index: u64, size: u64, proof: &[H], root: &H) -> bool {
    if index >= size { return false; }
    let (inner, border) = decomp(index, size);
    proof.len() == inner + border
        && chain_border(chain_inner(lh, &proof[..inner], index, false), &proof[inner..]) == *root
}
/// (size1, root1) is a prefix of (size2, root2)
pub fn verify_consistency(size1: u64, size2: u64, proof: &[H], root1: &H, root2: &H) -> bool {
    if size1 == size2 || size1 == 0 { return proof.is_empty() && (size1 == 0 || root1 == root2); }
    if size1 > size2 || proof.is_empty() { return false; }
    let (inner, border) = decomp(size1 - 1, size2);
    let shift = size1.trailing_zeros() as usize;
    let inner = inner - shift;
    let (seed, start) = if size1 == 1 << shift { (*root1, 0) } else { (proof[0], 1) };
    if proof.len() != start + inner + border { return false; }
    let proof = &proof[start..];
    let mask = (size1 - 1) >> shift;
    let h1 = chain_border(chain_inner(seed, &proof[..inner], mask, true), &proof[inner..]);
    let h2 = chain_border(chain_inner(seed, &proof[..inner], mask, false), &proof[inner..]);
    h1 == *root1 && h2 == *root2
}

#[test]
fn proofs() {
    let mut log = Log::default();
    for i in 0..20u8 { log.append(&[i]); }
    for n in 1..=20 {
        let root = log.root(n);
        for i in 0..n {
            let p = log.inclusion(i, n);
            assert!(verify_inclusion(leaf(&[i as u8]), i as u64, n as u64, &p, &root));
            assert!(!verify_inclusion(leaf(b"x"), i as u64, n as u64, &p, &root)); // tampered leaf
        }
        for m in 1..=n {
            let p = log.consistency(m, n);
            assert!(verify_consistency(m as u64, n as u64, &p, &log.root(m), &root));
            if m < n { assert!(!verify_consistency(m as u64, n as u64, &p, &leaf(b"x"), &root)); } // rewritten prefix
        }
    }
}

Run-checked: the CT reference vectors (eight leaves, their roots), the RFC 9162 §2.1.5 paths, all sizes up to 70, altered input rejected, agreement with literal transcriptions of §2.1.3.2 and §2.1.4.2. Needs sha2 = "0.10".

Complexity and constants

• Proofs: inclusion at most ceil(log2 n) hashes, consistency at most ceil(log2 n) + 1 (§2.1.4.1); at 1M, 20 hashes = 640 B.
• Measured (M4 Pro, release, sha2 0.10.9, 1M entries of 42 B, several runs): append 360-450 ns per entry; inclusion proof about 1.4 µs; consistency (m = 524,289) 1.1-1.5 µs; verify 4.8 µs and 5.0-5.4 µs.
• Store: 64 B per entry with every node kept; a tile log keeps 32 B per entry plus 1/256 of that per level above.
• One proof from tiles: one tile per level, three at 1M, order of 17 KB (my arithmetic from the tile rule) against 640 B, but immutable and cacheable.
• Cost drivers: the log pays fsync, one signature per head and bytes served; a monitor pays the download of new entries.

Efficiency

Cost: per entry about 0.4 µs of hashing and node storage (measured) plus its share of one durable write and one signature per head (Ed25519: order of tens of µs); a client check is one fetch and about 5 µs. Bound: operator fsync and bandwidth; monitor download.

Levers:

• Batch entries per head — one fsync and one signature per batch (group commit) — always; delay is the batch window, bounded by the MMD in CT.
• Static tiles instead of a proof API — no per-request compute, long-lived cache headers (tlog-tiles) — many readers; only /checkpoint is short-lived.
• Store complete subtrees or tiles — proof in about 1.4 µs instead of rehashing 10^6 leaves (order of 0.4 s, from the append loop) — any log with readers.
• Witness and monitor keep only the last head — O(1) state, one consistency proof (at most 21 hashes at 1M) per update (tlog-witness) — recurring checks.

Naive → standard → state of the art:

• Naive: sign a hash of the whole list, verifier replays it · O(n) per check.
• Standard: RFC 6962 tree, proof API, STH per batch · 640 B proof, about 5 µs to verify at 1M.
• State of the art: tile log, witness-cosigned checkpoints (Tessera, Sunlight, Rekor v2) · static 8,192 B files, clients build proofs.

Implementation notes

• Persist entries (fsync) before signing a head covering them; a head naming lost entries looks like tampering.
• Never sign a head inconsistent with an earlier one; a witness checks the old size and stores the new head atomically, or concurrent requests can roll it back (tlog-witness).
• Sign the log identity: RFC 6962's TreeHeadSignature lacks it (static CT spec), hence the checkpoint origin line.
• Verifiers: exact proof length, reject index >= size; canonicalise entries before hashing; require a cosignature quorum and a freshness bound.

Pitfalls

• A proof checked against a head fetched from the same log proves nothing.
• An SCT is not inclusion: before the MMD has passed the entry may not be in the tree.
• Without the 0x00/0x01 prefixes an inner node can pose as an entry, see tamper-evident audit log.
• Logs are public and permanent: logged certificates publish their names; never log secrets or personal data.

Variants and alternatives

In production

• Certificate Transparency: RFC 6962 and static-CT logs; Chrome requires certificates to carry SCTs satisfying its CT policy (SCTs).
• Go checksum database sum.golang.org: default GOSUMDB; the go command checks hashes of modules missing from go.sum there.
• Sigstore Rekor for signing events (supply chain, v2 is rekor-tiles); Android Binary Transparency for Pixel firmware.
• WhatsApp key transparency (2023); a public witness network cosigns checkpoints.

Implementations

Sources

• Laurie, Langley, Kasper, RFC 6962, Certificate Transparency, 2013. rfc
• Laurie, Messeri, Stradling, RFC 9162, Certificate Transparency Version 2.0, 2021. rfc
• C2SP: tlog-tiles · tlog-checkpoint · signed-note · tlog-witness · static-ct-api
• Russ Cox, Transparent Logs for Skeptical Clients, 2019. post
• Melara et al., CONIKS: Bringing Key Transparency to End Users, USENIX Security 2015. eprint
• Chrome CT policy · Go modules reference · Android Binary Transparency · IETF KEYTRANS draft
• Lawlor, Lewi, Deploying key transparency at WhatsApp, Engineering at Meta, 2023. post