Skip to main content
This document describes the connection arguments and how they are used in Polynomial Identity Language.

​
What is a connection argument?

Given a vector a=(a1,…,an)∈Fna = ( a_1 , \dots , a_n) \in \mathbb{F}_n and a partition §={S1,…,St}{\large{\S}} = \{ S_1, \dots , S_t \} of [n][n], we say ”aa copy-satisfies\textit{copy-satisfies} §{\large{\S}}” if for each Sk∈§S_k \in {\large{\S}}, we have that ai=aja_i = a_j whenever i,j∈Ski, j \in S_k , with i,j∈[n]i, j \in [n] and k∈[t]k \in [t]. Moreover, we say that a protocol (P,V)(\mathcal{P}, \mathcal{V}) is a connection argument if the protocol can be used by P\mathcal{P} to prove to V\mathcal{V} that a vector copy-satisfies\textit{copy-satisfies} a partition of [n][n].
We use the term “connection” instead of “copy-satisfaction” because the argument is used in PIL in a more general sense than in the original definition given in GWC19.

​
Example

Let §={{2},{1,3,5},{4,6}}{\large{\S}} = \{\{2\}, \{1, 3, 5\}, \{4, 6\}\} be a specified partition of [6][6]. Observe the two columns depicted below:  a 393131 b 397131(Table 1)\begin{aligned} \begin{array}{|c|c|}\hline \texttt{ a }\\ \hline \text{3}\\ \text{9}\\ \text{3}\\ \text{1}\\ \text{3}\\ \text{1}\\ \hline \end{array} \end{aligned} \hspace{0.2cm} \begin{aligned} \begin{array}{|c|c|}\hline \texttt{ b }\\ \hline \text{3}\\ \text{9}\\ \text{7}\\ \text{1}\\ \text{3}\\ \text{1}\\ \hline \end{array} \end{aligned} \tag{Table 1} The vector a copy-satisfies §\mathtt{a}\ \textit{copy-satisfies}\ {\large{\S}} because a1=a3=a5=3\mathtt{a}_1 = \mathtt{a}_3 = \mathtt{a}_5 = 3 and a4=a6=1\mathtt{a}_4 = \mathtt{a}_6 = 1. Observe that, since the singleton {2}\{2\} is in §{\large{\S}}, then a2\mathtt{a}_2 is not related to any other element in a\mathtt{a}. Also, the vector b\mathtt{b} does not copy-satisfies §\textit{copy-satisfies}\ {\large{\S}} because b1=b5=3≠7=b3\mathtt{b}_1 = \mathtt{b}_5 =3 \not= 7 = \mathtt{b}_3. In the context of programs, connection arguments can be written easily in PIL by introducing a column associated with the chosen partition. This is also done in [GWC19]. Recall that column values are evaluations of a polynomial at G=⟨g⟩G = \langle g \rangle and N\texttt{N} is the length of the execution trace. Given a polynomial a\texttt{a} and a partition §{\large{\S}}, suppose we want to write in PIL a constraint attesting to the copy-satisfiability\textit{copy-satisfiability} of a certain §{\large{\S}}. We first construct a permutation σ:[n]→[n]\sigma : [n] \to [n] such that for each set Si∈§S_i \in {\large{\S}}, we have that σ(§)\sigma({\large{\S}}) contains a cycle of all elements of SiS_i. In the above example, we would have σ=(5,2,1,6,3,4)\sigma = (5, 2, 1, 6, 3, 4). So then, we construct a polynomial SaS_a that encodes σ\sigma in the exponent of gg. That is: Sa(gi)=gσ(i)S_{\texttt{a}}(g^i) = g^{\sigma(i)} for i∈[n]i \in [n]. In the PIL context, the previous connection argument between a column a\texttt{a} and a column SA\texttt{SA}, encoding the values of SaS_{\texttt{a}}, can be declared using the keyword connect\texttt{connect} using the syntax: a connect {SA}\texttt{a}\ \texttt{connect}\ \{\texttt{SA}\}. 
include "config.pil";

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

{a} connect {SA};
A valid execution trace for this example was shown in Table 1 above.
The column SA\texttt{SA} does not need to be declared as a constant polynomial. The connection argument still holds true even if it is declared as committed.

​
Multiple copy satisfiability

Connection arguments can be extended to several columns by encoding each column with a “part” of the permutation. Informally, the permutation is now able to span across the values of each of the involved polynomials in a way that the cycles formed in the permutation must contain the same value.

​
Multi-column copy satisfiability

Given vectors a1,…,aka_1, \dots , a_k in Fn\mathbb{F}^n and a partition §={S1,...,St}{\large{\S}} = \{S_1,...,S_t\} of [kn][kn], we say a1,...,aka_1,...,a_k copy-satisfy §\textit{copy-satisfy}\ {\large{\S}} if for each Sm∈§S_m \in {\large{\S}}, we have that a‘l1‘,i=a‘l2‘,ja_{`{l_1}`,i} = a_{`{l_2}`,j} whenever i,j∈Smi,j \in S_m, with i,j∈[n]i,j \in [n], l1,l2∈[k]l_1, l_2 \in [k] and m∈[t]m \in [t]. For example, say that we have §={{1},{2,3,4,9},{5},{6},{7,10},{8,11},{12}}{\large{\S}} = \{\{1\}, \{2,3,4,9\}, \{5\}, \{6\}, \{7,10\}, \{8,11\}, \{12\}\}. Then, the below table depicts an execution trace for three columns a,b,c\texttt{a}, \texttt{b}, \texttt{c} that copy-satisfies §{\large{\S}}. An execution trace subject to a connection argument We reduce this problem to the one column case by thinking of the permutation σ\sigma as applied to the concatenation of column a\texttt{a}, then b\texttt{b} and finally c\texttt{c}. So, the permutation σ\sigma that makes a\texttt{a}, b\texttt{b} and c\texttt{c} copy-satisfy §{\large{\S}} is (1,9,2,3,5,6,10,11,4,7,8,12)(1, 9, 2, 3, 5, 6, 10, 11, 4, 7, 8, 12). In this case we construct polynomials SaS_{\texttt{a}}, SbS_{\texttt{b}} and ScS_c such that: Sa(gi) =gσ(i), Sb(gi) =k1⋅gσ(n+i), Sc(gi) =k2⋅gσ(2n+i)S_{\texttt{a}}(g^i)\ = g^{\sigma(i)},\ S_{\texttt{b}}(g^i)\ = k_1 \cdot g^{\sigma(n+i)},\ S_{\texttt{c}}(g^i)\ = k_2 \cdot g^{\sigma(2n+i)} where k1,k2∈Fk_1, k_2 \in \mathbb{F} are introduced here as a way of obtaining more elements (in a group GG of size nn) and enabling correct encoding of the [3n]→[3n][3n] \to [3n] permutation σ\sigma. See [GWC19] for more details on this encoding. The below table shows how to compute the polynomials SA\texttt{SA}, SB\texttt{SB} and SC\texttt{SC} encoding the permutation of the above example: Multi-column connection argument’s valid execution trace The PIL code for this example is easily written as follows: 
include "config.pil";

namespace Connection(%N);
pol commit a, b, c;
pol constant SA, SB, SC;

{ a, b, c } connect { SA, SB, SC };