Merkle Tree Certificates (a.k.a. Photosynthesis)

[David Benjamin]

Hi CT folks,

A bunch of us (myself, Devon O’Brien, Bas Westerbaan, Luke Valenta, and Filippo Valsorda) have been working on a design called Merkle Tree Certificates, which
https://datatracker.ietf.org/doc/draft-davidben-tls-merkle-tree-certs/
https://github.com/davidben/merkle-tree-certs
https://davidben.github.io/merkle-tree-certs/draft-davidben-tls-merkle-tree-certs.html

For folks who’ve seen an earlier iteration, this is a new version of the idea, building on some of the tlog work behind the Static CT API. We’ve been informally calling this iteration “Photosynthesis” because I enjoy silly puns too much: we’re converting sunlight into certificates. (From draft-laurie-pki-sunlight to sunlight.dev, there’s a history of CT things being called “sunlight”.)

Merkle Tree Certificates integrates CT into the certificate issuance process, rather than bolting it on after the fact. The integration lets us, I hope, deal with some inefficiencies in CT today and mitigate the size impacts of post-quantum keys/signatures in both certificate and log size. It’s a pretty long document, so I’ll give an overview here with an eye to the CT end of things:

In CT, CAs send individual certificates to a quorum of logs, with each log building its own independent tree. In MTC, the CAs construct logs, but containing only what they have issued. Log entries do not have signatures. Rather, putting an entry in the log and signing a new checkpoint constitutes the CA certifying everything in the checkpoint. Add in a public key hashing step and log sizes do not increase from post-quantum at all! We’re also working on a pruning extension to tlog which hopefully will help with the volume increase from short-lived certificates, without the churn of temporal sharding.

Instead of a quorum of logs, we use the cosignature and witness ideas from tlog. We’re also working on defining a mirror role that I think fits in this setting particularly well. These cosigners take the role of CT logs today, providing a quorum of evidence that a checkpoint is globally consistent and durably logged.

However, unlike CT, it’s all still the same per-CA tree. In CT, the monitor ecosystem can’t be guaranteed certificates are all cross-logged and must download the contents of each log. In MTC, mirrors are provably consistent with each other. If you got entries 1000-2000 from mirror A, there’s no need to re-download them from mirror B, as long as A and B’s checkpoints are consistent.

Then we package up the certificate info, an inclusion proof, and signatures into an X.509 certificate, which is what’s ultimately sent down to the client. (As a size optimization, these use a signed subtree instead of a root.)

Finally, we adapt an old STH discipline idea to mitigate PQ signatures: every hour or so, checkpoints are marked as “landmark checkpoints”. After your entry has been in the log for long enough for a landmark checkpoint, you can get a “signatureless certificate” anchored at it, but skipping the signatures. Instead, the landmark checkpoints are pre-distributed to clients. TLS servers can now present these smaller certificates when the client is up-to-date enough to already trust the landmark.

And that’s it in a nutshell. There’s a lot of pieces here, but it’s building on the work that’s already happened with CT and I expect can reuse or minimally adapt much of that existing code.

Let us know if you have any thoughts, either here or on GitHub!

David

[Ben Laurie]

This is a nice approach. However, it still leaves CAs having to deal with one of the hardest problems in CT: running a highly available and reliable log. As you know, I'm sure, this is actually impossible to do perfectly, which is probably why it is hard. :-)

If you allowed CAs instead to run multiple unreliable logs, and log in a quorum of those, then running the log is a lot cheaper and easier. The MMD can be cut down to seconds, or, at least, something much shorter than 24 hours. If logs occasionally die, then the rest of the quorum take up the slack.

