Tamper-Evident Audit Logs: Hash Chains, Merkle Trees, and External Anchoring

Date: September 6, 2026 · Author: Dmitrii Zatona 

TL;DR

• “Immutable” covers four designs: retention and WORM storage, a hash chain, a Merkle tree with signed checkpoints, and an external anchor. Only the last three give a third party evidence (Section 2).
• A hash chain proves one entry unchanged to a holder of a trusted later head; whoever holds the chain can regenerate the tail (Section 3).
• A Merkle tree with signed checkpoints gives logarithmic inclusion proofs and, with a verified consistency proof, append-only history relative to an earlier checkpoint. A checkpoint that never leaves the operator protects nobody (Section 4).
• An RFC 3161 token or a Bitcoin commitment bounds when a checkpoint existed; renewal and captured validation data are operating tasks (Section 5).
• The mechanisms are small. Keys, checkpoint distribution, retention, migration, monitoring and restore are where logs fail their audits (Sections 7 and 8).

A tamper-evident audit log is one whose modification can be detected by someone who did not write it. That definition excludes an audit table whose only protection is access control. A row in a database with a timestamp column records an event; it does not show a reader, later, that the row is the one that was written, that no row before it was removed, or that the sequence is the one the system produced. Three mechanisms do show those things: a hash chain, a Merkle tree with signed checkpoints, and an external time-stamp, or anchor, over the tree’s root. They are not interchangeable. Each proves a different thing, to a different party, at a different cost.

This article is the implementation view of a cryptographically verifiable audit trail: the data structures, the proof algorithms, working Rust for each, and the operating decisions that decide whether the guarantees hold in practice. A companion piece, the AI agent audit trail, owns the agent record: what goes into one step and what court rules and the EU AI Act ask of it. This article owns the log mechanics underneath, and the companion refers here for them. Where a specification is named as a worked example it is the ATL protocol, which I author; nothing below depends on it.

1. The question the auditor asks

The question arrives in four forms, from a customer’s security review or a SOC 2 auditor, and the four are not the same question.

How do you know a record was not edited? This asks for integrity of one entry.

How do you know nothing was deleted from the middle? This asks for integrity of the sequence.

How do you know the log you show me today is the log you had last quarter? An append-only history, relative to a state the auditor already holds.

How do you know when it was written? Time from a clock the operator does not control.

An answer of “access controls” addresses none of the four, because the party the auditor is asking about is the one holding the access controls. Access control over the write path and the signing key remains required evidence in its own right; what follows addresses what access control cannot show. Two further questions arrive with these four and no mechanism below answers them. How long do you keep it, and can you produce last year’s log? is a retention question, and the storage settings of Section 2’s level 0 are its answer. Is every in-scope system writing to this log? is a coverage question, and Section 8 explains why no proof over the log can settle it. The rest of this article assigns one mechanism to each of the four and states what each leaves open.

2. Four meanings of “immutable” for an audit log

The word covers four designs that differ in who can verify what: a retention policy, a hash chain, a Merkle tree with signed checkpoints, and an external anchor. Two terms in the table are defined in Section 4 and glossed here: a checkpoint is the operator’s signature over the tree’s root and its size, in some formats with a time; a consistency proof is the evidence that a later tree extends an earlier one.

Level 0 needs precise statement because storage products describe themselves in the same word. AWS documents S3 Object Lock as “a write-once-read-many (WORM) model to store objects,” and in compliance mode a protected version “can’t be overwritten or deleted by any user, including the root user” for the retention period; the page states that the only way to remove such an object early is to delete the AWS account (Object Lock documentation ). In governance mode users can’t overwrite or delete a version “unless they have special permissions,” and the page names the permission. Both modes stop deletion, and level 0 is the correct answer to the auditor’s retention question. Neither mode gives a third party a way to check, from a copy of the log, that the copy is complete or unchanged. That is the difference between retention and evidence.

The three levels above 0 build on each other. Level 2 replaces the chain’s pointer with a tree whose proofs are cheaper to check; level 3 binds level 2’s checkpoint to time.

3. Hash chain

