Using GKR in LogUps to Improve Proving Time

[hecmas]

The paper I refer to is the following 2023/1284.

My proposal for the GKR topic is as follows:

1. If you compare the cost of GKR versus the normal LogUp, the normal LogUp is much more efficient because the transformation we need to make from univariate FRI to multivariate FRI incurs (at least) in two additional commitments sent from P to V. The "good" thing about this transformation is that the number of "extra" commitments remains constant, regardless of how many lookups, permutations, or connections you attempt to prove. Therefore, the idea would be to do what is explained in the next point.
2. We can use the GKR approach to prove that the sum of ALL the permutations/lookups/connections we have done equals zero (i.e., they are correct). For each of these sums, we have roughly double the cost in field operations, but we avoid the extra commitments (i.e., those to the sums and to the intermediaries if we are interested in "reducing" the degree). In our case, the extra cost of field operations is more than covered by what it costs us to make such commitments plus the proof of commitment opening (Merkle proof + FRI).
3. To see a related use case from ConsenSys, they explain it here. In summary, they achieve a 200x improvement in verifying a large number of hashes.
4. The only thing that is not known in precision (at this moment) is from how many lookups/permutations/connections it becomes more efficient to use GKR than the normal approach. It seems that we will only know this accurately once we have an optimal implementation of what is needed: multivariate polynomial functionality, sumcheck, and GKR.

The only problem I see right now with this is that we don't have anything implemented for what is needed, and it would take weeks to have the initial numbers to know if it is indeed a significant improvement or not.