Skip to content

MTC.md

Latest commit

 

History

History
454 lines (366 loc) · 19.6 KB

MTC.md

File metadata and controls

454 lines (366 loc) · 19.6 KB
Raw

Merkle Tree Certificates: a tutorial

This document is background for the cactus codebase. It walks through the parts of draft-ietf-plants-merkle-tree-certs that you need to keep in your head while reading the code.

It's deliberately thinner than the IETF draft. For anything you can't find here, the draft is the source of truth — specs/draft-ietf-plants-merkle-tree-certs-05.txt is the version cactus targets, and section numbers in this doc match that file.

Why MTC exists

In a CT-style PKI, every certificate carries:

  1. The CA's signature on the cert itself.
  2. Two or more Signed Certificate Timestamps (SCTs), each a signature from a CT log saying "I have logged this certificate."

With ECDSA-P256 that's tolerable: each SCT is ~70 bytes. With ML-DSA-44, each SCT signature is 2,420 bytes and each public key is 1,312 bytes. Two SCTs plus the cert signature plus the cert's public key starts to crowd out the rest of the TLS handshake. Worse, every CT log has to store the same data over and over.

MTC inverts the design. Instead of "the CA signs the cert, then logs it", the CA logs the cert (a small structure with a hash where the public key would be) and then signs the log. Each issued certificate becomes a Merkle inclusion proof against a logged tree, plus one or more cosigner signatures over a subtree of that tree — never over the cert directly.

The win:

  • Log entries don't carry public keys or signatures, only (name, validity, hash-of-pubkey). Storage scales with issuance rate, not key/sig size.
  • The CA signs O(checkpoints) per unit time, not O(certs). Fewer signature operations.
  • An optional second mode — landmark-relative certificates — ships the inclusion proof without any signatures at all, by pre-distributing a small set of trusted subtree hashes to clients.

The big picture

+---------+   1. ACME order        +---------+
| client  | --------------------> |   CA    |
+---------+                       +---------+
                                       |
                                       | 2. add to issuance log
                                       v
+---------+   4. inclusion proof  +---------+
| client  | <-------------------- |   CA    |
+---------+   + cosignatures      +---------+
                                       ^
                                       | 3. sign subtree(s)
                                       |
                                  +---------+
                                  | mirrors |
                                  +---------+

The cert the client receives is an X.509 with:

  • Standard fields: subject, validity, SubjectPublicKeyInfo, extensions (e.g. SAN). Same as a regular leaf cert.
  • signatureAlgorithm = id-alg-mtcProof. New OID, no parameters.
  • signatureValue (a BIT STRING) whose body is not a signature but a TLS-presentation-language struct called MTCProof that contains:
    • The subtree the cert was logged into: (start, end).
    • An inclusion proof from the cert's leaf to that subtree.
    • One or more cosigner signatures over that subtree.

A relying party verifies the cert by:

  1. Re-deriving the leaf hash from the cert's TBS (with the public key replaced by its hash).
  2. Walking the inclusion proof up to the subtree hash.
  3. Checking that some sufficient set of trusted cosigners signed that subtree.

No signature on the cert itself. No SCTs.

§4: Subtrees, the new primitive

RFC 9162 (CT v2) defines a Merkle tree, but only ever talks about the root. MTC introduces subtrees: a subtree is any range [start, end) of leaves where:

  • 0 ≤ start < end ≤ tree_size.
  • start is a multiple of bit_ceil(end - start). (So [4, 8) is valid; [1, 4) is not.)

A subtree of size 2^k is full and lives at a fixed position in the larger Merkle tree. A non-power-of-two subtree is partial; it's only directly contained in a tree of size exactly end, but it can still be efficiently shown consistent with bigger trees (§4.4).

§4.5 is the algorithmic core of MTC: given any range [start, end), return the one or two subtrees that efficiently cover it. After a checkpoint flush, the CA uses §4.5 to find the covering subtree(s) for "everything I added since the last checkpoint" and signs each one. That's why a single MTCProof has one subtree even though multiple subtrees may be signed at each checkpoint — the proof picks the one that contains the cert's index.

In cactus, §4 lives in the tlogx/ package:

  • tlogx.FindSubtrees(start, end) — the §4.5 procedure.
  • tlogx.IsValid(start, end) — the §4.1 validity predicate.
  • tlogx.HashLeaf / tlogx.HashChildren — the RFC 9162 prefixes.
  • tlogx.GenerateInclusionProof / EvaluateInclusionProof — §4.3.
  • tlogx.GenerateConsistencyProof / VerifyConsistencyProof — §4.4.

§5: Certification authorities and issuance logs

