Abstract—Decentralized storage faces a fundamental trade-
off between replication overhead, recovery efficiency, and
security guarantees. Current approaches either rely on full
replication, incurring substantial storage costs, or employ
trivial erasure coding schemes that struggle with efficient
recovery, especially under high 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, our first contribution.
Red Stuff is a two-dimensional erasure coding protocol that
achieves high security with only 4.5x replication factor, while
providing self-healing of lost data. This means that recovery
is done without centralized coordination and requires band-
width proportional to the lost data. Finally, Red Stuff is the
first protocol to support storage challenges in asynchronous
networks, preventing adversaries from exploiting network
delays to pass verification without actually storing data.
This allows Red Stuff to be deployable in cryptoeconomic
systems that go beyond the classic honest-malicious setting.
However, Red Stuff on its own is not sufficient for
Walrus as it is designed with a static set of participants in
mind. To further support decentralization, we also introduce
a novel multi-stage epoch change protocol that efficiently
handles storage node churn while maintaining uninterrupted
availability during committee transitions. Our system in-
corporates authenticated data structures to defend against
malicious clients and ensures data consistency throughout
storage and retrieval processes.
Blockchains support decentralized computation through
the State Machine Replication (SMR) paradigm [1]. However,
they are practically limited to distributed applications that
require little data for operation. Since SMR requires all val-
idators to replicate data fully, it results in a large replication
factor ranging from 100 to 1000, depending on the number
of validators in each blockchain.
While full data replication is practically needed for com-
puting on state, it introduces substantial overhead when
applications only need to store and retrieve binary large
objects (blobs) not computed upon1
. Dedicated decentralized
storage [2] networks emerged to store blobs more efficiently.
