# 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:

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:

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:

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