RedStuff Recovery Example

A Walrus shard that loses its slivers recovers them by requesting recovery symbols from other shards. This recovery scenario continues the RedStuff encoding example and uses shard 3 as the failed shard.

How does a shard recover lost slivers?

Consider that shard 3 fails, losing its slivers, and needs to recover them. Recovery symbols are ordinary sliver symbols: each one is the symbol where a contacted shard's sliver intersects the lost sliver. This example recovers the primary sliver first. When the other shards hold their slivers, either order works, and storage nodes recover both slivers concurrently. Only in the worst-case initial sharing does the secondary sliver have to come first, because it needs only $N-2f$ symbols.

In the matrices in this section, red marks the symbols of the lost slivers and green marks the recovery symbols that other shards provide. Shards never store the lower-right quadrant. In the following matrix, row 3 is the primary sliver of shard 3 and column 3 is its secondary sliver.

$$\left[ \begin{array}{ccccc|cc} s_{0,0} & s_{0,1} & s_{0,2} & \color{red} s_{0,3} & s_{0,4} & r_{0,5} & r_{0,6} \\ s_{1,0} & s_{1,1} & s_{1,2} & \color{red} s_{1,3} & s_{1,4} & r_{1,5} & r_{1,6} \\ s_{2,0} & s_{2,1} & s_{2,2} & \color{red} s_{2,3} & s_{2,4} & r_{2,5} & r_{2,6} \\ \hline \color{red} r_{3,0} & \color{red} r_{3,1} & \color{red} r_{3,2} & \color{red} r_{3,3} & \color{red} r_{3,4} & & \\ r_{4,0} & r_{4,1} & r_{4,2} & r_{4,3} & r_{4,4} & & \\ r_{5,0} & r_{5,1} & r_{5,2} & r_{5,3} & r_{5,4} & & \\ r_{6,0} & r_{6,1} & r_{6,2} & r_{6,3} & r_{6,4} & & \\ \end{array} \right]$$

How does shard 3 recover its primary sliver?

To recover the primary sliver:

1. The node contacts 5 other shards and requests the recovery symbols for primary sliver 3.
2. Each contacted shard encodes its secondary sliver to obtain its recovery symbol, which is the symbol where that shard's sliver intersects the lost primary sliver. This step is necessary because these symbols are repair symbols.
3. Each contacted shard provides its recovery symbol to shard 3.

For example, shards 0, 1, 2, 4, and 6 provide the symbols $r_{3,0}$, $r_{3,1}$, $r_{3,2}$, $r_{3,4}$, and $r_{3,6}$, shown in green:

$$\left[ \begin{array}{c|c|c|c|c|c|c} s_{0,0} & s_{0,1} & s_{0,2} & \color{red} s_{0,3} & s_{0,4} & r_{0,5} & r_{0,6} \\ s_{1,0} & s_{1,1} & s_{1,2} & \color{red} s_{1,3} & s_{1,4} & r_{1,5} & r_{1,6} \\ s_{2,0} & s_{2,1} & s_{2,2} & \color{red} s_{2,3} & s_{2,4} & r_{2,5} & r_{2,6} \\ \color{green} r_{3,0} & \color{green} r_{3,1} & \color{green} r_{3,2} & & \color{green} r_{3,4} & & \color{green} r_{3,6}\\ \end{array} \right]$$

How does shard 3 recover its secondary sliver?

To recover the secondary sliver:

1. The node contacts at least 3 other shards to obtain recovery symbols.
2. Each contacted shard provides the recovery symbol from its primary sliver (highlighted as a row). The recovery symbols are already part of the primary slivers that the other shards store, so no re-encoding is necessary.
3. Shard 3 decodes the 3 symbols with erasure decoding to obtain its secondary sliver, unless all 3 are source symbols of that sliver.

For example, shards 0, 1, and 5 provide the recovery symbols $s_{0,3}$, $s_{1,3}$, and $r_{5,3}$, shown in green:

$$\left[ \begin{array}{ccccc} s_{0,0} & s_{0,1} & s_{0,2} & \color{green} s_{0,3} & s_{0,4} \\ \hline s_{1,0} & s_{1,1} & s_{1,2} & \color{green} s_{1,3} & s_{1,4} \\ \hline s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} & s_{2,4} \\ \hline \color{red} r_{3,0} & \color{red} r_{3,1} & \color{red} r_{3,2} & \color{red} r_{3,3} & \color{red} r_{3,4} \\ \hline r_{4,0} & r_{4,1} & r_{4,2} & r_{4,3} & r_{4,4} \\ \hline r_{5,0} & r_{5,1} & r_{5,2} & \color{green} r_{5,3} & r_{5,4} \\ \hline r_{6,0} & r_{6,1} & r_{6,2} & r_{6,3} & r_{6,4} \\ \end{array} \right]$$

Because $r_{5,3}$ is a repair symbol, shard 3 decodes the 3 symbols to obtain its secondary sliver. If shards 0, 1, and 2 respond instead, they provide $s_{0,3}$, $s_{1,3}$, and $s_{2,3}$, which are the symbols of the secondary sliver itself, so shard 3 does not need to decode.

For properties, Walrus-specific parameters, blob size limits, and sliver authentication details, see RedStuff properties and parameters.

How does shard 3 reconstruct the sliver?

Shard 3 reconstructs a lost sliver with erasure decoding. Each recovery symbol carries a Merkle proof, and the recovering shard verifies the symbols against the sliver hashes in the blob metadata before it decodes them. Decoding needs a fixed number of recovery symbols for each sliver type, and the shard does not attempt decoding with fewer.

After decoding, the shard checks the reconstructed sliver against its hash in the blob metadata. If the decoded sliver does not match that hash, the blob is inconsistently encoded. In that case the shard produces an inconsistency proof instead of a recovered sliver. The proof contains the recovery symbols and their Merkle proofs, so any entity can repeat the decoding and confirm the mismatch.