Paper 2021/453

Merkle^2: A Low-Latency Transparency Log System

Yuncong Hu, Kian Hooshmand, Harika Kalidhindi, Seung Jin Yang, and Raluca Ada Popa


Transparency logs are designed to help users audit untrusted servers. For example, Certificate Transparency (CT) enables users to detect when a compromised Certificate Authority (CA) has issued a fake certificate. Practical state-of-the-art transparency log systems, however, suffer from high monitoring costs when used for low-latency applications. To reduce monitoring costs, such systems often require users to wait an hour or more for their updates to take effect, inhibiting low-latency applications. We propose $\text{Merkle}^2$, a transparency log system that supports both efficient monitoring and low-latency updates. To achieve this goal, we construct a new multi-dimensional, authenticated data structure that nests two types of Merkle trees, hence the name of our system, $\text{Merkle}^2$. Using this data structure, we then design a transparency log system with efficient monitoring and lookup protocols that enables low-latency updates. In particular, all the operations in $\text{Merkle}^2$ are independent of update intervals and are (poly)logarithmic to the number of entries in the log. $\text{Merkle}^2$ not only has excellent asymptotics when compared to prior work, but is also efficient in practice. Our evaluation shows that $\text{Merkle}^2$ propagates updates in as little as 1 second and can support 100× more users than state-of-the-art transparency logs.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.IEEE S&P 2021
key managementtransparency logmerkle treeauthenticated data structure
Contact author(s)
yuncong_hu @ berkeley edu
2021-05-31: revised
2021-04-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuncong Hu and Kian Hooshmand and Harika Kalidhindi and Seung Jin Yang and Raluca Ada Popa},
      title = {Merkle^2: A Low-Latency Transparency Log System},
      howpublished = {Cryptology ePrint Archive, Paper 2021/453},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.