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 sub-systems 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 sub- systems (like registries, autonomous system owners, and BGP speakers/routers), that take advantage of OMT .