Skip to main content

Encoding, Overheads, and Verification

Walrus uses a bespoke erasure code construction called RedStuff, based on efficiently computable Reed-Solomon codes. For complete technical details, see the Walrus whitepaper. This page summarizes some of the basic techniques and terminology used by Walrus.

Basics​

Walrus encodes blobs using erasure codes to ensure data can be recovered even when some storage nodes are unavailable or malicious.

Erasure coding​

An erasure code transforms data by:

  1. Taking a blob and splitting it into (k) symbols.
  2. Encoding these into (n) symbols (where (n > k)).
  3. Distributing symbols so any subset can reconstruct the original blob.

This process allows Walrus encoding to be:

  • Highly efficient: Walrus can reconstruct a blob from just one-third of the encoded symbols.
  • Systematic: Some storage nodes hold part of the original blob, enabling fast random-access reads.
  • Deterministic: All encoding and decoding operations follow fixed algorithms with no discretion.

For each blob, multiple symbols are combined into a sliver, which is then assigned to a shard. Storage nodes manage one or more shards, and the corresponding slivers of each blob are distributed to all storage shards.

This detailed encoding setup results in an expansion of the blob size by a factor of 4.5-5. This is independent of the number of shards and the number of storage nodes.

Blob authentication​

Each blob has associated metadata, including a blob ID, that enables data authenticity verification.

Blob ID computation​

The blob ID is computed as an authenticator of the set of all shard data and metadata (byte size, encoding, blob hash):

  1. Sliver hashing: Walrus computes a hash of the sliver representation in each shard.
  2. Merkle tree construction: These hashes form the leaves of a Merkle tree.
  3. Blob hash derivation: The Merkle tree root becomes the blob hash.

Each storage node can use the blob ID to authenticate shard data by checking it against the corresponding blob hash in the authenticated structure (Merkle tree). A successful check confirms that the data matches what the blob writer intended.

Data integrity and consistency​

Clients compute slivers, metadata, and blob IDs when writing blobs. Because clients are untrusted, these computations might be incorrect due to bugs or malicious intent. Concretely, a client can make one or more of the following mistakes:

  • Incorrect sliver computation
  • Incorrect hash computation from the slivers
  • Incorrect blob ID computation from the sliver hashes and other metadata

Detection mechanisms​

Honest storage nodes that are assigned an incorrect sliver, or one with an incorrect hash, will attempt to recover it from other storage nodes and then notice the inconsistency. They can then extract one symbol per sliver to form an inconsistency proof, which is then used to mark the blob as invalid. After this, storage nodes can delete slivers belonging to inconsistently encoded blobs, and upon request, return either the inconsistency proof or an inconsistency certificate posted on-chain.

Incorrect sliver computation:

  • Can be detected by storage nodes using the process above.
  • Not guaranteed to trigger immediately after certification.
  • May persist in the network for longer periods.
  • Requires additional client-side consistency checks.

Incorrect hash computation:

  • Generally detected before or shortly after certification using the process above.

Incorrect blob ID computation:

  • Detected immediately when the client uploads metadata.
  • Storage nodes reject these blobs and never issue storage certificates.
  • Such blobs are never certified.

Consistency checks​

Clients perform consistency checks when reading blobs to ensure data integrity. Walrus offers two levels of verification: default and strict.

In most cases, the default consistency check is sufficient, particularly when the blob writer is trusted. The strict consistency check is only needed for specific availability guarantees. When the writer is known and trusted, consistency checks can be disabled entirely.

Default consistency check​

The default check balances performance with security by verifying only the read data.

Check process:

  1. Client requests blob metadata and verifies its authenticity.
  2. Client requests a subset of primary slivers (334 slivers minimum).
  3. Client verifies sliver authenticity using the metadata.
  4. Client decodes the original blob from these authentic slivers.

The first 334 primary slivers contain the unencoded data (potentially padded). This means the cryptographic hashes of these slivers, combined with the blob length, uniquely determine the blob content. Therefore, by recomputing the sliver hashes of the first 334 slivers and checking them against the metadata, the client can verify that the decoded data is correct. If the hashes match, the data is provided to the user, otherwise an error is returned.

Any correct client attempting to read a blob and performing the default consistency check, will either read the specific value authenticated by the writer or return an error.

Strict consistency check​

The strict check provides stronger guarantees by verifying the entire blob encoding, not just the read portion.

When a blob is encoded incorrectly, different sets of 334 slivers might decode to different data. The default check guarantees correct data when a read succeeds, but some read attempts might fail while others succeed. Storage nodes might later detect the blob as inconsistent, causing all subsequent reads to fail.

Check process:

  1. Client decodes the blob (same as default check).
  2. Client fully re-encodes the decoded blob.
  3. Client recomputes all sliver hashes and the blob ID.
  4. Client verifies the computed blob ID matches the requested blob ID.
  5. Read succeeds only if blob IDs match.

This check is more rigorous than the default check and provides the same data consistency property. It ensures the original writer encoded the blob correctly, eliminating the possibility of inconsistent reads across different clients or time periods.

Additionally, the strict check guarantees that any correct client attempting to read the blob during its lifetime will always succeed and read the same data intended by the writer, regardless of which consistency check they perform.

Consistency checks for quilts​

For quilt patches, only a variant of the default consistency check is available, because clients read only part of the quilt rather than the entire structure.