Connection arguments

The connection arguments is called copy-satisfy in GWC19. As its name, the argument is used to partition the commitment matrix and make the cells of the matrix in same partition contain the same value.

The Polynomial Identity Language (PIL) use **connect ** keyword to express connection arguments.

Definition

Given a vector $a=(a_1,...,a_n)\in {\mathbb{F}}_n$ and a partition $\S =\{S_1,\dots ,S_t\}$ of [n]. If for each $S_k\in \S$, the $a_i=a_j$ whenever $i,j\in S_k$, $i,j\in [n]$ and $k\in [t]$, then the elements whose indices in one $S_k$ are connected(copy-satisfy).

Example

Let $\S =\{\{2\},\{1,3,5\},\{4,6\}\}$ be a specified partition of column with 6 elements. Observe the two columns depicted below:

the column a is copy-satisfy because the indices of elements in $S_2\in \S$ is 1, 3, 5. and $a_1\equiv a_3\equiv a5=3$; the indices of elements in $S_3\in \S$ is 4, 6. and $a_4\equiv a_6=1$.

the column b is not copy-satisfy because the indices of elements in $S_2\in \S$ is 1, 3, 5. but $a_1=3\ne a_3=7$.

Given the column a as above. we can construct a permutation map $\sigma :[n]->[n]$ . Such for each $S_k\in \S$, the map $\sigma$ can make the elements whose indices in $S_k$ form a circle: 1 -> 3, 3 -> 5, 5 -> 1; 4 -> 6, 6 -> 4; 2->2.

In the zero-knowledge proof(ZKP), use the exponent of multiplicative generator($g$) as the value of column SA of $\sigma$ map: $$S{A}_i=g^{\sigma (i)}$$ So in this example, the column a and the column SA as below table:

PIL

In the PIL context, the previous connection argument between a column a and a column SA, encoding the values of $S_a$ as , can be declared using the keyword connect using the syntax a connect {SA}:

the snippet of code as below:

include "config.pil";

namespace Connection(%N); 
pol commit a; 
pol constant SA; 

{a} connect {SA};