RedStuff Encoding Example

This page continues from the RedStuff encoding algorithm overview with a concrete worked example.

Encoding

Consider a Walrus instance with $N = 7 = 3f + 1$ shards. This means the number of primary source symbols is $N - 2f = 3$, and secondary $N - f = 5$. A blob of size $S = 15 \cdot s$ can therefore be divided into 15 symbols of size $s$, and arranged 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]$$

Each of the columns of this row expansion is a secondary sliver. For example, $[r_{0,6}, r_{1,6}, r_{2,6}]$.

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. Neither difference changes how encoding and recovery work.

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. These symbols can be represented as the lower-right quadrant of what is called 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]$$

These symbols do not need to be stored on any node because they can always be recomputed by expanding either a primary or secondary sliver. For example, $r_{4,5}$ can be obtained by:

• 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: $[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.