Your HTTPS Is Toast (But Google Has a Plan): Merkle Tree Certificates and the Post-Quantum Web

Alright readers, buckle up. This one is a true banger for us.

A group of researchers in Sydney just dropped a paper that says you can break RSA-2048 with fewer than 100,000 physical qubits using LDPC error-correcting codes. That's nowhere near a typo. One hundred thousand. The previous estimate from Craig Gidney — the guy who literally wrote the reference implementation of Shor's algorithm — was around a million qubits. We just got a 10x improvement. The cryptography holding up every TLS connection on the internet is looking increasingly shaky.

And here's the kicker that nobody talks about enough: elliptic curve cryptography falls first. Because "better classical security" meant people chose 256-bit EC keys instead of 2048-bit RSA keys. Turns out Shor's algorithm mostly just cares about key size. Smaller keys = less work for the quantum computer. Congratulations on the own goal.

So Google, along with Cloudflare, said "okay we actually need to fix this" and shipped something into Chrome already. Today. In production. With real traffic.

Let's dig into exactly what they did and why it's genuinely clever.

How TLS Actually Works

When your browser hits https://github.com, there's a TLS handshake. This is the moment where the server goes "hey, I'm actually GitHub, here's my certificate proving it." The certificate is signed by a Certificate Authority (CA) like DigiCert. Your browser trusts DigiCert because it's baked into your OS trust store. Chain of trust. Classic stuff.

Here's what a modern X.509 certificate chain looks like in terms of cryptographic material during that handshake. The example is right below.