Each entry stores the hash of the previous entry, and each entry’s own hash covers that pointer. Change any earlier entry and every hash after it stops matching what was stored.

use sha2::{Digest, Sha256};
 
type Hash = [u8; 32];
 
/// One audit entry as stored: the previous entry's hash is part of what this
/// entry's hash covers, so changing any earlier entry changes this one.
struct Entry {
    prev: Hash,
    body: Vec<u8>, // canonical bytes of the record (RFC 8785 for JSON)
}
 
fn entry_hash(e: &Entry) -> Hash {
    let mut h = Sha256::new();
    h.update(b"audit-entry-v1"); // domain separation: an entry hash is nothing else
    h.update(e.prev);
    h.update((e.body.len() as u64).to_le_bytes()); // length prefix: keeps the encoding unambiguous if fields change
    h.update(&e.body);
    h.finalize().into()
}
 
/// Verifying the chain means walking it from a hash you already trust.
fn verify_chain(entries: &[Entry], trusted_head: Hash) -> bool {
    let mut expected = [0u8; 32]; // genesis: the first entry's prev is all zeros
    for e in entries {
        if e.prev != expected {
            return false;
        }
        expected = entry_hash(e);
    }
    expected == trusted_head
}

Two details in that code carry weight. The domain-separation string puts entry hashes in their own input domain, apart from the leaf and node hashes of Section 4, so that a value hashed for one purpose cannot be presented as a value hashed for another. The length prefix keeps the encoding unambiguous if a variable-length field is ever added before body; with the fixed 32-byte prev shown here it is not yet needed, and it costs eight bytes. And verify_chain takes a trusted_head: a chain verifies against something the verifier already holds, and where that trusted head came from is the thing the chain cannot answer.

The chain answers the first two of the auditor’s four questions, to a reader who holds a later entry that was not tampered with. NIST’s 2006 log-management guide recommended the ingredient the chain is built from, a message digest per archived file “stored securely,” with the note that the original digests “should be protected from alteration” (NIST SP 800-92 , Section 3.2); the chain is what links those digests so that one protected head covers all of them. Schneier and Kelsey’s 1999 construction went further with evolving per-entry keys, so that an attacker who takes the machine at time t finds it “impossible to undetectably modify or destroy” entries written before t (Schneier and Kelsey, 1999 , abstract); the same paper is explicit that no measure protects entries written after the compromise. That property, forward integrity, belongs to their evolving-key scheme, not to the static-key design in this article.

The chain’s limit is the party that holds it. Crosby and Wallach’s model is an “untrusted logger” that can roll the log back and build a new fork; and, for the auditor’s third question, they note that schemes built on a hash chain “require auditors examine every intermediate event between snapshots” (Crosby and Wallach, 2009 , Sections 1 and 2.1.2). Checking today’s head against last quarter’s costs one hash per entry written since, a hundred million if that is the quarter’s volume. That cost is the practical reason to use a tree.

4. Merkle tree, signed checkpoints, and append-only history

4.1 The construction

RFC 9162 defines the tree used by Certificate Transparency, and the definition is over “a list of data entries,” not over certificates (RFC 9162 , Section 2.1.1). A leaf is HASH(0x00 || entry); an interior node is HASH(0x01 || left || right), where the split point k is the largest power of two smaller than the number of entries. The two prefixes are the domain separation of Section 3 in fixed form: a leaf can never be presented as a node. RFC 6962, the earlier version, used the same prefixes with SHA-256 fixed; the tree itself is unchanged between the two documents.

Two proofs come with the tree. An inclusion proof for entry m is the list of sibling hashes from that leaf to the root, at most one per level. A consistency proof between a tree of size n₁ and a later tree of size n₂ is the list of hashes that lets a verifier recompute both roots from a single pass, and RFC 9162 bounds its length: “The number of nodes in the resulting proof is bounded above by ceil(log2(n)) + 1” (Section 2.1.4.1). For a log of a hundred million entries that is at most 28 hashes.

4.2 What the verifier does: inclusion and consistency proofs

