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-00
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. Because the active landmark subtrees form a contiguous
range of the log, their individual consistency proofs share the great
majority of their interior nodes, and verifying them independently
carries substantial redundancy.
This document defines a bulk subtree consistency proof, which
verifies an entire set of landmark subtrees against a single
reference checkpoint using proof material logarithmic in the size of
the log, rather than logarithmic per subtree. 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.
The construction in this document has not yet been validated against
a reference implementation. It is published to solicit review of the
approach. Open items are recorded in an appendix.
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. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 4
3. Structure of the Active Landmark Set . . . . . . . . . . . . 4
3.1. Contiguity . . . . . . . . . . . . . . . . . . . . . . . 4
3.2. Laminarity . . . . . . . . . . . . . . . . . . . . . . . 5
4. Bulk Subtree Consistency Proofs . . . . . . . . . . . . . . . 5
4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2. Proof Format . . . . . . . . . . . . . . . . . . . . . . 6
4.3. Frontier Decomposition . . . . . . . . . . . . . . . . . 7
4.4. Verification . . . . . . . . . . . . . . . . . . . . . . 7
4.4.1. Stage 1: Structural Checks . . . . . . . . . . . . . 7
4.4.2. Stage 2: Root Reconstruction . . . . . . . . . . . . 8
4.4.3. Stage 3: Nested Subtrees . . . . . . . . . . . . . . 9
5. Size Analysis . . . . . . . . . . . . . . . . . . . . . . . . 9
6. Relationship to draft-ietf-plants-merkle-tree-certs . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.1. Normative References . . . . . . . . . . . . . . . . . . 11
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 12
Open Questions . . . . . . . . . . . . . . . . . . . . . . . . . 12
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13
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.
Reilly Expires 28 January 2027 [Page 2]
Internet-Draft Bulk Subtree Proofs July 2026
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
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. Each independent consistency proof against the
reference checkpoint contains on the order of tens of hashes for a
log of the sizes contemplated in Section 6.4 of [MTC].
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.
1.1. Motivation
The redundancy is structural rather than incidental. Every active
landmark subtree is a node of the same Merkle Tree, and every
consistency proof against the same reference checkpoint reconstructs
the same root along overlapping paths. Above the point where two
subtrees' paths converge, their proofs are identical.
More strongly, the active landmark subtrees are not an arbitrary
collection of nodes. Landmark subtrees are constructed to cover
consecutive intervals (Section 6.3.1 of [MTC]), so the active set
covers a single contiguous range of log entries. A contiguous range
of a Merkle Tree can be proven against the root with a single
frontier decomposition, whose size is logarithmic in the size of the
log and independent of the number of subtrees in the range.
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. Reducing the
per-refresh proof material is therefore worth a modest amount of
specification complexity.
Reilly Expires 28 January 2027 [Page 3]
Internet-Draft Bulk Subtree Proofs July 2026
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.
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, LSB, and
the notation [start, end) for a subtree are used as defined there.
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.
Frontier: A minimal set of canonical Merkle Tree nodes whose ranges
are disjoint and whose union is exactly a given interval.
Bulk subtree consistency proof: A proof that every subtree in a
given set is consistent with a given checkpoint, verified as a
unit.
3. Structure of the Active Landmark Set
This section establishes the two properties the construction relies
on. Both follow from Section 4.5 and Section 6.3.1 of [MTC] and are
stated here so that a verifier can check them explicitly.
3.1. Contiguity
For each active landmark other than the lowest, the landmark's
subtrees are selected to cover [prev_tree_size, tree_size), where
prev_tree_size is the tree size of the preceding landmark. By the
properties given in Section 4.5 of [MTC], the returned subtrees
satisfy left.end = right.start, left.start <= prev_tree_size, and
right.end = tree_size.
Consequently the union of the subtrees of consecutive landmarks is
contiguous. It may extend below prev_tree_size -- the covering
procedure is permitted to include extra entries before the start of
the target interval, though never after its end -- but it contains no
gaps.
Reilly Expires 28 January 2027 [Page 4]
Internet-Draft Bulk Subtree Proofs July 2026
Let L be the set of active landmark subtrees, a be the minimum start
over all subtrees in L, and b be the maximum end. Then the union of
L is exactly [a, b).
3.2. Laminarity
Every subtree as defined in Section 4.1 of [MTC] corresponds to a
node of the Merkle Tree of hash operations. Any two such nodes are
either disjoint or nested. The set L is therefore a laminar family:
where subtrees of consecutive landmarks overlap, the overlap is
containment, not partial intersection.
This matters for verification. A subtree of L that is properly
contained in another subtree of L is redundant for the purpose of
covering [a, b), but its hash must still be verified, because the
relying party will accept landmark-relative certificates against it.
Section 4.4 handles this case explicitly.
4. Bulk Subtree Consistency Proofs
4.1. Overview
Verification proceeds in three stages.
1. The verifier reduces L to a maximal antichain A: the subtrees of
L that are not properly contained in any other subtree of L. The
elements of A are pairwise disjoint and their union is [a, b).
Each element of L \ A is contained in some element of A and is
verified in stage 3.
2. The verifier reconstructs the root hash of the reference
checkpoint from the hashes of A together with two frontier
proofs, one covering [0, a) and one covering [b, n), where n is
the reference checkpoint's tree size. Success proves every
element of A is consistent with the checkpoint.
3. For each element of L \ A, the verifier checks an inclusion proof
against its containing element of A. These proofs are short,
because the containment is shallow.
Stage 2 replaces |A| independent consistency proofs with proof
material of size O(log n). Stage 3 adds proof material proportional
to |L \ A|, but as Section 5 discusses, |L \ A| is small and the
individual proofs are of constant expected size.
Reilly Expires 28 January 2027 [Page 5]
Internet-Draft Bulk Subtree Proofs July 2026
4.2. 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 contained_in_start;
uint64 contained_in_end;
HashValue inclusion_proof<0..2^16-1>;
} NestedSubtreeProof;
struct {
uint64 tree_size;
SubtreeRef subtrees<1..2^16-1>;
HashValue left_frontier<0..2^16-1>;
HashValue right_frontier<0..2^16-1>;
NestedSubtreeProof nested_proofs<0..2^16-1>;
} BulkSubtreeProof;
tree_size MUST be the tree size of the reference checkpoint.
subtrees MUST contain one entry for each subtree in L, in ascending
order of start, with ties broken by descending order of end. Each
entry's hash is the subtree hash the relying party is being asked to
trust.
left_frontier MUST contain the hashes of the canonical nodes covering
[0, a), in ascending order of the node's start. It is empty when a
is zero.
right_frontier MUST contain the hashes of the canonical nodes
covering [b, tree_size), in ascending order of the node's start. It
is empty when b equals tree_size.
nested_proofs MUST contain one entry for each subtree in L \ A, in
the same order those subtrees appear in subtrees. Each entry
identifies the containing antichain element and carries a subtree
inclusion proof (Section 4.3 of [MTC]) from the nested subtree's
range to that element.
Reilly Expires 28 January 2027 [Page 6]
Internet-Draft Bulk Subtree Proofs July 2026
4.3. Frontier Decomposition
The canonical nodes covering an interval [s, e) are determined by the
following procedure, which returns them in ascending order of start:
def frontier(s, e):
""" Returns the canonical Merkle Tree nodes covering [s, e). """
nodes = []
while s < e:
# Largest full subtree starting at s that does not overrun e.
size = 1
while (s % (size * 2) == 0) and (s + size * 2 <= e):
size *= 2
nodes.append((s, s + size))
s += size
return nodes
Each returned node satisfies the subtree validity conditions of
Section 4.1 of [MTC]: start is a multiple of BIT_CEIL(end - start).
The number of nodes returned is at most 2 * BIT_WIDTH(e).
A verifier MUST derive the expected frontier node ranges itself using
this procedure rather than accepting ranges supplied in the proof.
Only the hashes are carried in left_frontier and right_frontier;
their ranges are implied. This prevents a malicious proof from
substituting a different decomposition.
4.4. Verification
Given a BulkSubtreeProof and a reference checkpoint root hash
root_hash whose tree size is tree_size, a relying party verifies as
follows.
4.4.1. Stage 1: Structural Checks
1. Check that subtrees is non-empty and sorted as required above.
If not, fail verification.
2. For each entry in subtrees, check that [start, end) is a valid
subtree per Section 4.1 of [MTC] and that end <= tree_size. If
not, fail verification.
3. For each pair of entries in subtrees, check that their ranges are
disjoint or nested. If any pair partially overlaps, fail
verification.
Reilly Expires 28 January 2027 [Page 7]
Internet-Draft Bulk Subtree Proofs July 2026
4. Let A be the set of entries not properly contained in any other
entry, and let a and b be the minimum start and maximum end over
all entries. Check that the ranges of A are pairwise disjoint
and that their union is exactly [a, b). If not, fail
verification.
5. Check that nested_proofs contains exactly one entry for each
element of subtrees not in A, in order. If not, fail
verification.
Step 4 is the check that makes the optimization safe. It establishes
that the antichain is a gapless cover of [a, b) before any hashing is
done, so a proof cannot omit a region of the range and have the
omission absorbed by a supplied frontier hash.
4.4.2. Stage 2: Root Reconstruction
6. Compute left_nodes as frontier(0, a) and right_nodes as
frontier(b, tree_size), per Section 4.3. Check that
left_frontier and right_frontier have exactly len(left_nodes) and
len(right_nodes) elements respectively. If not, fail
verification.
7. Construct a working list of (range, hash) pairs by concatenating,
in order: left_nodes zipped with left_frontier; the elements of A
in ascending order with their hashes; and right_nodes zipped with
right_frontier. The ranges in this list are disjoint, adjacent,
and cover [0, tree_size).
8. Repeatedly reduce the working list: find any adjacent pair ([s,
m), h_l) and ([m, e), h_r) such that [s, e) is a valid subtree
and m - s equals e - m, and replace the pair with ([s, e),
HASH(0x01 || h_l || h_r)). When no such pair remains, if the
list has more than one element, fold the remaining elements from
right to left: replace the last two elements ([s, m), h_l) and
([m, e), h_r) with ([s, e), HASH(0x01 || h_l || h_r)), repeating
until one element remains.
9. Check that the single remaining element's range is [0, tree_size)
and its hash is equal to root_hash. If not, fail verification.
Step 8 is the standard reduction from a frontier to a Merkle Tree
Hash and matches the tree structure defined in Section 2.1.1 of
[RFC9162]. The right-to-left fold at the end handles the partial
subtrees along the right edge of a tree whose size is not a power of
two.
Reilly Expires 28 January 2027 [Page 8]
Internet-Draft Bulk Subtree Proofs July 2026
4.4.3. Stage 3: Nested Subtrees
10. For each element of subtrees not in A, with range [s, e) and hash
h, and its corresponding NestedSubtreeProof:
1. Check that [contained_in_start, contained_in_end) is the
range of an element of A and that it contains [s, e). If
not, fail verification.
2. Evaluate the inclusion proof to reconstruct the containing
element's hash from h, following Section 4.3.2 of [MTC]
generalized from a leaf to an interior node: the proof
supplies the sibling hashes along the path from [s, e) to
[contained_in_start, contained_in_end).
3. Check that the result equals the containing element's hash.
If not, fail verification.
11. 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.
5. Size Analysis
The dominant term in the existing construction is |L| independent
consistency proofs. Using the example parameters of Section 6.3.1 of
[MTC] -- max_active_landmarks of 169, so |L| up to 338 -- and the
issuance rate estimates of Section 6.4 of [MTC], each proof carries
sufficient nodes to reconstruct both the subtree hash and the root
hash, on the order of tens of hashes for logs in the range
contemplated there.
Under the bulk construction:
* subtrees carries |L| hashes. This is not new material: the
relying party retains these hashes regardless, and Section 6.3.1
of [MTC] already accounts for them as 10,816 bytes at these
parameters.
* left_frontier and right_frontier together carry at most 2 *
BIT_WIDTH(tree_size) hashes. For a log of up to 2^32 entries this
is at most 64 hashes, or 2,048 bytes with SHA-256, independent
of |L|.
Reilly Expires 28 January 2027 [Page 9]
Internet-Draft Bulk Subtree Proofs July 2026
* nested_proofs carries material only for subtrees properly
contained in others. Nesting arises only where the covering
procedure of Section 4.5 of [MTC] extends a landmark's left
subtree below the previous landmark's tree size, so |L \ A| is
bounded by the number of landmark boundaries and the containment
is shallow. Each proof is expected to be a small constant number
of hashes.
The net effect is to replace material scaling as O(|L| log n) with
material scaling as O(log n) plus the subtree hashes the relying
party must hold in any case. At the parameters above this is roughly
two orders of magnitude in the consistency-proof component of each
update.
Implementers should measure this against their own landmark
allocation policies. The saving is largest for deployments with
frequent landmarks and long maximum certificate lifetimes, which are
exactly the deployments with the largest max_active_landmarks.
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 PLANTS working group prefers, the mechanism described here
could be incorporated directly into Section 7.4 of [MTC] rather than
published separately.
7. Security Considerations
The bulk proof asserts exactly what |L| individual subtree
consistency proofs assert: that each subtree hash is consistent with
the reference checkpoint. It is a change in encoding and
verification cost, not in the trust decision.
Reilly Expires 28 January 2027 [Page 10]
Internet-Draft Bulk Subtree Proofs July 2026
Three points require care.
The antichain cover must be checked before hashing. Step 4 of
Section 4.4 establishes that the elements of A are disjoint and
gaplessly cover [a, b). Without this check, a proof could omit a
subregion and supply a frontier hash that absorbs it, causing the
verifier to accept a subtree hash that is not in fact consistent with
the checkpoint. This check is inexpensive and MUST NOT be skipped.
Frontier ranges must be derived, not accepted. As noted in
Section 4.3, the proof carries frontier hashes but not frontier
ranges. A verifier that accepted attacker-supplied ranges could be
induced to reconstruct a different tree shape. Verifiers MUST
compute the decomposition from a, b, and tree_size.
Failure is all-or-nothing. A bulk proof either verifies every
subtree in L or verifies none. A relying party MUST NOT accept a
partial result by, for example, treating subtrees whose stage 3
checks passed as trusted after stage 2 failed. 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 and accepting standalone certificates.
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.
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.
8. IANA Considerations
This document has no IANA actions.
9. References
9.1. Normative References
[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, .
Reilly Expires 28 January 2027 [Page 11]
Internet-Draft Bulk Subtree Proofs July 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, .
Acknowledgements
This work responds to an open item recorded in Section 7.4 of [MTC].
The construction rests entirely on the subtree definitions and proof
procedures developed by the authors of that document.
Open Questions
The following are known to require further work and are recorded here
for working group discussion rather than presented as settled. The
construction in this document has not been validated against a
reference implementation.
* The stage 3 nested-subtree handling assumes containment is
shallow. This should be bounded analytically from the covering
procedure in Section 4.5 of [MTC] rather than asserted.
* The generalization of the inclusion proof procedure in
Section 4.3.2 of [MTC] from a leaf to an interior node is stated
informally in stage 3 and needs to be written out normatively.
* The reduction in step 8 of Section 4.4 is described procedurally.
A formulation in the recursive style of Section 4.4.1 of [MTC]
would be more consistent with the base document.
* 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 smaller still.
* Test vectors are not yet included and should be generated against
a reference implementation before this document advances.
Reilly Expires 28 January 2027 [Page 12]
Internet-Draft Bulk Subtree Proofs July 2026
Author's Address
Lawrence J. Reilly
Independent
Email: lawrencejohnreilly@gmail.com
Reilly Expires 28 January 2027 [Page 13]