PKI, Logs, And Tree Signatures L. J. Reilly Internet-Draft Independent Intended status: Standards Track 27 July 2026 Expires: 28 January 2027 Bulk Subtree Consistency Proofs for Merkle Tree Certificates draft-reilly-plants-bulk-subtree-proofs-01 Abstract Merkle Tree Certificates require relying parties to periodically obtain a set of active landmark subtrees and verify each is consistent with a reference checkpoint of the issuance log. As specified, this requires one subtree consistency proof per landmark subtree, and those proofs share a large fraction of their interior nodes. This document defines a bulk subtree consistency proof, which verifies an entire set of landmark subtrees against a single reference checkpoint from one shared set of hashes. It is a size optimization for the relying party update channel and introduces no change to certificate verification or to the security properties of Merkle Tree Certificates. This revision replaces the construction published in -00, which was incorrect. See Appendix "Changes from -00". Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 28 January 2027. Reilly Expires 28 January 2027 [Page 1] Internet-Draft Bulk Subtree Proofs July 2026 Copyright Notice Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. What the Proofs Share . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. Why the Decomposition Uses Full Subtrees . . . . . . . . . . 4 4. Bulk Subtree Consistency Proofs . . . . . . . . . . . . . . . 5 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Frontier Decomposition . . . . . . . . . . . . . . . . . 5 4.3. Deriving the Tiling . . . . . . . . . . . . . . . . . . . 6 4.4. Proof Format . . . . . . . . . . . . . . . . . . . . . . 6 4.5. Verification . . . . . . . . . . . . . . . . . . . . . . 7 5. Size Analysis . . . . . . . . . . . . . . . . . . . . . . . . 8 6. Relationship to draft-ietf-plants-merkle-tree-certs . . . . . 9 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 9 8. Security Considerations . . . . . . . . . . . . . . . . . . . 10 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 10.1. Normative References . . . . . . . . . . . . . . . . . . 10 Changes from -00 . . . . . . . . . . . . . . . . . . . . . . . . 11 Open Questions . . . . . . . . . . . . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 12 1. Introduction Merkle Tree Certificates [MTC] allow a relying party to accept landmark-relative certificates, which carry an inclusion proof to a landmark subtree and no signatures at all. This is the design's principal size optimization, and it depends on the relying party holding a current, verified set of active landmark subtrees. Section 7.4 of [MTC] specifies how that set is established. Before configuring subtrees as trusted, the relying party must obtain assurance that each subtree is consistent with checkpoints observed Reilly Expires 28 January 2027 [Page 2] Internet-Draft Bulk Subtree Proofs July 2026 by a sufficient set of cosigners. Given a reference checkpoint and cosignatures over it, this reduces to verifying, for each subtree, a subtree consistency proof (Section 4.4 of [MTC]) between that subtree and the reference checkpoint. The number of subtrees involved is not small. A relying party retains up to 2 * max_active_landmarks subtree hashes per CA. The example parameters given in Section 6.3.1 of [MTC] -- a seven-day maximum certificate lifetime with a landmark allocated hourly -- give a max_active_landmarks of 169, and therefore up to 338 active landmark subtrees. Section 7.4 of [MTC] observes that these proofs have many nodes in common and notes that a single proof verifying all the hashes at once is possible. This document specifies such a proof. Measured against the per-subtree baseline it reduces the consistency-proof component of a relying party update by a factor of roughly 2.6 to 5, depending on landmark density; see Section 5. 1.1. What the Proofs Share The active landmark subtrees cover a single contiguous range of the log, because landmark subtrees are constructed to cover consecutive intervals (Section 6.3.1 of [MTC]). Their consistency proofs against a common reference checkpoint therefore reconstruct the same root along heavily overlapping paths, and the material above the point where two subtrees' paths converge is identical between them. The construction below exploits this by transmitting one shared set of node hashes, chosen so that both the reference root and every individual landmark subtree hash can be recomputed from it. The relying party update channel is a broadcast channel: this material is distributed periodically to every relying party that trusts the CA. In the Web PKI that is a population measured in billions of clients, refreshing on the order of hourly. 2. Conventions and Definitions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. Reilly Expires 28 January 2027 [Page 3] Internet-Draft Bulk Subtree Proofs July 2026 This document uses the notation, Merkle Tree definitions, and subtree definitions of Section 4 of [MTC], which extend Section 2.1 of [RFC9162]. In particular HASH, HASH_SIZE, MTH, BIT_CEIL, BIT_WIDTH, and the notation [start, end) for a subtree are used as defined there. A subtree [start, end) is _full_ if end - start is a power of two, and _partial_ otherwise, per Section 4.1 of [MTC]. The _split point_ of a subtree [start, end) whose size is greater than one is start + k, where k is the largest power of two strictly less than end - start. This is the index at which the Merkle Tree Hash recursion of Section 2.1.1 of [RFC9162] divides the node into its two children. It is written SPLIT(start, end). The following additional terms are used: Covered range: The half-open interval spanned by the union of a set of subtrees, when that union is contiguous. Breakpoint: An endpoint of some subtree in the set being proven, or the endpoint of the log itself. Tile: A full subtree in the shared decomposition carried by the proof. Bulk subtree consistency proof: A proof that every subtree in a given set is consistent with a given checkpoint, verified as a unit. 3. Why the Decomposition Uses Full Subtrees A full subtree [start, end) is a node of the Merkle Tree over D_n for every n greater than or equal to end. A partial subtree is a node only when n equals end (Section 4.2 of [MTC]). This distinction governs the whole construction. Landmark subtrees are produced by the covering procedure of Section 4.5 of [MTC], which returns a full left subtree and a possibly-partial right subtree. In a reference checkpoint larger than the landmark's tree size, such a partial subtree is not a node of the tree at all, and no sequence of pairwise hash combinations over tree nodes will produce it or absorb it. Reilly Expires 28 January 2027 [Page 4] Internet-Draft Bulk Subtree Proofs July 2026 Consequently a bulk proof cannot be built by treating the landmark subtrees themselves as a partition of the tree. It must be built over a decomposition into full subtrees, from which both the root and each landmark subtree hash can be recomputed independently. That is what Section 4 does. 4. Bulk Subtree Consistency Proofs 4.1. Overview Let L be the set of subtrees to be proven and n the tree size of the reference checkpoint. 1. Collect the breakpoints: 0, n, and every endpoint of every subtree in L. 2. Between each pair of consecutive breakpoints, decompose the interval into full subtrees using FRONTIER (Section 4.2). The resulting tiles partition [0, n), are all nodes of the reference tree, and refine every subtree boundary in L. 3. The proof carries the tile hashes and the claimed subtree hashes. Tile ranges are not transmitted; the verifier derives them. 4. The verifier recomputes the reference root by descending the tree from [0, n) and stopping at tiles, then recomputes each claimed subtree hash by the same descent. Because every subtree boundary is a breakpoint, each subtree in L is exactly a union of tiles, and its hash is recoverable whether it is full or partial. Subtrees in L that are nested or that overlap require no special handling. 4.2. Frontier Decomposition FRONTIER(s, e) returns the full subtrees covering [s, e), in ascending order of start: def FRONTIER(s, e): """ Full subtrees covering [s, e), ascending by start. """ nodes = [] while s < e: size = 1 while s % (size * 2) == 0 and s + size * 2 <= e: size *= 2 nodes.append((s, s + size)) s += size return nodes Reilly Expires 28 January 2027 [Page 5] Internet-Draft Bulk Subtree Proofs July 2026 Each returned node has a size that is a power of two and a start that is a multiple of that size, so it satisfies Section 4.1 of [MTC] and is full. FRONTIER(s, e) returns at most 2 * BIT_WIDTH(e) nodes, and returns the empty list when s equals e. 4.3. Deriving the Tiling Given a list of subtree ranges L and a tree size n, the tiling is derived as follows: def TILING(L, n): """ Full subtrees partitioning [0, n), refined at every endpoint appearing in L. """ points = {0, n} for (start, end) in L: points.add(start) points.add(end) breakpoints = sorted(points) tiles = [] for p, q in zip(breakpoints, breakpoints[1:]): tiles.extend(FRONTIER(p, q)) return tiles Both the generator and the verifier MUST derive the tiling with this procedure. The proof carries tile hashes in exactly the order TILING returns the corresponding ranges. 4.4. Proof Format A bulk subtree consistency proof is defined below using the TLS presentation language (Section 3 of [RFC8446]), following the conventions of Section 6.1 of [MTC]: opaque HashValue[HASH_SIZE]; struct { uint64 start; uint64 end; HashValue hash; } SubtreeRef; struct { uint64 tree_size; SubtreeRef subtrees<1..2^16-1>; HashValue tiles<1..2^16-1>; } BulkSubtreeProof; tree_size MUST be the tree size of the reference checkpoint. Reilly Expires 28 January 2027 [Page 6] Internet-Draft Bulk Subtree Proofs July 2026 subtrees MUST contain one entry for each subtree being proven, in ascending order of start with ties broken by descending order of end, with no duplicates. Each entry's hash is the subtree hash the relying party is being asked to trust. tiles MUST contain the hash of each range returned by TILING(subtrees, tree_size), in the order returned. 4.5. Verification Given a BulkSubtreeProof, a reference checkpoint root hash root_hash, and that checkpoint's tree size n, a relying party verifies as follows. 1. Check that tree_size equals n and that subtrees is non-empty. If not, fail verification. 2. Check that the ranges in subtrees are in the required order, contain no duplicates, and that each [start, end) satisfies Section 4.1 of [MTC] with end less than or equal to n. If not, fail verification. 3. Compute the expected tiling as TILING(subtrees, n). Check that the number of entries in tiles equals the number of ranges returned. If not, fail verification. Associate each tile hash with the corresponding derived range. 4. Define COMPUTE(s, e) as follows: 1. If [s, e) is a tile range, return its hash. 2. Otherwise, if e - s is one, fail verification. 3. Otherwise, let m be SPLIT(s, e) and return HASH(0x01 || COMPUTE(s, m) || COMPUTE(m, e)). 5. Check that COMPUTE(0, n) equals root_hash. If not, fail verification. 6. For each entry of subtrees, check that COMPUTE(start, end) equals that entry's hash. If not, fail verification. 7. If all checks pass, every subtree in subtrees is consistent with the reference checkpoint, and the relying party MAY configure them as trusted subtrees per Section 7.4 of [MTC], subject to its cosigner requirements being met on the reference checkpoint itself. Reilly Expires 28 January 2027 [Page 7] Internet-Draft Bulk Subtree Proofs July 2026 COMPUTE descends the reference tree using SPLIT, so the order of hash combinations is fixed by the tree structure and there is no ambiguity for an implementation to resolve. Implementations SHOULD memoize COMPUTE, since the subtree checks in step 6 revisit nodes already computed in step 5. 5. Size Analysis Proof size is the number of tiles, which is determined by the number of distinct breakpoints and the width of the gaps between them. It is not independent of the number of subtrees: each additional landmark boundary refines the tiling. The saving relative to the baseline comes from sharing the upper portions of the tree between subtrees, not from eliminating per-subtree material altogether. The following figures were produced with the reference implementation described in Section 7, using a landmark allocation that yields the 338 active landmark subtrees of the Section 6.3.1 example of [MTC]. Baseline is the total size of one subtree consistency proof per landmark subtree; bulk is the tile count. Both are counted as transmitted hashes at 32 bytes each with SHA-256. +=============+==========+===========+==========+===========+ | Log entries | Subtrees | Baseline | Bulk | Reduction | +=============+==========+===========+==========+===========+ | 5,000 | 334 | 107,776 B | 21,344 B | 5.05x | +-------------+----------+-----------+----------+-----------+ | 50,000 | 334 | 119,680 B | 33,024 B | 3.62x | +-------------+----------+-----------+----------+-----------+ | 500,000 | 334 | 129,056 B | 45,184 B | 2.86x | +-------------+----------+-----------+----------+-----------+ | 4,400,000 | 338 | 150,080 B | 57,184 B | 2.62x | +-------------+----------+-----------+----------+-----------+ Table 1: Measured proof sizes The subtree hashes themselves are excluded from both columns, since the relying party retains them regardless; Section 6.3.1 of [MTC] already accounts for them as 10,816 bytes at these parameters. The reduction shrinks as the log grows relative to the number of landmarks, because the tiles between consecutive landmark boundaries become deeper decompositions. It is largest for deployments with sparse landmarks over a small log and smallest for dense landmarks over a large one. Implementers should measure against their own landmark allocation policy rather than assuming the figures above. Reilly Expires 28 January 2027 [Page 8] Internet-Draft Bulk Subtree Proofs July 2026 6. Relationship to draft-ietf-plants-merkle-tree-certs This document is a companion optimization. It does not modify certificate construction (Section 6 of [MTC]), certificate verification (Section 7.2 of [MTC]), the log structure (Section 5 of [MTC]), or the use of Merkle Tree certificates in TLS (Section 8 of [MTC]). It applies only to the establishment of trusted subtrees in Section 7.4 of [MTC], and only to the consistency-checking component of that section. The requirement that the reference checkpoint be cosigned by a set of cosigners sufficient to meet the relying party's policy (Section 7.3 of [MTC]) is unchanged and is not addressed here. Support is optional. A relying party that does not implement bulk proofs continues to verify per-subtree consistency proofs as specified. A CA or update service that does not produce bulk proofs is unaffected. If the working group prefers, the mechanism described here could be incorporated directly into Section 7.4 of [MTC] rather than published separately. 7. Implementation Status An independent reference implementation exists in Python and JavaScript. It implements the Merkle Tree Hash of Section 2.1 of [RFC9162], the subtree definitions and covering procedure of Section 4 of [MTC], per-subtree consistency proof generation for the baseline figures in Section 5, and the construction in this document. The construction has been checked on 600 randomized combinations of log size and landmark allocation. In each case every subtree hash asserted by the proof was compared against direct recomputation of the Merkle Tree Hash from the log, rather than against another implementation of the same proof technique. Cases in which landmark subtrees are partial, nested, or overlapping were confirmed to occur in the sample. Tampering cases -- corrupted subtree hashes, corrupted tile hashes, dropped tiles, reordered tiles, a dropped subtree entry, and verification against an unrelated root -- were each confirmed to be rejected. Test vectors have not yet been extracted into a stable, citable form. That is expected in a subsequent revision. Reilly Expires 28 January 2027 [Page 9] Internet-Draft Bulk Subtree Proofs July 2026 8. Security Considerations The bulk proof asserts exactly what a set of individual subtree consistency proofs asserts: that each subtree hash is consistent with the reference checkpoint. It is a change in encoding and verification cost, not in the trust decision. Tile ranges are derived, not transmitted. The verifier computes the tiling from the claimed subtree list and the reference tree size, so an attacker cannot supply a decomposition of its own choosing. Implementations MUST NOT accept tile ranges from the proof. The subtree list is self-authenticating with respect to the tiling. Adding or removing a subtree entry changes the derived breakpoints and therefore the expected tile count and ranges, so a proof cannot be trimmed to conceal a subtree or padded to smuggle one in without failing step 3 or step 5 of Section 4.5. Verification is all-or-nothing. A bulk proof either verifies every subtree it carries or verifies none. A relying party MUST NOT accept a partial result. Implementations should ensure a failed verification leaves the previously trusted subtree set untouched rather than partially replaced, so that a malformed or hostile update degrades to the relying party continuing with its prior state. Because the relying party continues to accept standalone certificates (Section 6.2 of [MTC]) whenever it lacks a trusted subtree, a failure of this mechanism is an availability and size regression, not an authentication failure. COMPUTE recurses to a depth bounded by BIT_WIDTH(n). Implementations handling untrusted input should bound the number of distinct subtrees accepted in a proof, since the tiling grows with the number of breakpoints and a proof carrying many closely spaced subtrees will produce a correspondingly large tiling. The privacy considerations of Section 11 of [MTC] apply unchanged. This document does not alter what the relying party fetches, only how much of it. 9. IANA Considerations This document has no IANA actions. 10. References 10.1. Normative References Reilly Expires 28 January 2027 [Page 10] Internet-Draft Bulk Subtree Proofs July 2026 [MTC] Benjamin, D., O'Brien, D., Westerbaan, B. E., Valenta, L., and F. Valsorda, "Merkle Tree Certificates", Work in Progress, Internet-Draft, draft-ietf-plants-merkle-tree- certs-04, May 2026, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . [RFC9162] Laurie, B., Messeri, E., and R. Stradling, "Certificate Transparency Version 2.0", RFC 9162, DOI 10.17487/RFC9162, December 2021, . Changes from -00 The construction published in -00 was incorrect. It was withdrawn after being implemented. The errors and their resolution are recorded here rather than silently removed, since -00 is publicly archived. *The laminarity argument was false.* Section 3.2 of -00 asserted that the active landmark subtrees form a laminar family of nodes of the reference checkpoint's Merkle Tree, and the construction folded them upward into the root on that basis. Partial subtrees are not nodes of a larger tree: per Section 4.2 of [MTC], a partial subtree is contained in MTH(D_n) only when n equals its end. The covering procedure of Section 4.5 of [MTC] explicitly returns a possibly- partial right subtree, so landmark sets routinely contain subtrees that do not exist as nodes in the reference tree and cannot be folded into its root by any sequence of pairwise combinations. This is why [MTC] uses consistency proofs rather than inclusion proofs here. Section 3 now states the distinction explicitly and the construction decomposes into full subtrees instead. *The merge rule was also wrong independently.* Step 8 of the -00 verification procedure merged adjacent equal-size pairs and then folded any remainder from right to left. Right-to-left folding does not reconstruct the root for valid partitions such as [(0,4), (4,8), Reilly Expires 28 January 2027 [Page 11] Internet-Draft Bulk Subtree Proofs July 2026 (8,13)] in a tree of size 13, since it attempts to form [4,13), which is not a subtree. Verification now descends the tree using SPLIT, so the combination order is determined by the tree rather than by the verifier's search order. *The size claim was wrong.* -00 claimed proof material of O(log n) independent of the number of subtrees, and a reduction of roughly two orders of magnitude. Both followed from the incorrect construction. Proof size scales with the number of landmark boundaries, because each boundary refines the tiling. Measured reductions are between 2.6x and 5x over the parameter range examined; see Section 5. *The nested-subtree machinery is gone.* Stage 3 of -00, with its NestedSubtreeProof structure and interior-node inclusion proofs, existed to handle subtrees contained within other subtrees. Because the tiling refines every subtree boundary, nested and overlapping subtrees are now handled by the same descent as everything else, and the structure has been removed. Size figures are now measured rather than estimated, and an implementation status section has been added. Open Questions * Test vectors should be extracted into a stable form and included directly in this document. * The tiling is derived from the subtree endpoints alone. A CA that knows its own landmark allocation policy may be able to choose landmark tree sizes that produce coarser tilings, reducing proof size further at no cost to anything else. This interacts with Section 6.3.2 of [MTC] and is worth investigating. * Whether the incremental case is worth specifying: a relying party refreshing its trusted subtree set typically retains most of the previous set, and a delta form of this proof may be substantially smaller than a full one. * Whether a bound should be placed on the number of subtrees a relying party will accept in a single proof, and if so what it should be. Author's Address Lawrence J. Reilly Independent Email: lawrencejohnreilly@gmail.com Reilly Expires 28 January 2027 [Page 12]