Subject: [DNSOP] Rough notes for an incremental zone digest

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 29 Aug 2019 18:51:26 +0530

See the attached figure. These are rough notes of a proposal. I sent
this to Duane Wessels a few days ago, but this is probably something for
dnsop@ readers to see too as there has been discussion about an
incremental design for zone digest before. Performing a hash tree using
an existing name tree like BIND's RBT does not appear to be simple. If
such a structure is specified as the canonical structure, it also won't
be appealing across implementations.

---

All the names in the zone are hashed using a suitable hash function
(need not be a crypto hash) into N hashtable buckets where N = 1<<M.

M is variable dependent on the number of names in the zone.  M is
ceil(log2(number of names in the zone / LOAD_FACTOR)) where an example
value for LOAD_FACTOR is 8. Then, an average of 8 names can exist in any
hash bucket.

Each item in the hash table bucket is a SHA-384 hash value and a pointer
to an ordered collection of names. This example uses RBTs for the
collections for fast insertion/deletion, but even a sorted linked list
should be ok, as the average number of names in a bucket is LOAD_FACTOR,
so insertion and lookup are O(1). The choice of collection data
structure does not matter as long as they are scanned in defined order.

The SHA-384 hash value stored in a bucket is the SHA-384 hash performed
in order over all the names and RDATA of the DNS nodes in that bucket
(by scanning the RBT or ordered linked list). This operation is O(1).

So there are N SHA-384 hash values where N is a power of 2. Using a
Merkle tree over it, you get the overall ZONEMD.

---

When inserting, hash the name into the appropriate bucket, recompute the
SHA-384 value for that hash bucket (by scanning the RBT or ordered
linked list) which is an O(1) operation. Then update the hashtree
upwards to get the ZONEMD as a O(log N) operation.

The hashtree is shown as a binary tree. Instead of 2 degrees, the parent
hashes can be computed for 4, 8, 16, 32, or 64 child hashes at a time to
reduce storage of intermediate SHA-384 hash values in the hashtree. It
would be faster too.

---

When inserting, if the total number of names in the zone is greater than
N * load_factor, then N is doubled and all the names in the zone are
rehashed. This is an O(total_number_of_names) event and occurs very
rarely in the lifetime of existing(loaded) zones.

---

In existing implementation data structures, one would have to add two
pointers and a color to every DNS node structure if using the RBT
structure hanging off the hash bucket, or 1 pointer if using ordered
singly linked list. Such a linked list can be insertion sorted, and the
bucket array + list would be simple to implement.

The main tree structure would have pointers to the hash bucket array and
the merkle tree.

LOAD_FACTOR can be tuned suitably to adjust memory utilization of the
bucket array vs. rate of update.

		Mukund

---

From: "Wessels, Duane" <[email-masked]>
Date: Thu, 29 Aug 2019 19:55:58 +0000

Thanks Mukund.  

For everyone else's benefit, what Mukund and I were discussing is ways
to make the ZONEMD algorithm more efficient for large dynamic zones.

The authors are intending for that to be future work, and not a part of
the current proposal, which has this to say about such zones:

   As specified at this time, ZONEMD is not designed for use in large,
   dynamic zones due to the time and resources required for digest
   calculation.  The ZONEMD record described in this document includes
   fields reserved for future work to support large, dynamic zones.

DW

> On Aug 29, 2019, at 6:21 AM, Mukund Sivaraman <[email-masked]> wrote:
> 
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop