Tamper-evident audit log

Deep dive

How it works

Parts:

• Leaf hash — SHA-256(0x00 || entry); binds one canonical entry.
• Merkle tree — node hashes SHA-256(0x01 || left || right); appends never change a full left subtree.
• Signed tree head (STH) — signed (size, root, time) per batch; the published commitment.
• Inclusion proof — O(log n) sibling hashes showing an entry is under a head.
• Consistency proof — O(log n) hashes showing a newer head extends an older one.
• Auditors / witnesses — keep and compare heads to expose split views.

1. Hashes (RFC 6962): leaf = SHA-256(0x00 || entry), node = SHA-256(0x01 || left || right); the prefixes stop an interior node posing as an entry.
2. Shape: split n leaves at k, the largest power of two below n. Appending never changes a full left subtree, so old proofs stay valid.
3. Signed tree head (STH): sign (size, root, time) with the log key and publish (tile logs: a checkpoint).
4. Inclusion proof for leaf i: sibling hashes up the path. The verifier recomputes the root and compares it with a trusted head.
5. Consistency proof (old size m, new size n): the subtree hashes that rebuild both roots. A rewritten prefix cannot produce both.
6. Gossip or anchor: auditors keep every head they saw and compare across observers (else a log can show different histories to different people: split view).

size 5:             root
                  /      \
            h(0..3)      leaf4      proof for leaf 2 = [leaf3, h(0,1), leaf4]
            /     \
        h(0,1)   h(2,3)

Code

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

fn hash(prefix: u8, a: &[u8], b: &[u8]) -> H { // SHA-256(prefix || a || b) without a concat buffer
    let mut s = Sha256::new();
    s.update([prefix]); s.update(a); s.update(b);
    s.finalize().into()
}
pub fn leaf(data: &[u8]) -> H { hash(0x00, data, &[]) }
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 (n >= 2)

/// MTH over leaf hashes (RFC 6962 2.1)
pub fn root(l: &[H]) -> H {
    match l.len() { 0 => Sha256::digest(b"").into(), 1 => l[0], n => { let k = split(n); node(&root(&l[..k]), &root(&l[k..])) } }
}

/// Audit path for leaf m (RFC 6962 2.1.1), bottom-up
pub fn inclusion(m: usize, l: &[H]) -> Vec<H> {
    if l.len() == 1 { return vec![]; }
    let k = split(l.len());
    if m < k { let mut p = inclusion(m, &l[..k]); p.push(root(&l[k..])); p }
    else { let mut p = inclusion(m - k, &l[k..]); p.push(root(&l[..k])); p }
}

/// RFC 9162 8.3.2
pub fn verify_inclusion(lh: H, idx: u64, size: u64, proof: &[H], want: &H) -> bool {
    if idx >= size { return false; }
    let (mut f, mut s, mut r) = (idx, size - 1, lh);
    for p in proof {
        if s == 0 { return false; }
        if f & 1 == 1 || f == s {
            r = node(p, &r);
            while f & 1 == 0 && f != 0 { f >>= 1; s >>= 1; }
        } else { r = node(&r, p); }
        f >>= 1; s >>= 1;
    }
    s == 0 && r == *want
}

/// Proof that the first m leaves are a prefix of l (RFC 6962 2.1.2)
pub fn consistency(m: usize, l: &[H]) -> Vec<H> { sub(m, l, true) }
fn sub(m: usize, l: &[H], b: bool) -> Vec<H> {
    let n = l.len();
    if m == n { return if b { vec![] } else { vec![root(l)] }; }
    let k = split(n);
    if m <= k { let mut p = sub(m, &l[..k], b); p.push(root(&l[k..])); p }
    else { let mut p = sub(m - k, &l[k..], false); p.push(root(&l[..k])); p }
}

/// Tree (first, r1) is a prefix of tree (second, r2) (RFC 9162 8.4.2)
pub fn verify_consistency(first: u64, second: u64, proof: &[H], r1: &H, r2: &H) -> bool {
    if first == 0 || first > second { return first == 0 && proof.is_empty(); }
    if first == second { return proof.is_empty() && r1 == r2; }
    let mut pr = proof.to_vec();
    if first.is_power_of_two() { pr.insert(0, *r1); }
    if pr.is_empty() { return false; }
    let (mut f, mut s) = (first - 1, second - 1);
    while f & 1 == 1 { f >>= 1; s >>= 1; }
    let (mut fr, mut sr) = (pr[0], pr[0]);
    for c in &pr[1..] {
        if s == 0 { return false; }
        if f & 1 == 1 || f == s {
            fr = node(c, &fr); sr = node(c, &sr);
            while f & 1 == 0 && f != 0 { f >>= 1; s >>= 1; }
        } else { sr = node(&sr, c); }
        f >>= 1; s >>= 1;
    }
    s == 0 && fr == *r1 && sr == *r2
}

