Paper 2023/1358

The Locality of Memory Checking

Weijie Wang, Yale University
Yujie Lu, Yale University
Charalampos Papamanthou, Yale University
Fan Zhang, Yale University

Motivated by the extended deployment of authenticated data structures (e.g., Merkle Patricia Tries) for verifying massive amounts of data in blockchain systems, we begin a systematic study of the I/O efficiency of such systems. We first explore the fundamental limitations of memory checking, a previously-proposed abstraction for verifiable storage, in terms of its locality---a complexity measure that we introduce for the first time and is defined as the number of non-contiguous memory regions a checker must query to verifiably answer a read or a write query. Our central result is an $\Omega(\log n /\log \log n)$ lower bound for the locality of any memory checker. Then we turn our attention to (dense and sparse) Merkle trees, one of the most celebrated memory checkers, and provide stronger lower bounds for their locality. For example, we show that any dense Merkle tree layout will have average locality at least $\frac 13 \log n$. Furthermore, if we allow node duplication, we show that if any write operation has at most polylog complexity, then the read locality cannot be less than $\log n/\log \log n$. Our lower bounds help us construct two new locality-optimized authenticated data structures (DupTree and PrefixTree) which we implement and evaluate on random operations and real workloads, and which are shown to outperform traditional Merkle trees, especially as the number of leaves increases.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
Memory checkingfoundations of cryptography
Contact author(s)
weijie wang @ yale edu
yujie lu @ yale edu
charalampos papamanthou @ yale edu
f zhang @ yale edu
2023-09-13: approved
2023-09-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Weijie Wang and Yujie Lu and Charalampos Papamanthou and Fan Zhang},
      title = {The Locality of Memory Checking},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1358},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.