Paper 2025/1082
Treebeard: A Scalable and Fault Tolerant ORAM Datastore
, University of Waterloo, University of Waterloo, University of Waterloo, University of WaterlooAbstract
We present Treebeard - the first scalable and fault tolerant Oblivious RAM (ORAM) based datastore designed to protect applications from access pattern attacks. Current ORAM systems face challenges in practical adoption due to their limited ability to handle concurrent workloads, scale effectively, and ensure fault tolerance. We address all three limitations in Treebeard by utilizing a multi-layer architecture that scales horizontally, handling thousands of requests in parallel, while replicating the data to prevent data loss upon failures. Experimental evaluation demonstrates Treebeard's ability to scale linearly, achieving a throughput of 160K ops/sec with 16 machines; this behavior is similar to the enclave-based state-of-the-art, Snoopy. Being fault-tolerant, Treebeard recovers from failures with close to zero downtime and achieves 13.8x the throughput of QuORAM, the latest fault tolerant ORAM system, even without scaling.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. USENIX SECURITY
- Keywords
- Oblivious RAM (ORAM)Scalable DatastoreFault ToleranceAccess PatternsPrivacy
- Contact author(s)
-
asetayes @ uwaterloo ca
cmahalingam @ uwaterloo ca
e94chen @ uwaterloo ca
smaiyya @ uwaterloo ca - History
- 2025-06-10: approved
- 2025-06-09: received
- See all versions
- Short URL
- https://ia.cr/2025/1082
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1082,
author = {Amin Setayesh and Cheran Mahalingam and Emily Chen and Sujaya Maiyya},
title = {Treebeard: A Scalable and Fault Tolerant {ORAM} Datastore},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1082},
year = {2025},
url = {https://eprint.iacr.org/2025/1082}
}
