DEV Community: Dmitrii Zatona

The Super-Tree: How One Merkle Tree Proves Another

Dmitrii Zatona — Sun, 01 Mar 2026 02:10:02 +0000

A transparency log that lives forever will eventually contain billions of entries. A single Merkle tree with a billion leaves has a depth of 30, which means inclusion proofs are 30 hashes long and every append touches 30 nodes. That is manageable. But the tree file on disk grows without bound, proof generation requires random access across the entire structure, and rotating keys or changing operational parameters means you are stuck with decisions you made on day one.

ATL Protocol splits the problem into two levels: short-lived Data Trees and an eternal Super-Tree. Each Data Tree accumulates entries for a bounded period (configurable -- say, 24 hours or 100,000 entries). When the period ends, the tree is closed, its root hash becomes a leaf in the Super-Tree, and a fresh Data Tree starts accepting new entries. The Super-Tree is itself a Merkle tree -- it grows by one leaf every time a Data Tree closes.

I want to walk through why this architecture exists, how the two levels connect cryptographically, and how two receipts held by two different people can independently prove that the entire log history was never rewritten -- without contacting the server.

Why Not One Big Tree

The obvious approach is a single append-only Merkle tree. Every entry is a leaf. The root hash represents the entire log state. This works, but it has operational problems.

First, the tree file grows forever. ATL uses memory-mapped slab files where every node (leaves and intermediates) is stored at a fixed offset. A tree with 1 million leaves has approximately 2 million nodes, each 32 bytes -- that is 64 MB per slab. With a single tree, you eventually have a multi-gigabyte file that must remain memory-mapped for proof generation. Splitting into bounded Data Trees means each slab is a fixed, predictable size.

Second, key rotation. If the log operator wants to rotate their Ed25519 signing key, a single-tree design forces a choice: sign new entries with the new key (breaking consistency with old checkpoints) or keep the old key forever (defeating the purpose of rotation). With Data Trees, each tree has its own checkpoint signed at close time. Rotating keys between trees is a natural boundary.

Third, anchoring granularity. In ATL Protocol v2.0, RFC 3161 timestamps anchor Data Tree roots, and Bitcoin OTS anchors the Super Root. The Super Root changes every time a Data Tree closes, so each new snapshot gets its own OTS anchor -- but each anchor commits to the entire log history up to that point, not just one tree. TSA timestamps give every Data Tree a seconds-level proof of time, while Bitcoin gives each Super Root snapshot permanent immutability. A single-tree design would force a choice between frequent expensive Bitcoin anchoring or infrequent timestamps.

The Genesis Leaf

When a new Data Tree starts, its first entry is not user data. It is a genesis leaf -- a cryptographic link to the previous tree.

pub const GENESIS_DOMAIN: &[u8] = b"ATL-CHAIN-v1";

pub fn compute_genesis_leaf_hash(prev_root_hash: &Hash, prev_tree_size: u64) -> Hash {
    let mut hasher = Sha256::new();
    hasher.update([LEAF_PREFIX]);
    hasher.update(GENESIS_DOMAIN);
    hasher.update(prev_root_hash);
    hasher.update(prev_tree_size.to_le_bytes());
    hasher.finalize().into()
}

The genesis leaf hash is:

SHA256(0x00 || "ATL-CHAIN-v1" || prev_root_hash || prev_tree_size_le)

This binds the new tree to the exact state of the previous tree at close time -- not just its root hash, but also its size. If the operator tries to rewrite the previous tree (changing entries, adding entries, removing entries), the root hash or the size changes, and the genesis leaf in the next tree no longer matches. The chain is broken, and any verifier who holds a receipt from the previous tree will detect the inconsistency.

The domain separator ATL-CHAIN-v1 prevents confusion between genesis leaves and regular data leaves. Without it, an attacker could craft a data entry whose payload hash and metadata hash happen to collide with a genesis leaf hash, potentially confusing the chain verification. The domain separator makes this a different hash domain entirely -- the input space for genesis leaves and data leaves does not overlap.

The 0x00 prefix is the RFC 6962 leaf prefix, shared with data leaves. This is intentional: the genesis leaf occupies a regular leaf slot in the Data Tree. The Merkle tree does not need special handling for it. It is leaf 0, hashed like any other leaf, included in proofs like any other leaf. The distinction between "genesis" and "data" exists only in the semantic layer, not in the tree structure.

The Super-Tree

When a Data Tree is closed, its root hash is appended to the Super-Tree as a new leaf. The Super-Tree is a standard RFC 6962 Merkle tree -- the same data structure, the same inclusion proofs, the same consistency proofs. The only difference is what its leaves represent: not individual documents, but entire Data Trees.

The Super-Tree root (super_root) is the single hash that represents the entire log history. Every Data Tree that ever existed, every entry that was ever written, is committed to by this one root. If you trust the super_root, you trust every entry in every Data Tree.

