World Wide Walrus: The Next Gen Data Storage Protocol

Key Takeaways

• Sui has achieved sustainable data storage through an incentive system called storage fund. However, it is inefficient for all Sui nodes to store large volumes of blob data, including media files.
  

• Walrus, a decentralized storage protocol, can efficiently store blob data by utilizing an erasure coding method called Red Stuff. Walrus leverages the Sui network for necessary features such as incentive systems and node coordination.

  
  

• Red Stuff uses two-dimensional encoding, which makes data recovery more cost-effective compared to full replication methods or those using RS encoding. This is particularly advantageous in environments where nodes can freely join and leave, or where the node set changes continuously with each epoch.
  

• A notable use case for Walrus is the Web3 media company Decrypt, which plans to upload its content to Walrus. Additionally, Walrus Sites allows for building decentralized frontends using Walrus and Sui.
  

• Mysten Labs continues to innovate at both consumer and infrastructure levels with developments like zkLogin and Mysticeti. Walrus is another such innovation, enabling a wider range of applications in the Sui ecosystem by handling large-scale data storage off-chain, which would be challenging for Sui to manage on its own.

1. Sui’s Storage Fund

1.1 Decentralized Ledger

What is blockchain? Given that blockchain is the product of various disciplines such as cryptography, philosophy, economics, and computer science, each person's perception of blockchain may vary. In this context, while blockchain offers numerous advantages over existing systems, such as transparency, security, and decentralization, these ultimately stem from one key characteristic: the 'distributed ledger.’

In simple terms, a blockchain is a distributed ledger maintained by multiple servers. These servers share and manage the same transaction history through consensus algorithms. The fact that everyone possesses the same ledger gives rise to blockchain's various advantages, making the distributed ledger the core of blockchain technology.

However, managing a distributed ledger is far more challenging compared to a centralized server. Achieving scalability is difficult due to the process of reaching consensus while communicating with nodes worldwide. Moreover, storing all historical records on every node rather than a single server is highly inefficient from a hardware perspective.

For instance, as of October 2024, the total size of the Bitcoin blockchain is approximately 600GB, while Ethereum's archive node size is about 19.5TB, and its full node size is around 1,100GB. If networks prioritizing decentralization over scalability have reached this scale, we can anticipate that networks focused on scalability will grow even more rapidly (for example, the Sei Network, one of the faster blockchains, has already recognized the storage issue and is optimizing its database model).

1.2 Problem Statement

Although the size of distributed ledgers may increase rapidly, it doesn't pose a significant problem in the early stages of a network. However, if this situation persists, when the distributed ledger size becomes extremely large in the future, the entry barrier for new nodes joining the network will become very high, potentially leading to increased transaction fees for future users. Thus, the incentive systems of most existing blockchains focus solely on computation rather than storage. While various technical discussions (EIP-4444, Verkle Trie, etc.) are taking place to reduce the storage burden on nodes, there have been few attempts to address the storage problem from an incentive system perspective.

1.3 Sui’s Unique Onchain Data Storage

In this respect, Sui can be considered a very interesting project, as it's a layer-1 blockchain that has strived to solve storage issues through incentives from its inception. Sui aims to achieve sustainable data storage through an economic mechanism called the Storage Fund, which operates as follows: The fees users submit to Sui validators are divided into 1) gas fees related to computation and 2) storage costs for data retention. Sui collects storage costs upfront from users for permanent data storage and pools this into the Storage Fund. The Storage Fund continuously redistributes the accumulated amount to validators while the data remains stored on-chain. Moreover, users can receive a refund of the corresponding storage costs if they delete their data.

Sui's unique on-chain data storage system produces two effects:

1. Since users can receive a storage cost rebate when deleting on-chain data, it can incentivize reducing the distributed ledger's capacity through economic incentives.

2. The unique incentive structure of collecting storage fees upfront and allocating them as incentives for future validators can address sustainability issues related to storage.

