The MERKLE3 Incremental Scheme for ZONEMD
draft-aklpdw-dnsop-zonemd-incremental-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Authors | Duane Wessels , Libor Peltan , Arya Khanna | ||
| Last updated | 2026-10-12 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| On agenda | dnsop at IETF-127 | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-aklpdw-dnsop-zonemd-incremental-00
DNSOP D. Wessels
Internet-Draft Verisign
Intended status: Standards Track L. Peltan
Expires: 15 April 2027 CZ.NIC
A. Khanna
NLnet Labs
12 October 2026
The MERKLE3 Incremental Scheme for ZONEMD
draft-aklpdw-dnsop-zonemd-incremental-00
Abstract
The ZONEMD Resource Record affirms the integrity of whole DNS zones
and helps verify their authenticity. It embeds a cryptographic hash
of the zone data, collated in a configurable way. It is used as a
checksum for zone transfers between name servers.
[RFC8976] defined a single ZONEMD collation scheme, SIMPLE. It is
sufficient for small and infrequently updated zones. This document
introduces the MERKLE3 scheme, targeting large, dynamic zones. It
uses a Merkle tree to enable parallelism and incremental computation.
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 15 April 2027.
Copyright Notice
Copyright (c) 2026 IETF Trust and the persons identified as the
document authors. All rights reserved.
Wessels, et al. Expires 15 April 2027 [Page 1]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
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. Reserved Words . . . . . . . . . . . . . . . . . . . . . 3
2. The MERKLE3 Scheme . . . . . . . . . . . . . . . . . . . . . 3
2.1. Computation . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Worked example . . . . . . . . . . . . . . . . . . . . . 4
2.3. MERKLE3 Scheme Inclusion/Exclusion Rules . . . . . . . . 5
2.4. MERKLE3 Scheme Digest Calculation . . . . . . . . . . . . 5
2.5. Adding an RRset . . . . . . . . . . . . . . . . . . . . . 6
2.6. Removing an RRset . . . . . . . . . . . . . . . . . . . . 6
2.7. Updating an RRset . . . . . . . . . . . . . . . . . . . . 6
2.8. Recomputing After Changes . . . . . . . . . . . . . . . . 6
3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6
4. Security Considerations . . . . . . . . . . . . . . . . . . . 7
5. Performance Considerations . . . . . . . . . . . . . . . . . 7
6. Privacy Considerations . . . . . . . . . . . . . . . . . . . 7
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7
8. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
9. Appendix: Design Decisions . . . . . . . . . . . . . . . . . 8
9.1. Use of Merkle Tree . . . . . . . . . . . . . . . . . . . 8
9.2. Shape of the Tree . . . . . . . . . . . . . . . . . . . . 8
9.3. Granularity of hashing . . . . . . . . . . . . . . . . . 9
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 10
10.1. Normative References . . . . . . . . . . . . . . . . . . 10
10.2. Informative References . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction
A ZONEMD record is generated with a choice of hash function and
collation scheme. For the hash function, choices of SHA-384 and
SHA-512 have been defined. The collation scheme decides how the hash
function is applied to the zone data. The SIMPLE scheme hashes the
concatenation of the records in the zone, in canonical order. With
its definition, [RFC8976] notes:
Wessels, et al. Expires 15 April 2027 [Page 2]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
| For the SIMPLE scheme, the digest is calculated over the zone as a
| whole. This means that a change to a single RR in the zone
| requires iterating over all RRs in the zone to recalculate the
| digest. SIMPLE is a good choice for zones that are small and/or
| stable, but it is probably not good for zones that are large and/
| or dynamic.
The SIMPLE scheme does not support parallelism or efficient
incremental computation. Every change to the zone requires re-
hashing all of the zone contents, serially. For DNSSEC signers,
computing ZONEMD with the SIMPLE scheme is the only step that cannot
be parallelized.
This document describes a new collation scheme targeting large,
dynamic zones. It organizes the records in the zone in a Merkle tree
structure. Records have fixed positions in the tree, so they are
unaffected by additions and removals. Changes to the zone only
require re-hashing the affected nodes of the tree and their parents.
Using this scheme, ZONEMD checksums can be computed in a highly-
parallel fashion. Given the prevalence of many-core CPUs, an order-
of-magnitude speedup is achievable. Implementations can persist the
tree structure for incremental computation, with even better
speedups.
1.1. Reserved Words
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.
2. The MERKLE3 Scheme
2.1. Computation
The MERKLE3 data structure is a trie. It consists of four levels:
level 0 (the root node), level 1 (up to 256 nodes), level 2 (up to
65,536 nodes), and level 3 (individual RRsets). The first three
levels (0, 1, and 2) are _inner nodes_. Nodes in levels 0 and 1 have
up to 256 children each. Children are identified by an unsigned
8-bit index from 0 to 255.
Every RRset is individually hashed, using the selected ZONEMD hash
algorithm. The records in the RRset are sorted in DNSSEC canonical
order, serialized in the DNSSEC canonical form, concatenated
together, and hashed once. Each RRset is assigned to a level-2 node
Wessels, et al. Expires 15 April 2027 [Page 3]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
in the tree, based on the first two bytes of its hash. The first
byte selects a node in level 1 and the second selects a node in level
2.
Note: in the incredibly unlikely case that two RRsets have the same
hash, they should not be deduplicated: both hashes should be inserted
in the tree.
Within each level-2 node, RRsets are sorted lexicographically by
their hashes. These hashes are concatenated and hashed, using the
same hash algorithm, to produce the hash of the level-2 node.
Level-2 nodes that have no children are not hashed at all.
Then, the hashes of the level-1 nodes are computed. The children of
each level-1 node (those that exist) are ordered by index. The
hashes are concatenated and hashed to produce the hash of the level-1
node. Again, level-1 nodes that have no children are not hashed at
all.
The root node is hashed from the level-1 nodes in the same way. The
hash of the root node is the final digest that is stored in the
ZONEMD record.
2.2. Worked example
Consider the following zone:
example.com. 300 IN SOA mname.example.com. rname.example.com. (
1 3600 7200 43200 300 )
example.com. 60 I NS ns1.foo.example.
example.com. 300 IN AAAA 2606:4700:10::ac42:93f3
example.com. 300 IN AAAA 2606:4700:10::6814:179a
The NS RRset is serialized as the following bytes, in hexadecimal:
07 6578616D706C65 03 636F6D 00 0002 0001 0000003C 0011 03 6E7331 03
666F6F 07 6578616D706C65 00
The NS RRset has a SHA384 hash value of:
089AAD19F7AE6D16 D4BBA103E784AA8F 0E2818E56921C439 5F59EC80A3C4C856
10D50D7D5B3A1DD7 8C51C0ED5A9F45CC
The first two bytes are relevant. The RRset is positioned under the
root node, under its (level-1) child node at index 8 (0x08), under
its (level-2) child node at index 154 (0x9A).
The SOA RRset is serialized as the following bytes, in hexadecimal:
Wessels, et al. Expires 15 April 2027 [Page 4]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
07 6578616D706C65 03 636F6D 00 0006 0001 0000012C 003A 05 6D6E616D65
07 6578616D706C65 03 636F6D 00 05 726E616D65 07 6578616D706C65 03
636F6D 00 00000001 00000E1 000001C2 00000A8C 00000012C
The SOA RRset has a SHA384 hash value of:
B5EE62F73B9094B4 B0E1FCF899FADBD5 5972359A355C82C9 24CEA28A1B73959E
CA9D6D00670FF32A 873B8AD03721A181
This RRset is positioned under the root node, under its (level-1)
child node at index 181 (0xB5), under its (level-2) child node at
index 238 (0xEE).
The two records in the AAAA RRset are serialized as the following
bytes, in hexadecimal:
07 6578616D706C65 03 636F6D 00 001C 0001 0000012C 0010 2606 4700 0010
0000 0000 0000 6814 179A
07 6578616D706C65 03 636F6D 00 001C 0001 0000012C 0010 2606 4700 0010
0000 0000 0000 AC42 93F3
The AAAA RRset has a SHA-384 hash value of:
9CDD7D2DB2C820F5 4DF2F64690A68665 D3459BEACC09F216 57D01848B2D195A9
5C0E24C3E7458B95 B03EFBDC8B252DEF
This RRset is positioned under the root node, under its (level-1)
child node at index 156 (0x9C), under its (level-2) child node at
index 221 (0xDD).
The final MERKLE3 ZONEMD SHA384 digest for this zone is:
5F0AD47C76A59B6E 287E221C296EA5C8 99AE5D473E4AE0E3 FF0FCEDF3E2345BE
7FC9F27CA1307775 4C98BB53B6288B64
2.3. MERKLE3 Scheme Inclusion/Exclusion Rules
The inclusion and exclusion rules for the MERKLE3 scheme are
identical to those for the SIMPLE scheme, described in
Section 3.3.1.1 of [RFC8976].
2.4. MERKLE3 Scheme Digest Calculation
A zone digest using the MERKLE3 scheme is calculated over the Merkle
tree in a bottom-up fashion. Each branch node in the tree has its
own hash value, which is calculated from the elements directly
beneath it.
Wessels, et al. Expires 15 April 2027 [Page 5]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
A leaf node's hash value is directly the RRset hash value and
corresponds to the leaf position in the tree.
A branch node (including root) hash value is calculated by
concatenating all of its child node hash values, sorted numerically,
as input to the zone digest hash function. Note that for branch
nodes, their assigned hash value may (in fact, usually will) not
correspond to its position in the tree (and the common prefix of
leaves' hash values).
The root node hash value becomes the zone digest, placed in the RDATA
of the apex ZONEMD RR.
Upon a change to a leaf node, the inner node hash values are
recalculated from the bottom up, until reaching the root node.
2.5. Adding an RRset
To add an RRset to the MERKLE3 data structure (subject to inclusion/
exclusion rules), its location is determined as described above. A
new leaf node is added with the RRset's hash, and a path of branch
nodes up to the tree as well if they don't exist yet.
2.6. Removing an RRset
To remove an RRset from the MERKLE3 data structure, its location is
determined as described above. If the RRset was previously placed in
the data structure, its full hash value should have the corresponding
leaf node, from which it is then removed. Any branch nodes becoming
empty are removed as well.
2.7. Updating an RRset
Updating an RRset in the MERKLE3 data structure is equivalent to
removing the former RRset and then adding the updated RRset.
2.8. Recomputing After Changes
To recompute the MERKLE3 ZONEMD digest it is only necessary to update
all inner hash values along paths from changed leaf nodes back to the
root node.
3. IANA Considerations
IANA is requested to update the "ZONEMD Schemes" registry on the
"Domain Name System (DNS) Parameters" web page as follows:
Value: TBD
Wessels, et al. Expires 15 April 2027 [Page 6]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
Description: Merkle Tree Incremental ZONEMD collation
Mnemonic: MERKLE3
Reference: [this document]
4. Security Considerations
All security considerations from [RFC8976] apply to this
specification and the MERKLE3 scheme.
5. Performance Considerations
The MERKLE3 scheme requires an implementation to maintain an in-
memory Merkle tree data structure of DNS zone data. This will
generally be in addition to an implementation's primary data
structure for referencing zone data. As a sample data point, the .SE
zone from 2026-02-16 with 8 million records and 1.41 million RRsets
required an additional 285 MB of memory in the author's proof-of-
concept implementation.
Compared to the SIMPLE scheme ([RFC8976]), the time to compute an
initial MERKLE3 digest can be larger in a single-threaded
application, due to the need to populate the Merkle tree data
structure. However, when parallelization and multi-threading are
leveraged, the MERKLE3 scheme can perform significantly better.
However, the time to compute updates to the MERKLE3 digest are
essentially zero on modern computer systems, whereas the SIMPLE
scheme provides no reduction in time for computing updates.
The above considerations apply only to well-balanced Merkle trees.
An attacker with the ability to insert RRsets into a zone may be able
to intentionally unbalance the MERKLE3 data structure, similar to the
Nurgle attack [Nurgle]. The performance of the MERKLE3 scheme in
such an attack may be degraded at a rate proportional to the fraction
of RRsets under the attacker's control. In other words, an attacker
would need to control a significant fraction of RRsets in a large
zone in order to affect performance.
6. Privacy Considerations
This specification has no impact on user privacy.
7. Acknowledgements
The authors wish to thank members of the DNSOP working group for
their input.
Wessels, et al. Expires 15 April 2027 [Page 7]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
8. Changes
RFC Editor: Please remove this section before publication.
This section lists substantial changes to the document as it is being
worked on.
* From -00 to -01
- this
- that
- the other
9. Appendix: Design Decisions
9.1. Use of Merkle Tree
Merkle Tree ensures strong cryptographic properties of the resulting
hash while enabling tiny updates to the large structure to be
processed in logarithmic time.
A proposed alternative was to simply XOR the hashes of individual
RRsets. This would be much simpler to implement, wouldn't need any
persistent data structures, would be much faster to compute, and
would even allow validating an incremental change without accessing
the whole zone. Unfortunately, such a scheme is not
cryptographically secure; it could only serve as a checksum against
random errors.
9.2. Shape of the Tree
Several variations of the Merkle tree design were considered,
focusing on its height and branching factor (the number of children
of a node). There were two main proposals: a radix tree and a static
tree.
In the radix tree proposal, inner nodes that have no siblings would
be collapsed into their parents. The leaves of the tree
(representing individual RRsets) would be located at varying depths
from the root. Such a binary tree would have a maximum height of
256, but due to the uniform distribution of nodes by the hash
function, the real height would be logarithmic to the number of
nodes. It would scale dynamically for the size of the zone while
offering logarithmic-time operations.
In the static tree proposal, all leaf nodes would be located at
exactly the same height, and all the nodes above them would exist
unconditionally. RRsets would be hashed under the leaf nodes. Its
operations scale linearly if there are many more RRsets than nodes.
Wessels, et al. Expires 15 April 2027 [Page 8]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
There were concerns that a single static tree scheme would not cater
to the performance needs of both medium-sized and large zones, that
multiple schemes of different configurations would be needed.
These proposals were experimentally implemented with various
configurations. They were compared by measuring their runtime
performance and memory usage in various scenarios (many tiny zones
and one TLD-like large zone):
* binary radix tree
* 256-ary radix tree
* 256-ary static tree, depth 2
* 256-ary static tree, depth 3
* 256-ary static tree, depth 4
The single-threaded comptuation times of building the whole tree
(non-incremental update) of 8-million RR se. zone were in seconds,
respectively:
Binary radix: 9.11, 256-ary Radix: 7.98, 256-ary Static2: 11.43,
Static3: 8.03 Static4: 11.11
And the memory consumptions of the persistent Merkle tree were in
MiB, respectively:
Binary radix: 616, 256-ary Radix: 369, 256-ary Static2: 279, Static3:
285, Static4: 749
The penultimate option (256-ary static tree, depth 3) proved
versatile and almost best in each scenario. It provides good speeds
for medium and large zones alike. It was not necessary to define
multiple static tree schemes to cover all needs.
Note that the needs for very small zones were not considered, as they
are adequately satisfied by the SIMPLE scheme.
9.3. Granularity of hashing
While the final design operates on units of RRsets, smaller and
larger units were considered.
One proposal considered hashing individual resource records (RRs).
This would ease the processing of updates: an addition or removal of
an RR could be processed without knowledge of the RRset it is
contained within. But it would require many more invocations of the
hash function (one per RR instead of one per RRset) and would
significantly increase the size of the tree.
Wessels, et al. Expires 15 April 2027 [Page 9]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
Another proposal considered hashing whole Nodes (all the RRsets at a
particular owner name). This would shrink the Merkle tree, but
increase the effort to process an update (significantly more data
would have to be hashed to update a single node). Notably, the zone
apex, which often contains many RRsets, is affected by every update;
this proposal would greatly increase the effort for it.
The accepted proposal, where RRsets are hashed, strikes a balance
between hashing too many times and hashing too much. The alternative
proposals were not implemented or experimentally evaluated.
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8976] Wessels, D., Barber, P., Weinberg, M., Kumari, W., and W.
Hardaker, "Message Digest for DNS Zones", RFC 8976,
DOI 10.17487/RFC8976, February 2021,
<https://www.rfc-editor.org/info/rfc8976>.
10.2. Informative References
[Nurgle] He, Z., Li, Z., Qiao, A., Luo, X., Zhang,, X., Chen, T.,
Song, S., Liu, D., and W. Miu, "Nurgle: Exacerbating
Resource Consumption in Blockchain State Storage via MPT
Manipulation", May 2024,
<http://dx.doi.org/10.1109/SP54263.2024.00125>.
Authors' Addresses
Duane Wessels
Verisign
Email: dwessels@verisign.com
Libor Peltan
CZ.NIC
Email: libor.peltan@nic.cz
Wessels, et al. Expires 15 April 2027 [Page 10]
Internet-Draft The MERKLE3 ZONEMD Scheme October 2026
Arya Khanna
NLnet Labs
Email: arya@nlnetlabs.nl
Wessels, et al. Expires 15 April 2027 [Page 11]