In ATL Protocol v2.0, Bitcoin OTS anchors the super_root, not individual Data Tree roots. Each time the Super-Tree grows, the new Super Root gets its own OTS anchor -- and each anchor commits to every Data Tree in the log up to that point. TSA timestamps anchor individual Data Tree roots for faster, per-tree time proofs.

What a Receipt Contains

Every Receipt-Full in ATL Protocol v2.0 includes a super_proof:

{
  "genesis_super_root": "sha256:aabb...",
  "data_tree_index": 150,
  "super_tree_size": 152,
  "super_root": "sha256:ccdd...",
  "inclusion": ["sha256:...", "sha256:...", "sha256:..."],
  "consistency_to_origin": ["sha256:...", "sha256:..."]
}

Six fields. Each one does something specific.

genesis_super_root is the Super-Tree root when it contained exactly one leaf -- the first Data Tree ever closed. This is the identity of the log. Two receipts with the same genesis_super_root claim to be from the same log instance.

data_tree_index is the position of this receipt's Data Tree in the Super-Tree. Data Tree 0 is the first tree the log ever created. Data Tree 150 is the 151st.

super_tree_size is how many Data Trees the Super-Tree contained at the time this receipt was issued.

super_root is the Super-Tree root hash at that size.

inclusion is a Merkle inclusion proof -- the sibling hashes needed to reconstruct the super_root from the Data Tree root at position data_tree_index. This proves that this specific Data Tree is part of the Super-Tree.

consistency_to_origin is a Merkle consistency proof from Super-Tree size 1 to super_tree_size. This proves that the current Super-Tree is an append-only extension of the genesis state -- no historical Data Trees were removed or modified.

Verifying Super-Tree Inclusion

The first verification step: is this Data Tree actually in the Super-Tree?

pub fn verify_super_inclusion(data_tree_root: &Hash, super_proof: &SuperProof) -> AtlResult<bool> {
    if super_proof.super_tree_size == 0 {
        return Err(AtlError::InvalidTreeSize {
            size: 0,
            reason: "super_tree_size cannot be zero",
        });
    }

    if super_proof.data_tree_index >= super_proof.super_tree_size {
        return Err(AtlError::LeafIndexOutOfBounds {
            index: super_proof.data_tree_index,
            tree_size: super_proof.super_tree_size,
        });
    }

    let expected_super_root = super_proof.super_root_bytes()?;
    let inclusion_path = super_proof.inclusion_path_bytes()?;

    let inclusion_proof = InclusionProof {
        leaf_index: super_proof.data_tree_index,
        tree_size: super_proof.super_tree_size,
        path: inclusion_path,
    };

    verify_inclusion(data_tree_root, &inclusion_proof, &expected_super_root)
}

The Data Tree root is the leaf. The Super-Tree is the tree. Standard Merkle inclusion verification -- the same algorithm used for verifying individual entries within a Data Tree. The Super-Tree does not need special proof algorithms. It reuses the same verify_inclusion function because it is the same data structure.

Two structural checks before any cryptographic work: tree size cannot be zero (there is no Super-Tree with no Data Trees), and the index cannot exceed the size (you cannot be at position 150 in a tree with 100 leaves). These catch malformed proofs before touching the expensive hash operations.

Verifying Consistency to Origin

The second verification step: is the Super-Tree an honest extension of the genesis state?

pub fn verify_consistency_to_origin(super_proof: &SuperProof) -> AtlResult<bool> {
    if super_proof.super_tree_size == 0 {
        return Err(AtlError::InvalidTreeSize {
            size: 0,
            reason: "super_tree_size cannot be zero",
        });
    }

    let genesis_super_root = super_proof.genesis_super_root_bytes()?;
    let super_root = super_proof.super_root_bytes()?;

    if super_proof.super_tree_size == 1 {
        if super_proof.consistency_to_origin.is_empty() {
            return Ok(use_constant_time_eq(&genesis_super_root, &super_root));
        }
        return Err(AtlError::InvalidProofStructure {
            reason: format!(
                "consistency_to_origin must be empty for super_tree_size 1, got {} hashes",
                super_proof.consistency_to_origin.len()
            ),
        });
    }

    let consistency_path = super_proof.consistency_to_origin_bytes()?;

    let consistency_proof = ConsistencyProof {
        from_size: 1,
        to_size: super_proof.super_tree_size,
        path: consistency_path,
    };

    verify_consistency(&consistency_proof, &genesis_super_root, &super_root)
}

This is an RFC 9162 consistency proof, but with a specific twist: from_size is always 1. The proof says: "the Super-Tree at size 1 (containing just the first Data Tree) is a prefix of the Super-Tree at size N." If this holds, then Data Tree 0 is still at position 0, unchanged. Data Tree 1 is still at position 1. And so on, up to the current size.

The genesis case (super_tree_size == 1) is a degenerate consistency proof: the only valid state is genesis_super_root == super_root with an empty proof path. If someone provides a non-empty path for size 1, the proof is structurally invalid -- there is nothing to prove consistency between a tree of size 1 and itself except equality.

