HMT: A Hardware-Centric Hybrid Bonsai Merkle Tree Algorithm for High-Performance Authentication

Merkle tree is a widely used tree structure for authentication of data/metadata in a secure computing system. Recent state-of-the art secure systems use a smaller-sized MT, namely Bonsai Merkle Tree (BMT) to protect the metadata such as encryption counters. Common BMT algorithms were designed for traditional Von Neumann architectures with a software-centric implementation in mind, hence they use a lot of recursions and are often sequential in nature. However, the modern heterogeneous computing platforms employing Field-Programmable Gate Array (FPGA) devices require concurrency-focused algorithms to fully utilize the versatility and parallel nature of such systems. Our goal for this work is to introduce HMT, a hardware-friendly BMT algorithm that enables the verification and update processes to function independently and provides the benefits of relaxed update while being comparable to eager update in terms of update complexity. The methodology of HMT contributes both novel algorithm revisions and innovative hardware techniques to implementing BMT. We introduce a hybrid BMT algorithm that is hardware-targeted, parallel and relaxes the update depending on BMT cache hit but makes the update conditions more flexible compared to lazy update to save additional write-backs. Deploying this new algorithm, we have designed a new BMT controller with a dataflow architecture, speculative buffers and parallel write-back engines that allows for multiple concurrent relaxed authentication. Our empirical performance measurements have demonstrated that HMT can achieve up to 7x improvement in bandwidth and 4.5x reduction in latency over baseline in subsystem level tests. In a real secure-memory system on a Xilinx U200 accelerator FPGA, HMT exhibits up to 14\% faster execution in standard benchmarks compared to state-of-the art BMT solution on FPGA.