1.4 What About... Blob?

While Sui's Storage Fund is a powerful tool, it's not an efficient method for all types of data. This is because on-chain data includes both small-volume essential data for state calculations, such as transaction data, and enormous data like blobs that include media files.

Blockchain transaction data is small in volume and essential for calculating the state of the distributed ledger, so all nodes participating in the network must replicate and store it. However, for large-volume, supplementary blob data such as images, videos, and music, it's highly inefficient for all nodes to replicate and store them. Therefore, to handle such data as well, Mysten Labs is actively launching a new data storage protocol called Walrus. But with so many decentralized storage protocols for archival purpose already existing, is there really a need for yet another storage protocol? What exactly is Walrus, and how does it differentiate itself from existing storage protocols?

2. Walrus: The Next Gen Data Storage Protocol

2.1 Previous Decentralized Storage Protocols

Before delving into Walrus, let's examine existing storage protocols. On-chain storage of blob data, including images, videos, and documents, is crucial in the blockchain industry. Notable examples of blob data range from on-chain storage of original NFT files to datasets used for AI model training, decentralized frontend hosting for dApps, and storage of rollup transaction data. As these examples illustrate, storing something on-chain is a powerful act that can prove integrity.

Due to this importance, many protocols have attempted to store large-scale data like blobs in a decentralized manner before Walrus. Filecoin, Arweave, Storj, and Sia are prominent examples. Let's examine how these protocols approached blob storage and what differentiates Walrus from them.

Note that the abbreviations used in the following examples mean:

• B: blob

• W: blob writer

• R: blob reader

• f: the number of byzantine nodes

• n: total number of nodes

2.1.1 Full Replication: IPFS, Arweave

The most intuitive and simple method to store blobs in a distributed environment is for nodes to replicate and store the entire B uploaded by W. For example, if you upload an image file, instead of nodes splitting and dividing the image file, they replicate and store the image file as is. Prominent examples include IPFS and Arweave. Of course, this doesn't mean that storage nodes participating in IPFS and Arweave download all files stored across the entire network; rather, they store some of the files in their complete form.

W propagates B and the corresponding commitment (binding commitment, e.g., hash) to the nodes and waits until receiving f+1 signatures. (Assumption: n = 3f+1; At least f+1 signatures are required to ensure that at least one honest node, excluding f Byzantine nodes, has stored B.) Once f+1 signatures arrive, W can generate an availability certificate, guaranteeing that anyone can fully access the file on that network.

However, full replication has many drawbacks, primarily inefficiency:

• Write: When W propagates files to nodes to store data on the network, it has a complexity of O(nB).

• Read: In an asynchronous environment, reading data incurs a cost of O(nB) because requests must be sent to f+1 nodes.

• Recovery: To recover data in an asynchronous environment, a storage node must send requests to f+1 other nodes, costing O(nB) for each storage node. When applied to the entire network, this results in a cost of O(n^2 B). Note that this is the worst cast cost.

2.1.2 Encode and Share: Storj, Sia

As mentioned above, the Full replication method had advantages of being simple, intuitive, and easy to access complete files, but its drawback was the high storage cost for the entire network. To address this, decentralized storage networks using Reed Solomon (RS) encoding emerged. Notable examples are Storj and Sia.

RS encoding is a prominent method for implementing erasure coding, widely used in real life for CDs, DVDs, QR codes, etc. Erasure coding divides original data into multiple pieces and generates additional recovery data from these pieces. Even if some data is lost, the original data can be restored to a certain extent using the recovery data.

Let's look at an example of the Encode and Share method. W divides B into f+1 data chunks and additionally encodes 2f extra repair chunks. Thanks to RS encoding's characteristics, the original B can be recovered with just f+1 chunks out of a total of 3f+1 chunks. Here, each chunk's size is O(B/n).