Again, this reuses verify_consistency -- the same RFC 9162 implementation I wrote about in a previous post. The Super-Tree does not reinvent consistency proofs. It parametrizes them differently (always from size 1), but the algorithm is identical.

Cross-Receipt Verification

This is the part that makes the two-level architecture worth the complexity.

Suppose Alice receives a receipt today, and Bob receives a receipt next month. They have never communicated. The server might have been compromised in between. Can Alice and Bob independently determine whether the log was tampered with, without talking to the server?

Yes.

pub fn verify_cross_receipts(
    receipt_a: &Receipt,
    receipt_b: &Receipt,
) -> CrossReceiptVerificationResult {
    // ...

    // Step 1: Both receipts must have super_proof
    let super_proof_a = receipt_a.super_proof.as_ref()?;
    let super_proof_b = receipt_b.super_proof.as_ref()?;

    // Step 2: Same genesis?
    let genesis_a = super_proof_a.genesis_super_root_bytes()?;
    let genesis_b = super_proof_b.genesis_super_root_bytes()?;

    if !use_constant_time_eq(&genesis_a, &genesis_b) {
        // Different logs entirely
        return result;
    }

    // Step 3: Both consistent with genesis?
    let consistency_a = verify_consistency_to_origin(super_proof_a);
    let consistency_b = verify_consistency_to_origin(super_proof_b);

    match (consistency_a, consistency_b) {
        (Ok(true), Ok(true)) => {
            result.history_consistent = true;
        }
        // ...
    }

    result
}

Three checks, no server required:

Same genesis? If genesis_super_root differs, the receipts are from different log instances. Done.
Receipt A consistent with genesis? If the consistency proof from size 1 to A's super_tree_size verifies, then the Super-Tree at A's snapshot is an honest extension of genesis.
Receipt B consistent with genesis? Same check for B.

If both receipts are consistent with the same genesis, then by the transitive property of Merkle consistency, the history between them was not modified. The operator cannot have deleted Data Trees, reordered them, or substituted different content -- because both receipts independently prove that their respective Super-Tree snapshots are append-only extensions of the same origin.

This works because consistency proofs are transitive. If the Super-Tree at size 50 is consistent with size 1, and the Super-Tree at size 100 is consistent with size 1, then size 100 is consistent with size 50. Any modification to the first 50 Data Trees would break at least one of the two consistency proofs.

No communication between Alice and Bob. No server access. No trusted third party. Two receipts, one function call, and the math proves the rest.

Why `from_size` Is Always 1

I could have designed the consistency proof to go from the previous receipt's Super-Tree size to the current one. That would be a shorter proof -- proving consistency from size 50 to size 100 requires fewer hashes than proving from size 1 to size 100.

But it would also require the verifier to have the previous receipt. Cross-receipt verification would become sequential: to verify receipt C, you need receipt B, and to verify receipt B, you need receipt A, all the way back to the genesis.

By always proving consistency from size 1, every receipt is self-contained. Each receipt independently proves its relationship to the origin. Verification is O(1) receipts, not O(N). Any single receipt, in isolation, proves that the entire log history up to that point is an append-only extension of genesis.

The cost is a slightly longer proof path. For a Super-Tree with 1000 Data Trees, the consistency proof from size 1 is at most 2 * ceil(log2(1000)) = 20 hashes -- 640 bytes. For a Super-Tree with a million Data Trees, it is 40 hashes -- 1280 bytes. This is negligible compared to the value of self-contained verification.

The Two-Level Trust Chain

Putting it all together, the verification chain for a single receipt is:

Entry level: Verify the document hash matches the receipt's payload_hash. This proves "this document is what was anchored."
Data Tree level: Verify the Merkle inclusion proof from the entry's leaf hash to the Data Tree root (proof.root_hash). This proves "this entry is in this Data Tree."
Super-Tree level (inclusion): Verify the Super-Tree inclusion proof from the Data Tree root to the Super Root (super_proof.super_root). This proves "this Data Tree is in the Super-Tree."
Super-Tree level (consistency): Verify the consistency proof from genesis to the current Super Root. This proves "the Super-Tree was never rewritten."
Anchor level: Verify external anchors (TSA on the Data Tree root, Bitcoin OTS on the Super Root). This proves "these roots existed at these specific times, attested by parties outside the operator's control."

Each level builds on the one below it. Compromise any level and the chain breaks -- the verifier gets a definitive failure, not a silent pass.

And because every level uses standard Merkle proofs (RFC 9162 inclusion and consistency), the entire verification stack is built from two primitives. One for "this leaf is in this tree." One for "this smaller tree is a prefix of this larger tree." Everything else is composition.

The full implementation is open source: github.com/evidentum-io/atl-core (Apache-2.0)

Files discussed in this post:

src/core/verify/super_tree.rs -- Super-Tree verification: inclusion, consistency to origin, cross-receipt verification
src/core/merkle/crypto.rs -- genesis leaf hash with ATL-CHAIN-v1 domain separator
src/core/receipt.rs -- SuperProof struct definition

98 Bytes That Prove Your Document Existed

