Lab 02 — Transparency-Log Inclusion-Proof Verifier (RFC 6962 / Merkle)

Difficulty: 5/5 | Runs locally: yes, standard library only

Pairs with the Phase 14 WARMUP Chapter 6 (keyless signing and transparency logs). This is the cryptographic mechanism under Sigstore/Rekor and Certificate Transparency.

Why This Lab Exists (Purpose & Goal)

Keyless signing (Sigstore) and the web's certificate trust both rest on transparency logs: append-only Merkle trees that make every signing event (or every issued TLS certificate) publicly auditable, so a maliciously-issued signature or certificate cannot be hidden. The goal of this lab is to build the inclusion-proof verifier — the code that proves an entry is in the log by recomputing the Merkle root from a short audit path and checking it against the log's signed root. This is real RFC 6962 Merkle verification, and it is one of the most elegant, high-leverage cryptographic primitives in security.

The Concept, In the Weeds

A transparency log is a Merkle tree of entries. RFC 6962 specifies domain-separated hashing — and the domain separation is itself a security control:

leaf hash = H(0x00 || data)        node hash = H(0x01 || left || right)

The 0x00/0x01 prefixes prevent a second-preimage attack: without them, an attacker could present an internal node's value as if it were a leaf, forging an inclusion proof for data that was never logged. To prove entry e is included, the log provides an inclusion proof — the audit path of sibling hashes from e's leaf up to the root. The verifier (root_from_proof) recomputes the root by hashing up the path, then checks it equals the root in the Signed Tree Head — a structure the log operator signs over (root, tree size). The full check (verify_inclusion):

verify the STH — the root is only trustworthy if a trusted log operator signed it (an untrusted or forged STH is rejected before the proof is even considered);
recompute the root from the leaf + audit path;
compare to the signed root — a match proves inclusion; a mismatch means not included.

Because the log is append-only and public, you can also monitor it: a signing event you didn't authorize (someone signing as you) appears in the log and is detectable — the audit property that makes transparency logs valuable.

Why This Matters for Protecting the Company

Transparency is what turns "trust me, this signature is legitimate" into "verify it's publicly logged and monitor for ones you didn't make." It is how Certificate Transparency caught mis-issued TLS certificates (and made CT mandatory in browsers), and how Sigstore makes software signing auditable without long-lived keys. When you can verify an inclusion proof and reason about a transparency log, you can build (and assess) systems where a malicious signature can't hide — protecting both the company's software-signing integrity and its TLS/PKI posture, and giving customers a publicly auditable trust guarantee.

Secure Implementation Patterns

The anti-pattern. Trust the log's claimed root, or hash without domain separation:

if claimed_root == recompute(leaf, path): trusted()   # no STH signature -> attacker forges the root
H(left + right)                                         # no 0x00/0x01 -> internal node forgeable as leaf

The secure pattern — STH-first, domain-separated Merkle verification (mirrors solution.py):

def hash_leaf(data):  return sha256(b"\x00" + data).hexdigest()                  # RFC 6962 domain sep
def hash_node(l, r):  return sha256(b"\x01" + bytes.fromhex(l) + bytes.fromhex(r)).hexdigest()

def root_from_proof(leaf_data, proof):
    node = hash_leaf(leaf_data)
    for step in proof:                                                            # walk leaf -> root
        node = hash_node(step.sibling, node) if step.sibling_is_left else hash_node(node, step.sibling)
    return node

def verify_inclusion(leaf_data, proof, sth, *, trusted_logs):
    ok, reason = verify_sth(sth, trusted_logs=trusted_logs)                       # 1. TRUST the root first
    if not ok:
        return False, reason                                                      #    (untrusted/forged STH)
    if not hmac.compare_digest(root_from_proof(leaf_data, proof), sth.root):
        return False, "not-included"                                             # 2/3. recompute + compare
    return True, "included"

The real-world equivalent (Phase 14 HITCHHIKERS): rekor-cli get returns the entry + inclusion proof; cosign/clients verify it against Rekor's signed tree head. Browsers do the same for CT.

Production practices to carry forward:

Verify the signed tree head before the proof — recomputing a root the attacker chose proves nothing; trust the root via the log operator's signature first.
Use RFC 6962 domain separation (0x00 leaf / 0x01 node) to stop second-preimage forgery.
Monitor the log for entries under your identities you didn't create — the auditability is the point.
Pin trusted log keys, and for production, verify consistency proofs too (that the log is truly append-only between tree heads).

Validation — What You Should Be Able to Do Now

Explain how a transparency log makes a signature auditable and why append-only matters.
Implement RFC 6962 domain-separated hashing and explain the second-preimage attack it prevents.
Verify an inclusion proof: STH-first, recompute root, compare; detect a forged STH, an untrusted log, a tampered audit path, and a not-included entry.

The Broader Perspective

This lab teaches public verifiability — the idea that trust scales when it can be audited by anyone, not just asserted by an authority. Merkle trees and transparency logs recur across security: Certificate Transparency (TLS/PKI), Sigstore/Rekor (software signing), the hash-chained audit ledger (Phase 11), git itself, and blockchains. The deep pattern — an append-only, tamper-evident, publicly-auditable record of security-relevant events — is one of the most powerful tools you have for making "trust me" into "verify me." Mastering the inclusion-proof math lets you reason about, and build, auditable trust into any system.

Interview Q&A

"How does a transparency log let you trust a signature?" — Every signing event is in an append-only Merkle log whose root the operator signs; an inclusion proof (audit path) lets you recompute the root from your leaf and check it against the signed root, proving the entry is logged. Public + append-only means a malicious signature can't hide. RFC 6962's 0x00/0x01 prefixes stop presenting a node as a leaf.
"Why verify the signed tree head first?" — Otherwise you're checking your leaf against a root the attacker supplied; the STH signature is what makes the root trustworthy before you use it.

Extension (Stretch)

Implement RFC 6962 consistency proofs (prove the log is append-only between two tree heads), handle non-power-of-two trees with the index-based RFC 6962 algorithm, and verify a real Rekor entry's inclusion proof with rekor-cli.

References

RFC 6962 (Certificate Transparency — Merkle inclusion/consistency proofs); Sigstore/Rekor docs.
Phase 14 WARMUP Chapter 6; Phase 11 (hash-chained ledger) cross-reference.

Security Engineer