Fast Integrity Checking for Secure Cloud Storage: A Quantitative Approach

Merkle hash trees are the standard method to protect the integrity and freshness of stored data. However, hash trees introduce additional compute and I/O costs on the I/O critical path, and prior efforts have not fully characterized these costs. In this paper, we quantify performance overheads of storage-level hash trees in realistic settings. We identify that hashing (CPU) costs are the primary performance bottleneck, and develop an analytical model demonstrating why this occurs. We then design an optimized tree structure called Dynamic Merkle Trees (DMTs) that exploits patterns in workloads to reduce tree traversal costs. We implement DMTs in a block device driver and a file system and through extensive evaluation show that DMTs can exploit patterns in workloads to deliver up to a 2.2 × throughput and latency improvement over the state of the art. Our novel approach provides a promising new direction to achieve integrity guarantees in storage efficiently and at scale.