Dmitrii Zatona — Sat, 21 Feb 2026 04:48:01 +0000

A checkpoint in ATL Protocol is a signed snapshot of the transparency log state. It captures the root hash of the Merkle tree at a specific tree size, at a specific moment in time, from a specific log instance. If you have a checkpoint and the corresponding signature verifies, you know the exact state of the log at that point.

The entire wire format is 98 bytes. Fixed size. No variable-length fields. No parser required.

I want to walk through why it looks the way it does, byte by byte.

The Layout

Offset  Size   Field
0       18     Magic bytes: "ATL-Protocol-v1-CP" (ASCII)
18      32     Origin ID (SHA256 of instance UUID)
50      8      Tree size (u64 little-endian)
58      8      Timestamp (u64 little-endian, Unix nanoseconds)
66      32     Root hash (SHA256)
---
Total: 98 bytes

That is the complete wire format. The Ed25519 signature (64 bytes) and the key ID (32 bytes) are stored separately -- they are not part of the 98-byte blob. This separation is a deliberate design decision that I will explain below.

Fixed Size, No Parser

Everyone reaches for JSON first. Or Protobuf. Or CBOR. Or MessagePack. These are fine formats for APIs, configuration, and data interchange. They are not fine for the thing you cryptographically sign.

The problem with variable-length encodings in a signed context is ambiguity. JSON has key ordering issues -- the same logical object can produce different byte sequences depending on which keys come first. This is well-known enough that RFC 8785 (JSON Canonicalization Scheme) exists specifically to address it. Protobuf has field ordering that is technically undefined in the spec; different implementations can serialize the same message into different bytes. CBOR has multiple valid encodings for the same value.

When I sign a checkpoint, I need to know exactly what I signed. Not "a checkpoint with these fields" but "these exact 98 bytes." If the serialization is ambiguous, the verification is ambiguous. If two implementations serialize the same checkpoint differently, one of them will fail to verify a signature produced by the other.

A fixed 98-byte blob has zero ambiguity. Any implementation in any language reads it the same way:

Read 18 bytes of magic.
Read 32 bytes of origin ID.
Read 8 bytes, interpret as u64 little-endian -- that is the tree size.
Read 8 bytes, interpret as u64 little-endian -- that is the timestamp.
Read 32 bytes of root hash.

Done. No length prefixes to parse. No delimiters to scan for. No TLV encoding to decode. No canonical form debates, because the bytes ARE the canonical form.

The serialization in Rust:

pub fn to_bytes(&self) -> [u8; CHECKPOINT_BLOB_SIZE] {
    let mut blob = [0u8; CHECKPOINT_BLOB_SIZE];
    blob[0..18].copy_from_slice(CHECKPOINT_MAGIC);
    blob[18..50].copy_from_slice(&self.origin);
    blob[50..58].copy_from_slice(&self.tree_size.to_le_bytes());
    blob[58..66].copy_from_slice(&self.timestamp.to_le_bytes());
    blob[66..98].copy_from_slice(&self.root_hash);
    blob
}

No allocations. No error paths. The return type is [u8; 98], not Vec<u8> or Result<Vec<u8>>. It cannot fail.

The Signature Lives Outside

This is the design decision that seems obvious in hindsight but that many implementations get wrong.

The Ed25519 signature and the key ID are stored alongside the checkpoint, but they are not part of the 98-byte signed blob. The method to_bytes() always produces the exact data that was signed. Always. No exceptions.

Why does this matter? Consider the alternative: include the signature in the serialized format. Now the signature signs... what? The data plus the signature itself? That is a chicken-and-egg problem. You cannot compute a signature over data that includes the signature, because you do not have the signature yet when you need to hash the data.

The common workaround is to define a "signing input" that differs from the "stored format" -- serialize the checkpoint without the signature for signing, then serialize it again with the signature for storage. Now you have two serialization formats for the same logical object, and every implementation must know which one to use when. Bugs creep in. Someone verifies the stored format instead of the signing input. The signature fails. Hours of debugging follow.

I avoided this entirely. to_bytes() returns what was signed. The signature is a separate field. Verification reconstructs the blob and checks:

pub fn verify(&self, verifier: &CheckpointVerifier) -> AtlResult<()> {
    if self.key_id != verifier.key_id {
        return Err(AtlError::InvalidSignature(format!(
            "key_id mismatch: checkpoint has {}, verifier has {}",
            hex::encode(self.key_id), hex::encode(verifier.key_id)
        )));
    }
    let blob = self.to_bytes();
    verifier.verify(&blob, &self.signature)
}

Notice the key ID check before the signature verification. key_id is SHA256(public_key), and it is checked first. Ed25519 verification is not free -- it involves elliptic curve operations. If the key ID does not match, I reject immediately without touching the expensive crypto. This is a fast-rejection pattern: filter out obviously wrong keys with a cheap hash comparison before doing real work.

Magic Bytes With a Version Baked In

The first 18 bytes of every checkpoint are the ASCII string "ATL-Protocol-v1-CP". This serves two purposes.

