[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
- [DNSOP] Rough notes for an incremental zone digest Mukund Sivaraman
- Re: [DNSOP] Rough notes for an incremental zone d… Wessels, Duane