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

["Wessels, Duane" <[e-mail]>]

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 <[e-mail]> wrote:
> 
> 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
> <zonemd.jpg>_______________________________________________
> DNSOP mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/dnsop