W uses binding commitments like Merkle trees to commit to all chunks and sends each node a chunk along with a proof of inclusion showing that the chunk is included in the Merkle tree. Storage nodes receiving chunks verify their validity using the commitment and send a signature back to W.

W generates an availability certificate when it receives at least 2f+1 signatures from nodes (as B can be recovered via f+1 even if f out of 2f+1 are Byzantine nodes). The Encode and Share method is more efficient in data writing and reading processes compared to Full replication, but still has the drawback of inefficient data recovery.

• Write: It costs a total of O(B) as W propagates chunks of size O(B/n) to the network for data storage.

• Read: R has a complexity of O(B/n) * O(n) = O(B) as it must request chunks from nodes and receive f+1 valid responses.

• Recovery: In an asynchronous environment, to recover data, each storage node incurs a cost of O(B) as it needs to receive chunks from 2f+1 nodes. Applied to the entire network, this results in a total cost of O(nB), which is still inefficient.

Increasing the efficiency of the data recovery process is crucial because, being a decentralized protocol, nodes can freely join and leave the network. In cases where the node set changes with each epoch, new nodes need to receive and recover chunks from previous nodes. Recognizing this issue, Walrus utilizes a new encoding method.

2.1.3 Red Stuff: Walrus

Walrus can achieve a recovery cost of O(B/n) for each node and a total recovery cost of O(B) for the entire network through Red Stuff encoding. Let's examine this in more detail below.

2.2. Walrus Overview

Walrus is a decentralized storage protocol based on erasure-coding. Anyone can interact with Walrus to store arbitrary data and prove that the data is stored. Like IPFS, Walrus itself is not a blockchain. However, Walrus leverages the Sui network for help with storage node lifecycle management, blob lifecycle management, and the introduction of incentive systems.

Sui has achieved exceptionally high scalability compared to other blockchains with its own consensus and smart contracts. However, if Sui were to handle blobs in addition to transaction data, it would be inefficient as all nodes would replicate large volumes of blobs, greatly increasing the replication factor. (The replication factor refers to how much data is replicated and stored across the entire network compared to the original data.)

Therefore, Walrus uses erasure-coding to divide blobs into smaller units called slivers and allocate them to nodes, allowing large volumes of data to be stored in a decentralized protocol with a replication factor of just 4-5. In particular, unlike existing decentralized storage protocols, Walrus has the advantage of significantly reducing data recovery costs by using an encoding method called Red Stuff. So, what is Red Stuff?

2.3 Red Stuff

2.3.1 Encoding

Unlike RS encoding, Red Stuff encodes the blob in two dimensions. This is for efficient sliver recovery. In the primary dimension, encoding is similar to RS-encoding, dividing B into f+1 primary slivers. Red Stuff goes a step further, dividing each of the f+1 primary slivers into 2f+1 secondary slivers in the secondary dimension. As a result, B becomes a matrix of (f+1) * (2f+1). Note that the example in the above figure assumes f=1.

Based on this two-dimensional matrix, additional repair symbols are generated for both dimensions. (Note that a symbol is a smaller unit of data than a sliver.) First, the symbols of 2f+1 columns are expanded from f+1 to 3f+1, and then the symbols of f+1 rows are expanded from 2f+1 to 3f+1.

The commitment to B can be easily calculated. W calculates commitments for each rows and columns including the additional repair symbols, then combines all these sliver commitments to create the blob commitment.

2.3.2 Write

The process of storing data in the Walrus protocol is similar to protocols using existing RS encoding. W encodes the original data with Red Stuff to generate sliver pairs to send to each node. A sliver pair here refers to a pair of primary and secondary slivers, with a total of 3f+1 sliver pairs generated.

W then propagates 3f+1 sliver pairs and sliver commitments to 3f+1 nodes each. Upon receiving these, nodes verify the slivers through the commitments and send signatures back to W. When W receives 2f+1 signatures, it generates an availability certificate and publishes it on-chain (Sui network). This is because even if f Byzantine nodes sign, there are signatures from f+1 honest nodes, making it possible to recover the original data.