Root CA certificate
    └── Intermediate CA certificate
            └── End-entity certificate (the website's cert)

Each of those links contains an EC public key and an ECDSA signature. An ECDSA P-256 signature? 64 bytes. A public key? Also tiny. The whole chain comes in around 4kB today. Fast. Efficient. Fine.

Now quantum happens.

Post-Quantum Crypto Is Absolutely Massive

NIST standardized the post-quantum algorithms. ML-DSA (formerly CRYSTALS-Dilithium) is the main signature scheme. ML-KEM handles key exchange and is already deployed — Chrome has been doing post-quantum key exchange since 2023. The key exchange story is basically solved. The certificate story is a disaster.

Here's the comparison that should make you wince as much as I am.

That's a 37x increase in signature size for the smallest security level. And remember — a certificate chain has multiple signatures. Root CA, intermediate CA, end-entity. Plus Signed Certificate Timestamps (SCTs) from Certificate Transparency logs.

Do the back-of-napkin math (in Python, naturally):

# Today's classical chain
ecdsa_sig = 64      # bytes
ec_pubkey = 32      # bytes
sigs = 3            # root + intermediate + end-entity
pubkeys = 3
scts = 2            # certificate transparency proofs

classical_total = (ecdsa_sig * sigs) + (ec_pubkey * pubkeys) + (scts * 64)
# = 192 + 96 + 128 = ~416 bytes of crypto material
# Full cert chain with metadata: ~4kB

# Naive quantum-resistant drop-in replacement
ml_dsa_sig = 2420   # ML-DSA-44 signature
ml_dsa_pubkey = 1312
sigs = 3
pubkeys = 3
scts = 2            # now these need to be quantum-resistant too

quantum_total = (ml_dsa_sig * sigs) + (ml_dsa_pubkey * pubkeys) + (scts * ml_dsa_sig)
# = 7260 + 3936 + 4840 = ~16,036 bytes of crypto material
# Full cert chain: ~15kB+

15 kilobytes of cryptographic material per TLS handshake. And that's if ML-DSA holds up. If it doesn't and we fall back to SPHINCS+ (a purely hash-based scheme that we're almost certain is quantum-secure because it reduces to hash function security), you're looking at 50kB+ certs. Per connection. For every HTTPS request.

Bas Westerbaan from Cloudflare said it plainly.

The bigger you make the certificate, the slower the handshake and the more people you leave behind. Our problem is we don't want to leave people behind in this transition.

If people disable the new encryption because it slows their browsing, we've failed. The deployment had to be zero-cost in performance terms or it wouldn't happen.

You Don't Need a Signature on Every Certificate

Here's where the clever bit comes in. Merkle Trees have been kicking around in computer science since Ralph Merkle published his thesis in 1979. You know them from git commits, from Bitcoin, from certificate transparency logs. The insight for MTCs is applying the same idea to the certificate issuance problem.

Instead of: CA signs every certificate individually

Do this: CA signs ONE tree head that covers MILLIONS of certificates

                    [Tree Head] ← CA signs this ONCE (1 ML-DSA sig)
                   /           \
            [Hash A,B]        [Hash C,D]
           /         \       /          \
        [Hash A]  [Hash B]  [Hash C]  [Hash D]
           |          |        |          |
        [Cert A]  [Cert B]  [Cert C]  [Cert D]

Where each hash node is: SHA256(left_child || right_child)

To prove that Cert A is included in the tree, you don't need the tree head signature plus Cert A plus Cert B plus Cert C plus Cert D. You just need:

1. Cert A itself
2. Hash B (sibling)
3. Hash C,D (uncle)
4. The signed Tree Head

That's your inclusion proof. The client can verify it by computing (this is pure Python — no framework, no magic, just hashing up a tree):

import hashlib

def verify_inclusion_proof(cert, proof_hashes, tree_head, tree_head_signature, ca_public_key):
    """
    Verify that a certificate is included in a Merkle tree.
    
    cert: the certificate data (leaf)
    proof_hashes: sibling hashes along the path to the root
    tree_head: the root hash of the Merkle tree
    tree_head_signature: CA's ML-DSA signature over tree_head
    ca_public_key: CA's ML-DSA public key (fetched out-of-band, once)
    """
    
    # Step 1: Verify the CA's signature over the tree head
    # This is the ONLY signature verification needed per handshake
    if not ml_dsa_verify(tree_head, tree_head_signature, ca_public_key):
        return False  # Tree head is bogus
    
    # Step 2: Compute the leaf hash
    current_hash = hashlib.sha256(cert).digest()
    
    # Step 3: Walk up the tree using the proof path
    for sibling_hash in proof_hashes:
        # Convention: sort so smaller hash goes left (doesn't matter which)
        if current_hash < sibling_hash:
            current_hash = hashlib.sha256(current_hash + sibling_hash).digest()
        else:
            current_hash = hashlib.sha256(sibling_hash + current_hash).digest()
    
    # Step 4: If we reach the tree head, the cert is in the tree
    return current_hash == tree_head


def inclusion_proof_size(n_certs, hash_size=32):
    """
    A Merkle inclusion proof needs log2(N) hashes.
    For a tree of 1 million certs: log2(1,000,000) ≈ 20 hashes
    """
    import math
    n_hashes = math.ceil(math.log2(n_certs))
    return n_hashes * hash_size


# Tree covering 1,000,000 certificates
proof_size = inclusion_proof_size(1_000_000)
print(f"Inclusion proof: {proof_size} bytes")   # 640 bytes
print(f"One ML-DSA-44 sig: 2420 bytes")
print(f"Three ML-DSA-44 sigs (classical chain): {2420 * 3} bytes")
print(f"MTC total crypto (1 sig + 1 pubkey + 1 proof): {2420 + 1312 + proof_size} bytes")

Inclusion proof: 640 bytes
One ML-DSA-44 sig: 2420 bytes
Three ML-DSA-44 sigs (classical chain): 7260 bytes
MTC total crypto (1 sig + 1 pubkey + 1 proof): 4372 bytes

Instead of 15kB+ of post-quantum crypto garbage being thrown at every TLS handshake, you get roughly 4kB — comparable to what we have today. The CA's big ML-DSA signature is only transmitted once per tree head, shared across millions of certificates.

The title of the article says "squeezing 15kB into 700 bytes." That tracks because the Merkle proof itself (the bit that changes per certificate) is around 640 bytes. The CA public key and the tree head signature are distributed out-of-band and only fetched once, not per-connection.

The Out-of-Band Distribution Is the Secret Sauce

This is the architectural move that makes the whole thing work.

In classic PKI, the full certificate chain — including all the CA signatures — travels in the TLS handshake. Every connection, every time. With MTCs, that model flips:

• The CA public key (ML-DSA, big) → fetched once, stored in the browser/OS
• The signed Tree Head (ML-DSA signature, big) → distributed periodically via update mechanisms, not per-connection
• The inclusion proof (tiny Merkle path) → sent in the TLS handshake

Here's what the new TLS 1.3 handshake looks like with MTCs (think of this like async/await — the heavy work is deferred and the fast path is all that's left at connection time):

Client                                    Server
  |                                          |
  |-- ClientHello + {tree_heads I know} ---> |
  |                                          |
  |   Server checks: do I have a cert        |
  |   covered by any of your tree heads?     |
  |                                          |
  |<-- ServerHello + Certificate (MTC) ------|
  |    [domain info + inclusion proof only]  |
  |    [NO signatures sent at all!]          |
  |                                          |
  |   Client verifies inclusion proof        |
  |   against the tree head it already has.  |
  |   Done. Authenticated.                   |
  |                                          |

The ServerKeyExchange signature for the actual session is still there — that proves the server actually controls the private key corresponding to the public key in the certificate. That's ML-DSA too. But we've eliminated the entire CA certificate chain from the handshake.

In code terms, the server's certificate is now dead simple:

# Traditional X.509 cert (simplified, many more fields in reality)
class X509Certificate:
    subject: str             # "github.com"
    subject_public_key: bytes # EC or ML-DSA public key
    validity_not_before: datetime
    validity_not_after: datetime
    # Signed by intermediate CA:
    issuer_signature: bytes   # ECDSA or ML-DSA - BIG for PQ
    # Intermediate CA cert also sent, signed by root CA:
    intermediate_cert: bytes  # Another huge signature chain


# Merkle Tree Certificate (MTC)
class MerkleTreeCertificate:
    subject: str             # "github.com"  
    subject_public_key: bytes # ML-DSA public key
    validity_not_before: datetime
    validity_not_after: datetime
    tree_id: bytes           # Which tree batch this is from
    inclusion_proof: list[bytes]  # ~20 hashes of 32 bytes each = 640 bytes
    # No issuer signature. It's proven by the inclusion proof.
    # The CA signature is in the tree head, distributed separately.

The certificate itself has no signature. The trust comes entirely from the Merkle inclusion proof and the tree head that the browser already has. This is genuinely elegant.

Certificate Transparency Gets an Upgrade

Here's a bonus that I don't see talked about enough: MTCs make Certificate Transparency (CT) mandatory by design, not bolted on after the fact.

Quick CT background: after the 2011 DigiNotar breach — where a Dutch CA got compromised and issued ~500 fraudulent certificates used to spy on Iranians — the industry realized "hey, maybe CAs should be publicly accountable." CT was invented. Now every certificate must be logged to public append-only ledgers before browsers trust it. You can check if a cert for your domain was issued without your knowledge.

The problem: CT transparency proofs (SCTs — Signed Certificate Timestamps) are additional cryptographic material tacked onto the existing certificate. With post-quantum signatures, SCTs become another massive blob of data per handshake.

With MTCs, the tree IS the transparency log. You cannot issue a valid MTC without it being in the public Merkle tree. There's no separate SCT mechanism. Transparency is load-bearing architecture, not an audit trail addon. If you're not in the tree, you have no certificate. Done.

# Old world: CT is optional overhead added to X.509
class CertificateTransparency_Old:
    sct_list: list[SignedCertificateTimestamp]  # Extra sigs per handshake
    # CA can still issue certs and submit to CT after the fact
    # Misissuance possible before log submission
    
# New world: MTC - transparency is structural
class MerkleTreeCertificate:
    inclusion_proof: list[bytes]
    # The proof IS the transparency record.
    # No proof = no valid cert. No exceptions.
    # The CA signs the tree head = logs exactly what it issued

The Quantum Threat Is More Real Than You Think

Here's where Scott Aaronson's blog post comes in. The Sydney paper estimates breaking RSA-2048 with under 100,000 physical qubits using LDPC error-correcting codes instead of surface codes. Aaronson says the claim is "entirely plausible." His main caveat is engineering difficulty — LDPC codes require non-local error syndrome measurements, which are harder to implement in superconducting qubit hardware.

But here's the thing that should actually keep you up at night: this is published, open research. The arguments for publishing (crypto community does responsible disclosure, open warnings accelerate migration) seem to be winning. Every improvement to Shor's algorithm resource requirements is a loud public countdown clock.

And "Harvest Now, Decrypt Later" attacks are already happening. Nation-state actors are recording encrypted TLS traffic today, betting they'll be able to decrypt it when viable quantum computers exist. Your communications from 2026 might be decrypted in 2032. The threat isn't just future connections — it's current connections that need to remain secret in the future.

The migration timeline is brutal:

2011: DigiNotar breach → Certificate Transparency invented
2013: CT deployment begins
2018: CT required by Chrome (7 years later)
2023: ML-KEM in Chrome for key exchange (quantum-safe key exchange)
2026: MTC Phase 1 (now, 1000 Cloudflare test certs)
2027 Q1: Phase 2 (CT log operators onboarded)  
2027 Q3: Phase 3 (Chrome Quantum-Resistant Root Store)
????: Full ecosystem migration

Internet security migrations take a decade minimum. We started the clock.

Where It Gets Complicated

The real MTC spec has one more wrinkle worth understanding: the "landmark" system.

You can't just issue one giant Merkle tree forever. Certificates expire. New certificates get issued. The tree needs to grow. But if Chrome needs to have a fresh tree head to validate any certificate, and tree heads update frequently, you get a freshness problem — servers with certificates in "old" batches can't authenticate to clients that only have "new" tree heads.

The spec handles this by growing a single large tree over time. Periodically, "subtree heads" (called landmarks) are snapshotted and pushed to browsers:

# Conceptually, the tree grows append-only
class MTCLog:
    """
    A single, growing Merkle tree. New certificates are added as leaves.
    Periodically, the current root is signed and distributed as a landmark.
    """
    def __init__(self):
        self.leaves: list[bytes] = []      # Certificate data
        self.batch_size: int = 1000        # Certs added per batch
        
    def add_certificate(self, cert: bytes):
        leaf_hash = sha256(cert)
        self.leaves.append(leaf_hash)
    
    def get_tree_head(self) -> bytes:
        """Compute current Merkle root."""
        return self._compute_root(self.leaves)
    
    def create_landmark(self, ca_private_key) -> Landmark:
        """
        Periodically called (e.g., every few hours).
        Signs current tree head. Browsers fetch these.
        """
        tree_head = self.get_tree_head()
        signature = ml_dsa_sign(tree_head, ca_private_key)
        return Landmark(
            tree_head=tree_head,
            signature=signature,
            timestamp=now(),
            n_leaves=len(self.leaves)
        )
    
    def generate_inclusion_proof(self, cert_index: int) -> list[bytes]:
        """
        Generate proof that cert at index is in the tree.
        Returns O(log N) hashes.
        """
        return self._merkle_proof(self.leaves, cert_index)


# MTC lifespans are brief - a week at most
# Anything older triggers fallback to traditional X.509
# (servers provision BOTH types during transition period)

Browsers receive landmark updates out-of-band — through browser updates, OS updates, or a dedicated update mechanism. When you connect to a server, your browser sends along which landmarks it currently knows about. If the server's MTC falls within a batch covered by one of your landmarks, auth works instantly, no extra round trips.

If your landmarks are stale (say, you haven't opened Chrome in three weeks), the server falls back to a traditional X.509 certificate. That's the "both types provisioned" model during the transition period.

How the Rollout is going to Happen

Google isn't hand-waving here. They have a concrete plan:

Phase 1 (Now): Cloudflare has enrolled ~1,000 TLS certificates as MTCs. Chrome makes MTC connections, but every MTC connection is backed by a traditional X.509 cert as a safety net. They're measuring: what breaks? How fast is it? What middleboxes freak out?

The "what breaks" question is non-trivial. Protocol ossification is a known enemy of TLS upgrades. There are literal firewall appliances out there that deep-packet-inspect TLS and break when they see unexpected extensions. Every time someone has tried to extend TLS, something has broken. This phase exists to find those things before they affect users at scale.

Phase 2 (Q1 2027): CT log operators with established "usable" logs get invited to participate in running MTC tree generation. These are organizations that have already proven they can run high-availability, globally distributed append-only logs. The infrastructure skills transfer directly.

Phase 3 (Q3 2027): Chrome launches the Chrome Quantum-Resistant Root Store (CQRS) — a separate root store that only accepts MTC certificates. CAs that want to issue quantum-resistant certificates must meet the new requirements and only issue MTCs. No hybrid "X.509 with PQ signatures" admitted.

Note what Google explicitly said they will NOT do: add traditional X.509 certificates with post-quantum cryptography to the Chrome Root Store. The "just upgrade the signature algorithm in X.509" path is a dead end. Too slow, too big, no CT guarantees. MTCs or bust.

Is This Enough?

Fair question. A few things to keep in mind:

Algorithm risk is hedged. The "hybrid" approach means a certificate is only forgeable if an attacker breaks BOTH classical ECDSA (which requires a quantum computer) AND ML-DSA (which has no known attack). If ML-DSA turns out to be broken (unlikely but not impossible — it's relatively new), you'd need to fall back to SPHINCS+ (SLH-DSA), which is purely hash-based and considered extremely conservative. SPHINCS+ signatures are 50kB. That's why MTCs with their log(N) proof compression matter so much — even if we need to upgrade the signature scheme, the MTC architecture can absorb it without exploding handshake sizes.

Key exchange is already done. ML-KEM in Chrome for TLS key exchange is shipping. Post-quantum handshake encryption exists now. The authentication piece (certificates) is what's still being solved.

The IETF PLANTS working group (PKI, Logs, And Tree Signatures — love that acronym) is standardizing this. Multiple browser vendors and CAs are involved. This isn't Google going rogue; it's coordinated industry movement.

The 100,000 qubit paper isn't Q-Day. Scott Aaronson notes that building 100,000 qubits with the required error correction using LDPC codes is still an enormous engineering challenge, especially for superconducting hardware. We're not there. But direction matters as much as distance. Every year, qubit counts go up and error rates go down.

The Conclusion

Here's the thing that I keep coming back to: this solution is correct. Not correct as in "good enough for now." Correct as in — the architectural insight that you don't need individual signatures on individual certificates, that a single log-rooted signature can authenticate millions of certificates via compact Merkle proofs, that transparency can be structural rather than optional — these ideas make the system better than what we have today. Not just quantum-resistant. Actually better.

That's rare. Usually security upgrades cost you something. Latency, complexity, bandwidth, compatibility. MTCs are net positive on almost every axis:

• Faster handshakes than post-quantum X.509 would be
• Mandatory transparency (misissuance becomes structurally impossible)
• Roughly equivalent to current performance even with PQ algorithms
• Smaller per-connection overhead even at today's security levels

The distributed ledger for trust. The compact proof of inclusion. The out-of-band distribution of trust anchors. It all hangs together.

Is the 2027 timeline going to be enough? Probably not for the full ecosystem. Corporate network appliances, embedded devices, ancient Android phones — these will lag for years. The migration will be incomplete when the threat becomes critical, because that's how every internet security migration has gone. CT took seven years to become mandatory. IPv6 has been "the future" for thirty years.

But the architectural foundation is being laid correctly. The code is in Chrome. The IETF working group exists. Cloudflare is running real traffic through it.

Start of the beginning, not end of the end. But it's the right start.