First, it identifies the format. If someone accidentally feeds a JPEG, a Protobuf message, or a random 98-byte buffer to a checkpoint parser, the magic bytes will not match. The error is InvalidCheckpointMagic, not a confusing downstream failure from misinterpreted fields.

Second, the v1 in the magic string bakes the wire format version into the data itself. If I ever need to change the checkpoint format -- add fields, change sizes, use a different hash function -- the new format gets different magic bytes (say, "ATL-Protocol-v2-CP"). A v1 parser encountering a v2 checkpoint cleanly rejects it instead of silently misinterpreting bytes 18-50 as an origin ID when v2 might use those bytes for something else entirely.

Eighteen bytes is generous for magic bytes. I chose a human-readable string over a shorter binary magic number because checkpoint blobs end up in hex dumps, log files, and debugging sessions. Seeing 41544C2D50726F746F636F6C2D76312D4350 in a hex dump is recognizable. Seeing 89504E47 requires you to remember that those are PNG magic bytes.

Nanosecond Timestamps

The timestamp field is a u64 encoding Unix nanoseconds. Not seconds, not milliseconds -- nanoseconds.

The range of a u64 in nanoseconds covers from 1970 to approximately the year 2554. That is sufficient.

I chose nanosecond precision because a transparency log can process multiple entries within the same millisecond. If two checkpoints have the same millisecond-resolution timestamp, their ordering becomes ambiguous. With nanosecond resolution, even entries processed microseconds apart have distinct timestamps. The timestamp is generated by current_timestamp_nanos() with clamping to u64::MAX to handle the theoretical case where system time exceeds the representable range.

Little-Endian Encoding

The two u64 fields (tree size and timestamp) are encoded as little-endian. This is an explicit choice, not a default.

Little-endian matches the native byte order of modern hardware: x86, ARM (in its default configuration), and RISC-V. On these architectures, encoding a u64 as little-endian is a no-op -- the in-memory representation is already little-endian. This eliminates an entire class of byte-swapping bugs on the most common platforms.

I wrote an explicit test that verifies the encoding:

test_endianness: 0x0102_0304_0506_0708 encodes as
[0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01]

The test name is test_endianness. It exists because byte order is the kind of thing that is trivially correct on one platform and silently wrong on another. The test makes the encoding a documented, verified property of the format, not an assumption.

JSON Roundtrip, but Not for Crypto

Checkpoints need a human-readable representation for APIs, debugging, and storage in systems that do not handle raw binary well. I implemented a CheckpointJson struct with string encodings:

Hashes are encoded as "sha256:<64 hex characters>"
Signatures are encoded as "base64:<base64 string>"

The to_json() and from_json() methods convert between the binary checkpoint and this JSON representation. But -- and this is important -- cryptographic operations always operate on the 98-byte binary blob, never on JSON. The Ed25519 signature is computed over to_bytes(), not over serde_json::to_string().

To enforce this, the main Checkpoint struct does not derive Serialize or Deserialize. There is no #[derive(Serialize)] on it. This is intentional. If someone accidentally tries to JSON-serialize a Checkpoint directly, the compiler stops them. They must go through to_json() explicitly, which forces them to think about which representation they are working with.

Trust Model: Signature as Integrity Check

Per ATL Protocol v2.0, the Ed25519 signature on a checkpoint is an integrity check, not a trust anchor. This is a deliberate departure from PKI-style trust.

The signature proves: "this checkpoint was issued by the holder of this private key." It does not prove: "you should trust this key." The distinction matters.

Trust in ATL Protocol comes from external anchors: RFC 3161 TSA timestamps (a trusted third-party timestamping authority attests to when the checkpoint existed) and Bitcoin OTS (the checkpoint hash is anchored in the Bitcoin blockchain, providing a timestamp that no single party can forge). The Ed25519 signature binds the checkpoint to a specific log instance. The external anchors prove the checkpoint existed at a specific point in time.

This design means that compromising the Ed25519 signing key does not retroactively compromise past checkpoints. If a checkpoint was anchored via RFC 3161 or Bitcoin OTS before the key was compromised, that anchor remains valid regardless of what happens to the key afterwards. The key is not the trust root -- it is a consistency mechanism.

The Test Suite

The checkpoint implementation has a test suite that covers the wire format exhaustively:

test_checkpoint_blob_size -- verifies the blob is exactly 98 bytes.
test_magic_bytes -- verifies the first 18 bytes are "ATL-Protocol-v1-CP".
test_endianness -- verifies little-endian encoding of u64 fields.
test_wire_format_layout -- verifies every field is at the correct byte offset.
test_sign_and_verify -- round-trip: create checkpoint, sign, verify.
test_verify_wrong_key_fails -- signature from key A does not verify with key B.
test_verify_tampered_data_fails -- flip a byte in the checkpoint, verification fails.
test_verify_tampered_signature_fails -- flip a byte in the signature, verification fails.
test_json_roundtrip -- binary to JSON to binary produces identical bytes.
test_empty_tree_checkpoint -- a checkpoint for an empty tree (tree_size = 0) is valid.