The inclusion check (Section 2.1.3.2) first rejects any leaf index that is not smaller than the tree size. It then keeps two counters, the leaf’s index and the last index in the tree, and a running hash that starts at the leaf. For each proof hash it fails if the last-index counter is already zero, and otherwise decides whether the sibling sits on the left or the right. Two things settle that: the low bit of the leaf counter, and whether the leaf counter has reached the last index. It then hashes accordingly with the 0x01 prefix; when the proof node was on the left only because the leaf counter equalled the last index, both counters are shifted until the leaf counter is odd or zero; then both counters shift one level up. It accepts only if it consumed every proof hash, the last-index counter reached zero, and the result equals the root in the checkpoint.

The consistency check (Section 2.1.4.2) runs one pass with two running hashes, one for the old root and one for the new. If the old tree was a complete power-of-two subtree, the proof carries nothing for it, and the verifier begins from the old root it already holds. Proof nodes that lie inside the old tree’s prefix update both running hashes; nodes to the right of the old tree update only the new one. It accepts only if the old running hash reproduces the old root the verifier already holds, the new one reproduces the new root in the new checkpoint, and every level was consumed. The proof is unique and minimal; the RFC’s own words are that it “outputs the (unique) minimal consistency proof” (Section 2.1.4).

Neither algorithm touches the database or the operator. The inclusion check takes the leaf hash (or the entry bytes to compute it), the leaf index, the tree size, the proof hashes, and the root from a checkpoint the verifier trusts. The consistency check takes the two tree sizes, the proof hashes, the old root the verifier already holds, and the new root from the new checkpoint.

4.3 In code

The example below is compiled against atl-core, the reference verification library for ATL, which exports the RFC 9162 tree and both proofs at its crate root. The crate has no single-part leaf helper (ATL’s leaf covers two hashes, Section 9), so the RFC leaf is written out.

use atl_core::{
    compute_root, generate_consistency_proof, generate_inclusion_proof, verify_consistency,
    verify_inclusion, Hash,
};
use sha2::{Digest, Sha256};
 
/// RFC 9162 leaf: the 0x00 prefix keeps a leaf from ever colliding with an
/// interior node, which is hashed with 0x01 (atl-core's `hash_children`).
fn leaf_hash(entry_bytes: &[u8]) -> Hash {
    let mut h = Sha256::new();
    h.update([0x00u8]);
    h.update(entry_bytes);
    h.finalize().into()
}
 
fn main() -> Result<(), Box<dyn std::error::Error>> {
    // The log at checkpoint time: leaf hashes in append order.
    let entries: Vec<&[u8]> = vec![b"{\"event\":\"login\"}", b"{\"event\":\"export\"}", b"{\"event\":\"delete\"}"];
    let mut leaves: Vec<Hash> = entries.iter().map(|e| leaf_hash(e)).collect();
    let old_root = compute_root(&leaves);
    let old_size = leaves.len() as u64;
 
    // Storage callback: level 0 is the leaves; returning None for higher
    // levels makes atl-core recompute interior nodes from the leaves.
    let by_level = |leaves: &Vec<Hash>| {
        let leaves = leaves.clone();
        move |level: u32, index: u64| -> Option<Hash> {
            if level == 0 { leaves.get(index as usize).copied() } else { None }
        }
    };
 
    // Inclusion: prove entry 1 is under old_root. The proof is at most one hash per level.
    let proof = generate_inclusion_proof(1, old_size, by_level(&leaves))?;
    assert!(verify_inclusion(&leaves[1], &proof, &old_root)?);
 
    // The log grows; a new checkpoint is signed over new_root.
    leaves.push(leaf_hash(b"{\"event\":\"login\"}"));
    leaves.push(leaf_hash(b"{\"event\":\"share\"}"));
    let new_root = compute_root(&leaves);
    let new_size = leaves.len() as u64;
 
    // Consistency: prove the tree at new_size extends the tree at old_size.
    // A holder of the old checkpoint needs only this proof and the new root.
    let consistency = generate_consistency_proof(old_size, new_size, by_level(&leaves))?;
    assert!(verify_consistency(&consistency, &old_root, &new_root)?);
 
    // A rewritten history fails: any old root other than the real one is rejected.
    assert!(!verify_consistency(&consistency, &[0xff; 32], &new_root)?);
    Ok(())
}

