Decentralized storage systems face a fundamental trade-off between
replication overhead, recovery efficiency, and security guarantees.
Current approaches either rely on full replication, incurring sub-
stantial storage costs, or employ trivial erasure coding schemes
that struggle with efficient recovery especially under high storage-
node churn. We present Walrus, a novel decentralized blob storage
system that addresses these limitations through multiple technical
innovations.

At the core of Walrus is Red Stuff, a two-dimensional erasure
coding protocol that achieves high security with only 4.5x repli-
cation factor, while enabling self-healing recovery that requires
bandwidth proportional to only the lost data (𝑂 (|𝑏𝑙𝑜𝑏|/𝑛) versus
𝑂 (|𝑏𝑙𝑜𝑏|) in traditional systems). Crucially, Red Stuff is the first
protocol to support storage challenges in asynchronous networks,
preventing adversaries from exploiting network delays to pass ver-
ification without actually storing data.

Walrus also introduces a novel multi-stage epoch change proto-
col that efficiently handles storage node churn while maintaining
uninterrupted availability during committee transitions. Our sys-
tem incorporates authenticated data structures to defend against
malicious clients and ensures data consistency throughout stor-
age and retrieval processes.