Each test name documents a specific property of the format. If a future change breaks any of these properties, the test name tells you exactly what broke and why it matters.

Why 98 Bytes

The number 98 is not arbitrary. It is the sum of the minimum fields needed to identify a unique log state:

18 bytes to identify the format and version.
32 bytes to identify which log instance (origin).
8 bytes to identify how many entries are in the log (tree size).
8 bytes to identify when this snapshot was taken (timestamp).
32 bytes to cryptographically commit to the entire log contents (root hash).

There is nothing to remove. The magic bytes prevent misidentification. The origin prevents cross-log confusion. The tree size and timestamp locate the snapshot in the log's history. The root hash commits to every entry ever written. Remove any field and the checkpoint becomes ambiguous or forgeable.

There is nothing to add, either. Anything beyond these fields -- the signature, the key ID, metadata, annotations -- belongs outside the signed blob. The 98 bytes are the statement. Everything else is commentary on the statement.

The full implementation is open source: github.com/evidentum-io/atl-core (Apache-2.0)

The file discussed in this post:

src/core/checkpoint.rs -- checkpoint wire format, serialization, signing, verification (1080 lines)
Ed25519 signatures via ed25519-dalek crate

I Shipped a Broken Consistency Proof Verifier. Here's How I Found Out.

Dmitrii Zatona — Sat, 21 Feb 2026 03:52:45 +0000

ATL Protocol needs append-only integrity. Every entry that was ever written to a transparency log must remain exactly where it is, exactly as it was. If an operator, a compromised server, or a software defect silently drops or mutates a past record, the entire trust model is gone. Not degraded -- gone.

Consistency proofs enforce this. A consistency proof takes two snapshots of the same log -- say, one at size 4 and another at size 8 -- and proves that the first four entries in the larger log are byte-for-byte identical to the entries in the smaller log. No deletions. No substitutions. No reordering. The proof is a short sequence of hashes that lets any verifier independently confirm the relationship between the two tree roots.

RFC 9162 (Certificate Transparency v2) specifies the exact algorithm for generating and verifying these proofs. I implemented it from scratch in Rust for ATL Protocol. Not a wrapper around an existing C library. Not a condensed version. The complete SUBPROOF algorithm from Section 2.1.4.

Or at least, that was the plan.

The Shortcut That Bit Me

When I first read Section 2.1.4 of RFC 9162, the verification algorithm looked overengineered. Bit shifting, a boolean flag, nested loops, an alignment phase. I thought I understood the essence of what it was doing and could distill it to something simpler.

So I wrote a simplified verifier. It did four things:

Check that the proof path is not empty.
If from_size is a power of two, check that path[0] matches old_root.
Check that path.len() does not exceed 2 * log2(to_size).
Return true.

That last line is the problem. My simplified implementation never reconstructed the tree roots. It checked surface properties -- non-empty path, plausible length, matching first element in the power-of-two case -- and called it good. The tests I had at the time all passed, because valid proofs do have these properties. I moved on to other parts of the codebase.

I do not remember exactly when the doubt crept in. Probably while re-reading the RFC for an unrelated reason. The verification algorithm does two parallel root reconstructions from the same proof path, and my version did zero. That is not a minor difference. That is the entire security property missing.

The Attack

I sat down and tried to break my own code. It took about five minutes.

The old root is public -- anyone monitoring the log already has it. An attacker constructs a proof starting with old_root (passing the "first hash matches" check), followed by arbitrary garbage. The proof length of 3 is within any reasonable bound for an 8-leaf tree. My simplified verifier checks these surface properties, never reconstructs either root, and returns true. The attacker has just "proved" that the log grew from 4 to 8 entries with content they control.

The concrete attack:

#[test]
fn test_regression_simplified_impl_vulnerability() {
    let leaves: Vec<Hash> = (0..8).map(|i| [i as u8; 32]).collect();
    let old_root = compute_root(&leaves[..4]);
    let new_root = compute_root(&leaves);

    let attack_proof = ConsistencyProof {
        from_size: 4,
        to_size: 8,
        path: vec![
            old_root,   // Passes simplified check
            [0x00; 32], // Garbage
            [0x00; 32], // Garbage
        ],
    };

    assert!(
        !verify_consistency(&attack_proof, &old_root, &new_root).unwrap(),
        "CRITICAL: Simplified implementation vulnerability not fixed!"
    );
}

This proof passes every check the simplified verifier performs. The path is non-empty. from_size is 4 (a power of two), and path[0] is indeed old_root. The path length of 3 is well within 2 * log2(8) = 6. My old code would have returned true and accepted a completely forged log extension.

The test name is test_regression_simplified_impl_vulnerability. The word "regression" is deliberate -- it means this is not a hypothetical attack I imagined for educational purposes. I wrote the broken code first. I found the hole. I rewrote the verifier. The test exists so that no future refactor can quietly reintroduce the same vulnerability. My mistake, immortalized in the test suite.

