Grand product argument

To motivate the concrete algorithm, consider the following. Assume $h$ is a cryptographically secure hash function. If we compute

$$GP=\prod _{i=1}^n\frac{h(i,f(i))}{h(i,f(\sigma (i)))}$$

we expect to be $GP=1$ if and only if $f(\sigma (i))=f(i)$. One direction is easy to see, for the other one we would conclude that either there was a hash collision or some unlikely scenario arises (details are left as an exercise).

One useful observation is that we can write the $GP$ alternatively like this:

$$GP=\prod _{i=1}^n\frac{h(i,f(i))}{h(i,f(\sigma (i)))}=\prod _{i=1}^n\frac{h(i,f(i))}{h(\sigma (i),f(i))}$$

because the values are in the equivalence class defined by $\sigma$. In fact, the numerator is exactly the same, and the denominator as well: noticed that on the original denominator we had $h(\sigma (i),f(\sigma (i))$ which, if the permutation holds, is equal to $h(\sigma (i),f(i)$. But the advantage of this equivalent representation is that we do not have to explicitely compose the polynomial $f$ with $\sigma$.

Now, in practice we want to have an efficient "hash" function that has the same security properties as before, such that $GP=1$ implies (with high probability) that the permutation property holds. For this we consider the class of functions:

$$h(i,f(i))=i+\beta \cdot f(i)+\gamma$$

for random interactive challenges $\beta$ and $\gamma$. It is possible to show using Schwartz-Zippel that those will behave similar to the cryptographic hash function in our discussion above, but they are efficiently computable (for more details see the original paper).

We will now step by step construct the argument that takes advantage of this. First we start by defining a numerator and denominator functions, and their respective accumulators.

Exercise 15

Compute the numerator using the formula

$$(column-1)\cdot n+i+\beta \cdot f({\omega }^i)+\gamma$$

and the denominator as

$$\sigma (column-1)\cdot n+i+\beta \cdot f({\omega }^i)+\gamma$$

def numerator(i, column,f,sigma,beta, gamma):
#Solve here!    
    return value    

def denominator(i, column,f,sigma,beta, gamma):
#Solve here!
    return value

#Test cases
assert numerator(3,1,a,sigma,42,42) == 87
assert denominator(3,1,a,sigma,42,42) == 90

assert numerator(6,2,b,sigma,42,42) == 94
assert denominator(6,2,b,sigma,42,42) == 91