We introduce Walrus, a third approach to decentralized blob storage. It combines fast linerarly decodable erasure codes that can scale to 100s of storage nodes to get extremely high resilience at a low storage overhead; and leverages a modern blockchain, Sui for its control plane, from storage node life cycle management, to blob life cycle management, to economics and incentives, doing away with the need for a full custom blockchain protocol.
At the heart of Walrus, lies a new encoding protocol, called Red Stuff that uses a novel two-
dimensional (2D) encoding algorithm based on fountain codes . Unlike RS codes, fountain codes rely
primarily on XOR or other very fast operations over large data blobs, avoiding complex mathematical
operations. This simplicity allows for the encoding of large files in a single pass, resulting in significantly
faster processing. The 2D encoding of Red Stuff enables the recovery of lost slivers using bandwidth
proportional to the amount of lost data (O( |blob| ) in our case). Additionally, Red Stuff incorporates au- n
thenticated data structures to defend against malicious clients, ensuring that the data stored and retrieved remains consistent.
Walrus operates in epochs, each managed by a committee of storage nodes. All operations within an epoch can be sharded by blobid, enabling high scalability. The system facilitates blob writing by encoding data into primary and secondary slivers, generating Merkle commitments, and distributing these slivers across storage nodes. The read process involves collecting and verifying slivers, with both best-effort and incentivized pathways to address potential system failures. To ensure uninterrupted availability to both read and write blobs while handling the naturally occurring churn of a permissionless system, Walrus features an efficient committee reconfiguration protocol.
Another key innovation in Walrus is its approach to storage proofs, which are mechanisms to ver- ify that storage nodes are indeed storing the data they claim to hold. Walrus addresses the scalability challenge associated with these proofs by incentivizing all storage nodes to hold slivers of all stored files. This complete replication enables a novel storage attestation mechanism that challenges the storage node as a whole, rather than each file individually. Consequently, the cost of proving file storage scales log- arithmically with the number of stored files, as opposed to the current linear scaling in many existing systems.
Finally, we also introduce an economic model based on staking, with rewards and penalties to align incentives and enforce long-term commitments. The system includes a pricing mechanism for storage resources and write operations, complemented by a token governance model for parameter adjustments.
In summary, we make the following contributions:
• We define the problem of Asynchronous Complete Data-Sharing and propose the Red Stuff the first protocol to solve it efficiently even under Byzantine Faults
• WepresentWalrus,thefirstpermisionlessdecentralizedstorageprotocoldesignedforlowreplication cost and the ability to efficiently recover lost data due to faults or participant churn
• We extend Walrus with an economic model based on staking, with rewards and penalties to align incentives and enforce long-term commitments as well as propose the first asychronous challenge protocol that allows for efficient storage proofs
2 Models and Definitions
Walrus relies on the following assumptions.
Cryptographic assumptions. Throughout the paper, we use hash() to denote a collision resistant hash function. We also assume the existence of secure digital signatures and binding commitments.