How Consistency Proofs Actually Work

A Merkle tree is a binary hash tree where leaves and internal nodes are domain-separated:

leaf_hash = SHA256(0x00 || data)
node_hash = SHA256(0x01 || left_hash || right_hash)

In an append-only log, new entries are added to the right side of the tree. The left subtrees are immutable once formed. A consistency proof leverages this structure: it provides the minimum set of intermediate hashes that a verifier needs to reconstruct both the old root (from the smaller tree) and the new root (from the larger tree) using a single walk over the proof path.

The critical property -- the one my simplified version missed entirely -- is that the verifier does not simply check whether old_root appears somewhere in the new tree. It must reconstruct both roots from the same proof path. If any hash in the path is incorrect -- even by a single bit -- both reconstructions produce wrong results, and the proof fails.

The RFC 9162 algorithm works by decomposing the tree at the largest power-of-two boundary, then recursively collecting the sibling hashes that the verifier will need. The bit-level operations in the verification algorithm encode the tree structure implicitly: each bit of the size counters tells the verifier whether a proof hash belongs on the left or right at each level.

Five Structural Invariants

After the rewrite, before the verification algorithm processes a single hash, my implementation enforces five structural invariants. Each invariant eliminates a category of malformed or malicious proofs with zero cryptographic work:

Invariant 1: Valid bounds. from_size must not exceed to_size. A proof that claims the tree shrank is structurally impossible in an append-only log. Rejecting it immediately avoids nonsensical bit arithmetic downstream.

if proof.from_size > proof.to_size {
    return Err(AtlError::InvalidConsistencyBounds {
        from_size: proof.from_size,
        to_size: proof.to_size,
    });
}

Invariant 2: Same-size proofs require an empty path. When from_size == to_size, the only valid consistency proof is an empty one -- verification reduces to old_root == new_root. If someone submits a non-empty path for equal sizes, they are attempting to inject hashes into the verification pipeline. Reject it without processing.

Invariant 3: Zero old size requires an empty path. Every tree is consistent with the empty tree by definition. A non-empty proof from size zero is an attempt to force the verifier to process attacker-controlled data for a case that requires no proof at all.

Invariant 4: Non-trivial proofs need at least one hash. When from_size is not a power of two and from_size != to_size, the proof must contain at least one hash. The RFC 9162 algorithm prepends old_root to the proof path only when from_size is a power of two. For non-power-of-two sizes, an empty path means the proof is incomplete -- the verifier has nothing to work with.

Invariant 5: Path length bounded by O(log n). A Merkle tree of depth d requires at most O(d) hashes in a consistency proof. I compute the bound as 2 * ceil(log2(to_size)):

let max_proof_len = ((64 - proof.to_size.leading_zeros()) as usize)
    .saturating_mul(2);
if proof.path.len() > max_proof_len {
    return Err(AtlError::InvalidProofStructure { ... });
}

A 100-hash proof for an 8-leaf tree is rejected before any hashing occurs. Without this bound, an attacker could force the verifier into an arbitrarily expensive hash chain.

These five checks are structural preconditions, not defense-in-depth extras. Every class of malformed proof that can be rejected without hashing should be rejected without hashing. My simplified version skipped this discipline entirely.

The Full Verification Algorithm

The replacement verifier is a faithful implementation of RFC 9162. A single pass over the proof path, maintaining two running hashes and two bit-shifted size counters:

// Step 1: If from_size is a power of 2, prepend old_root to path
let path_vec = if is_power_of_two(from_size) {
    let mut v = vec![*old_root];
    v.extend_from_slice(path);
    v
} else {
    path.to_vec()
};

// Step 2: Initialize bit counters with checked arithmetic
let mut fn_ = from_size.checked_sub(1)
    .ok_or(AtlError::ArithmeticOverflow {
        operation: "consistency verification: from_size - 1",
    })?;
let mut sn = to_size - 1;

// Step 3: Align -- shift right while LSB(fn) is set
while fn_ & 1 == 1 {
    fn_ >>= 1;
    sn >>= 1;
}

// Step 4: Initialize running hashes from the first proof element
let mut fr = path_vec[0];
let mut sr = path_vec[0];

// Step 5: Process each subsequent proof element
for c in path_vec.iter().skip(1) {
    if sn == 0 { return Ok(false) }

    if fn_ & 1 == 1 || fn_ == sn {
        // Proof hash is a left sibling
        fr = hash_children(c, &fr);
        sr = hash_children(c, &sr);
        while fn_ & 1 == 0 && fn_ != 0 {
            fn_ >>= 1;
            sn >>= 1;
        }
    } else {
        // Proof hash is a right sibling (only affects new root)
        sr = hash_children(&sr, c);
    }
    fn_ >>= 1;
    sn >>= 1;
}

// Step 6: Final check
Ok(use_constant_time_eq(&fr, old_root)
    && use_constant_time_eq(&sr, new_root)
    && sn == 0)

