Connection arguments

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

What is a connection argument?

Given a vector \(a = ( a_1 , \dots , a_n) \in \mathbb{F}_n\) and a partition \({\large{\S}} = \{ S_1, \dots , S_t \}\) of \([n]\), we say “\(a\) \(\textit{copy-satisfies}\) \({\large{\S}}\)” if for each \(S_k \in {\large{\S}}\), we have that \(a_i = a_j\) whenever \(i, j \in S_k\) , with \(i, j \in [n]\) and \(k \in [t]\).

Moreover, we say that a protocol \((\mathcal{P}, \mathcal{V})\) is a connection argument if the protocol can be used by \(\mathcal{P}\) to prove to \(\mathcal{V}\) that a vector \(\textit{copy-satisfies}\) a partition of \([n]\).

Info

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 \({\large{\S}} = \{\{2\}, \{1, 3, 5\}, \{4, 6\}\}\) be a specified partition of \([6]\).

Observe the two columns depicted below:

\[ \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 \(\mathtt{a}\ \textit{copy-satisfies}\ {\large{\S}}\) because \(\mathtt{a}_1 = \mathtt{a}_3 = \mathtt{a}_5 = 3\) and \(\mathtt{a}_4 = \mathtt{a}_6 = 1\).

Observe that, since the singleton \(\{2\}\) is in \({\large{\S}}\), then \(\mathtt{a}_2\) is not related to any other element in \(\mathtt{a}\).

Also, the vector \(\mathtt{b}\) does not \(\textit{copy-satisfies}\ {\large{\S}}\) because \(\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 = \langle g \rangle\) and \(\texttt{N}\) is the length of the execution trace.

Given a polynomial \(\texttt{a}\) and a partition \({\large{\S}}\), suppose we want to write in PIL a constraint attesting to the \(\textit{copy-satisfiability}\) of a certain \({\large{\S}}\).

We first construct a permutation \(\sigma : [n] \to [n]\) such that for each set \(S_i \in {\large{\S}}\), we have that \(\sigma({\large{\S}})\) contains a cycle of all elements of \(S_i\).

In the above example, we would have \(\sigma = (5, 2, 1, 6, 3, 4)\). So then, we construct a polynomial \(S_a\) that encodes \(\sigma\) in the exponent of \(g\). That is:

\[ S_{\texttt{a}}(g^i) = g^{\sigma(i)} \]

for \(i \in [n]\).

In the PIL context, the previous connection argument between a column \(\texttt{a}\) and a column \(\texttt{SA}\), encoding the values of \(S_{\texttt{a}}\), can be declared using the keyword \(\texttt{connect}\) using the syntax: \(\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.

Info

The column \(\texttt{SA}\) does not need to be declared as a constant polynomial. The connection argument will still hold 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 \(a_1, \dots , a_k\) in \(\mathbb{F}^n\) and a partition \({\large{\S}} = \{S_1,...,S_t\}\) of \([kn]\), we say \(a_1,...,a_k\) \(\textit{copy-satisfy}\ {\large{\S}}\) if for each \(S_m \in {\large{\S}}\), we have that \(a_{{l_1},i} = a_{{l_2},j}\) whenever \(i,j \in S_m\), with \(i,j \in [n]\), \(l_1, l_2 \in [k]\) and \(m \in [t]\).

For example, say that we have \({\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 \(\texttt{a}, \texttt{b}, \texttt{c}\) that copy-satisfies \({\large{\S}}\).

We reduce this problem to the one column case by thinking of the permutation \(\sigma\) as applied to the concatenation of column \(\texttt{a}\), then \(\texttt{b}\) and finally \(\texttt{c}\).

So, the permutation \(\sigma\) that makes \(\texttt{a}\), \(\texttt{b}\) and \(\texttt{c}\) copy-satisfy \({\large{\S}}\) is \((1, 9, 2, 3, 5, 6, 10, 11, 4, 7, 8, 12)\).

In this case we construct polynomials \(S_{\texttt{a}}\), \(S_{\texttt{b}}\) and \(S_c\) such that:

\[ 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 \(k_1, k_2 \in \mathbb{F}\) are introduced here as a way of obtaining more elements (in a group \(G\) of size \(n\)) and enabling correct encoding of the \([3n] \to [3n]\) permutation \(\sigma\).

See GWC19 for more details on this encoding.

The below table shows how to compute the polynomials \(\texttt{SA}\), \(\texttt{SB}\) and \(\texttt{SC}\) encoding the permutation of the above example:

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 };