PaperlayerView exact revision on arXiv

Source-linked AI summary

Walrus: An Efficient Decentralized Storage Network

George Danezis, Giacomo Giuliari, Eleftherios Kokoris Kogias, Markus Legner, Jean-Pierre Smith, Alberto Sonnino, Karl Wüst

arXiv:2505.05370v4cs.DCcs.CR

TL;DR

Decentralized storage must reduce replication and recovery costs without sacrificing security or availability under churn. Walrus combines Red Stuff’s two-dimensional erasure coding with authenticated structures and epoch reconfiguration to address these constraints. The deployed system uses low storage overhead, supports recovery and committee transitions, and has secured 686 TB of data in production.

  • Problem

    Existing decentralized storage approaches trade high replication overhead against inefficient erasure-coded recovery, especially when storage nodes churn.

  • Method

    Walrus combines the Red Stuff two-dimensional encoding protocol with authenticated data structures and a committee reconfiguration protocol for epoch changes.

  • Results

    686 TB of unencoded data had been registered in production since launch, with 477 TB still active.

  • Takeaways & Limitations

    Walrus provides a production-grade decentralized storage system designed for low replication cost, efficient recovery, and uninterrupted availability during committee transitions.

  • Takeaways & Limitations

    Encode-and-share recovery can cost O(n|B|), and malicious clients may upload inconsistent slivers that are not guaranteed to be recoverable.

Abstract

from arXiv · show

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 erasure-coding schemes that struggle with efficient recovery, especially under high churn. We present Walrus, a 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 a 4.5x replication factor, while providing self-healing of lost data. This means that recovery is done without centralized coordination and requires bandwidth proportional to the amount of lost data. 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 multi-stage epoch-change protocol that efficiently handles storage node churn while maintaining uninterrupted availability during committee transitions. Our system incorporates authenticated data structures to defend against malicious clients and ensure data consistency throughout storage and retrieval. Walrus has been deployed in production since March 2025 and has secured 686 TB of data by July 2026. We conduct an experimental evaluation of the deployed system and demonstrate that Walrus achieves practical performance at scale and outperforms the Arweave decentralized storage system.

1 Introduction

Decentralized storage must balance replication cost, recovery efficiency, and security under node failures and churn. Walrus addresses these tensions with Red Stuff, authenticated data structures, and epoch-aware operation.

  • Replication-based storage provides easy access and migration but can require more than 25 copies for twelve-nines durability, creating 25× storage overhead.
  • Erasure coding lowers storage overhead by splitting blobs into slivers, but recovery can require O(|blob|) network transmission and thus assumes low churn.
  • Walrus uses Red Stuff, a self-healing two-dimensional encoding protocol that recovers lost slivers with bandwidth proportional to lost data and authenticates slivers against malicious clients.
  • Walrus must also handle epoch transitions because continued writes to departing nodes can race with sliver transfer to incoming nodes, threatening uninterrupted operation.
  • The paper defines Asynchronous Complete Data Storage, presents Walrus for permissionless low-cost recovery, and reports a production-grade implementation deployed on testnet and mainnet.

2 Models and Definitions

The paper models epochs of storage committees with Byzantine faults and asynchronous communication, then defines the encoding and blockchain abstractions used by Walrus. Its ACDS construction assumes a linear, optionally systematic erasure code.

  • Each epoch has n = 3f + 1 storage nodes, with up to f Byzantine nodes that may deviate arbitrarily.
  • The network is asynchronous: honest messages may be delayed or reordered but are eventually delivered unless the epoch ends.
  • ACDS uses a linear erasure code that produces n symbols from t source symbols, allowing any t correctly encoded symbols to reconstruct the blob.
  • Walrus treats an external blockchain as a black box for control operations, assuming it orders updates and does not indefinitely censor transactions.

3 Asynchronous Complete Data Storage (ACDS)

This section formalizes Complete Data Storage and its asynchronous extension, then introduces Red Stuff as a solution. The framework requires reliable writing, consistent reading, and valid retrieval despite Byzantine behavior.

  • The paper defines ACDS and presents Red Stuff as its asynchronous solution before establishing the protocol’s correctness and complexity.
  • Complete Data Storage guarantees that honest writers eventually distribute recoverable parts, honest readers agree on success or failure, and valid blobs remain readable.
  • The formal model uses n = 3f + 1 nodes and permits up to f malicious participants.
  • ACDS is defined as a Complete Data Storage protocol secure in asynchronous networks.
  • The section introduces two strawman designs to expose inefficiencies that the proposed protocol must overcome.

