Ordered Merkle Tree: A Dynamic Authenticated Data Structure for Security Kernels

Abstract

We introduce a family of authenticated data structures — Ordered Merkle Trees (OMT) —and illustrate their utility in security kernels for a wide variety of sub-systems. Specifically the utility of two types of OMTs: a) the index ordered merkle tree (IOMT) and b) the range ordered merkle tree (ROMT), are investigated for their suitability in security kernels for various subsystems of Border Gateway Protocol (BGP), the Internet’s inter-autonomous system routing infrastructure. We outline simple generic security kernel functions to maintain OMTs, and sub-system specific security kernel functionality for BGP subsystems (like registries, autonomous system owners, and BGP speakers/routers), that take advantage of OMTs.