For the three-then-five-entry tree above, the inclusion proof is two hashes and the consistency proof four. A production log stores interior nodes so that get_node returns them at levels above zero instead of recomputing; the library uses stored nodes for aligned power-of-two subtrees when the callback supplies them and recomputes the rest from the leaves.

4.4 The checkpoint

A root by itself is a number. What makes it a commitment is a signature by the operator over the root and the tree size, in some formats with a time, issued on a schedule. RFC 9162 calls this the Signed Tree Head; its tree head carries “uint64 timestamp; uint64 tree_size; NodeHash root_hash” and an extensions vector, and the signature is computed over the whole tree head (Sections 4.9 and 4.10). The current transparency-log ecosystem uses a text form of the same thing: the C2SP checkpoint is “a signed note where the body is precisely formatted” as three lines, the log’s origin identifier, “the tree size, the ASCII decimal representation of the number of leaves,” and the base64 root hash (C2SP tlog-checkpoint ). ATL’s checkpoint is a fixed 98-byte binary blob with the same content plus an origin identifier, signed with Ed25519 by default (Section 9). The format matters less than one rule the three share and one the ecosystem adds around them.

The shared rule is that the operator signs each checkpoint and, in C2SP’s words, “MUST not sign any checkpoint which is inconsistent with any checkpoint it previously signed.” The added rule is that the checkpoint has to leave the operator; that is a design principle, and Sections 4.5 and 7 are about it. RFC 9162 requires the log to sign “the same Merkle Tree Hash with a fresh timestamp” when idle, so that a client always receives a head no older than the log’s declared merge delay (Section 4.10); read from the outside, that lets a monitor distinguish a quiet log from a stalled one. The same section caps the rate, because each signed head “could be used to mark individual clients”; for an internal audit log the cost of witnessing and anchoring each checkpoint is the other constraint on frequency.

Batching follows from this. Entries are appended continuously; a checkpoint is signed on a cadence, and an entry is committed to the log’s history only when a checkpoint covering it exists. Tessera, the successor to the Trillian log library, states the rule directly: “An entry is considered published once it is committed to by a published Checkpoint” (transparency-dev/tessera ). Four decisions follow for the write path.

• What the client holds before the checkpoint. A receipt, the self-contained evidence file a customer keeps for one entry, itemised in Section 7, arrives one of two ways: returned in two stages, or returned once the checkpoint exists. In the two-stage form the first stage is a signed acknowledgement from the operator, a promise to include the entry within a stated delay; it is evidence of the operator’s promise and nothing more, and the client has to know when to stop waiting. Sigstore’s Rekor v2 chose the second form and “now blocks on returning a response until a checkpoint has been published” (rekor-tiles client guidance ), and its write latency is its checkpoint cadence.
• Cadence. Blocking writes make write latency equal to checkpoint cadence, so a design that blocks signs checkpoints frequently and anchors on its own, slower schedule (Section 5). A count-based trigger under bursty load produces a checkpoint storm, and if every checkpoint is witnessed or anchored, a storm of those as well.
• Idempotency and lookup. A client that times out and retries must not create a duplicate leaf; submissions carry an idempotency key, and the log exposes a lookup by entry hash so that a client which crashed between stages can retrieve its receipt.
• Durability and the sequencer. An entry is durably persisted before any acknowledgement, and the log has one writer that assigns positions. That sequencer is a single point that needs its own availability story, and the write path needs a bounded queue with defined behaviour when the sequencer, a witness, or the anchor cannot keep up: fail the write, or acknowledge it as unpublished, but never both silently.

4.5 Split views and witnesses

A signed checkpoint protects a party who holds it. It does not, on its own, stop the operator from signing two different checkpoints of the same size for two different parties. RFC 9162’s security considerations name the behavior, “presenting different, conflicting views of the Merkle Tree at different times and/or to different parties,” and say how it surfaces: it “can be detected by multiple clients comparing their instances of the STHs” (Section 11.3). The RFC leaves that comparison, gossip, “an active area of research and not defined here.”