Strawman I: Replication.

The strawman protocols illustrate the central cost trade-off: full replication simplifies recovery but scales poorly, while encode-and-share reduces dissemination cost yet makes recovery and complete dispersal expensive.

  • Strawman I: Replication.: Replication sends the blob to all nodes and waits for f + 1 acknowledgments forming an availability certificate.
  • Strawman I: Replication.: Full replication requires O(n|B|) network transmission and storage, with asynchronous recovery potentially reaching O(n^2|B|) total cost.
  • Strawman II: Encode & Share.: Encode-and-share splits B into f + 1 slivers plus 2f repair slivers, allowing any f + 1 slivers to reconstruct the blob.
  • Strawman II: Encode & Share.: Readers collect f + 1 valid slivers, reconstruct B, and recompute the commitment to verify consistency.
  • Strawman II: Encode & Share.: Recovered nodes retain only their encoded sliver, but each recovery still costs O(|B|) despite the eventual O(|B|/n) storage cost.
  • Strawman II: Encode & Share.: Although dissemination costs O(|B|), complete dispersal costs O(n|B|) because missing slivers require downloading the entire blob, including during epoch changes.

3.3 Final Design: Red Stuff

Red Stuff extends erasure coding with a two-dimensional encoding scheme designed for self-healing recovery in long-running decentralized storage. It combines primary and secondary slivers with authenticated commitments to support efficient recovery and Byzantine fault tolerance.

  • 3.3 Final Design: Red Stuff: Red Stuff adds a secondary encoding dimension so lost slivers can be recovered efficiently rather than requiring full-blob transfers.The design targets recovery costs proportional to lost data and inversely scaling with the number of nodes.
  • 3.3 Final Design: Red Stuff: Red Stuff adapts linear erasure coding and the Twin-code framework to a Byzantine fault-tolerant setting with a single storage-node set.The primary dimension follows prior Reed-Solomon-style encoding, while the secondary dimension enables efficient sliver recovery.
  • 3.3 Final Design: Red Stuff: The blob is split into f+1 primary and 2f+1 secondary slivers, then extended with repair symbols across both dimensions.The resulting symbols form an [f+1, 2f+1] matrix with n encoded rows and n encoded columns assigned to nodes.
  • 3.3 Final Design: Red Stuff: Vector commitments cover each extended sliver and the metadata, allowing nodes to prove that returned symbols match the originally written data.A vector commitment to the metadata forms the blob commitment used by the protocol.

Write Protocol.

Red Stuff’s write protocol distributes a committed primary-secondary sliver pair to each node and forms an availability certificate from signed acknowledgments. Its read protocol reconstructs metadata and the blob only from commitment-verified responses.

  • Write Protocol: The writer creates n=3f+1 sliver pairs and sends each node its pair together with the metadata containing sliver commitments.Nodes verify their pairs, recompute the blob commitment, and sign acknowledgments when checks pass.
  • Write Protocol: The production deployment stores metadata fully on every node, although an optimization reduces metadata overhead from quadratic to linear system-wide overhead.The optimized approach stores only a constant amount per node, whereas production currently forgoes it.
  • Write Protocol: Collecting 2f+1 signatures lets the writer stop retransmissions while ensuring at least f+1 correct nodes hold a sliver pair.This bounds the required delivery acknowledgment without waiting for every node.
  • Write Protocol: Readers select the vector commitment agreed upon by honest replies, discard openings that fail verification, and decode only after collecting f+1 correct primary slivers.The reader re-encodes the result and checks the recomputed metadata before returning the blob.

Sliver Healing.