2.3.3 Read

The process of reading data from Walrus is also identical to protocols using existing RS encoding, and only primary slivers need to be used. When R receives f+1 or more valid primary slivers from storage nodes, it can recover B and read the data.

2.3.4 Recovery

The biggest advantage of Red Stuff compared to RS encoding is evident in the data recovery process. Assuming the network is in an asynchronous environment and nodes can freely enter and leave, there may be nodes that don't receive slivers from W. Therefore, these nodes need to communicate with other nodes to recover slivers.

Let's examine how a node that didn't receive slivers recovers data through the above figure (f=1).

• a: Assume a situation where Node 1 fully possesses the first sliver pair, Node 3 has the third sliver pair, and Node 4 needs to recover the fourth sliver pair.

• b: Nodes 1 and 3 send symbols that overlap with the fourth sliver pair (S14, S34, S41, S43) to Node 4.

• c: Since Node 4 now has f+1 or more symbols for the fourth secondary sliver, it can recover the fourth secondary sliver. Extending this logic means that all 2f+1 honest nodes can recover their secondary slivers.

• d: The fact that 2f+1 nodes all have secondary slivers means there are 2f+1 symbols in each row, which allows for the recovery of all primary slivers using these 2f+1 symbols. In conclusion, if f+1 or more nodes in the network have slivers, the remaining nodes can communicate with them to recover all slivers.

The size of a symbol is O(B/n^2), and each node needs to download O(n) symbols, so the recovery cost per node is O(B/n). Extending this to the entire network, the cost for all nodes to recover slivers corresponds to O(B). Considering that the cost of recovering data is O(n^2B) in the full replication method and O(nB) in the encode and share method, the Red Stuff method can process this very efficiently at a cost of O(B). In other words, the data recovery cost is constant regardless of the number of nodes (n) participating in the network.

2.4 Walrus Storage Flow

Red Stuff is one method of encoding data. Now, let's look at the big picture of how data storage occurs in Walrus, including interactions with Red Stuff and the Sui network.

1. A user wanting to store data in Walrus acquires storage resources. Storage resources can be purchased directly from the Walrus system object smart contract on the Sui network or from a secondary market. Storage resources can be understood as permissions to store data in Walrus, specifying the start epoch, end epoch (details below), and how much capacity can be stored.
   

2. The user applies Red Stuff encoding to the blob they want to store and computes the blob ID. Subsequent steps can be performed directly or by publishers existing in the network.
   

3. To register the blob ID with the storage resource, the user updates the storage resource on the Sui network to trigger an event.
   

4. The user propagates the blob metadata to all storage nodes and distributes each sliver to the respective nodes.
   

5. Storage nodes receive the slivers and verify whether the metadata matches the blob ID and the slivers match the metadata, and if the user transmitting the sliver has appropriate storage resources. If deemed valid, storage nodes send signatures for the respective slivers to the user.
   

6. When the user receives 2f+1 or more signatures, they generate an availability certificate and transmit it to the Sui network. From this point, the PoA (point of availability) status is updated on the Sui network, indicating that the blob is available to everyone.
   

7. If there are storage nodes that haven't received slivers for that blob even after confirming the PoA, they can sync with other storage nodes to recover the slivers.

Note that the Walrus protocol has an epoch concept for a certain period, and the set of participating storage nodes changes with each epoch. The amount of data allocated to storage nodes varies according to the delegated WAL tokens each epoch. Also, because participating nodes can change each epoch, there's an inevitable process of transferring slivers every time the epoch changes. Note that in the default case, slivers are transferred from the previous node to the new node directly instead of going through the recovery process.

However, if there's too much data and the sliver transfer time becomes longer than the epoch, the epoch may not end. To prevent this, Walrus separates the data storage (write) and retrieval (read) processes into different epochs just before the end of an epoch.