The ecosystem’s answer is the witness: an independent party that holds the log’s last checkpoint it saw, receives each new one with a consistency proof, checks it, and adds its own signature. C2SP’s witness specification puts it in one sentence: “Witnesses verify that the checkpoint is consistent with their previously recorded state of the log” and return a cosignature (C2SP tlog-witness ). A checkpoint carrying cosignatures from witnesses under separate administrative control is evidence that those witnesses saw one consistent history.

Two points about what counts as a witness. A customer holding receipts is not one: they see only the checkpoints covering their own entries, never check consistency between them, and cannot detect a fork made for them alone. Their receipts become evidence when compared with someone else’s. And for a small team the witness is the monitoring job of Section 7, run under an account the log operators cannot administer, if it persists every checkpoint it verified and publishes its own signature over them. “Separate administrative control” has to be something an auditor can see, a separate cloud account or identity boundary, not a different team on the same org chart.

5. External anchoring: RFC 3161 and Bitcoin

A witness cosignature says that an independent party saw a checkpoint. It does not fix a time that a court or a regulator can check against a clock outside both the operator and the witness. That is the third level.

The idea predates the transparency-log ecosystem by two decades. Haber and Stornetta’s 1991 paper set the goal as making it “infeasible for a user either to back-date or to forward-date his document,” and held that this should hold “even with the collusion of a time-stamping service” (Haber and Stornetta, 1991 , abstract). The two anchors in use today divide along that line: one trusts a service’s key, the other trusts the Bitcoin chain as seen from a node the verifier runs or trusts.

An RFC 3161 time-stamp token is issued by a Time Stamping Authority that is given a hash of the data, the messageImprint, rather than the data, and is required “not to examine the imprint being time-stamped” beyond checking its length (RFC 3161 , Section 2.1). The token is the TSA’s signature over that hash and a time. It proves that the hash existed no later than that time, to anyone who trusts the TSA’s key. The key is the cost. If it is compromised, “any token signed by the TSA using that private key cannot be trusted anymore,” and because the key has a finite lifetime, tokens “SHOULD be time-stamped again” at a later date to renew trust (Section 4). Renewal is an operating task with defined triggers and a defined mechanism. RFC 4998, the Evidence Record Syntax, names the triggers: renewal “is necessary if the private key of a Timestamping Unit has been compromised,” or if an algorithm the token uses is no longer secure, and it has to happen “before cryptographic algorithms used within Archive Timestamps become weak or timestamp certificates become invalid” (RFC 4998 , Sections 1.1 and 1.2). The mechanism it defines renews a whole set of tokens at once by hashing them into a tree and time-stamping its root, rather than re-stamping each token. And verification years later needs what was true at stamping time: RFC 4998 provides for keeping certificates, revocation information and the then-current view of algorithm suitability inside the evidence record, so that a verifier can evaluate the chain as it stood on the day of stamping rather than as it stands on the day of verification.

An OpenTimestamps proof replaces the TSA’s key with a Bitcoin block. Calendar servers aggregate submitted hashes into a Merkle tree and commit the root into a transaction; the proof shows that “the message must have existed prior to when the block header was created” (OpenTimestamps design description ). The lifecycle has two stages: the calendar first returns a pending proof, and the client later has to “upgrade an incomplete timestamp, which adds the path to the Bitcoin blockchain” once the calendar’s transaction is confirmed (opentimestamps-client ). A proof that is never upgraded, or whose calendar disappears before it is, stays incomplete; submitting to more than one calendar, which the client supports, and running the upgrade on a schedule are operating decisions the protocol leaves to the operator. Verification needs block headers: the client’s documentation states that “to verify timestamps you need a local Bitcoin Core node,” and an offline verifier needs a trusted header set delivered some other way. The proof’s time is a block height rather than a clock reading.

