  Merkle hash trees are the state-of-the-art method to protect the integrity of
storage systems. However, using a hash tree can severely degrade performance,
and prior works optimizing them have yet to yield a concrete understanding of
the scalability of certain designs in the context of large-scale cloud storage
systems. In this paper, we take a first-principles approach to analyzing hash
tree performance for storage by introducing a definition of an optimal hash
tree and a principled methodology for evaluating hash tree designs. We show
that state-of-the-art designs are not scalable; they incur up to 40.1X
slowdowns over an insecure baseline and deliver <50% of optimal performance
across various experiments. We then exploit the characteristics of optimal hash
trees to design Dynamic Hash Trees (DHTs), hash trees that can adapt to
workload patterns on-the-fly, delivering >95% of optimal read and write
performance and up to 4.2X speedups over the state-of-the art. Our novel
methodology and DHT design provides a new foundation in the search for
integrity mechanisms that can operate efficiently at scale.
