There are different ways to describe the GKR algorithm
from Libra paper:
\(\tilde{V}_i(g) = \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} f_i(x,y)\)
\(= \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} \left( \widetilde{add}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x) + \tilde{V}_{i+1}(y))\right.\)
\(\left. + \tilde{mult}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x)\tilde{V}_{i+1}(y)) \right)\)
from hyrax paper:
$$\widetilde{V_0}(q’,q)=\sum\limits_{h’\in \{0,1\}^{b_N}}\sum\limits_{h_L\in \{0,1\}^{b_G}}\sum\limits_{h_R\in \{0,1\}^{b_G}}P_{q’,q,1}(h’,h_L,h_R)$$
$$=\sum\limits_{h’\in \{0,1\}^{b_N}}\sum\limits_{h_L\in \{0,1\}^{b_G}}\sum\limits_{h_R\in \{0,1\}^{b_G}}\widetilde{eq_1}(q’,h’)$$
$$\cdot [\widetilde{mul_1}(q,h_L,h_R)(\widetilde{V_1}(h’,h_L)\times \widetilde{V_1}(h’,h_R) )$$
$$+\widetilde{add_1}(q,h_L,h_R)(\widetilde{V_1}(h’,h_L)+ \widetilde{V_1}(h’,h_R) )]$$
what is the cost difference between being able to express repetition or not in the circuit?
suppose there are \(2^l\) inputs in the current layer, \(2^k\) gates and \(2^r\) repetitions
The verifier needs to compute the multilinear extension of each gate in a layer.
for Libra: there are three variables, \(g\) going through the gates thus it needs \(k\) bits to present, \(x\) and \(y\) going through the inputs thus they both needs \(l\) bits to present, so totally, the number of variable of the multilinear function in this sumcheck protocol on this layer would be
\(2l+k\)
for Hyrax: there are also four variables, \(h’\) going through all the repetitions, \(q\) going through the gates in one repitition, \(h_L\), \(h_R\) going though the inputs in one repetition. Therefore the total number of variable of the multilinear function in this sumcheck protocol on this layer would be
\(r+(k-r)+2(l-r)=2l+k-2r\)
Conclusion: the difference is \(2r\)