What is anchored is a value the checkpoint commits to. ATL anchors the roots themselves: an RFC 3161 token over a Data Tree root and a Bitcoin proof over a Super-Tree root, which bounds when each root existed. Anchoring the signed checkpoint bytes instead bounds, in addition, when the operator’s signature existed; either way, every entry under the root inherits the bound through its inclusion proof. One anchor per anchored checkpoint is enough, and the anchoring cadence is a separate decision from the checkpoint cadence: anchoring every checkpoint of a log that checkpoints every second means over thirty million requests a year, a volume to check against the time-stamp service’s terms before the design is chosen. The alternatives are to anchor on an hourly or daily schedule, or to hash a batch of checkpoints into a small tree and anchor its root, which is what ATL does for its Bitcoin anchor (Section 9). Which TSA, and why, is a documented choice an auditor will ask about. For an entry, the chain of evidence is then: entry hash, inclusion proof to a root, signed checkpoint over that root, and an anchor over the root or over the checkpoint. All four fit in one file and verify offline, given the verifier’s trust material: the operator’s public key, the TSA’s certificate chain together with the revocation status captured at stamping time, or block headers from a node the verifier trusts.

6. Data model and canonicalization

Two choices in the data model decide what a proof means and what it discloses.

The first is what the leaf covers. Hashing the whole entry puts everything under the proof and discloses everything to whoever verifies it, since verification recomputes the leaf from those bytes. The alternative is to split the entry in two. The payload stays in private storage and enters the leaf only as a hash. The metadata travels with the proof. A verifier can then check existence and integrity without seeing content. The cost is that the metadata is disclosed to every holder of the proof unless a field was encrypted first; identifiers and hashes belong there, user content does not. The split is also the answer to erasure: deleting a payload under a retention or data-protection obligation leaves its hash in the leaf, so the tree, the checkpoints and every proof remain valid while the content is gone. The companion article works through the split for the record of one agent step.

The second is canonicalization. A leaf hash is reproducible only if two honest parties serialize the entry identically, and JSON does not guarantee that: key order, whitespace, escaping and number formatting all vary by library. RFC 8785, the JSON Canonicalization Scheme, exists because “hashing and signing need the data to be expressed in an invariant format” (RFC 8785 , abstract). Its number rule defers to ECMAScript’s shortest round-trip form, and that is a rule a JSON library does not necessarily follow by default: a runtime that prints a float as 0.10000000000000001 where the canonical form is 0.1 produces a different hash. Canonicalize before hashing, refuse duplicate keys, and treat the canonical bytes, not the parsed object, as the thing the proof is about.

7. Operating a tamper-evident audit log

The mechanisms are small. The operating decisions decide whether the guarantees hold, and each one below is what an auditor will ask about on the first day.

Keys and custody. The checkpoint key is the log’s identity, used for nothing else. It lives in an HSM or a key-management service, where the parties who can invoke a signature are enumerated and each signature is itself logged; the signature algorithm is constrained by what that key store supports, so choose the store first. Ed25519 is a reasonable default where the key store supports it; RFC 8032 specifies “small public keys (32 or 57 bytes) and signatures (64 or 114 bytes)” (RFC 8032 , Section 1). Publish a key identifier with every checkpoint, so a verifier can tell which key to check against.

Rotation. Plan the rotation before the first checkpoint, and make it a protocol rather than an intention: the rotation is itself an entry in the log; the new public key is signed by the old one; both keys are valid for a stated overlap; witnesses and monitors are told in advance. A planned rotation and a suspected compromise are different procedures, and the second ends the old key’s validity at a stated tree size rather than after an overlap. Every retired public key stays available for as long as checkpoints signed by it are in circulation, recorded in the log and in the verifier’s trust bundle, because a retired-key list that anyone can append to is a way to forge history.

Clocks. Anchors do not replace clock discipline. Entry and checkpoint timestamps are the operator’s clock and stay so; keep it synchronized, require each checkpoint’s timestamp to be later than the previous one, which RFC 9162 imposes on signed tree heads with “Each subsequent timestamp MUST be more recent than the timestamp of the previous update” (Section 4.10), and alarm when the gap between a checkpoint’s timestamp and its anchor’s time exceeds a stated bound. A checkpoint whose own timestamp is later than its anchor’s time claims to have been made after it was proven to exist; that is forward-dating, and it will be asked about.