A CA has a single CA ID (§5.1), a trust anchor ID. Each issuance log it operates has a log number (1–65535); the log's ID is derived as CA-ID.0.logNumber (§5.2). cactus runs one log, configured by its log.number.

The log is an append-only tree of MerkleTreeCertEntry structures. Each entry begins with an extensions<0..2^16-1> vector (empty in cactus) followed by a type. Any index MAY be a null_entry. Serial numbers are kept non-zero by requiring a non-zero log number (see §6).

Each non-null entry is a tbs_cert_entry: the TBS-style fields of the cert with the public key replaced by HASH(SubjectPublicKeyInfo). The cert's "issuer" is a special DN containing the CA ID (§5.1).

A CA's parameters are published in its CA certificate via a critical id-pe-mtcCertificationAuthority extension (§5.5) carrying the log hash algorithm, the CA cosigner's signature algorithm, and a minSerial; cactus encodes/decodes this in cert/cacert.go.

The log is published as tiles (c2sp.org/tlog-tiles). For cactus, that means the read-path (HTTP) serves files at:

  • /checkpoint — a c2sp signed-note with the latest size + root.
  • /tile/<L>/<NNN>[.p/<W>] — Merkle hash tiles.
  • /tile/entries/<NNN>[.p/<W>] — entry blobs (the "data" tiles). A single entry is read by fetching its data tile and splitting out the entry at its position within the tile; there is no per-entry endpoint.

Cactus's log/ and tile/ packages own this. The log is a single-writer affair: one goroutine ticks every checkpoint_period_ms, appends pooled entries to the tilewriter, signs the new checkpoint

  • covering subtrees, and writes the checkpoint and tiles to disk via temp-file + rename. The covering-subtree cosigner signatures are kept only in memory — they travel inside issued certs (the MTCProof), so they are not separately published. The "lock" against multiple writers is documentation, not fcntl — see docs/threat-model.md.

Cosigners

Anyone who attests to the log's append-only property is a cosigner. There are two kinds:

  • CA cosigner (§5.5): the CA itself, attesting that "I issued every entry in this subtree." The CA's signature is the bedrock — without it the cert isn't authentic at all.
  • Mirror cosigner (c2sp tlog-mirror): a third party that follows the log, verifies consistency proofs, and signs subtrees too. Mirrors prove transparency: a misbehaving CA can't issue a cert that mirrors haven't seen.

A cosigner's signature is over a structure called CosignedMessage (§5.3.1):

struct {
    uint8 label[12] = "subtree/v1\n\0";
    opaque cosigner_name<1..2^8-1>;   // "oid/" + cosigner ID
    uint64 timestamp;                  // 0 for MTC proofs
    opaque log_origin<1..2^8-1>;       // "oid/" + log ID
    uint64 start;
    uint64 end;
    HashValue subtree_hash;
} CosignedMessage;

The 12-byte label is domain separation (§12.8): it does not begin with the DER SEQUENCE tag 0x30, so a subtree signature can never collide with a TBSCertificate / TBSCertList / OCSP signing input. The structure is compatible with the c2sp tlog-cosignature ML-DSA-44 construction. MTC proofs always use timestamp = 0.

In cactus, the cosigner abstraction is in signer/:

  • signer.Signer — a small interface whose core method is Sign(rand, msg) → sig (plus Algorithm() and PublicKey()).
  • signer.FromSeed(alg, seed) — derives a key from a 32-byte seed via HKDF. cactus is ML-DSA-only: ML-DSA-44/65/87, using Go's built-in crypto/mldsa (FIPS 204). That package needs Go 1.27+, so the whole module is go 1.27 in go.mod — no per-file build tags. Until Go 1.27 is released, a gotip 1.27-devel toolchain builds it (gotip build ./...).

§6: Building the certificate

§6.2 specifies how the X.509 cert is laid out:

  • signatureAlgorithm and tbsCertificate.signature both use id-alg-mtcProof with absent parameters.
  • signatureValue is a BIT STRING whose body — with no further ASN.1 wrapping — is the TLS-presentation encoding of:
struct {
    MerkleTreeCertEntryExtension extensions<0..2^16-1>;
    uint48 start;
    uint48 end;
    HashValue inclusion_proof<0..2^16-1>;
    MTCSignature signatures<0..2^16-1>;
} MTCProof;
  • extensions mirrors the log entry's extensions (empty in cactus).
  • start/end are 48-bit, leaving room in the serial for the log number.
  • signatures MUST be sorted by cosigner_id (shorter first, then lexicographically) with no duplicates.
  • serialNumber is (log_number << 48) | index (§6.2). The non-zero log number keeps the serial non-zero (RFC 5280 §4.1.2.2 forbids a zero serial), and lets a relying party revoke whole logs by serial range (§7.5).