This is essentially my RAIL idea in another guise and my experiments show that you can make logs extremely fast once reliability stops being a requirement (not a surprise, I'm sure). All you're really doing here is exposing the reliability mechanism to the world instead of hiding it behind a complicated and tricky system.

--
You received this message because you are subscribed to the Google Groups "certificate-transparency" group.
To unsubscribe from this group and stop receiving emails from it, send an email to certificate-transp...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/certificate-transparency/CAF8qwaCKPThSe3D4amuvZ5EK2ZtnQyG0MiOw6CavPeCM81PqTA%40mail.gmail.com.

[David Benjamin]

There's a section which discusses this a bit:
https://davidben.github.io/merkle-tree-certs/draft-davidben-tls-merkle-tree-certs.html#section-10.3-7

In short, there's no need for CAs to operate a highly available log. A log ecosystem that uses mirrors, which would be the most natural analog to X.509 + CT today, can push the reliability requirement to the mirrors. The only requirement on the CA would then be to produce a *consistent* log, i.e. pick a single order for all its issued certificates, and only sign subtrees matching that order. Unlike CT, this consistency does not need to take into account a globally-accessible log submission API. Additions only happen when the CA itself issues a certificate, and can be batched as needed.

Even if the CA fails in the consistency requirement and produces a split view, each mirror would be locked to one particular view and serve the corresponding entries to monitors. Views that fail to reach a quorum of mirrors won't be accepted by relying parties anyway. Views that do will be visible to monitors. The mirrors will be very obviously inconsistent, and I think an ecosystem would want to repair that mishap, rather than hope the rest of the ecosystem properly handles a doubled up log, but in the meantime, both views and contents are perfectly visible.

In fact, although the draft doesn't mention it right now, relying parties could plausibly tolerate the CA not serving anything at all. The mirror protocol we've sketched out in tlog is push-based, so the CA could just privately build its tree, upload the contents out to mirrors, and the ecosystem relies on mirrors for access to the contents.

(Do you have a pointer to your RAIL idea?)

[Ben Laurie]

On Wed, 2 Jul 2025 at 15:14, David Benjamin <davi...@chromium.org> wrote:

There's a section which discusses this a bit:
https://davidben.github.io/merkle-tree-certs/draft-davidben-tls-merkle-tree-certs.html#section-10.3-7

In short, there's no need for CAs to operate a highly available log. A log ecosystem that uses mirrors, which would be the most natural analog to X.509 + CT today, can push the reliability requirement to the mirrors. The only requirement on the CA would then be to produce a *consistent* log, i.e. pick a single order for all its issued certificates, and only sign subtrees matching that order. Unlike CT, this consistency does not need to take into account a globally-accessible log submission API. Additions only happen when the CA itself issues a certificate, and can be batched as needed.

Even if the CA fails in the consistency requirement and produces a split view, each mirror would be locked to one particular view and serve the corresponding entries to monitors. Views that fail to reach a quorum of mirrors won't be accepted by relying parties anyway. Views that do will be visible to monitors. The mirrors will be very obviously inconsistent, and I think an ecosystem would want to repair that mishap, rather than hope the rest of the ecosystem properly handles a doubled up log, but in the meantime, both views and contents are perfectly visible.

In fact, although the draft doesn't mention it right now, relying parties could plausibly tolerate the CA not serving anything at all. The mirror protocol we've sketched out in tlog is push-based, so the CA could just privately build its tree, upload the contents out to mirrors, and the ecosystem relies on mirrors for access to the contents.

This does not fix the problem - if a CA is required to produce a *single* consistent log, then they still have the problem of running a highly available log, because otherwise they cannot issue certificates.

As I've pointed out, running n *unreliable* (but consistent when available) logs is pretty easy, and, with a little care, should mean that certs can always be issued, even if some logs are down. The mirrors can be responsible for aggregation so this is invisible to the RPs.

To view this discussion visit https://groups.google.com/d/msgid/certificate-transparency/55c799f3-6dd3-4e02-8bc6-e87a79e19616n%40googlegroups.com.

[Winston de Greef]

As far as I understand, there is nothing in the spec stopping a CA from running multiple trees for issuing certificates. The impression I had is that a CA log is more like an intermediate certificate than a root certificate in traditional PKI.

So CAs can already decide to run multiple consistent (with themselves) when available logs.

Also, when we usually talk about logs having issues with availability, this is because they can't handle the strain of all the read requests, so if they don't have to host a highly available read path, then presumably there would be no availability problems. I remember a log operator (I believe sectigo) having no issue keeping the write path highly available, but struggling a lot to keep the read path available. I guess what I mean is that historically availability of the write path has never been an issue (although there is very little attention for this, because if a write request is rejected, this doesn't really matter, so this could just all be bias).

Sincerely,

Winston de Greef

To view this discussion visit https://groups.google.com/d/msgid/certificate-transparency/CABrd9SSobKpjMcsoPW_y%3D_9FEUrJ3oaJXjBMwSTjm2ZDv7Hb3w%40mail.gmail.com.

[Winston de Greef]

Ps. I mean consistent with themselves as in not consistent with the other logs operated by the ca.

Sincerely,

Winston de Greef

[Ben Laurie]

On Wed, 2 Jul 2025 at 15:14, David Benjamin <davi...@chromium.org> wrote:

There's a section which discusses this a bit:
https://davidben.github.io/merkle-tree-certs/draft-davidben-tls-merkle-tree-certs.html#section-10.3-7

In short, there's no need for CAs to operate a highly available log. A log ecosystem that uses mirrors, which would be the most natural analog to X.509 + CT today, can push the reliability requirement to the mirrors. The only requirement on the CA would then be to produce a *consistent* log, i.e. pick a single order for all its issued certificates, and only sign subtrees matching that order. Unlike CT, this consistency does not need to take into account a globally-accessible log submission API. Additions only happen when the CA itself issues a certificate, and can be batched as needed.

Even if the CA fails in the consistency requirement and produces a split view, each mirror would be locked to one particular view and serve the corresponding entries to monitors. Views that fail to reach a quorum of mirrors won't be accepted by relying parties anyway. Views that do will be visible to monitors. The mirrors will be very obviously inconsistent, and I think an ecosystem would want to repair that mishap, rather than hope the rest of the ecosystem properly handles a doubled up log, but in the meantime, both views and contents are perfectly visible.

In fact, although the draft doesn't mention it right now, relying parties could plausibly tolerate the CA not serving anything at all. The mirror protocol we've sketched out in tlog is push-based, so the CA could just privately build its tree, upload the contents out to mirrors, and the ecosystem relies on mirrors for access to the contents.

(Do you have a pointer to your RAIL idea?)

I forgot to respond to this: I'm not sure I ever wrote it up publicly, but I have internal docs, I'll send you something...

 

To view this discussion visit https://groups.google.com/d/msgid/certificate-transparency/55c799f3-6dd3-4e02-8bc6-e87a79e19616n%40googlegroups.com.

[David Benjamin]

Yup. There is some point at which multiplication of CA operators into many CA instances becomes costly to the ecosystem, but if a CA finds that its issuance volume requires it, it seems plausible for a relying party to accept multiple of them. (Or maybe we get excited about actual intermediate-style delegation, though that also has costs with PQ... it's quite annoying that pubkeys and sigs are no longer free.)

Between better log implementations and MTC's design, the write path also has a very different shape from where X.509 + CT started. We don't have SCTs anymore. In X.509 + CT, blowing just one MMD is a disaster. It means we have some unmonitored, valid certificate out in the wild. In MTC, if some distributed issuance frontend falls over and some entries never get sequenced into the log, no certificates were issued at all. If some CA achieves 1 second issuance times for 99.99...% of issuances but occasionally one takes a minute, that certificate just wasn't issued until a minute later.

Obviously, those outcomes are still bad. We don't want huge issuance delays or flaky issuance. But taking away the security dependency lets us move from demanding 100%, to the usual engineering questions of figuring out what latency distribution and how many 9s are achievable and acceptable for each deployment (and scaling with that particular CA's issuance volume), and whether something workable can be built.

You received this message because you are subscribed to a topic in the Google Groups "certificate-transparency" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/certificate-transparency/w0sUcZ7FO0g/unsubscribe.
To unsubscribe from this group and all its topics, send an email to certificate-transp...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/certificate-transparency/CAD2RJqaqeygWUK550UBnAUE8mfgCT__gEbO00bfvpxvcz0hFCg%40mail.gmail.com.

[David Benjamin]

Hi all!

To give an update on this work, we gave a quick presentation[1] of Merkle Tree Certificates at secdispatch in IETF 123. The result is we now have the PLANTS mailing list, PKI, Logs, And Tree Signatures!

I'd like to invite you all to join in the discussion at the list. You can find a link to subscribe and skim the archives here:
https://mailman3.ietf.org/mailman3/lists/pla...@ietf.org/

Beyond making as many plant puns as possible, the first order of business is to settle on a scope and charter for an IETF working group. There's an initial draft version at [2].

David

[1] https://datatracker.ietf.org/meeting/123/materials/slides-123-dispatch-merkle-tree-certificates-00.pdf
[2] https://mailarchive.ietf.org/arch/msg/plants/ZdemgcZ93pedIcHsVM1lw-z-i8o/