Authenticated LSM Trees with Minimal Trust

Yuzhe Tang, Kai Li, Ju Chen

Research output: Chapter in Book/Entry/PoemConference contribution


In the age of user-generated contents, the workloads imposed on information-security infrastructures become increasingly write intensive. However, existing security protocols, specifically authenticated data structures (ADSs), are historically designed based on update-in-place data structures and incur overhead when serving write-intensive workloads. In this work, we present LPAD (Log-structured Persistent Authenticated Directory), a new ADS protocol designed uniquely based on the log-structure merge trees (LSM trees) which recently gain popularity in the design of modern storage systems. On the write path, LPAD supports streaming, non-interactive updates with constant proof from trusted data owners. On the read path, LPAD supports point queries over the dynamic dataset with a polynomial proof. The key to enable this efficiency is a verifiable reorganization operation, called verifiable merge, in LPAD. Verifiable merge is secured by the execution in an enclave of trusted execution environments (TEE). To minimize the trusted computing base (TCB), LPAD places the code related to verifiable merge in enclave, and nothing else. Our implementation of LPAD on Google LevelDB codebase and on Intel SGX shows that the TCB is reduced by 20 times: The enclave size of LPAD is one thousand code lines out of more than twenty thousands code lines of a vanilla LevelDB. Under the YCSB workloads, LPAD improves the performance by an order of magnitude comparing with existing ADSs.

Original languageEnglish (US)
Title of host publicationSecurity and Privacy in Communication Networks - 15th EAI International Conference, SecureComm 2019, Proceedings
EditorsSongqing Chen, Kim-Kwang Raymond Choo, Xinwen Fu, Wenjing Lou, Aziz Mohaisen
Number of pages18
ISBN (Print)9783030372309
StatePublished - 2019
Event15th International Conference on Security and Privacy in Communication Networks, SecureComm 2019 - Orlando , United States
Duration: Oct 23 2019Oct 25 2019

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume305 LNICST
ISSN (Print)1867-8211


Conference15th International Conference on Security and Privacy in Communication Networks, SecureComm 2019
Country/TerritoryUnited States


  • Key-value stores
  • LSM trees
  • Query authentication
  • Storage security
  • TEE

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Authenticated LSM Trees with Minimal Trust'. Together they form a unique fingerprint.

Cite this