How to Build a Merkle Tree Certificate Issuer in Python to Keep Post-Quantum Certificates Small

Every secure connection starts with a proof of identity. A server hands your browser a certificate, a small signed document that ties a domain name to a public key, and the browser checks the signature of the certificate authority (CA) that issued it. Today those signatures are tiny. The post-quantum signatures meant to replace them, which are designed to stay secure against a future quantum computer, are much larger. Cloudflare’s September 29, 2026 announcement says that “PQ signatures are roughly 40 times larger than classical ones” and that a typical TLS handshake already carries “five signatures and two keys”. Swap every one of those for a post-quantum equivalent and each full handshake begins by downloading roughly 15 kilobytes of signatures and keys before a single byte of your page arrives.

Cloudflare says the answer with broad industry support is Merkle Tree Certificates (MTCs), which it calls “the path forward”. In its words, “MTCs batch certificates into an append-only Merkle tree, allowing a CA to sign the root of that tree instead of many individual certificates.” Cloudflare says its new CA will support MTC issuance, “targeting early 2027 for inclusion in Chrome’s newly launched Quantum-resistant Root Store”. The design is specified in an IETF draft from the PLANTS working group, draft-ietf-plants-merkle-tree-certs, and I worked from revision 06, posted on September 21, 2026.

In this tutorial you will build a working miniature of that design in Python and measure it. You will write a CA that issues certificates by appending them to a log, signs a whole batch of them with one ML-DSA signature (the post-quantum signature scheme standardized in NIST’s FIPS 204), and hands each website a short proof instead of a signature of its own. Then you will add the trick Cloudflare calls the landmark optimization, which lets an up-to-date browser accept a certificate that carries no signatures at all, and you will attack your own code to see what it refuses. Every number in this post was printed by code you can run yourself.

The vocabulary you need

Nothing here requires cryptography experience, but eight terms come up constantly, so it helps to have them straight before you write any code.

• Certificate authority (CA): the organization that checks that a website controls its domain name and then vouches for the pairing of that name and a public key.
• Relying party: whoever checks a certificate before trusting it. In this tutorial that is a browser.
• Digital signature: a value that only the holder of a private key can produce and that anyone holding the matching public key can verify.
• Merkle tree: a tree of hashes. Every leaf is the hash of one entry, every interior node is the hash of its two children, and the single hash at the top, the root, changes if any entry changes.
• Inclusion proof: the handful of sibling hashes along the path from one leaf up to the root. Someone who knows only the root can use it to check that an entry really belongs to the tree.
• Issuance log: an append-only list of every certificate the CA has issued. New entries go on the end and old entries never change.
• Subtree: a slice of the log, written [start, end), that forms a Merkle tree by itself and has its own hash.
• Cosigner: a party that signs a subtree hash. The CA is one cosigner. An independent mirror, which keeps its own copy of the log, is another.

Two more terms name the two kinds of certificate you will build. A standalone certificate carries an inclusion proof plus the cosigners’ signatures, so any browser that trusts the cosigners can check it. A landmark-relative certificate carries only an inclusion proof, and works only for a browser that already holds the matching subtree hash.

What this tutorial is, and what it is not

The design is still an Internet-Draft, and details may change. My code borrows the draft’s ideas, its subtree rule and its size arithmetic, but not its wire format. There is no ASN.1 or X.509 encoding, no ACME issuance, no TLS handshake, and the bytes that get signed are my own layout. Treat the result as a lab for understanding the design, never as a certificate authority. A short list near the end names what the real draft adds.

Prerequisites

• Python 3.10 or newer. I tested on Python 3.13.14 on Windows 11.
• The cryptography package, version 47.0.0 or newer. Its documentation marks the ML-DSA classes as added in 47.0.0. I used 50.0.1, which installed from a prebuilt wheel with no compiler.
• pytest for the tests in Step 7 (I used 9.1.1).
• Comfort reading Python. If Merkle trees are new to you, the earlier tutorial on building a Merkle tree in Python explains hashing and proofs more slowly. This one moves quickly through the basics and spends its time on certificates.

Create a folder for the project, then create and activate a virtual environment and install the two packages:

python -m venv .venv
.venv\Scripts\activate           # on macOS or Linux: source .venv/bin/activate
pip install cryptography pytest

Over the seven steps you will create thirteen small files in that one folder: six modules (merkle.py, entries.py, ca.py, relying_party.py, server.py, scenario.py), six demo scripts named demo1_sizes.py to demo6_scale.py, and test_mtc.py. Each step shows a file, explains it, and shows what running it prints.

Step 1: Measure the problem

Before building the fix, see the problem with your own eyes. This script generates one key of each kind, signs the same message, and prints how many bytes each public key and signature takes. ECDSA on the P-256 curve stands in for today’s classical signatures. ML-DSA comes in three parameter sets, 44, 65 and 87, with larger numbers giving more security margin and bigger objects.

"""Step 1: measure how large post-quantum keys and signatures are."""

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec, mldsa
from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat

MESSAGE = b"sign this handshake transcript"


def p256_sizes():
    key = ec.generate_private_key(ec.SECP256R1())
    r, s = decode_dss_signature(key.sign(MESSAGE, ec.ECDSA(hashes.SHA256())))
    public = key.public_key().public_bytes(Encoding.X962, PublicFormat.UncompressedPoint)
    return len(public), len(r.to_bytes(32, "big") + s.to_bytes(32, "big"))


def mldsa_sizes(private_key_class):
    key = private_key_class.generate()
    return len(key.public_key().public_bytes_raw()), len(key.sign(MESSAGE))


schemes = {
    "ECDSA P-256": p256_sizes(),
    "ML-DSA-44": mldsa_sizes(mldsa.MLDSA44PrivateKey),
    "ML-DSA-65": mldsa_sizes(mldsa.MLDSA65PrivateKey),
    "ML-DSA-87": mldsa_sizes(mldsa.MLDSA87PrivateKey),
}

baseline = schemes["ECDSA P-256"][1]
print(f"{'scheme':<12} {'public key':>10} {'signature':>10} {'signature vs P-256':>19}")
for name, (public_len, sig_len) in schemes.items():
    print(f"{name:<12} {public_len:>10} {sig_len:>10} {sig_len / baseline:>18.1f}x")

SIGNATURES, KEYS = 5, 2  # Cloudflare: five signatures and two keys in a typical TLS handshake
print(f"\nAuthentication bytes for {SIGNATURES} signatures + {KEYS} public keys:")
for name, (public_len, sig_len) in schemes.items():
    print(f"  {name:<12} {SIGNATURES * sig_len + KEYS * public_len:>7,} bytes")

Run it with python demo1_sizes.py. You should see:

scheme       public key  signature  signature vs P-256
ECDSA P-256          65         64                1.0x
ML-DSA-44          1312       2420               37.8x
ML-DSA-65          1952       3309               51.7x
ML-DSA-87          2592       4627               72.3x

Authentication bytes for 5 signatures + 2 public keys:
  ECDSA P-256      450 bytes
  ML-DSA-44     14,724 bytes
  ML-DSA-65     20,449 bytes
  ML-DSA-87     28,319 bytes

What the numbers mean

ECDSA’s two 32-byte values, r and s, make a 64-byte signature (the ASN.1 wrapper used in real certificates adds a few bytes, which we ignore). The smallest ML-DSA set, ML-DSA-44, produces a 2,420-byte signature and a 1,312-byte public key, about 37.8 times the classical signature. Those sizes agree with Table 2 of NIST’s FIPS 204, and 37.8 is in line with Cloudflare’s “roughly 40 times”.