Checkpoint distribution. A checkpoint stored only in the operator’s database is level 1 in a level 2 costume. Decide once, as policy, where every checkpoint goes: to the customer with their receipt, to a witness, to an anchor, to a public endpoint, and to an append-only location outside the operator’s own account. The set of parties holding a checkpoint is the set of parties the operator can no longer rewrite history against.

The verifier and its trust material. Ship the verifier as a separate binary that has no access to the database and no network dependency on the log. If verification requires the operator’s API, the operator is still in the trust path; the same holds for the trust material, whether that is the operator’s public key, the TSA’s certificates or a set of block headers. It reaches the customer out of band, at onboarding, in a contract annex or from a domain the log does not control, and not from the log’s own endpoint. The binary itself is a signed, reproducible release. In an anchor-based design such as ATL’s the receipt can be accepted on its anchors alone and the operator’s signature serves as an integrity check, which takes the operator’s key out of the trust path but leaves the TSA’s certificates or the block headers in it. ATL’s reference verifier performs no I/O at all (test suite at a pinned revision); it reads a receipt and trust material and returns a result.

Receipts. A self-contained receipt per entry is an inclusion proof, a checkpoint, and the anchors over it. Per entry at scale that multiplies storage, so the working shape is a receipt per batch with per-entry inclusion proofs generated on demand from the retained tree. State the corollary plainly: a receipt the customer does not store is not distribution, and a customer who never compares checkpoints with anyone holds evidence of that checkpoint but is not a witness to it.

Retention. Serving a consistency proof between any two historical sizes for the whole retention period means keeping every leaf hash, the interior nodes or the ability to recompute them, every checkpoint, every anchor token and proof, and the full key history. Anchors cannot be regenerated after loss and go into storage that is separate from the log’s own.

Migration. An existing audit table becomes a level 2 log by hashing its current rows, in a fixed order, into the first tree and signing the first checkpoint over it. The cutover is the hard part: writes are frozen or dual-written during the copy; the ordering key and the canonical byte form of a row, including nulls, time zones and floating-point fields, are written into the boundary record so that they survive later schema changes; and it is decided and stated whether the new log is the system of record or a shadow of the old table, because a shadow’s completeness is the shadow writer’s coverage. The operator has to record the boundary and state it: rows before the first checkpoint carry whatever integrity the old system had, and the new log proves only that they have not changed since the checkpoint. That first checkpoint is anchored and distributed more widely than any other. A migration that presents the old rows as having been tamper-evident all along is the first false statement in the new log.

Monitoring. A log that is never checked is not tamper-evident, only tamper-evidence-capable. The monitor is owned by a team that does not operate the log, keeps the last checkpoint it verified in storage the operator cannot write to, fetches each new checkpoint, obtains the consistency proof from the previous one, verifies it, verifies the anchor and any key rotation, and alarms on failure, on a stale checkpoint, and on a missing anchor. Sigstore’s documentation describes the role: “Auditors can monitor the log for consistency, meaning that the log remains append-only” (Sigstore documentation ). The monitor’s own run history is retained, because it is the evidence an auditor asks for. A consistency failure has three causes to rule out first, tampering, a restore from backup, and a bug in the writer, and the response to all three is the same: freeze the log, preserve what every party holds, and escalate before anyone explains.

Backup and restore. A restore from a backup taken before the last published checkpoint, followed by new writes, produces a history that diverges from the published one, and a monitor holding the published checkpoint reports the divergence as a fork, because it is one. Disaster recovery therefore replays the durable sequence up to at least the last published tree size before accepting new writes, or declares a restart under a new origin identifier with the old log’s final checkpoint recorded in the new log’s first entry. Anchors and witness cosignatures cannot be re-obtained for a history that was lost.

8. What it does not prove, and what breaks

The proofs leave the following outside their guarantees.

