[DNSOP] Rough notes for an incremental zone digest

Mukund Sivaraman <muks@mukund.org> Thu, 29 August 2019 13:22 UTC

Return-Path: <muks@mukund.org>
X-Original-To: dnsop@ietfa.amsl.com
Delivered-To: dnsop@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C16661200F4 for <dnsop@ietfa.amsl.com>; Thu, 29 Aug 2019 06:22:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=mukund.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id sQOXutdd-R3c for <dnsop@ietfa.amsl.com>; Thu, 29 Aug 2019 06:22:56 -0700 (PDT)
Received: from mail.akira.org (mail.akira.org [IPv6:2a01:4f8:13b:607::228]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 28EDD12008F for <dnsop@ietf.org>; Thu, 29 Aug 2019 06:22:55 -0700 (PDT)
Received: from jurassic.lan.banu.com (unknown [60.243.81.75]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature ECDSA (P-256) server-digest SHA256) (No client certificate requested) by mail.akira.org (Postfix) with ESMTPSA id 676B679000BD; Thu, 29 Aug 2019 13:22:52 +0000 (GMT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mukund.org; s=mail; t=1567084973; bh=zjfbVj1dumZTIzyx8vJDzUketYGAJFEXeWdYc9eyQEA=; h=Date:From:To:Subject:From; b=CDtloTxtASAW+xghiDUAn2V3RABo00WloETaTEHXF8wUOIclm6t5ngBHB/o8Edkzk 5jNJCF16ZsE815usTbUtjV2dxAFjxbQrkmzZWLuMMbFoyp7pY89wD0xO9I+daQ1YdH Q2yyBgWhUoB84Buxob8oF/rTmFf190y0TCf1W8pU=
Date: Thu, 29 Aug 2019 18:51:26 +0530
From: Mukund Sivaraman <muks@mukund.org>
To: dnsop@ietf.org
Message-ID: <20190829132126.GA2835@jurassic.lan.banu.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="gKMricLos+KVdGMg"
Content-Disposition: inline
User-Agent: Mutt/1.12.0 (2019-05-25)
Archived-At: <https://mailarchive.ietf.org/arch/msg/dnsop/q6wHvALjM6tsSS2t67CIrHDBQfA>
Subject: [DNSOP] Rough notes for an incremental zone digest
X-BeenThere: dnsop@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: IETF DNSOP WG mailing list <dnsop.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/dnsop>, <mailto:dnsop-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/dnsop/>
List-Post: <mailto:dnsop@ietf.org>
List-Help: <mailto:dnsop-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dnsop>, <mailto:dnsop-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 29 Aug 2019 13:22:58 -0000

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