Red Stuff self-heals slivers through cross-dimensional symbol recovery, allowing honest nodes to reconstruct missing secondary slivers without centralized coordination. The resulting recovery cost is comparable to ordinary reads and writes, but requires higher storage overhead than classic BFT erasure coding.

  • Sliver Healing: Any node can recover its secondary sliver by requesting f+1 nodes for row symbols that correspond to its encoded column.This process eventually gives all 2f+1 honest nodes their secondary slivers.
  • Sliver Healing: O(|B|/n) communication per recovering node and O(|B|) total recovery cost make Red Stuff’s protocol communication complexity almost independent of n.The total recovery cost is equivalent to the cost of a read and a write.
  • Sliver Healing: The recovery guarantees rely on honest nodes eventually holding correct sliver pairs or proving that the encoding was incorrect.The protocol’s stated properties include write completeness, validity, and read consistency.
  • Sliver Healing: Red Stuff raises storage overhead from 3× to 4.5× because the extra information enables single-sliver recovery in O(|B|/n) instead of O(|B|).Storing only sufficient primary and secondary symbols avoids the naive 9× amplification, trading CPU for storage.

4 Walrus: A Decentralized Blob Store

Walrus combines Red Stuff, authenticated metadata, and blockchain coordination to provide decentralized blob storage with efficient recovery, secure reads, and seamless committee reconfiguration.

  • System architecture: Walrus integrates Red Stuff with a blockchain control plane for metadata, governance, and blob read/write operations.Its implementation uses Reed-Solomon codes, Merkle trees, and Sui, although these components are not fundamental to the design.
  • Blob writes: A Walrus write reserves blockchain storage, distributes committed sliver pairs, collects 2f+1 signed acknowledgments, and records an on-chain availability certificate.After the certificate is published, the writer may delete its local copy and go offline.
  • Consistency and faults: Client-side re-encoding and metadata verification ensures honest readers either obtain the same blob or reject it as inconsistent.This consistency check follows directly from Red Stuff’s guarantees.
  • Security model: The deployment fixes 1000 shards as the security unit, with n=3f+1 and an adversary limited to at most one-third of the shards.Shard assignment changes with delegated stake without requiring re-encoding as committees grow.
  • Committee reconfiguration: Walrus handles committee churn by directing writes to the incoming committee while reads continue from the outgoing committee, avoiding downtime during reconfiguration.Red Stuff also keeps faulty-node migration bandwidth from scaling to the full file size, while reconfiguration preserves availability across epochs.

5 Detailed Algorithms

Walrus’s algorithms encode blobs into two-dimensional primary and secondary slivers, authenticate their metadata, and coordinate storage, retrieval, and recovery through threshold operations.

  • Encoding: EncodeBlob reshapes data into an (f+1) × (2f+1) matrix, extends columns and rows to n symbols, and assigns one primary and one secondary sliver to each node.The resulting two-dimensional layout supports the protocol’s recovery procedures.
  • Commitments and identifiers: Walrus authenticates slivers and metadata with Merkle trees, then derives the blob ID by hashing the commitments together with the blob size.Metadata is erasure-encoded into n shares with Merkle openings for verification.
  • Supporting procedures: The algorithmic interface includes erasure encoding and decoding, authenticated opening verification, symbol requests, inconsistency proofs, and blockchain certificate operations.These helpers connect data-plane recovery with on-chain registration and availability state.
  • Client operations: StoreBlob encodes the blob, creates metadata, reserves space on-chain, sends each node its assigned slivers and proofs, and stores a certificate after 2f+1 signed acknowledgments.The client also retrieves metadata and reads after an availability certificate exists.

6 Red Stuff Proofs

The Red Stuff proofs establish write completeness, read consistency, and validity under the protocol’s threshold-based reconstruction and authenticated verification rules.

  • Operational enforcement: The client and storage-node procedures verify slivers against commitments, require on-chain certification for serving data, and produce inconsistency proofs when recovery fails.These operations connect the formal guarantees to the deployed storage workflow.
  • Reconstruction lemmas: A primary sliver reconstructs from 2f+1 symbols, whereas a secondary sliver reconstructs from f+1 symbols.These thresholds follow from the respective erasure-code reconstruction parameters.
  • Formal guarantees: Red Stuff’s formal results prove Write Completeness, Read Consistency, and Validity for correctly encoded blobs.The proofs assume binding vector commitments and use deterministic re-encoding to validate reconstructed data.
  • Write completeness: Nodes outside the initial recipients recover secondary slivers from shared symbols, then obtain enough primary symbols to reconstruct their primary slivers.This mechanism eventually gives all honest nodes both sliver types under a binding commitment.
  • Read consistency: Read consistency follows because deterministic re-encoding and commitment recomputation prevent two honest readers from accepting different outcomes for the same blob.A reader that detects a mismatch or receives an inconsistency proof returns ⊥, and the same inconsistency must be detectable by other honest readers.

