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 system. Even though recent state-of-the art systems use MAC based authentication to protect the actual data, they still use 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 architecture with software-centric implementations in mind, hence they use a lot of recursions and are often sequential in nature. The predominantly recursive and sequential nature of these traditional BMT algorithms make them largely unsuitable for use and challenging to implement in the modern heterogeneous computing platforms employing Field-Programmable Gate Array (FPGA) devices. 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. Deploying this new algorithm, we have designed a new BMT controller with a dataflow architecture and speculative buffers that allow multiple parallel authentication on-flight which was not possible with the conventional algorithms. This new MT subsystem enables up to 7x improvement in bandwidth while also exhibiting up to 4.5x reduction in latency over the baseline.