This MTCProof can carry two flavors of cert:

  • Standalone certificate (§6.3): the proof's subtree is one of the §4.5 covering subtrees from a recent checkpoint, and the signatures<> slice has at least one cosigner. Issuable immediately after the next checkpoint.
  • Landmark-relative certificate (§6.4): the proof's subtree is a special pre-distributed landmark subtree, and the signatures<> slice is empty. Issuable only after the entry has been included in a landmark, but smaller and signature-free.

The cert assembly code is in cert/ and ca/:

  • cert.MTCProof / cert.MTCSubtree / cert.MTCSignature — TLS-presentation encoders.
  • cert.BuildCAName — the §5.2 issuer DN.
  • ca.Validator / ca.Issuer — turn an ACME order + CSR into a TBSCertificateLogEntry, submit to the log, await the inclusion proof, assemble the X.509 cert.
  • cert.BuildLandmarkRelativeCert — clones a standalone cert with a different MTCProof (signature-less, points at a landmark subtree).

A worked example

Suppose:

  • The log has 100 entries.
  • The previous checkpoint was at size 95.
  • A flush runs and produces checkpoint 100.

The CA:

  1. Calls tlogx.FindSubtrees(95, 100) → it returns [(start: 88, end: 96), (start: 96, end: 100)].

    Note that (88, 96) covers indices 88–95, seven of which (88, 89, 90, 91, 92, 93, 94) are from before the previous checkpoint — that's fine; "efficiently cover" doesn't mean "exactly cover".

  2. Computes the Merkle hashes of those two subtrees from the tiles.

  3. Signs each subtree's MTCSubtreeSignatureInput with its CA cosigner key.

  4. Optionally fans the request out to mirrors. Each mirror that has caught up returns its own signature.

  5. Persists the signed checkpoint to disk. The per-subtree cosigner signatures are kept only in memory — they travel inside issued certs (the MTCProof), so they are not separately published (see the §5 note above).

When a client wants the cert at index 97:

  1. Index 97 is in subtree (96, 100). The CA computes the §4.3 inclusion proof from leaf 97 up to the subtree's root.
  2. The X.509 cert is assembled with serial=97, the inclusion proof, and however many cosigner signatures are attached to subtree (96, 100).

§6.4: Landmark-relative certificates

This is the subtle part. The promise: a cert with no signatures that an up-to-date relying party can verify in ~constant time.

A landmark is a designated tree size. Landmarks are allocated by the CA (or some coordinating party) at a regular cadence — say, once per hour — and they're append-only and strictly increasing.

For each landmark N with tree size T_N, define its landmark subtrees as the §4.5 covering subtrees of [T_{N-1}, T_N). So if a CA runs hourly landmarks and issues 4M certs/hour, each landmark has one or two subtrees, each ~22 levels deep (~2M leaves).

Relying parties periodically download the active landmarks (the most recent max_active_landmarks of them) and store just the subtree hashes — about 10 KiB per CA at typical settings. When an authenticating party presents a landmark-relative cert:

  1. The cert's MTCProof has a subtree [s, e) and an inclusion proof.
  2. The relying party looks up that subtree in its trusted set.
  3. If found and the inclusion proof matches the trusted hash, the cert is valid. No cosigner signature is consulted.

That's the size optimization: the cert ships an inclusion proof (~32 bytes × log₂(N)) and zero signatures.

In cactus:

  • landmark/sequence.go is the CA-side allocator (§6.4.2). Append-only on disk; the in-memory state replays from JSONL on restart.
  • landmark.Sequence.Handler() serves the §6.4.1 text-format URL that relying parties poll.
  • cert.BuildLandmarkRelativeCert re-uses the existing standalone cert's TBS (so subject, validity, SPKI all match) and replaces only the signature value with a landmark MTCProof.
  • acme.Server advertises the landmark-relative cert as a rel="acme-optional-alternate" URL on the standalone cert response, served by handleCertLandmarkRelative at /cert/{id}/landmark-relative/{number} (see "Doing it over ACME" below).
  • cmd/cactus-cli cert landmark-relative derives the same cert from a standalone cert plus the log's tiles, for use outside ACME.