#[test]
fn proofs_verify() {
    assert_eq!(Sha256::digest(b"abc")[..4], [0xba, 0x78, 0x16, 0xbf]);
    assert_eq!(leaf(b"")[..4], [0x6e, 0x34, 0x0b, 0x9c]); // RFC 6962 one-leaf tree
    let l: Vec<H> = (0..70u32).map(|i| leaf(&i.to_be_bytes())).collect();
    for n in 1..=l.len() {
        let r = root(&l[..n]);
        for i in 0..n { assert!(verify_inclusion(l[i], i as u64, n as u64, &inclusion(i, &l[..n]), &r)); }
        for m in 1..=n { assert!(verify_consistency(m as u64, n as u64, &consistency(m, &l[..n]), &root(&l[..m]), &r)); }
    }
}

consistency(m, l) needs 0 < m <= l.len(). Run-checked: SHA-256 abc, the RFC 6962 one- and 8-leaf roots, all proofs for sizes up to 70, and rejection of altered proofs, wrong leaves and rewritten prefixes. Needs sha2 = "0.10".

Complexity and constants

• Append: one leaf hash plus on average one node hash (n leaves have n-1 nodes). Keep only the right edge (at most log2 n hashes); the STH root folds it.
• A node input is 65 bytes = two SHA-256 blocks; a leaf up to 55 bytes is one. Measured (Apple M4 Pro, release, sha2 0.10.9): 42-byte leaf 131 ns, node 257 ns.
• Proof: ceil(log2 n) x 32 B. At 1M leaves: 20 hashes, 640 B, verify 4.8 µs; consistency (m = 524,289) 21 hashes, 5.0 µs.
• Storage, every node kept: 64 B per entry; tile logs keep 8,192 B tiles of 256 hashes.

Efficiency

Cost: a ~100-byte entry costs about 0.4 µs of hashing (M4 Pro, measured) plus its share of one fsync (about 4 ms here) and of one signature per batch (Ed25519: order of tens of µs). Bound: fsync latency, then hashing.

Levers:

• Group commit, one fsync and one signature per batch — per entry 4035 µs → 43 µs (batch 100) → 6.3 µs (batch 1000), measured here — always; adds batch delay.
• Store computed nodes or tiles — O(log n) reads per proof instead of a 280 ms recompute at 1M leaves (measured) — any log with readers.
• Hardware SHA-2 — 2.97 GB/s vs about 0.5 GB/s for the sha2 default build (openssl speed, measured) — beyond order of 10^5 entries/s.
• Static tiles, clients build proofs — no per-request hashing, CDN-cacheable — public logs.
• Keep the last trusted head, fetch only consistency proofs — O(log n) per update — monitors.

Naive → standard → state of the art:

• Naive: hash chain, fsync per entry, verifier replays all · O(n) hashes to verify, ~4 ms per append.
• Standard: RFC 6962 tree, STH per batch, group commit · 640 B proof, about 5 µs verify at 1M entries.
• State of the art: tile log, witness-cosigned checkpoints (Tessera, Sunlight, Rekor v2) · static 8,192 B tiles.

Implementation notes

• Write the entry, fsync, and only then sign and publish a head covering it; a head promising entries lost in a crash looks like tampering. Keep the signing key off the log host.
• Never sign a smaller size, or an equal size with another root. Put a log identifier in the signed data so heads cannot be replayed across logs.
• Canonicalise entries before hashing (fixed field order, length prefixes).

Pitfalls

• Without the 0x00/0x01 prefixes an inner node can be submitted as a leaf (second preimage).
• Duplicating the last node on odd levels (Bitcoin) lets different leaf lists share a root (CVE-2012-2459); RFC 6962 splitting does not.
• A proof checked against a root fetched from the same log proves nothing; compare with a stored or witness-signed head.
• Cutting the newest entries is invisible without an earlier head kept elsewhere: anchor with witness cosigning or trusted timestamping.
• Never log raw secrets or personal data: the log cannot forget.

Variants and alternatives

In production

• Cloud infrastructure: AWS CloudTrail log file integrity validation delivers hourly digest files with a hash of each log file, signed with SHA-256 with RSA.
• Web PKI: Certificate Transparency logs (RFC 6962); Chrome enforces SCTs in its CT policy; static-CT logs (Sunlight).
• Software distribution: the Go module checksum database; Sigstore Rekor (v1 on Trillian, v2 on Tessera); npm provenance is logged in a public transparency ledger.
• Government and health: Estonia's eHealth Foundation partnered with Guardtime in 2016 to protect patient records with hash-tree (KSI) integrity.
• Host logs: systemd-journald Forward Secure Sealing.

Implementations

Sources

• RFC 6962, Certificate Transparency, 2013. rfc
• RFC 9162, Certificate Transparency Version 2.0, 2021 (verification algorithms used above). rfc
• Scott A. Crosby, Dan S. Wallach, Efficient Data Structures for Tamper-Evident Logging, USENIX Security 2009. paper
• Bruce Schneier, John Kelsey, Secure Audit Logs to Support Computer Forensics, ACM TISSEC 2(2), 1999. doi
• Giorgia Azzurra Marson, Bertram Poettering, Practical Secure Logging: Seekable Sequential Key Generators, ESORICS 2013. eprint
• C2SP, tlog-tiles and tlog-checkpoint specs. tiles · checkpoint
• AWS, Validating CloudTrail log file integrity. docs
• Chrome, Certificate Transparency Policy. policy
• Estonian World, Estonia to protect patient records with Guardtime blockchain technology, 2016. article