The second table multiplies by Cloudflare’s count of five signatures and two keys per handshake. Classical authentication costs 450 bytes. The same handshake built from ML-DSA-44 costs 14,724 bytes, about 33 times as much, and we chose the smallest parameter set. These totals count only signatures and keys, not names, dates or framing, so treat them as a budget rather than a packet capture.

Checkpoint: your ML-DSA-44 row should read 1312 and 2420. If the import of mldsa fails, your cryptography is older than 47.0.0, so run pip install --upgrade cryptography.

Step 2: Learn the data structure under MTCs

Merkle Tree Certificates lean on the Merkle tree from Certificate Transparency, as defined in RFC 9162. Create merkle.py. It has three jobs: hash a list of entries into one root, decide which slices of the list count as valid subtrees, and build and check inclusion proofs.

"""Merkle tree hashing and subtree inclusion proofs (RFC 9162 section 2.1, applied to subtrees)."""

import hashlib


def sha256(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()


def leaf_hash(entry: bytes) -> bytes:
    return sha256(b"\x00" + entry)  # 0x00 marks a leaf


def node_hash(left: bytes, right: bytes) -> bytes:
    return sha256(b"\x01" + left + right)  # 0x01 marks an interior node


def bit_ceil(n: int) -> int:
    """Smallest power of two that is >= n (and 1 for n = 0)."""
    return 1 if n <= 1 else 1 << (n - 1).bit_length()


def split_point(n: int) -> int:
    """Largest power of two strictly smaller than n (for n >= 2)."""
    return 1 << ((n - 1).bit_length() - 1)


def mth(entries: list[bytes]) -> bytes:
    """Merkle Tree Hash of a list of entries."""
    n = len(entries)
    if n == 0:
        return sha256(b"")
    if n == 1:
        return leaf_hash(entries[0])
    k = split_point(n)
    return node_hash(mth(entries[:k]), mth(entries[k:]))


def is_valid_subtree(start: int, end: int) -> bool:
    """The draft's alignment rule: start must be a multiple of bit_ceil(end - start)."""
    return 0 <= start <= end and start % bit_ceil(end - start) == 0


def subtree_hash(entries: list[bytes], start: int, end: int) -> bytes:
    if end > len(entries) or not is_valid_subtree(start, end):
        raise ValueError(f"[{start}, {end}) is not a valid subtree of a {len(entries)}-entry log")
    return mth(entries[start:end])


def _audit_path(entries: list[bytes], m: int) -> list[bytes]:
    n = len(entries)
    if n == 1:
        return []
    k = split_point(n)
    if m < k:
        return _audit_path(entries[:k], m) + [mth(entries[k:])]
    return _audit_path(entries[k:], m - k) + [mth(entries[:k])]


def inclusion_proof(entries: list[bytes], start: int, end: int, index: int) -> list[bytes]:
    """The sibling hashes needed to rebuild the hash of subtree [start, end) from entries[index]."""
    if end > len(entries) or not is_valid_subtree(start, end):
        raise ValueError(f"[{start}, {end}) is not a valid subtree of a {len(entries)}-entry log")
    if not start <= index < end:
        raise ValueError("index is not inside the subtree")
    return _audit_path(entries[start:end], index - start)


def root_from_proof(index: int, start: int, end: int, entry_hash: bytes, proof: list[bytes]) -> bytes:
    """Fold a proof into the subtree hash it implies (RFC 9162 section 2.1.3.2, on [start, end))."""
    if not is_valid_subtree(start, end) or not start <= index < end:
        raise ValueError("index or subtree is invalid")
    fn, sn = index - start, end - start - 1
    r = entry_hash
    for sibling in proof:
        if sn == 0:
            raise ValueError("proof is too long")
        if fn & 1 or fn == sn:
            r = node_hash(sibling, r)
            while not fn & 1 and fn != 0:  # skip levels where this node has no sibling
                fn >>= 1
                sn >>= 1
        else:
            r = node_hash(r, sibling)
        fn >>= 1
        sn >>= 1
    if sn != 0:
        raise ValueError("proof is too short")
    return r

Hashing with two prefixes

leaf_hash puts a 0x00 byte in front of an entry before hashing, and node_hash puts 0x01 in front of two child hashes. This is called domain separation. It guarantees that a hash computed for a leaf can never be confused with one computed for an interior node, which would otherwise let an attacker present two child hashes as a single entry. mth, the Merkle Tree Hash, splits a list at the largest power of two that is smaller than its length, hashes each side, and combines the results. A one-entry list is just its leaf hash.

Which slices are valid subtrees

You might expect any slice of the log to be a subtree. The draft is stricter: start must be a multiple of BIT_CEIL(end - start), where BIT_CEIL is the smallest power of two that is at least as large as its argument, and that is exactly what is_valid_subtree checks. The point of the rule is that only aligned slices line up with the shape of the big tree, so a smaller tree can be proven consistent with the larger one. The draft also states a property that makes signatures durable: “As a Merkle Tree grows, its subtrees remain unchanged.” A signature on a subtree therefore stays valid no matter how much the log grows afterwards.

Inclusion proofs

inclusion_proof collects, level by level, the hash of the sibling you would need to combine with. root_from_proof does the reverse: it folds those siblings back into one hash. The variables fn and sn track the entry’s position and the last position at the current level, which tells the function whether each sibling sits to the left or the right, and lets it refuse proofs that are too long or too short. It is the verification algorithm from RFC 9162 section 2.1.3.2, applied to the range [start, end) instead of the whole tree, which is how the draft’s subtree proofs in its section 4.3 work.

Now create demo2_merkle.py to try all three ideas on a 13-entry log, the size of the draft’s Figure 3:

"""Step 2: check subtrees, then build and evaluate an inclusion proof."""

from merkle import inclusion_proof, is_valid_subtree, leaf_hash, root_from_proof, subtree_hash

entries = [f"entry-{i}".encode() for i in range(13)]  # 13 entries, like Figure 3 in the draft

print("Which ranges are valid subtrees?")
for start, end in [(0, 13), (4, 8), (8, 13), (6, 8), (12, 13), (3, 7), (2, 6), (5, 9), (12, 24)]:
    print(f"  [{start:>2}, {end:>2})  valid = {is_valid_subtree(start, end)}")

sub = subtree_hash(entries, 8, 13)
print("\nhash of subtree [8, 13) at 13 entries :", sub.hex()[:24], "...")

grown = entries + [f"entry-{i}".encode() for i in range(13, 20)]
print("hash of subtree [8, 13) at 20 entries :", subtree_hash(grown, 8, 13).hex()[:24], "...")
print("unchanged after the log grew          :", subtree_hash(grown, 8, 13) == sub)

index = 10
proof = inclusion_proof(entries, 8, 13, index)
print(f"\nproof that entry {index} is inside [8, 13): {len(proof)} sibling hashes")
for i, sibling in enumerate(proof):
    print(f"  sibling {i}: {sibling.hex()[:24]} ...")
rebuilt = root_from_proof(index, 8, 13, leaf_hash(entries[index]), proof)
print("proof rebuilds the subtree hash       :", rebuilt == sub)

Run python demo2_merkle.py. Your hashes will match mine because the entries are fixed strings:

Which ranges are valid subtrees?
  [ 0, 13)  valid = True
  [ 4,  8)  valid = True
  [ 8, 13)  valid = True
  [ 6,  8)  valid = True
  [12, 13)  valid = True
  [ 3,  7)  valid = False
  [ 2,  6)  valid = False
  [ 5,  9)  valid = False
  [12, 24)  valid = False

hash of subtree [8, 13) at 13 entries : d482cd9b9a5abf2c2026a173 ...
hash of subtree [8, 13) at 20 entries : d482cd9b9a5abf2c2026a173 ...
unchanged after the log grew          : True

proof that entry 10 is inside [8, 13): 3 sibling hashes
  sibling 0: 5b0dd1c265fcb991f5423cf4 ...
  sibling 1: 1a1381c863f0033dfb056983 ...
  sibling 2: 62f2725ac8bfff3f113f0c66 ...
proof rebuilds the subtree hash       : True

Reading the output

The validity table follows the rule: [4, 8) starts on a multiple of 4 and [8, 13) starts on a multiple of 8, so both are valid, while [3, 7) and [2, 6) hold four entries but start off the grid. The last row, [12, 24), is the instructive failure. It holds 12 entries, BIT_CEIL(12) is 16, and 12 is not a multiple of 16. So a CA cannot simply declare the next 12 certificates to be a subtree. The real draft handles arbitrary intervals by covering them with two valid subtrees: “While one subtree can be inefficient, two subtrees are sufficient to efficiently cover any interval”. To keep this lab short, our CA only closes blocks whose size is a power of two.

The two hashes for [8, 13) are identical even though the log grew from 13 to 20 entries, which is the “subtrees remain unchanged” property in action. Finally, entry 10 needs three sibling hashes to reach the hash of [8, 13). Here is where they come from:

                 [8, 13)                <- the hash a cosigner signs
                /       \
          [8, 12)        entry 12       <- sibling 3
          /     \
     [8, 10)   [10, 12)                 <- sibling 2 is [8, 10)
               /      \
          entry 10   entry 11           <- sibling 1 is entry 11

Starting from entry 10, combine with entry 11 to get [10, 12), combine that with [8, 10) to get [8, 12), then combine with entry 12 to reach [8, 13). Three hashes, 96 bytes, prove membership in a range of five entries, and the count grows only logarithmically with the range size.

Checkpoint: you should see valid = False for exactly four rows, unchanged after the log grew : True, and proof rebuilds the subtree hash : True.

Step 3: Issue by logging

Here is the idea that gives MTCs their nickname. A traditional CA signs each certificate and then submits it to transparency logs afterwards. An MTC CA has no separate signing step: its issuance log is the list of certificates it has issued. Cloudflare summarizes the philosophy as “don’t log what you issue, issue by logging.” Transparency stops being an add-on, because a certificate that is not in the log does not exist.

The log entry

Create entries.py. An entry records what the CA certified: the subject name, the validity period, and the subscriber’s key.

"""A simplified issuance-log entry, loosely modeled on the draft's MTCLogEntry."""

import hashlib
import struct

TBS_CERT_ENTRY = 1  # the draft's entry type for "this entry certifies a subject and a key"


def encode_entry(subject: str, public_key: bytes, not_before: int, not_after: int) -> bytes:
    subject_bytes = subject.encode("utf-8")
    key_hash = hashlib.sha256(public_key).digest()  # the log stores a hash of the key, not the key
    return b"".join(
        [
            struct.pack(">H", 0),  # extensions: an empty list
            struct.pack(">H", TBS_CERT_ENTRY),
            struct.pack(">H", len(subject_bytes)),
            subject_bytes,
            struct.pack(">QQ", not_before, not_after),
            key_hash,
        ]
    )

Why the log stores a hash of the key

Notice key_hash: the entry holds a SHA-256 hash of the subscriber’s public key, not the key. This mirrors the draft, whose TBSCertificateLogEntry carries a subjectPublicKeyInfoHash field and whose text says: “TBSCertificateLogEntry does not include signatures and hashes public keys, so post-quantum algorithms do not contribute to this size.” Cloudflare makes the same point about the logs: “the log only needs to carry hashes of public keys; there are no per-entry signatures, and the signature on the tree head covers the whole log.” You will see the effect in a moment: a 67-byte entry stands in for a key that alone is 1,312 bytes.

The CA, its cosigners and its certificates

Create ca.py. It defines a Cosigner that signs with ML-DSA-44, a Certificate that carries an inclusion proof and optional signatures, a Landmark (used in Step 4), and the CertificationAuthority that ties them together.

"""A miniature Merkle Tree CA: an issuance log, cosigners, standalone and landmark-relative certificates."""

import hashlib
import struct
from dataclasses import dataclass, field

from cryptography.hazmat.primitives.asymmetric import mldsa

from entries import encode_entry
from merkle import inclusion_proof, subtree_hash

SIGNATURE_CONTEXT = b"mtc-teaching-demo/subtree/v1"


def cosigned_message(log_origin: str, start: int, end: int, subtree: bytes) -> bytes:
    """The bytes a cosigner signs: which log, which range of entries, which hash."""
    origin = log_origin.encode("utf-8")
    return struct.pack(">H", len(origin)) + origin + struct.pack(">QQ", start, end) + subtree


class Cosigner:
    """Holds an ML-DSA-44 key and signs subtrees of a named log."""

    def __init__(self, name: str, seed_label: str | None = None):
        self.name = name
        seed = hashlib.sha256(b"demo-seed/" + (seed_label or name).encode()).digest()  # repeatable keys
        self._key = mldsa.MLDSA44PrivateKey.from_seed_bytes(seed)
        self.public_key = self._key.public_key()

    def sign(self, log_origin: str, start: int, end: int, subtree: bytes) -> bytes:
        return self._key.sign(cosigned_message(log_origin, start, end, subtree), SIGNATURE_CONTEXT)


@dataclass
class Certificate:
    subject: str
    public_key: bytes
    not_before: int
    not_after: int
    index: int  # position of this certificate's entry in the issuance log
    start: int  # the subtree [start, end) that the proof leads to
    end: int
    proof: list[bytes]
    signatures: dict[str, bytes] = field(default_factory=dict)  # empty for landmark-relative

    @property
    def proof_bytes(self) -> int:
        return sum(len(h) for h in self.proof)

    @property
    def signature_bytes(self) -> int:
        return sum(len(s) for s in self.signatures.values())


@dataclass
class Landmark:
    start: int
    end: int
    subtree_hash: bytes
    signatures: dict[str, bytes]


class CertificationAuthority:
    def __init__(self, ca_id: str, cosigners: list[Cosigner], standalone_block: int = 4, landmark_block: int = 16):
        self.ca_id = ca_id
        self.cosigners = cosigners
        self.standalone_block = standalone_block
        self.landmark_block = landmark_block
        self.entries: list[bytes] = []  # the issuance log
        self.requests: list[tuple] = []  # what each entry certified: subject, key, validity
        self.landmarks: list[Landmark] = []

    def issue(self, subject: str, public_key: bytes, not_before: int, not_after: int) -> Certificate:
        """Issue by logging: appending the entry to the log IS issuing the certificate."""
        index = len(self.entries)
        self.entries.append(encode_entry(subject, public_key, not_before, not_after))
        self.requests.append((subject, public_key, not_before, not_after))
        return self.standalone_certificate(index)

    def _cosign(self, start: int, end: int) -> tuple[bytes, dict[str, bytes]]:
        digest = subtree_hash(self.entries, start, end)
        return digest, {c.name: c.sign(self.ca_id, start, end, digest) for c in self.cosigners}

    def _certificate(self, index: int, start: int, end: int, signatures: dict[str, bytes]) -> Certificate:
        subject, key, not_before, not_after = self.requests[index]
        proof = inclusion_proof(self.entries, start, end, index)
        return Certificate(subject, key, not_before, not_after, index, start, end, proof, signatures)

    def standalone_certificate(self, index: int) -> Certificate:
        start = index - index % self.standalone_block
        end = min(start + self.standalone_block, len(self.entries))
        _, signatures = self._cosign(start, end)
        return self._certificate(index, start, end, signatures)

    def allocate_landmark(self) -> Landmark | None:
        """Close the next full block of entries as a landmark, if that many entries exist."""
        start = self.landmarks[-1].end if self.landmarks else 0
        end = start + self.landmark_block
        if end > len(self.entries):
            return None
        digest, signatures = self._cosign(start, end)
        landmark = Landmark(start, end, digest, signatures)
        self.landmarks.append(landmark)
        return landmark

    def landmark_certificate(self, index: int) -> Certificate | None:
        """A signature-free certificate, possible only once a landmark covers this entry."""
        for landmark in self.landmarks:
            if landmark.start <= index < landmark.end:
                return self._certificate(index, landmark.start, landmark.end, {})
        return None

Take it in pieces:

• Cosigner generates an ML-DSA-44 key from a seed derived from its name, purely so your demo keys are identical on every run; a real cosigner would generate a random key and guard it carefully. Its sign method signs a message that names the log, the range [start, end) and the subtree hash. ML-DSA accepts an optional context string when signing, and we pass a fixed one so that a signature made by the same key under a different context will not verify here.
• issue is issuing by logging. It appends the encoded entry to self.entries, remembers what the entry certified, and returns a standalone certificate.
• standalone_certificate picks the subtree: it starts at the beginning of the entry’s block of four and ends at the block’s end or the current end of the log, whichever comes first. Because start is a multiple of the block size, the alignment rule holds automatically. Then _cosign hashes that subtree and asks every cosigner to sign it. Four entries per block is a toy value. The draft’s own estimate for a busy CA is subtrees of around 3,000 certificates.
• Cloudflare notes that Chrome’s draft policy “mandates at least two cosignatures: one from a Chrome-recognized Mirroring Cosigner operated by a distinct organization, and one from the issuing MTC CA itself.” So our CA is configured with two cosigners: itself and a mirror.

The relying party

Create relying_party.py. This is the browser’s side, and it is the most important file in the project, because it decides what is trusted.

"""A relying party (think: a browser) that verifies certificates from the miniature CA."""

from cryptography.exceptions import InvalidSignature

from ca import SIGNATURE_CONTEXT, Certificate, Landmark, cosigned_message
from entries import encode_entry
from merkle import leaf_hash, root_from_proof


class RelyingParty:
    def __init__(self, ca_id: str, cosigner_keys: dict, required_cosigners: list[str]):
        self.ca_id = ca_id
        self.cosigner_keys = cosigner_keys  # cosigner name -> ML-DSA-44 public key
        self.required_cosigners = required_cosigners  # policy: every one of these must have signed
        self.trusted_subtrees: dict[tuple[int, int], bytes] = {}  # (start, end) -> subtree hash

    def _cosigned(self, start: int, end: int, subtree: bytes, signatures: dict[str, bytes]) -> bool:
        message = cosigned_message(self.ca_id, start, end, subtree)
        for name in self.required_cosigners:
            key, signature = self.cosigner_keys.get(name), signatures.get(name)
            if key is None or signature is None:
                return False
            try:
                key.verify(signature, message, SIGNATURE_CONTEXT)
            except InvalidSignature:
                return False
        return True

    def install_landmark(self, landmark: Landmark) -> bool:
        """The out-of-band update: trust a landmark subtree only if it is properly cosigned."""
        if not self._cosigned(landmark.start, landmark.end, landmark.subtree_hash, landmark.signatures):
            return False
        self.trusted_subtrees[(landmark.start, landmark.end)] = landmark.subtree_hash
        return True

    def verify(self, cert: Certificate, now: int) -> tuple[bool, str]:
        if not cert.not_before <= now <= cert.not_after:
            return False, "rejected: outside the validity period"
        # Rebuild the log entry from what the certificate claims, then hash it as a leaf.
        entry = encode_entry(cert.subject, cert.public_key, cert.not_before, cert.not_after)
        try:
            subtree = root_from_proof(cert.index, cert.start, cert.end, leaf_hash(entry), cert.proof)
        except ValueError as exc:
            return False, f"rejected: bad inclusion proof ({exc})"
        trusted = self.trusted_subtrees.get((cert.start, cert.end))
        if trusted is not None:
            if trusted == subtree:
                return True, "accepted: matches a trusted landmark subtree, no signature checked"
            return False, "rejected: this range is a trusted landmark, but the hash differs"
        if self._cosigned(cert.start, cert.end, subtree, cert.signatures):
            return True, "accepted: the subtree is cosigned by every required cosigner"
        return False, "rejected: not a trusted landmark and not sufficiently cosigned"

The verify method follows the same order as the draft’s verification procedure:

1. Check the validity period. The draft is explicit that the new scheme replaces only one part of certificate checking: “This procedure only replaces the signature verification portion of X.509 path validation. The relying party MUST continue to perform other checks, such as checking expiry.”
2. Rebuild the log entry from the certificate’s own claims (subject, key, validity) and hash it as a leaf. The browser never trusts a stored entry, so any changed field changes the hash.
3. Fold the inclusion proof into the subtree hash it implies.
4. If that (start, end) range is a trusted subtree, the hash must match it exactly. No signature is checked.
5. Otherwise, require valid signatures from every cosigner the browser’s policy names.

Run it

Create scenario.py, which builds a CA with two cosigners, gives it a batch of subscribers and provides a browser to test against. It uses a fixed current time so the output is repeatable.

"""Shared demo setup: a CA, a mirror cosigner, and a batch of subscribers."""

import hashlib

from cryptography.hazmat.primitives.asymmetric import mldsa

from ca import CertificationAuthority, Cosigner
from relying_party import RelyingParty

CA_ID = "ca.example"
NOW = 1_790_000_000  # a fixed "current time" in Unix seconds, so the output is repeatable
WEEK = 7 * 24 * 3600


def subscriber_key(i: int) -> bytes:
    seed = hashlib.sha256(f"subscriber-{i}".encode()).digest()
    return mldsa.MLDSA44PrivateKey.from_seed_bytes(seed).public_key().public_bytes_raw()


def build_ca(count: int):
    """A CA with two cosigners (itself and a mirror) that has issued `count` certificates."""
    ca = CertificationAuthority(CA_ID, [Cosigner(CA_ID), Cosigner("mirror.example")])
    certs = [ca.issue(f"site{i}.example", subscriber_key(i), NOW - 3600, NOW + WEEK) for i in range(count)]
    return ca, certs


def new_relying_party(ca: CertificationAuthority) -> RelyingParty:
    keys = {cosigner.name: cosigner.public_key for cosigner in ca.cosigners}
    return RelyingParty(CA_ID, keys, required_cosigners=[cosigner.name for cosigner in ca.cosigners])

Now demo3_standalone.py issues six certificates and verifies each one:

"""Step 3: issue by logging, then verify standalone certificates."""

from scenario import NOW, build_ca, new_relying_party

ca, certs = build_ca(6)
browser = new_relying_party(ca)

print(f"log size: {len(ca.entries)} entries; cosigners: {[c.name for c in ca.cosigners]}")
print(f"one log entry is {len(ca.entries[0])} bytes; one ML-DSA-44 public key alone is {len(certs[0].public_key)} bytes\n")
for cert in certs:
    ok, why = browser.verify(cert, NOW)
    print(
        f"{cert.subject:<14} index={cert.index} subtree=[{cert.start},{cert.end}) "
        f"proof={len(cert.proof)} hashes ({cert.proof_bytes:>2} B) "
        f"signatures={cert.signature_bytes:>4} B -> {ok}"
    )
print("\nverdict for the last certificate:", why)

Run python demo3_standalone.py:

log size: 6 entries; cosigners: ['ca.example', 'mirror.example']
one log entry is 67 bytes; one ML-DSA-44 public key alone is 1312 bytes

site0.example  index=0 subtree=[0,1) proof=0 hashes ( 0 B) signatures=4840 B -> True
site1.example  index=1 subtree=[0,2) proof=1 hashes (32 B) signatures=4840 B -> True
site2.example  index=2 subtree=[0,3) proof=1 hashes (32 B) signatures=4840 B -> True
site3.example  index=3 subtree=[0,4) proof=2 hashes (64 B) signatures=4840 B -> True
site4.example  index=4 subtree=[4,5) proof=0 hashes ( 0 B) signatures=4840 B -> True
site5.example  index=5 subtree=[4,6) proof=1 hashes (32 B) signatures=4840 B -> True

verdict for the last certificate: accepted: the subtree is cosigned by every required cosigner

Read it row by row. The first line confirms the effect of hashing keys: one log entry is 67 bytes while one ML-DSA-44 public key is 1,312. site0 was the first entry, so at that moment its subtree was [0,1), with an empty proof. site2 was issued when the log held three entries, so its subtree is [0,3) and it needs one sibling hash. By site4 the first block of four is complete, so a new block begins at [4,5). Every row carries 4,840 bytes of signatures, which is two ML-DSA-44 signatures of 2,420 bytes each: one from the CA and one from the mirror. Every certificate verifies.

Checkpoint: all six rows end in True, and the verdict line says the subtree is cosigned by every required cosigner.

Step 4: Drop the signatures with landmarks

A standalone certificate works for any browser that trusts the cosigners, but look at what it costs: 4,840 bytes of signatures to protect 32 bytes of proof. The draft’s answer is the landmark-relative certificate, which “contains no signatures and instead assumes the relying party had predistributed information about which subtrees were trusted.”

The trick is to move the expensive part out of the handshake. The CA periodically closes a large subtree, a landmark, gets it cosigned once, and publishes it. Browsers download landmarks through an ordinary out-of-band update channel, verify the cosignatures once, and remember the subtree hash. From then on, any certificate whose proof leads to that subtree is convincing on the strength of hashes alone. Cloudflare describes the check this way: “If the inclusion proof connects that certificate to a cosigned landmark, and the public key then proves possession during the TLS handshake, the client knows it is talking to the right server.”

You already wrote most of the machinery. In ca.py, allocate_landmark closes the next block of 16 entries and cosigns it, and landmark_certificate builds a certificate with an empty signatures dictionary. In relying_party.py, install_landmark is the update channel: it stores a subtree hash only after the required cosigners have signed it. What is missing is the server’s choice of which certificate to send. Create server.py:

"""The server side of the handshake: pick which certificate to send."""

from ca import Certificate


def choose_certificate(
    standalone: Certificate, landmark_relative: Certificate | None, client_landmarks: set
) -> Certificate:
    """Send the small landmark-relative certificate only if the client says it holds that landmark."""
    if landmark_relative is not None and (landmark_relative.start, landmark_relative.end) in client_landmarks:
        return landmark_relative
    return standalone  # the fallback that always works

The function encodes a rule from the draft: “An authenticating party SHOULD NOT send a landmark-relative certificate without a signal that the relying party trusts the corresponding landmark subtree.” In real TLS that signal travels in the handshake (the draft recommends using TLS trust anchor IDs), and the same section adds a preference: “If both a landmark-relative and a standalone certificate are usable, an authenticating party SHOULD preferentially use the landmark-relative certificate.” Our version passes the browser’s landmarks in as a set. Now create demo4_landmark.py:

"""Step 4: landmarks let an up-to-date client skip the signatures entirely."""

from scenario import NOW, build_ca, new_relying_party
from server import choose_certificate

ca, standalone_certs = build_ca(20)
landmark = ca.allocate_landmark()
print(f"landmark allocated: [{landmark.start}, {landmark.end}) covers {landmark.end - landmark.start} certificates")

up_to_date, stale = new_relying_party(ca), new_relying_party(ca)
print("up-to-date browser installs the cosigned landmark:", up_to_date.install_landmark(landmark))
print("stale browser never received the update\n")

target = 5
standalone = standalone_certs[target]
landmark_cert = ca.landmark_certificate(target)
for label, cert in [("standalone", standalone), ("landmark-relative", landmark_cert)]:
    print(
        f"{label:<18} subtree=[{cert.start},{cert.end}) proof={len(cert.proof)} hashes "
        f"({cert.proof_bytes} B) + signatures {cert.signature_bytes} B "
        f"= {cert.proof_bytes + cert.signature_bytes} B"
    )

print("\nWhat each browser is served, and whether it accepts it:")
for name, browser in [("up-to-date", up_to_date), ("stale", stale)]:
    served = choose_certificate(standalone, landmark_cert, set(browser.trusted_subtrees))
    kind = "landmark-relative" if not served.signatures else "standalone"
    ok, why = browser.verify(served, NOW)
    print(f"  {name:<10} served {kind:<17} -> {ok}: {why}")

print("\nWhat if the stale browser were wrongly served the landmark-relative certificate?")
print("  ", stale.verify(landmark_cert, NOW)[1])

print("\nEntry 18 was issued after the landmark closed:")
print("   landmark_certificate(18) ->", ca.landmark_certificate(18))

Run python demo4_landmark.py:

landmark allocated: [0, 16) covers 16 certificates
up-to-date browser installs the cosigned landmark: True
stale browser never received the update

standalone         subtree=[4,6) proof=1 hashes (32 B) + signatures 4840 B = 4872 B
landmark-relative  subtree=[0,16) proof=4 hashes (128 B) + signatures 0 B = 128 B

What each browser is served, and whether it accepts it:
  up-to-date served landmark-relative -> True: accepted: matches a trusted landmark subtree, no signature checked
  stale      served standalone        -> True: accepted: the subtree is cosigned by every required cosigner

What if the stale browser were wrongly served the landmark-relative certificate?
   rejected: not a trusted landmark and not sufficiently cosigned

Entry 18 was issued after the landmark closed:
   landmark_certificate(18) -> None

What this shows

The landmark [0, 16) closes the first 16 certificates. For site5, the standalone certificate is 4,872 bytes (one 32-byte hash plus 4,840 bytes of signatures) while the landmark-relative one is 128 bytes (four hashes, no signatures), about 38 times smaller for the same entry. The proof got longer, from one hash to four, because the landmark subtree is bigger, but four hashes are nothing next to two signatures. The up-to-date browser paid for the two ML-DSA verifications once, when it installed the landmark, and every certificate in that landmark is now cheap.

The last three sections of the output show the costs the draft warns about. A stale browser advertises no landmarks, so it is served the standalone certificate and accepts it. Serve it the small one by mistake and it refuses. And entry 18 arrived after the landmark closed, so landmark_certificate(18) returns None: it must wait for the next landmark. The draft puts it plainly: “They require a processing delay to construct, and only work in a sufficiently up-to-date relying party.” Cloudflare draws the operational conclusion: “That’s why it’s important that servers retain a standalone certificate fallback.”

Checkpoint: the up-to-date browser gets a landmark-relative certificate and the stale one gets a standalone certificate, and both are accepted.

Step 5: Break it on purpose

A verifier is only as good as the things it refuses. Create demo5_attacks.py, which takes a good certificate and damages it seven ways, then tries a subtler attack on the update channel:

"""Step 5: break it on purpose and watch the relying party say no."""

import dataclasses

from ca import Cosigner
from scenario import NOW, WEEK, build_ca, new_relying_party, subscriber_key

ca, standalone_certs = build_ca(20)
landmark = ca.allocate_landmark()
browser = new_relying_party(ca)
browser.install_landmark(landmark)

good_landmark = ca.landmark_certificate(5)
good_standalone = standalone_certs[5]
print("baseline landmark-relative:", browser.verify(good_landmark, NOW)[0])
print("baseline standalone       :", browser.verify(good_standalone, NOW)[0])


def attempt(label, cert, now=NOW):
    ok, why = browser.verify(cert, now)
    print(f"{label:<42} -> {ok}: {why}")


print()
attempt("1. change the subject name", dataclasses.replace(good_landmark, subject="evil.example"))
attempt("2. swap in the attacker's key", dataclasses.replace(good_landmark, public_key=subscriber_key(999)))
attempt("3. claim a different index", dataclasses.replace(good_landmark, index=6))
attempt("4. truncate the proof", dataclasses.replace(good_landmark, proof=good_landmark.proof[:-1]))

only_ca = {k: v for k, v in good_standalone.signatures.items() if k == "ca.example"}
attempt("5. standalone, mirror signature missing", dataclasses.replace(good_standalone, signatures=only_ca))

impostor = Cosigner("mirror.example", seed_label="attacker")  # same name, different key
forged = dict(good_standalone.signatures)
forged["mirror.example"] = impostor.sign("ca.example", good_standalone.start, good_standalone.end, b"\x00" * 32)
attempt("6. standalone, forged mirror signature", dataclasses.replace(good_standalone, signatures=forged))

attempt("7. valid certificate, two weeks later", good_landmark, now=NOW + 2 * WEEK)

fake_update = dataclasses.replace(landmark, subtree_hash=b"\x11" * 32)  # attacker-chosen hash, real signatures
print("\n8. push a forged landmark update -> installed:", new_relying_party(ca).install_landmark(fake_update))

Run python demo5_attacks.py:

baseline landmark-relative: True
baseline standalone       : True

1. change the subject name                 -> False: rejected: this range is a trusted landmark, but the hash differs
2. swap in the attacker's key              -> False: rejected: this range is a trusted landmark, but the hash differs
3. claim a different index                 -> False: rejected: this range is a trusted landmark, but the hash differs
4. truncate the proof                      -> False: rejected: bad inclusion proof (proof is too short)
5. standalone, mirror signature missing    -> False: rejected: not a trusted landmark and not sufficiently cosigned
6. standalone, forged mirror signature     -> False: rejected: not a trusted landmark and not sufficiently cosigned
7. valid certificate, two weeks later      -> False: rejected: outside the validity period

8. push a forged landmark update -> installed: False

What each result teaches

• Attacks 1 to 3 change the subject, swap in an attacker’s key, or claim a different log position. Each one changes the leaf hash or the direction the proof folds, so the rebuilt subtree hash no longer equals the trusted landmark. The browser reports the same message for all three because it cannot say which field was wrong, only that the result is not the hash it trusts. One comparison catches every edit.
• Attack 4 drops one hash from the proof. The length check at the end of root_from_proof rejects it as too short, so the browser never gets as far as comparing hashes.
• Attacks 5 and 6 target standalone certificates, where signatures are the only defense. Removing the mirror’s signature violates the browser’s policy, and forging it with a different key fails ML-DSA verification, which the code catches as InvalidSignature.
• Attack 7 is a perfectly valid certificate presented two weeks after it expired. Nothing about hashes or signatures covers this, which is why verify checks the validity period first.

Why installing a landmark must check signatures

Attack 8 is the one to remember. The attacker takes a real landmark update, keeps the genuine signatures, and swaps in a hash of their own choosing. The signatures cover the hash, so they no longer verify and the update is refused. If install_landmark skipped that check, an attacker who could reach the update channel could plant a trusted subtree containing certificates for any name they liked, and every landmark-relative certificate would then pass without a single signature being examined. The update channel is part of your trust base, and it must be authenticated with the same cosigners as everything else.

Checkpoint: all seven attempts print False and the update line says installed: False.

Step 6: Measure how it scales

You have seen the design work on 16 certificates. The whole point is that it keeps working at Internet scale, so create demo6_scale.py. It measures real proofs, builds a tree of more than a million entries, reproduces the draft’s own size estimates, totals up the handshake budgets, and times the two kinds of verification.

"""Step 6: how do proofs grow, and what does a handshake cost?"""

import hashlib
import time

from cryptography.hazmat.primitives.asymmetric import mldsa

from merkle import inclusion_proof, leaf_hash, mth, root_from_proof

HASH = 32
MLDSA44_SIGNATURE, MLDSA44_KEY = 2420, 1312
P256_SIGNATURE, P256_KEY = 64, 65


def proof_hashes(n: int) -> int:
    """Worst-case proof length for a subtree of n entries: ceil(log2(n))."""
    return (n - 1).bit_length()


print("Measured proofs for the leftmost entry (the longest path):")
for n in [1, 2, 3, 5, 8, 100, 3000, 8192]:
    entries = [b"e%d" % i for i in range(n)]
    measured = len(inclusion_proof(entries, 0, n, 0))
    print(f"  {n:>5} entries: {measured:>2} hashes measured, formula says {proof_hashes(n):>2}")

n = 1 << 20
start_time = time.perf_counter()
entries = [i.to_bytes(4, "big") for i in range(n)]
root = mth(entries)
proof = inclusion_proof(entries, 0, n, 777_777)
elapsed = time.perf_counter() - start_time
rebuilt = root_from_proof(777_777, 0, n, leaf_hash(entries[777_777]), proof)
print(f"\nA real tree of {n:,} entries: proof = {len(proof)} hashes = {len(proof) * HASH} bytes")
print(f"  proof rebuilds the root: {rebuilt == root}   (built and proved in {elapsed:.1f} s)")

print("\nThe draft's own estimates, from the formula:")
sizes = [("standalone subtree, about 3,000 certificates", 3000), ("landmark subtree, about 5,400,000", 5_400_000),
         ("subtree of 2**32 certificates", 2**32)]
for label, count in sizes:
    hashes = proof_hashes(count)
    print(f"  {label:<46} {hashes:>2} hashes = {hashes * HASH:>4} bytes")
landmark_proof = proof_hashes(5_400_000) * HASH
print(f"  three ML-DSA-44 signatures = {3 * MLDSA44_SIGNATURE} bytes = {3 * MLDSA44_SIGNATURE / landmark_proof:.1f}x that proof")

standalone_proof = proof_hashes(3000) * HASH
budgets = {
    "classical: 5 signatures + 2 keys": 5 * P256_SIGNATURE + 2 * P256_KEY,
    "naive ML-DSA-44 swap: 5 signatures + 2 keys": 5 * MLDSA44_SIGNATURE + 2 * MLDSA44_KEY,
    "MTC standalone: key + signature + proof + 2 cosignatures": MLDSA44_KEY + MLDSA44_SIGNATURE + standalone_proof + 2 * MLDSA44_SIGNATURE,
    "MTC landmark-relative: key + signature + proof": MLDSA44_KEY + MLDSA44_SIGNATURE + landmark_proof,
}
print("\nAuthentication bytes in one handshake (ignoring names, dates and framing):")
for label, total in budgets.items():
    print(f"  {label:<58} {total:>7,}")

key = mldsa.MLDSA44PrivateKey.generate()
public, message = key.public_key(), b"transcript"
signature = key.sign(message)
runs = 2000
t0 = time.perf_counter()
for _ in range(runs):
    public.verify(signature, message)
verify_us = (time.perf_counter() - t0) / runs * 1e6
fake_proof = [hashlib.sha256(bytes([i])).digest() for i in range(23)]
entry_hash = leaf_hash(b"x")
t0 = time.perf_counter()
for _ in range(runs):
    root_from_proof(1_234_567, 0, 2**23, entry_hash, fake_proof)
proof_us = (time.perf_counter() - t0) / runs * 1e6
print(f"\nOn this machine: ML-DSA-44 verify = {verify_us:.0f} us, a 23-hash proof = {proof_us:.0f} us")

Run python demo6_scale.py. It takes a few seconds because it hashes over a million entries:

Measured proofs for the leftmost entry (the longest path):
      1 entries:  0 hashes measured, formula says  0
      2 entries:  1 hashes measured, formula says  1
      3 entries:  2 hashes measured, formula says  2
      5 entries:  3 hashes measured, formula says  3
      8 entries:  3 hashes measured, formula says  3
    100 entries:  7 hashes measured, formula says  7
   3000 entries: 12 hashes measured, formula says 12
   8192 entries: 13 hashes measured, formula says 13

A real tree of 1,048,576 entries: proof = 20 hashes = 640 bytes
  proof rebuilds the root: True   (built and proved in 2.0 s)

The draft's own estimates, from the formula:
  standalone subtree, about 3,000 certificates   12 hashes =  384 bytes
  landmark subtree, about 5,400,000              23 hashes =  736 bytes
  subtree of 2**32 certificates                  32 hashes = 1024 bytes
  three ML-DSA-44 signatures = 7260 bytes = 9.9x that proof

Authentication bytes in one handshake (ignoring names, dates and framing):
  classical: 5 signatures + 2 keys                               450
  naive ML-DSA-44 swap: 5 signatures + 2 keys                 14,724
  MTC standalone: key + signature + proof + 2 cosignatures     8,956
  MTC landmark-relative: key + signature + proof               4,468

On this machine: ML-DSA-44 verify = 66 us, a 23-hash proof = 10 us

Proof size grows with the logarithm

The first block compares measured proof lengths with the formula (n - 1).bit_length(), which is the ceiling of the base-2 logarithm of n. They agree at every size, from a single entry up to 8,192 entries (13 hashes). The second block builds a real tree of 1,048,576 entries and proves entry 777,777 with 20 hashes, 640 bytes, and the proof rebuilds the root. A million certificates share a single cosigned hash, and each carries 640 bytes of proof.

The third block uses the same formula on the draft’s own scenarios and lands on its numbers. Section 6.5 estimates about 3,000 certificates per standalone subtree (12 hashes, 384 bytes) and about 5,400,000 per landmark subtree (23 hashes, 736 bytes). It also says: “Proof sizes grow logarithmically, so 32 hashes, or 1024 bytes, is sufficient for subtrees of up to 2^32 (4,294,967,296) certificates.” The 736-byte landmark proof is, in the draft’s words, “almost ten times smaller than the three ML-DSA-44 signatures necessary to include post-quantum SCTs”. Our arithmetic says 7,260 bytes divided by 736 is 9.9.

The handshake budget

The last table puts four designs side by side, using the same 450 and 14,724 byte baselines from Step 1:

• Naive swap, 14,724 bytes. Replace all five signatures and both keys with ML-DSA-44.
• MTC standalone, 8,956 bytes. One public key (1,312), one signature proving the server holds its key (2,420), a 12-hash proof (384), and two cosignatures (4,840).
• MTC landmark-relative, 4,468 bytes. The same key and signature plus a 23-hash proof (736), with no cosignatures. This is exactly the shape Cloudflare reports from its Chrome experiment: “the handshake only needs to transmit one public key, one signature, and one inclusion proof of less than 1kB”.
• Classical today, 450 bytes. For reference.

So a landmark-relative MTC handshake is about a third of the naive post-quantum swap, and the standalone fallback still beats it by roughly 40 percent. Cloudflare’s experiment used classical signatures rather than post-quantum ones, and it reported that landmark MTCs were 9 percent faster at the median than a classical chain, with most of that gain coming from dropping intermediate certificates. Cloudflare expects the improvement to grow once post-quantum signatures are in play, but that has not been measured yet.

Is verification slower?

The final line times both checks on my machine: an ML-DSA-44 signature verification took about 65 microseconds and a 23-hash proof took about 10 microseconds in pure Python. Your numbers will differ, and neither is large next to the delay of a single network round trip. The argument for MTCs is not saved CPU time. It is bytes: on the wire in every handshake, and in the logs that must store every certificate.

Checkpoint: the measured and formula columns match on every row, the million-entry proof is 20 hashes, and the draft-estimate block prints 384, 736 and 1024 bytes.

Step 7: Lock it in with tests

The demos show behavior once. Tests keep it true when you change something. Create test_mtc.py:

import dataclasses
import hashlib

import pytest

from ca import Cosigner
from merkle import inclusion_proof, is_valid_subtree, leaf_hash, node_hash, root_from_proof, subtree_hash
from scenario import NOW, WEEK, build_ca, new_relying_party, subscriber_key
from server import choose_certificate


def test_leaves_and_nodes_are_domain_separated():
    assert leaf_hash(b"") == hashlib.sha256(b"\x00").digest()
    left, right = leaf_hash(b"a"), leaf_hash(b"b")
    assert node_hash(left, right) == hashlib.sha256(b"\x01" + left + right).digest()
    assert leaf_hash(left + right) != node_hash(left, right)


def test_subtree_alignment_rule():
    for start, end in [(0, 13), (4, 8), (8, 13), (6, 8), (5, 5), (12, 13)]:
        assert is_valid_subtree(start, end)
    for start, end in [(3, 7), (2, 6), (5, 9), (9, 8)]:
        assert not is_valid_subtree(start, end)


@pytest.mark.parametrize("n", range(1, 34))
def test_every_proof_in_every_valid_subtree_rebuilds_its_hash(n):
    entries = [b"e%d" % i for i in range(n)]
    for start in range(n):
        for end in range(start + 1, n + 1):
            if not is_valid_subtree(start, end):
                continue
            expected = subtree_hash(entries, start, end)
            for index in range(start, end):
                proof = inclusion_proof(entries, start, end, index)
                assert root_from_proof(index, start, end, leaf_hash(entries[index]), proof) == expected


def test_proofs_of_the_wrong_length_are_rejected():
    entries = [b"e%d" % i for i in range(8)]
    proof = inclusion_proof(entries, 0, 8, 3)
    with pytest.raises(ValueError):
        root_from_proof(3, 0, 8, leaf_hash(entries[3]), proof[:-1])
    with pytest.raises(ValueError):
        root_from_proof(3, 0, 8, leaf_hash(entries[3]), proof + [proof[0]])


def test_a_subtree_hash_survives_log_growth():
    entries = [b"e%d" % i for i in range(13)]
    before = subtree_hash(entries, 8, 13)
    assert subtree_hash(entries + [b"more", b"entries"], 8, 13) == before


def test_standalone_certificates_verify_for_every_entry():
    ca, certs = build_ca(20)
    browser = new_relying_party(ca)
    assert all(browser.verify(cert, NOW)[0] for cert in certs)


def test_landmark_certificates_need_the_landmark():
    ca, _ = build_ca(20)
    landmark = ca.allocate_landmark()
    cert = ca.landmark_certificate(5)
    browser = new_relying_party(ca)
    assert not browser.verify(cert, NOW)[0]
    assert browser.install_landmark(landmark)
    assert browser.verify(cert, NOW)[0]
    assert cert.signature_bytes == 0


def test_no_landmark_until_a_full_block_exists():
    ca, _ = build_ca(15)
    assert ca.allocate_landmark() is None
    assert ca.landmark_certificate(3) is None


def test_a_landmark_missing_a_required_cosignature_is_not_installed():
    ca, _ = build_ca(20)
    landmark = ca.allocate_landmark()
    del landmark.signatures["mirror.example"]
    assert not new_relying_party(ca).install_landmark(landmark)


def test_tampered_subject_key_index_and_proof_are_rejected():
    ca, _ = build_ca(20)
    landmark = ca.allocate_landmark()
    browser = new_relying_party(ca)
    browser.install_landmark(landmark)
    good = ca.landmark_certificate(5)
    assert browser.verify(good, NOW)[0]
    for bad in [
        dataclasses.replace(good, subject="evil.example"),
        dataclasses.replace(good, public_key=subscriber_key(999)),
        dataclasses.replace(good, index=6),
        dataclasses.replace(good, proof=good.proof[:-1]),
    ]:
        assert not browser.verify(bad, NOW)[0]


def test_standalone_policy_needs_every_cosigner_with_a_valid_signature():
    ca, certs = build_ca(20)
    browser = new_relying_party(ca)
    good = certs[5]
    only_ca = {"ca.example": good.signatures["ca.example"]}
    assert not browser.verify(dataclasses.replace(good, signatures=only_ca), NOW)[0]
    impostor = Cosigner("mirror.example", seed_label="attacker")
    forged = dict(good.signatures)
    forged["mirror.example"] = impostor.sign("ca.example", good.start, good.end, b"\x00" * 32)
    assert not browser.verify(dataclasses.replace(good, signatures=forged), NOW)[0]


def test_expired_certificates_are_rejected():
    ca, certs = build_ca(4)
    assert not new_relying_party(ca).verify(certs[0], NOW + 2 * WEEK)[0]


def test_the_server_falls_back_to_standalone_for_stale_clients():
    ca, certs = build_ca(20)
    landmark = ca.allocate_landmark()
    small = ca.landmark_certificate(5)
    assert choose_certificate(certs[5], small, {(landmark.start, landmark.end)}) is small
    assert choose_certificate(certs[5], small, set()) is certs[5]
    assert choose_certificate(certs[5], None, {(landmark.start, landmark.end)}) is certs[5]

Run python -m pytest -q:

.............................................                                                                    [100%]
45 passed in 0.30s

The exhaustive test is the strongest one. For every log size from 1 to 33 it tries every valid subtree and every entry inside it, builds the proof, and checks that it rebuilds the subtree hash. That is where off-by-one mistakes in proof generation hide, and it covers the awkward non-power-of-two trees that a hand-picked example would skip. The remaining tests pin down the certificate rules: landmark certificates need the landmark, a landmark update missing a required cosignature is refused, tampering of every kind is rejected, the cosigner policy holds, expiry is enforced, and the server falls back to the standalone certificate.

Check the whole thing end to end

From the project folder, with the virtual environment active, run everything once more:

python demo1_sizes.py
python demo2_merkle.py
python demo3_standalone.py
python demo4_landmark.py
python demo5_attacks.py
python demo6_scale.py
python -m pytest -q

You are done when the demos print what you saw above and pytest ends with 45 passed. Only the timing lines in the last demo change from run to run, and signature bytes are never printed, only their lengths.

Common mistakes and gotchas

• Using any range as a subtree. The alignment rule is not decoration. subtree_hash raises ValueError for [12, 24) because such a range cannot be proven consistent with the larger tree. Cover awkward intervals with two aligned subtrees, as the draft describes in section 4.5.
• Trusting a landmark update without checking its cosignatures. Step 5’s attack 8 shows why. The update channel must be authenticated.
• Serving a landmark-relative certificate to a browser that never announced the landmark. The small certificate fails on stale clients, so always keep the standalone certificate ready.
• Forgetting the non-signature checks. Validity dates, names and the rest of certificate checking still apply. MTCs replace only the signature step.
• Comparing the wrong sizes. Proof length depends on the size of the subtree, not the whole log, and the worst case is the ceiling of the base-2 logarithm of that size. Add the handshake signature and the key when you compare with today’s designs.
• Mistaking the lab for the standard. This code is a teaching model. It is not wire-compatible with the draft and must never issue real certificates.

What the real draft adds

The draft is far more complete than this lab. It encodes the proof inside the X.509 signatureValue as an MTCProof structure, and builds each certificate’s serial number from the log number and the entry’s index. Its cosigners sign a richer message, and mirrors check that every new log state is append-only and consistent with the last. It defines a numbered landmark sequence whose landmarks expire, and it lets relying parties keep lists of revoked serial-number ranges. Its TLS section describes how a client tells the server which landmarks it holds, and the ACME section describes how a website requests a certificate. Cloudflare says its ACME infrastructure will be a fork of Boulder, the software that powers Let’s Encrypt, and that Let’s Encrypt is developing MTC support in Boulder itself.

Where to go next

• Read the draft’s section 4 (subtrees), section 6.5 (size estimates) and section 8 (use in TLS), then Cloudflare’s post from top to bottom.
• Extend the lab: implement the two-subtree cover from section 4.5 so landmarks can close at any tree size, or make the relying party keep only the newest few landmarks.
• Key exchange is the other half of the post-quantum migration. The hybrid key exchange tutorial builds it with X25519 and ML-KEM, and Cloudflare’s post-quantum visibility tools show how to audit it per connection.
• For the wider migration plan, see the post-quantum adoption checklist.

Sources

• Cloudflare: Building a post-quantum certificate authority with Merkle Tree Certificates (September 29, 2026)
• IETF Internet-Draft draft-ietf-plants-merkle-tree-certs-06, Merkle Tree Certificates (September 2026)
• RFC 9162, Certificate Transparency Version 2.0, section 2.1 (Merkle tree hashing and inclusion proofs)
• NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (Table 2, key and signature sizes)
• pyca/cryptography documentation: ML-DSA