  Authenticated data storage on an untrusted platform is an important computing
paradigm for cloud applications ranging from big-data outsourcing, to
cryptocurrency and certificate transparency log. These modern applications
increasingly feature update-intensive workloads, whereas existing authenticated
data structures (ADSs) designed with in-place updates are inefficient to handle
such workloads. In this paper, we address this issue and propose a novel
authenticated log-structured merge tree (eLSM) based key-value store by
leveraging Intel SGX enclaves.
  We present a system design that runs the code of eLSM store inside enclave.
To circumvent the limited enclave memory (128 MB with the latest Intel CPUs),
we propose to place the memory buffer of the eLSM store outside the enclave and
protect the buffer using a new authenticated data structure by digesting
individual LSM-tree levels. We design protocols to support query authentication
in data integrity, completeness (under range queries), and freshness. The proof
in our protocol is made small by including only the Merkle proofs at selective
levels.
  We implement eLSM on top of Google LevelDB and Facebook RocksDB with minimal
code change and performance interference. We evaluate the performance of eLSM
under the YCSB workload benchmark and show a performance advantage of up to
4.5X speedup.
