Cryptology ePrint Archive: Report 2021/453

Merkle^2: A Low-Latency Transparency Log System

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

Abstract: 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.

Category / Keywords: cryptographic protocols / key management; transparency log; merkle tree; authenticated data structure

Original Publication (with minor differences): IEEE S&P 2021

Date: received 6 Apr 2021, last revised 30 May 2021

Contact author: yuncong_hu at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20210531:054243 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]