How to build a trusted database system on untrusted storage

TLDR

Emerging applications require storing sensitive state on untrusted hosts. The paper proposes TDB, a trusted database system that uses a small trusted storage area to secure large amounts of untrusted storage. TDB encrypts data and stores a collision‑resistant hash in trusted storage, employing a low‑level data model and log‑structured storage to uniformly protect data and metadata. Preliminary results show TDB outperforms a standard embedded database, confirming the architecture’s viability.

Abstract

Some emerging applications require programs to maintain sensitive state on untrusted hosts. This paper presents the architecture and implementation of a trusted database system, TDB, which leverages a small amount of trusted storage to protect a scalable amount of untrusted storage. The database is encrypted and validated against a collision-resistant hash kept in trusted storage, so untrusted programs cannot read the database or modify it undetectably. TDB integrates encryption and hashing with a low-level data model, which protects data and metadata uniformly, unlike systems built on top of a conventional database system. The implementation exploits synergies between hashing and log-structured storage. Preliminary performance results show that TDB outperforms an off-the-shelf embedded database system, thus supporting the suitability of the TDB architecture.