Red Stuff is the innovative technical core of the Walrus network, serving as a two-dimensional (2D) erasure coding protocol that balances storage efficiency with high security. While traditional systems use full replication (requiring 25x overhead for high security) or simple 1D erasure coding (which is expensive to repair), Red Stuff enables Walrus to achieve "twelve nines" of security with only a 4.5x replication factor.
The Mechanics of Red Stuff
Unlike standard encoding that splits a file into a simple list of pieces, Red Stuff organizes a blob into a matrix of symbols.
• 2D Matrix Structure: A blob is initially split into a grid of (f+1) rows and (2f+1) columns.
• Primary and Secondary Slivers: The system extends this grid with repair symbols in both dimensions. Each storage node is assigned a "primary sliver" (an extended row) and a "secondary sliver" (an extended column).
• Threshold Flexibility: The 2D approach allows for different reconstruction thresholds. For instance, nodes can use a low-threshold dimension to recover missing data during write flows, while a high-threshold dimension is utilized for the read path to ensure security in asynchronous networks.
• Self-Healing Recovery: Red Stuff's most significant advantage is its efficient recovery process. If a node loses its data, it can reconstruct its slivers using bandwidth proportional only to the lost data (O(∣blob∣/n)), whereas traditional systems require transmitting the entire blob (O(∣blob∣)) for every repair.
Walrus Proofs and Challenges
@Walrus 🦭/acc utilizes Red Stuff to implement the first asynchronous storage challenge protocol, which ensures nodes are actually storing the data they were assigned without assuming messages arrive within a fixed timeframe.
• Write Certificates and PoA: To prove data is available, a writer must collect 2f+1 signatures from nodes to form a Write Certificate. This is published on the Sui blockchain as a Point of Availability (PoA), creating an on-chain obligation for nodes to maintain that data.
• The Asynchronous Challenge Protocol: Near the end of an epoch, nodes engage in a challenge where they must exchange specific symbols and proof-of-inclusion against the blob's metadata.
• Byzantine Resistance: The math of Red Stuff prevents malicious nodes from "faking" storage. To pass a challenge for a symbol they don't have, a malicious node would need to reconstruct the primary sliver, which requires 2f+1 symbols. However, even if they collude with all other malicious nodes (f−1 others) and slow down some honest nodes (f nodes), they can only gather 2f−1 symbols, which is insufficient to pass the challenge.
• Fraud Proofs for Inconsistent Encoding: If a malicious writer uploads data that does not follow the correct Red Stuff encoding, storage nodes can generate a third-party verifiable proof of inconsistency. If f+1 nodes attest to this inconsistency on-chain, the blob is marked as invalid, allowing nodes to delete the faulty data.
• Probabilistic Relaxations: To save bandwidth, Walrus can use a lightweight challenge protocol. This uses a decentralized random coin to select only a subset of blobs for verification; if reads begin to fail, the system dynamically increases the number of challenges
