RedStuff Encoding Example

RedStuff encoding arranges a blob as a matrix of source symbols, expands the columns to produce primary slivers, and expands the rows to produce secondary slivers. The following example traces these steps for a Walrus instance with 7 shards and continues from the RedStuff encoding algorithm overview.

How does RedStuff encoding work?

RedStuff encoding has 4 steps:

1. Arrange the source symbols of the blob in a matrix with $N - 2f$ rows and $N - f$ columns.
2. Apply the primary encoding to each column. Each row of the expanded matrix is a primary sliver.
3. Apply the secondary encoding to each row. Each column of the expanded matrix is a secondary sliver.
4. Store one primary sliver and one secondary sliver, a sliver pair, on each shard.

Consider a Walrus instance with $N = 7 = 3f + 1$ shards, so $f = 2$. This means the number of primary source symbols is $N - 2f = 3$, and secondary $N - f = 5$. You can therefore divide a blob of size $S = 15 \cdot s$ into 15 symbols of size $s$ and arrange them in the matrix as follows.

$$\left[ \begin{array}{ccccc} s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} & s_{0,4} \\ s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} & s_{1,4} \\ s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} & s_{2,4} \\ \end{array} \right]$$

Then, the primary encoding acts on the columns of the matrix, expanding them such that each column is composed of 3 source symbols and 4 repair symbols ($s_{i,j}$ indicates source symbols, while $r_{i,j}$ indicates repair symbols).

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

Each of the rows of this column expansion is a primary sliver. For example, $[r_{5,0}, r_{5,1}, r_{5,2}, r_{5,3}, r_{5,4}]$.

Similarly, the secondary encoding on the rows of the matrix produces the expanded rows.

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

The secondary encoding adds 2 repair symbols to each row of 5 source symbols, so columns 5 and 6 are new and hold only repair symbols ($r_{i,5}$ and $r_{i,6}$).

Each of the columns of this row expansion is a secondary sliver, so a secondary sliver holds 3 symbols, one from each row. For example, $[r_{0,6}, r_{1,6}, r_{2,6}]$. Expanding such a column with the primary encoding gives 3 source symbols and 4 repair symbols, that is, 7 symbols in total.

For simplicity, this example and the recovery example pair primary sliver $i$ with secondary sliver $i$ (as in the Walrus paper), and store sliver pair $i$ on shard $i$. In the implementation, sliver pair $i$ holds primary sliver $i$ and secondary sliver $N-1-i$, and the sliver-pair-to-shard mapping assigns sliver pairs to shards. Each shard therefore stores exactly one sliver pair, that is, one primary sliver and one secondary sliver. Neither difference changes how encoding and recovery work.

What is the fully expanded message matrix?

Thanks to the linearity of Reed-Solomon codes, the expansion of:

• the repair secondary slivers (columns 5 and 6) with the primary encoding, and
• the repair primary slivers (rows 3, 4, 5, and 6) with the secondary encoding,

results in the same set of symbols, which is essential for recovery. You can represent these symbols as the lower-right quadrant of the fully expanded message matrix.

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

No node needs to store these symbols because you can always recompute them by expanding either a primary or secondary sliver. For example, you can obtain $r_{4,5}$ from:

• the secondary-encoding expansion of primary sliver 4: $[r_{4,0}, r_{4,1}, r_{4,2}, r_{4,3}, r_{4,4}, \color{blue} r_{4,5}, r_{4,6}]$, or
• the primary-encoding expansion of secondary sliver 5, which extends its 3 symbols to 7: $[r_{0,5}, r_{1,5}, r_{2,5}, r_{3,5}, \color{blue} r_{4,5}, r_{5,5}, r_{6,5}]$.

For a worked example of sliver recovery after shard failure, see RedStuff recovery example. For properties, Walrus-specific parameters, blob size limits, and sliver authentication details, see RedStuff properties and parameters.

Which erasure code does RedStuff use?

Both the primary and the secondary encoding use Reed-Solomon codes. The current encoding type, RS2, is RedStuff with the Reed-Solomon erasure code, and its configuration holds the number of source symbols for both encodings. Walrus no longer supports the original RedStuff encoding, which used the RaptorQ erasure code. With Reed-Solomon codes, the number of symbols you need to recover a sliver is exactly the number of source symbols.