In recent years, interest in data storage solutions in the Web3 world has increased, and Walrus Finance (WAL) stands out as one of the projects offering a decentralized approach to this need. Specifically providing solutions for securely storing large volumes of files on the blockchain, Walrus positions itself not only as a data storage tool but also as an economic protocol empowered by tokenomic incentives. Built on the Sui blockchain, the project aims to build a scalable and sustainable infrastructure by integrating off-chain data management with on-chain verification processes.
One unique feature of Red Stuff is its ability to work in an asychronous network while supporting storage challenges, making it the first of its kind. This is only possible thanks to the two-dimensional encoding that allows for different encoding thresholds per dimension. The low-threshold di- mension can be used from nodes that did not get the symbols during the write flow to recover what they missed, whereas the high-threshold dimension can be used for the read flow to prevent the adversary from slowing down honest nodes during challenge periods and collecting sufficient information to reply to challenges.
One final challenge for Walrus, and in general, any encoding-based decentralized storage system is operating se- curely across epochs each managed by a different committee of storage nodes. This is challenging because we want to ensure uninterrupted availability to both read and write blobs during the naturally occurring churn of a permissionless system, but if we keep writing data in the nodes about to depart, they keep needing to transfer them to the nodes that are replacing them. This creates a race for the resources of those nodes, which will either stop accepting writes or fail to ever transfer responsibility. Walrus deals with this through its novel multi-stage epoch change protocol that naturally fits the principles of decentralized storage systems.
Red Stuff
The encoding protocol above achieves the objective of a low overhead factor with very high assurance, but is still not suitable for a long-lasting deployment. The main challenge is that in a long-running large-scale system, storage nodes routinely experience faults, lose their slivers, and have to be replaced. Additionally, in a permissionless system, there is
5There may be an extra O(logn) cost depending on the commitment scheme.
S11
S21
S31
S41
some natural churn of storage nodes even when they are well incentivized to participate.
Both of these cases would result in enormous amounts of data being transferred over the network, equal to the total size of data being stored in order to recover the slivers for new storage nodes. This is prohibitively expensive. We would instead want the system to be self-healing such that the cost of recovery under churn is proportional only to the data that needs to be recovered, and scale inversely with n.
To achieve this, Red Stuff encodes blobs in two dimen- sions (2D-encoding). The primary dimension is equivalent to the RS-encoding used in prior systems. However, in order to allow efficient recovery of slivers of B we also encode on a secondary dimension. Red Stuff is based on linear erasure coding (see section II) and the Twin-code framework, which provides erasure coded storage with efficient recovery in a crash-tolerant setting with trusted writers. We adapt this framework to make it suitable in the byzantine fault tolerant setting with a single set of storage nodes, and we add additional optimizations that we describe further below.
Encoding: Our starting point is the second strawman design that splits the blobs into f +1 slivers. Instead of simply encoding repair slivers, we first add one more dimension to the splitting process: the original blob is split into f + 1 primary slivers (vertical in the figure) into 2f + 1 secondary slivers (horizontal in the figure). Figure 2 illustrates this process. As a result, the file is now split into (f + 1)(2f + 1) symbols that can be visualized in an [f + 1, 2f + 1] matrix.
