Paper accepted to Workshop on Verifiable Database Systems @ SIGMOD 2023

Merkle trees (and its variants) are widely used for building secure outsourced data systems. The adoption of Merkle trees for high-performance data systems, however, uncovered major performance challenges.

First and unlike classical data structures, Merkle trees involve expensive cryptographic operations and are thus CPU-bound.

Second, they are not well suited for modern multi-core CPUs because they introduce a single point of contention making Merkle trees hard to parallelize. While recent work aimed at replacing Merkle trees to circumvent their performance problem, we suggest new techniques to speed-up this ubiquitous data structure and achieve high-performance.

In this paper, we present initial results showing that in contrast to common wisdom it is indeed possible to build high-performance Merkle trees with orders of magnitude performance improvements.