Paper 2016/1063

Authenticated LSM Trees with Minimal Trust

Yuzhe (Richard) Tang, Ju Chen, and Kai Li

Abstract

In the age of user-generated contents, the workloads imposed on information-security infrastructures become increasingly write-intensive. How- ever, 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-structured merge trees (LSM trees) which recently gained 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 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 compared with that of existing update-in-place ADSs.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. SecureComm 2019
Keywords
SGXTEEhash functionsauthentication codes
Contact author(s)
ytang100 @ syr edu
History
2019-08-13: last of 5 revisions
2016-11-15: received
See all versions
Short URL
https://ia.cr/2016/1063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1063,
      author = {Yuzhe (Richard) Tang and Ju Chen and Kai Li},
      title = {Authenticated LSM Trees with Minimal Trust},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1063},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1063}},
      url = {https://eprint.iacr.org/2016/1063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.