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

Bonsai Merkle tree (BMT) is a widely used data structure for authenticating data/metadata in a secure computing system. However, the predominantly recursive andsequential nature of traditional BMT algorithms make them challenging to implement with Field-Programmable Gate Array (FPGA) in modern heterogeneous computing platforms. In this work, we introduce HMT, a hardware-friendly implementation methodology for BMT that enables the verification and update processes to function independently, as well as saves additional write-backs by making the update conditions more flexible compared to previous algorithms. The methodology of HMT contributes both novel algorithm revisions and innovative hardware techniques to implementing BMT. Our empirical performance measurements have demonstrated that HMT can achieve up to 7x improvement in bandwidth and 4.5x reduction in latency over the baseline.