• Truth of the entries. The log proves that an entry was committed and not changed. It does not prove that the event the entry describes happened, or happened as described.
• Completeness against what was never written. A consistency proof covers the tree. An event the application did not submit leaves no hole in the tree for the proof to find. Completeness is provable only relative to a checkpoint, and only if the writer’s coverage is established by other means.
• Time before the anchor. The timestamp in a checkpoint is the operator’s claim. The bound an anchor gives is “no later than”; the gap between an entry and its anchor is a design parameter.
• One view, without witnesses. An operator can sign two histories for two parties; each verifies alone. Detection needs the parties, or witnesses, to compare.
• Anything, for checkpoints signed after a key theft. A stolen checkpoint key signs whatever its holder wants from that point on, including a rewritten past. What protects the past is that earlier checkpoints were already held by others or anchored; against those holders the past cannot be rewritten, and anything the thief signs diverges from what they hold. Anchors do not tell when the theft happened.
• Level 0 as evidence. Retention and WORM settings protect against deletion. They are not something a third party can verify from a copy of the log.

The operation has its own failure modes, and a design document lists them next to the proofs.

• Loss of the signing key, as distinct from theft, ends the log’s identity: nothing further can be signed, and the log restarts under a new origin with a stated boundary.
• TSA certificate expiry or revocation is a renewal trigger under RFC 4998, which says an archive time-stamp can become invalid when the certificate’s validity period expires or is revoked; tokens renewed before that event, with their validation data captured, keep their evidential value. A TSA that shuts down cannot renew anything, and renewal moves to another.
• Calendar outage leaves OpenTimestamps proofs pending; the upgrade job retries, and proofs submitted to a second calendar can complete through it.
• Clock drift produces checkpoint timestamps that go backwards, which a monitor enforcing the RFC 9162 ordering rule reports; the fix is clock discipline, not a looser monitor.
• Algorithm deprecation over a ten-year retention is handled by RFC 4998-style renewal of the anchors and by a hash-algorithm field in every checkpoint from the first one.
• A consistency failure is triaged with tampering, restore, and writer bug ruled out first, in that order of consequence, and the freeze-preserve-escalate response of Section 7 applies before the cause is known.

9. One assembly: levels 2 and 3 in one receipt

Levels 2 and 3 compose into one receipt per entry, kept under level 0 retention. ATL is one specification of that composition; I describe it because I wrote it, and any log with the same properties would serve. The leaf is SHA256(0x00 || PayloadHash || MetadataHash), the RFC 9162 tree with a two-part leaf, metadata canonicalized with RFC 8785 before hashing. The checkpoint is the 98-byte blob signed with Ed25519, with a key identifier. For anchors, an RFC 3161 token covers a Data Tree root, and an OpenTimestamps proof covers the root of a Super-Tree that aggregates all Data Tree roots, so that one Bitcoin transaction covers many checkpoints. A receipt carries entry, inclusion proof, checkpoint, super-tree proof and anchors, and verifies offline given trust material. The reference verifier accepts it only when at least one anchor verifies against caller-supplied trust material, and reports a receipt with no verifiable anchor as indeterminate rather than valid; it performs no I/O, so it checks the structure of a Bitcoin proof and leaves the comparison with a block header to the caller, and a receipt whose only anchor is a Bitcoin proof is not accepted by the library alone.

None of that is required to get the properties in this article, and none of it is where the effort goes. The mechanisms are small: a hash chain is thirty lines, a tree with signed checkpoints and consistency proofs is a library call and a key, an anchor is a request. The service around them is the work: durable sequencing, tree storage and retention, a proof API, receipts, key custody and rotation, the monitor under someone else’s account, and the anchor retry and upgrade jobs. Each of the auditor’s four questions has a mechanism behind it. What every answer depends on is a commitment to an earlier state that sits outside the operator’s control, whether a checkpoint someone else holds or a root an anchor fixed in time, and someone who checks the state the operator presents against it: once, for the time question, and each time the log grows, for the other three. The mechanisms produce the commitment. The checking is a job, and it belongs to someone other than the operator.

If your audit log has to answer those questions for a customer or an auditor and it lives in a database table, that is contract work I take on.