Paper 2025/1082 Original: eprint.iacr.org/2025/1082 ↗
Treebeard: A Scalable and Fault Tolerant ORAM Datastore
Abstract
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
- Preprint.
- History
- 2025-06-09: last updated
- 2025-06-09: published
- Short URL
- https://ia.cr/2025/1082
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}