In other words, when the epoch changes and the node reconfiguration process begins, the data storage process proceeds in the next epoch from this point, while the data reading process still continues in the current epoch. When 2f+1 or more nodes in the new committee of the next epoch indicate that sliver recovery is fully prepared, the read operations also smoothly transition to the next epoch.

3. Walrus Applications

Let's examine some use cases for Walrus.

3.1 Decrypt Media

Decrypt is a Web3-focused media company that announced plans to store their articles and videos on Walrus at the Token 2049 event this September. The advantages Decrypt can gain by utilizing Walrus are:

• Authenticity: As a media company, ensuring content authenticity is crucial. Decrypt can secure authenticity by storing content on Walrus.

• Permanence: According to the Pew Research Center, over 1/3 of online content from 2013 to 2023 has been lost. By storing content on Walrus, Decrypt can maintain their content for a long time.

• Profitability: Walrus is planning to facilitate interoperability between Decrypt's content and dApps, allowing Decrypt to easily monetize their content. For example, encrypted media could be stored on Walrus, with decryption keys provided only to paying subscribers for content access.

3.2 Walrus Sites

Walrus Sites are decentralized frontend websites based on Sui and Walrus. The fundamental sources like HTML, CSS, JavaScript, and images are stored on Walrus, with their entry points stored as objects on Sui. These objects include the website's metadata and point to the blob IDs where the website sources are stored.

Interestingly, Walrus's docs are already an example of Walrus Sites, hosted by Walrus. Additionally, Walrus offers Flatland NFTs on the Sui testnet as an example of Walrus Sites. Flatland is an NFT collection on Sui that can be minted from a Walrus-hosted frontend, with each NFT having its own personalized Walrus Site.

3.3 Akord

Akord is a Walrus-based data management platform that provides an interface and user experience similar to Dropbox. The most distinctive feature of Akord is that it uses end-to-end encryption, ensuring data privacy by encrypting data when it is stored on the platform. Users can easily encrypt and store data as if they were using a Web2 service, and the data stored through Akord is securely stored on Walrus.

3.4 Others

• DA Layer: Besides storing arbitrary files, Walrus can securely store transaction data for rollup networks due to its use of erasure coding. This means Walrus can serve as a DA layer like Celestia, EigenDA, or Avail.

• AI: Walrus can store data requiring authenticity or transparency in AI model training and inference, such as clean data used for AI model training or AI model weights.

• Blockchain History: For rapidly scalable blockchain networks, managing the entire blockchain history from the genesis block can be very challenging. With appropriate safeguards, Walrus could serve as an archive for these blockchains' histories.

3.5 Testnet Blob Upload

Source: Walrus

Note that currently, anyone can store arbitrary files on the Walrus testnet. You can also search for stored blobs using their blob ID, so readers interested in experiencing Walrus are encouraged to give it a try. Although it's been less than a month since the testnet launched, Walrus has already grown rapidly, storing a capacity of 4,343 GB of data.

4. Final Thoughts

Recently, the Sui ecosystem has been receiving tremendous attention and is growing at an incredibly rapid pace. I believe this is because Sui has continuously innovated in both application-friendly areas such as Move on Sui, Deepbook, zkLogin, SuiNS, and infrastructure areas like Narwhal, Bullshark, and Mysticeti. Walrus is also part of this direction for Sui, and by solving the blob storage problem off-chain, which is difficult for the Sui network to handle on its own, it will enable the utilization of an even more diverse range of applications in the Sui ecosystem.

Furthermore, while Walrus will have a very close relationship with the Sui network, it is clearly a separate protocol which is blockchain-agnostic. Thus, we anticipate Walrus not only serving as simple data storage but also potentially functioning as a DA layer for rollups. Moreover, we see Walrus will play a significant role beyond just the Sui ecosystem, as protocols across other blockchain ecosystems could leverage Walrus as their storage layer.