The relying-party side is exercised by integration/TestEnhancementURLSwitchover (over ACME) and integration/TestCLICertLandmarkRelative (via cactus-cli): each obtains a landmark-relative cert and verifies it against the live log (signature-free, the inclusion proof reconstructs the log's subtree hash) without consulting any cosigner key.

§7.2: Verifying a certificate

Step-by-step, the relying party's job:

  1. Check the cert's signatureAlgorithm is id-alg-mtcProof.
  2. Decode the BIT STRING body as MTCProof.
  3. The cert's serialNumber is the entry index. (Reject if it's in the relying party's revocation-by-index list, §7.5 — cactus doesn't fully implement this, but the data model carries it.)
  4. Reconstruct TBSCertificateLogEntry from the cert's TBS by replacing subjectPublicKeyInfo with HASH(SubjectPublicKeyInfo).
  5. Wrap that in a MerkleTreeCertEntry{type=tbs_cert_entry,data=...} and compute the leaf hash: HASH(0x00 || entry).
  6. Evaluate the inclusion proof from the leaf hash up to the MTCProof.subtree hash.
  7. Either match the subtree against a trusted-subtree set (landmark fast path) or verify enough cosigner signatures over the subtree to satisfy local policy.

Cactus's helpers:

  • cert.SplitCertificate — split a cert DER into TBS, alg-id, sig BIT STRING.
  • cert.RebuildLogEntryFromTBS — step 4.
  • cert.EntryHash — step 5 (single-pass per §7.2's inline algorithm).
  • tlogx.EvaluateInclusionProof — step 6.
  • cert.VerifyMTCSignature — step 7's cosigner check.

The shape of all these helpers — small, composable, zero hidden state — is intentional. A relying-party library outside cactus should be able to import just cert/ and tlogx/ and verify certs with a few function calls.

§9: Doing it over ACME

ACME is what the authenticating party (the cert holder) uses to request certs. The MTC draft layers two changes onto RFC 8555:

  1. The order moves to valid once the entry is sequenced — i.e. when its log index is assigned and the next checkpoint is signed — not when the cosignatures arrive. This decouples ACME state from cosignature collection latency.

  2. Cert download negotiation. The client may send Accept: application/pem-certificate-chain-with-properties. The server then includes a CertificatePropertyList alongside the PEM (cactus uses an adjacent MTC PROPERTIES PEM block; the trust-anchor-ids draft hasn't pinned the wire format yet). The property list carries a single trust_anchor_id — the CA ID (§8.1) for a standalone cert, or the specific landmark's ID CA-ID.1.logNumber.L (§8.2) for a landmark-relative cert. A relying party advertises a landmark group CA-ID.2.logNumber.L (§8.2.1) in its trust_anchors to accept the CA's standalone certs and all active landmarks at once.

  3. Enhancement URL. The standalone cert response carries a Link: <…>; rel="acme-optional-alternate" header (draft §9.1) pointing at the landmark-relative variant, at /cert/{id}/landmark-relative/{number}. The number pins the single landmark the entry is relative to (ContainingIndex), so the URL is an immutable resource: it returns HTTP 202 (Accepted) + Retry-After until that landmark is allocated, then the cert. An optional alternate is an optional, non-blocking substitute — a client retries the 202 later but must never let it hold up deploying the standalone cert.

    This replaced an earlier rel="alternate" + 503 + Retry-After design. alternate is load-bearing: clients (e.g. lego, via go-retryablehttp) fetch it eagerly during issuance and honour the Retry-After on the 503, so a not-yet-available landmark stalled issuance for the full interval. acme-optional-alternate + 202 is non-blocking, and pinning the landmark number keeps the URL stable.

Cactus implements the above in acme/ plus the property-list builder in cert/properties.go.

Cactus implementation map

If you're reading the code, this is the order I'd recommend:

  1. cert/entry.go — TBSCertificateLogEntry encoder + the single-pass §7.2 entry hash. Fundamental; everything else downstream of "what's in the log".
  2. tlogx/subtree.go and tlogx/inclusion.go — §4 primitives.
  3. log/log.go — the issuance log: how new entries get into a checkpoint, how covering subtrees get signed, how Wait blocks for a committed entry.
  4. cert/proof.go — MTCProof, MTCSubtree, MTCSignature on the wire.
  5. ca/issuer.go — assemble the X.509 cert from a CSR + a log.Issued.
  6. acme/handler.go — the ACME state machine.
  7. landmark/sequence.go — §6.4.1/2 allocator.
  8. mirrorpush/client.go — the push client that replicates the log to external c2sp.org/tlog-mirror mirrors and retains their cosignatures. (cactus itself is not a mirror; there is no mirror/ package.)

The integration test integration/TestParallelIssuance exercises 1–6 end-to-end: 100 certs in parallel, each one re-parsed and re-verified using the §7.2 procedure on the live log.

Further reading