Walrus protocol makes assumptions to guarantee data integrity, nodes can't tamper with stored data without detection.
• The digital signatures ensure that only authorized nodes can perform actions.
• Binding commitments prevent nodes from pretending to store tha data they don't have.
Without these cryptographic tools, Walrus can't enforce trust in a decentralized, permissionless network.
• Some nodes may behave maliciously, delay messages or leave the network unexpectedly. By assuming f faulty nodes in a 3f+1 committee, Walrus can guarantee consensus and data safety even under attacks.
• Epochs simplify reasoning about nodes which are responsible for which data at a given time.
These assumptions create a mathematically safe network where Walrus protocol can guarantee data availability and accountability despite adversaries.
• Erasure coding allows data to be reconstructed from a subset of nodes, reducing storage overhead. Systematic codes allow optimization. It ensures robustness against node failure or departure.
Following assumptions make the system storage-effiecient and resilient.
A. 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.
B. Network and adversarial assumptions:
Walrus runs in epochs, each with a static set of storage nodes. At the end of the epoch "n=3f+1" storage nodes are elected as part of the the storage committee of the epoch and each one controls a storage shard such that a malicious adversary can control up to "f" of them.
The corrupted nodes can deviate arbitrarily from the protocol. The remaining nodes are honest and strictly adhere to the protocol. If a node controlled by the adversary at epoch "e" is not a part of the storage node set at epoch "e+1" then the adversary can adapt and compromise a different node at epoch "e+1" after the epoch change has completed.
We assume every pair of honest nodes has access to a reliable and authenticated channel. The network is asynchronous, so the adversary can arbitrarily delay or reorder messages between honest nodes, but must eventually deliver every message unless the epoch ends first. If the epoch ends then the messages can be dropped.
Our goal is not only to provide a secure decentralized system but to also detect and punish any storage node that does not hold the data that it is assigned. This is a standard additional assumption for dencentralized storage system to make sure that honest parties cannot be covertly compromised forever.
C. Erasure codes:
As part of Walrus, we propose Asynchronous Complete Data Storage (ACDS) that uses an erasure coding scheme. While not necessary for the core parts of the protocol, we also assume that the encoding scheme is systematic for some of our optimizations, meaning that the source symbols of the encoding scheme also appear as part of its output symbols.
Let Encode (B,t,n) be the encoding algorithm. Its output are "n" symbols such that any "t" can be used to reconstruct "B". This happens by first splitting "B" into "t" symbols of size "O(|B|t)" which are called source symbols. These are then expanded by generating "n−t" repair symbols for a total of "n" output symbols. On the decoding side, anyone can call Decode(T,t,n) where "T" is a set of at least "t" correctly encoded symbols, and it returns the blob "B".
ACDS shares some similarities with Asychronous Verifiable information Dispersal (AVID) [14, 15], given that the main goal of both protocol is to distribute data. However, they also have significant differences most notably the lack of completeness in AVID protocols which is critical for Walrus.
D. Blockchain substrate:
Walrus uses an external blockchain as a black box for all control operations that happen on Walrus. A blockchain protocol can be abstracted as a computational black box that accepts a concurrent set of transactions, each with an input message "Tx(M)" and outputs a total order of updates to be applied on the state "Res(seq,U)". We assume that the blockchain does not deviate from this abstract and does not censor "Tx(M)" indefinitely. Any high-performance modern SMR protocol satisfies these requirements, in implementation they use Sui.
Walrus makes these assumptions because it operates in a decentralized, potentially adversarial, and unreliable network. With these assumptions, Walrus cannot formally guarantee security, reliability, or accountability.
