Permutation arguments

Definition

Given two vectors, $\mathrm{a}=(a_1,...,a_n)$ and $\mathrm{b}=(b_1,...,b_n)$ $\in {\mathbb{F}}_p^n$, the vectors $\mathrm{a}$ and $\mathrm{b}$ are permutations of each other if there exists a bijective mapping $\sigma :[n]\to [n]$ such that $\mathrm{a}=\sigma (\mathrm{b})$, where $\sigma (\mathrm{b})$ is defined by: $$\sigma (\mathrm{b}):=(b_{\sigma (1)},\cdots ,b_{\sigma (n)})$$ A protocol ($\mathcal{P}$,$\mathcal{V}$) is a permutation argument if the protocol can be used by $\mathcal{P}$ to prove to $\mathcal{V}$ that two vectors in ${\mathbb{F}}_p^n$ are a permutation of each other. Unlike inclusion arguments, the two vectors subject to a permutation argument must have the same length.

In the PIL context, the permutation argument between two columns $\mathrm{a}$ and $\mathrm{b}$ can be declared using the keyword is and using the syntax: {$\mathrm{a}$} is {$\mathrm{b}$}. where a and b do not necessarily need to be defined in same programs. like below snippet of permutation code:

include "config.pil"; 

namespace A(%N);
pol commit a, b;

{a} is {b};

namespace B(%N);
pol commit a, b;

{a} is {A.b};

A valid execution trace with the number of rows N=4, for the above example, is shown in the below table. A.a, A.b and B.a are permutations of each other.

Permutation arguments over multiple columns

Permutation arguments in PIL can be written not only over single columns but over multiple columns as well.

That is, given two subsets of committed columns ${\mathrm{a}}_1,\cdots ,{\mathrm{a}}_m$ and ${\mathrm{b}}_1,\cdots ,{\mathrm{b}}_m$ of some program(s), we can write {${\mathrm{a}}_1,\cdots ,{\mathrm{a}}_{\mathrm{m}}$} in {${\mathrm{b}}_1,\cdots ,{\mathrm{b}}_{\mathrm{m}}$} to denote that the rows generated by columns {${\mathrm{b}}_1,\cdots ,{\mathrm{b}}_m$} are a permutation of the rows generated by columns {${\mathrm{a}}_1,\cdots ,{\mathrm{a}}_m$}.

A natural application for this generalization is showing that a set of columns in a program is precisely a commonly known operation such as XOR, where the correct XOR operation is carried out in a distinct program (see the following example).

include "config.pil"; 

namespace Main(%N);
pol commit a, b, c;

{a,b,c} is {in1,in2,xor};

namespace XOR(%N);
pol constant in1, in2, xor;

However, the functionality is further extended by the introduction of selectors in the sense that one can still write a permutation argument even though it is not satisfied over the entire trace of a set of columns, but only over a subset.

Suppose that we are given the following execution traces:

Notice that columns {$\mathrm{a}$,$\mathrm{b}$,$\mathrm{c}$} of the program A and columns {$\mathrm{d}$,$\mathrm{e}$,$\mathrm{f}$} of the program B are permutations of each other only over a subset of the trace.

To still achieve a valid permutation argument over such columns, we have introduced a committed column $\mathrm{sel}$ set to 1 in rows where a permutation argument is enforced, and is 0 elsewhere.

Therefore, the permutation argument is valid only if,

• $\mathrm{sel}$ is correctly computed, and
• the subset of rows chosen by $\mathrm{sel}$ in both programs shows a permutation.

The corresponding PIL code of the previous programs can now be written as follows:

namespace A(4);
pol commit a, b, c;
pol commit sel;

sel {a, b, c} is B.sel {B.e, B.d, B.f};

namespace B(6);
pol commit d, e, f; 
pol commit sel;

The $\mathrm{sel}$ column should be turned on (i.e., $\mathrm{sel}$ set to 1) the same number of times in both programs. Otherwise, a permutation cannot exist between any of the columns, since the resulting vectors would be of different lengths. This allows the use of this kind of argument even if both execution traces do not contain the same amount of rows.