A permutation argument is a proof that two lists hold the same elements, but possibly in a different order. For example, [2,3,1] is a permutation of [1,2,3] and vice-versa.

The permutation argument is useful for proving one list is a sorted version of another. That is, if list B has the same elements of list A and the elements of B are sorted, then we know the prover correctly sorted A.

To determine if two lists are the same, we typically sort them and compare them element-wise.

However, to know that a list is sorted, we need to check that 1) the elements are in order and 2) the output of the sorting algorithm contains the same elements as the inputs.

This creates a circular dependency -- to know that one list is a permutation of the other, we have to know their sorted versions are identical. But to know that the sorting algorithms were executed properly, we have to know the output of the sort is a permutation of the input.

This isn't a problem in regular code, but in ZK we must constrain every step of the computation.

We’ve already shown how to prove a list is sorted. This chapter focuses on proving two lists are permutations of each other.

Option 1: Writing constraints for a sorting algorithm

In an earlier chapter, we showed how to write constraints for the Selection Sort algorithm. The Selection Sort algorithm runs in $\mathcal{O}(n^2)$ time, so it will have $\mathcal{O}(n^2)$ constraints. We could use a more efficient algorithm like merge sort to accomplish the same thing in $\mathcal{O}(n \log n)$ constraints, but better solutions exist as we will soon see.

Option 2: Attempt to constrain a 1-to-1 mapping directly

One can try to directly write a circuit that is satisfied if and only if one list is a permutation of the other. In other words, each element in one list has a matching element in the other list and vice-versa.