7 Evaluation

Walrus was evaluated on public deployments under realistic operating conditions, showing low latency, high client throughput, and continued availability during shard reassignment and recovery.

  • Deployment: 686 TB of unencoded data across 17.6 million blobs had been registered by 9,675 wallets since the March 2025 public launch.The system recorded a peak daily certification rate of approximately 10 blobs per second and 1.95 Gbps average goodput on its largest certification day.
  • Walrus Latency: Walrus read blobs up to 135 MB in under 5 seconds and wrote blobs of the same size in under 20 seconds, outperforming Arweave’s roughly 25-second reads and over-30-minute writes.For blobs smaller than 20 MB, Walrus writes were consistently around 10 seconds.
  • Walrus Latency: Walrus’s data-upload latency grew linearly from around 8 MiB upward after constant-sized metadata overhead dominated small uploads, supporting latency bounded by network delays.The evaluation used public deployments exposed to real users and infrastructure outside the authors’ control.
  • Client Throughput: A single client reached around 400 MB/s read throughput and 62 MB/s write throughput on Walrus, compared with Arweave’s roughly 7 MB/s read throughput.Arweave write throughput was omitted because its client communicates through a central gateway and could not be measured reliably.
  • 7.4 Epoch-Change Overhead: Shard reassignments were frequent but mostly small, with twelve of 36 epochs moving at least five shards and the largest reassignment moving 27 shards.At epoch 9, transferring four shards involved 636 GB of metadata and 890 GB of slivers; later failures required sequential recovery lasting 16 to 21 hours per shard.
  • 7.4 Epoch-Change Overhead: Walrus remained available for storing and reading data while recovering shards after complete node failures, validating uninterrupted epoch changes.At least two recovery cases involved nodes that were no longer online to hand over their slivers.

8 Related Work

Related decentralized storage systems trade replication cost, recovery behavior, and operational flexibility in different ways. Walrus uses erasure coding and Red Stuff to reduce overhead while supporting efficient healing and permissionless churn.

  • Replication-Based Systems: Replication-based systems such as IPFS, Filecoin, and Arweave provide complete copies for access and migration but incur substantial storage overhead and depend on selected nodes.Replication can also expose systems to Sybil attacks that make purported copies unreliable.
  • Comparison with Existing Systems: Walrus maintains a 4.5× overhead, survives loss of up to two-thirds of shards, and continues accepting writes with up to one-third of shards unresponsive.Unlike Filecoin and Arweave, Walrus uses erasure coding and relies on Sui rather than a separate blockchain for node management.
  • Erasure-Coded Systems: Storj achieves a 2.75× replication factor with Reed-Solomon coding but relies on users to reconstruct and re-encode the full file when parts are lost.Walrus instead uses Red Stuff to provide efficient reconstruction, which the paper identifies as important under permissionless churn.
  • Erasure-Coded Systems: Red Stuff differs from Twin-code by encoding across differently sized dimensions and integrating authenticated data structures for Write Completeness and Byzantine fault tolerance.These properties distinguish Walrus’s recovery and integrity design from related two-encoding approaches.
  • Related Availability Protocols: Semi-AVID can provide verifiable data storage but cannot achieve Write Completeness without reconstructing the full data, making it costly for epoch changes and unsuitable for systems with churn.The paper positions it as appropriate mainly for permissioned systems without churn or short-lived data storage.

9 Conclusion

Walrus combines two-dimensional BFT erasure coding with blockchain-based storage to provide resilience, efficient recovery, scalability, and dynamic node availability. Its committee reconfiguration protocol maintains uninterrupted data availability as the network evolves.

  • Walrus combines fast erasure codes with modern blockchain technology to achieve resilience, low storage overhead, efficient data management, and scalability.Operations are organized in epochs and sharded by identifier to handle large data volumes.
  • Red Stuff uses two-dimensional BFT encoding to support efficient data recovery, load balancing, and dynamic storage-node availability.
  • Walrus provides committee reconfiguration that guarantees uninterrupted data availability during network evolution.The system includes a production-grade end-to-end design and implementation.
Loading 2505.05370v4…