Permutation Argument and Copy constraints

Recall our discussion on the recursive constraints $f_1,f_2,f_3$ and $f_4$ for our squared Fibonacci example. What we wanted to achieve essentially was to ensure that some values (input or output) in a previous row were re-used in a subsequent row. This is nothing else than what is commonly known as the "wiring" of a circuit: an input wire may be linked to multiple gates, or the output wire of a gate can be the input of another. Mathematically we can think of wiring as a partition of positions in the table representing the circuit into equivalence classes (defined by equality). Consider the following image. Here we can see the 4 partitions as different colors both on the table and on the circuit.

Exercise 14

Compute a dictionary encoding a permutation over the three columns $a,b,c$. That is, compute a mapping from $1,2,\cdots ,12$ to $1,2,\cdots ,12$ that encodes the equivalence relation of the wiring between the three columns. For example $2\to 5$ and $5\to 2$ because 5 is the first position ($(4+1)$) of the second column.

sigma = {}
#First input
sigma[1] = 1

#First cycle
sigma[2] = 5
sigma[5] = 2

#Solve here!

If implemented correctly, your permutation should pass the following checks.

print("Length should be 12:", len(sigma) == 12)
print("There should be no repeated elements in the domain:", len(set(sigma.keys())) == 12 ) 
print("Both the image and domain should be the indexes from 1 to 12", set(sigma.keys()) == set(range(1,13)) == set(sigma.values()))
print("The cycle (3,4+2,8+1) should be in sigma:" , sigma[3] == 4+2 and sigma[4+2] == 8+1 and sigma[8+1] == 3)

The mathematical property we want to check for a given function $f:I\to \mathbb{F}$ is the following:

$$\mathrm{\forall }i\in I:f(i)=f(\sigma (i))$$

If this holds, we know that all values in our equivalence classes are equal. We can in fact check this for our permutation $\sigma$ and our three columns $a,b,c$ as follows.

def get_wire_value(pos):
    if 1 <= pos <= n:               # column a
        return a(ω**pos)
    elif n+1 <= pos <= 2*n:         # column b
        return b(ω**(pos - n))
    elif 2*n+1 <= pos <= 3*n:       # column c
        return c(ω**(pos - 2*n))


for i in range(1, 3*n + 1):
  assert get_wire_value(i) == get_wire_value(sigma[i])

Now the question is, how does the prover convince the verifier that this holds without sharing all intermediate computation values?

One simple way to achieve this is to run the equality testing protocol for:

$$f\circ \sigma -f=0$$

over the domain $\mathrm{\Omega }$ and an interpolated version of $\sigma$. Unfortunately, this solution is inefficient since the composition of two polynomials of degree $n$ has degree of about $n^2$. For instance if we compose $a$ and $b$ we obtain a polynomial of degree 9 (why?):

a(b)

Instead, we are going to introduce a new protocol to approach this check in an efficient way. Fundamentally, what we want to do is to capture the "for all" quantifier where we check $f(\sigma (i))$ with $f(i)$ using a product, in a way that we avoid computing the costly polynomial composition.