Merkle2: A Low-Latency Transparency Log System

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 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, 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 Merkle 2 are independent of update intervals and are (poly)logarithmic to the number of entries in the log. Merkle 2 not only has excellent asymptotics when compared to prior work, but is also efficient in practice. Our evaluation shows that Merkle 2 propagates updates in as little as 1 second and can support 100× more users than state-of-the-art transparency logs.