The bit operations encode the tree structure. fn_ tracks the position within the old tree boundary, sn tracks the position within the new tree. When a proof hash is a left sibling (fn_ & 1 == 1 or fn_ == sn), it contributes to both root reconstructions. When it is a right sibling, it only contributes to the new root -- the old tree did not extend that far.

The fn_ == sn condition handles the transition point where both trees share a common subtree root and then diverge. The alignment loop at the start skips tree levels where the old tree's boundary falls at an odd index, synchronizing the bit counters with the proof path.

This is the part I tried to skip. Every bit operation matters. Getting any of it wrong means either accepting invalid proofs or rejecting valid ones.

Constant-Time Hash Comparison

The final verification step compares reconstructed hashes against expected roots. A standard == comparison on byte arrays short-circuits on the first differing byte, leaking timing information proportional to the position of the first mismatch.

I use the subtle crate for constant-time comparison:

fn use_constant_time_eq(a: &Hash, b: &Hash) -> bool {
    use subtle::ConstantTimeEq;
    a.ct_eq(b).into()
}

Root hashes are public in a transparency log, so timing side-channels here are less exploitable than in password verification. I use constant-time comparison anyway -- the cost is zero for 32 bytes, and if the function is ever reused in a context where the hash is not public, there is no latent vulnerability waiting to be discovered.

The sn == 0 check in the final expression is part of the RFC specification: after processing all proof elements, the bit-shifted to_size - 1 counter must have reached zero. If it has not, the proof path was the wrong length for the claimed tree sizes. This catches a specific class of attack where the proof contains valid hashes but claims incorrect sizes.

Checked Arithmetic

If from_size is 0 and the code computes from_size - 1 without checking, the result wraps to u64::MAX on release builds. Every subsequent bit operation produces garbage.

Every arithmetic operation uses Rust's checked arithmetic:

let mut fn_ = from_size.checked_sub(1)
    .ok_or(AtlError::ArithmeticOverflow {
        operation: "consistency verification: from_size - 1",
    })?;

No wrapping_sub. No unchecked_add. No silent truncation. If an operation would overflow, it returns an explicit error naming the specific operation. The structural invariants already prevent from_size == 0 from reaching this code path. The checked arithmetic is a second layer: if someone refactors the invariant checks, the arithmetic still will not silently produce wrong results.

Adversarial Test Suite

After the simplified-implementation incident, I was not going to rely on happy-path tests alone. The adversarial test suite in adversarial_tests.rs (344 lines) exists specifically to verify that incorrect, malicious, and boundary-case inputs produce correct rejections. Every test includes both a positive case (valid proof accepted) and a negative case (tampered proof rejected):

Replay attacks across trees. Generate a valid consistency proof for one tree, then attempt to verify it against a different tree with the same sizes but different leaf data:

#[test]
fn test_adversarial_replay_different_tree() {
    let proof_a = generate_consistency_proof(4, 8, get_node_a).unwrap();

    let old_root_b = compute_root(&leaves_b[..4]);
    let new_root_b = compute_root(&leaves_b);

    // Proof from tree A must not verify against tree B
    assert!(!verify_consistency(&proof_a, &old_root_b, &new_root_b).unwrap());
}

The proof is cryptographically bound to specific leaf content. Same structure, different data, different hashes, verification fails.

Replay attacks across sizes. Take a valid proof for (4 -> 8) and relabel it as (3 -> 7). The bit operations in the verification algorithm are size-dependent -- each bit of the size counter determines left-vs-right sibling ordering. A proof path that is valid for one pair of sizes is invalid for another, even if the underlying data is the same.

Boundary size testing. Sizes at or near powers of two trigger different code paths in the bit manipulation logic. I test pairs around every boundary: 63/64, 64/65, 127/128, 128/129, 255/256. Off-by-one errors here are the most common failure mode in Merkle tree implementations because is_power_of_two gates whether old_root is prepended to the proof path.

All-ones binary sizes. Values like 7 (0b111), 15 (0b1111), and 31 (0b11111) have every bit set, maximizing the iterations in the alignment loop and exercising every branch condition. These are the sizes most likely to expose off-by-one errors in the bit-shifting logic.

Proof length attacks. A proof with 100 elements for an 8-leaf tree is rejected by Invariant 5 before any hashing occurs. Without the O(log n) bound, an attacker could force the verifier into an extended hash computation.

Duplicate hash attacks. A proof where every element is old_root is rejected because the hash reconstruction deterministically produces wrong intermediate values. The algorithm's correctness does not depend on hash diversity.

Each test is accompanied by single-bit-flip verification: flipping one byte in any proof hash causes the proof to fail. This confirms that the verification is sensitive to every byte of every hash in the proof path.

The 415 lines of consistency.rs and 344 lines of adversarial tests do not prove the implementation is correct in a formal sense -- that would require a proof assistant. But they do prove that every attack vector I could identify is covered, and they document those vectors permanently in the test names and assertions. Including the vector I accidentally created myself.

The full implementation is open source: github.com/evidentum-io/atl-core