Paper accepted to Workshop on Verifiable Database Systems @ SIGMOD 2023
Towards Merkle Trees for High-Performance Data Systems
Muhammad El-Hindi, Tobias Ziegler and Carsten Binnig will show how it is possible to build high-performance Merkle trees with orders of magnitude performance improvements.
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.