Assume that we have data chunks such that $y_{1,1}, y_{1,2}, \dots, y_{k,k}$ . Every $y_{i,j}$ is a field element. We encode this data using an evaluation form via RS-code.
| $y_{1,1}$ | $y_{1,2}$ | $y_{1,3}$ | $\dots$ | $y_{1,k}$ |
|---|---|---|---|---|
| $y_{2,1}$ | $y_{2,2}$ | $y_{2,k}$ | ||
| $y_{3,1}$ | $y_{3,k}$ | |||
| $\dots$ | $\cdots$ | |||
| $y_{k,1}$ | $y_{k,2}$ | $\dots$ | $y_{k,k}$ |
We have $f_i(j)=y_{i,j}$ where $i,j=1,\dots, k$. Now, we extend the data as row-wise and calculate the commitment of rows.
| $f_1(1)$ | $f_1(2)$ | $f_1(3)$ | $\dots$ | $f_1(k)$ | $\dots$ | $\dots$ | $f_1(n)$ | $C_1$ |
|---|---|---|---|---|---|---|---|---|
| $f_2(1)$ | $f_2(2)$ | $f_2(k)$ | $f_2(n)$ | $C_2$ | ||||
| $f_3(1)$ | $f_3(k)$ | |||||||
| $\dots$ | $\cdots$ | |||||||
| $f_k(1)$ | $f_k(2)$ | $\dots$ | $f_k(k)$ | $\dots$ | $\dots$ | $f_k(n)$ | $C_n$ |
Now, let's define a new polynomial $h(x)$ such that;
$h_i(x)=\frac{f_1(x)-y_{1,i}}{x-i}+\frac{f_2(x)-y_{2,i}}{x-i}+\dots+\frac{f_k(x)-y_{k,i}}{x-i}$
For the first column, if $f_i(1)=y_{i,1}$ for $i=1,\dots,k$ then $h_1(x)$ is polynomial.
$h_1(x)=\frac{f_1(x)-y_{1,1}}{x-1}+\frac{f_2(x)-y_{2,1}}{x-1}+\dots+\frac{f_k(x)-y_{k,1}}{x-1}$ , then we have
$h_1(x)(x-1)=\sum_{i=1}^{k}f_i(x)-y_{i,1}$ , now let’s separate the right hand side
$h_1(x)(x-1)=\sum_{i=1}^{k}f_i(x)-\sum_{i=1}^{k}y_{i,1}$ , if we calculate this equation at the secret value $\tau$ we have
$h_1(\tau)(\tau-1)=\sum_{i=1}^{k}f_i(\tau)-\sum_{i=1}^{k}y_{i,1}$, if we calculate the pairing of both side we have,
$e (g^{h_1(\tau)}, g^{\tau-1}) =e (g, g)^{{h_1(\tau)}{(\tau-1})}= e(\frac{\prod C_i}{g^{\sum y_{i,1}}},g)$ since $g^{\sum_{i=1}^{k}f_i(\tau)}=\prod C_i$.
Prover has to commit $h_i(x)$ and sends $com h_i=g^{h_i(\tau)}$ to node $i$.
The verifier only calculates $g^{\tau-i}$ and then checks the pairing. If it holds, then this proves that this column is encoded correctly.