Treebeard: A Scalable and Fault Tolerant ORAM Datastore
summary
Treebeard presents a horizontally scalable ORAM datastore with a three‑layer proxy: a stateless router that epoch‑batches and deterministically maps requests, a replicated stash/position‑map layer using Raft replication, and an ORAM layer that implements multipath reads plus parameterized multipath eviction (eviction rate A and path count K). Evaluation shows linear scaling to 160K ops/sec on 16 machines, close‑to‑zero recovery downtime, a manageable stash size under multipath eviction, and 13.8x the throughput of QuORAM.
AI-written summary · about
chapters (15)
- 0:00Treebeard and ORAM challenges
- 2:26Limitations of current ORAM
- 3:47Parallelism vs security vs scalability
- 5:17ORAM scalability and security
- 6:21Fault tolerance vs security trade-offs
- 7:26Treebeard architecture
- 8:32Handling read operations
- 10:40Stash layer and position map
- 11:22Multipath reads for ORAM
- 12:05Multipath eviction
- 12:29Treebeard scalability evaluation
- 13:13Scaling each layer impact
- 13:35Fault tolerance vs Corm
- 13:58Stash size management
- 14:41Summary and future work
related talks
35mSystems @Scale Summer Q&A Week 3
52mThe Computer Science behind a modern distributed data store
01h 11mFearless global transactions with
42mApache Ozone - State of the Union
14mSMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory
23mOblivP2P: An Oblivious Peer-to-Peer Content Sharing System
23mBodega: Localized Linearizable Reads at Anywhere Anytime via Roster Leases
43mRa: a Raft implementation