Cyclicity in PIL

This document describes how to introduce cyclicity to execution traces in Polynomial Identity Language.

In order to synchronize the execution trace of a given program with the subgroup \(G\) of the multiplicative group \(\mathbb{F}^*\), over which interpolation is performed, an extra constant polynomial (or precompiled column) is added to the trace.

An explanation of what this group \(G = \langle g \rangle\) is, and why it is naturally a cyclic group, was discussed in the Basic Concepts section of the zkProver.

Non-cyclic SM example¶

Consider a program with the following execution trace of length \(\%\texttt{N} = 4\);

\[ \begin{aligned}\begin{array}{|l|c|c|}\hline \texttt{row} &\ \mathtt{a} & \mathtt{b} \\ \hline \ \text{ 0} & \ \texttt{1} & \texttt{1} \\ \hline \ \text{ 1} & \ \texttt{0} & \texttt{2} \\ \hline \ \text{ 2} & \texttt{-1} & \texttt{2} \\ \hline \ \text{ 3} & \ \texttt{1} & \texttt{1} \\ \hline \end{array} \end{aligned} \]

Denote the cyclic group over which interpolation is carried out as \(G = \{ g, g^2, g^3, g^4 = 1 \} \subset \mathbb{F}\).

Info

We use the symbols \(\texttt{a}\) and \(\texttt{b}\), that denote columns of the execution trace, to also denote the corresponding polynomials resulting from interpolation. The columns \(\texttt{a}\) and \(\texttt{b}\) are best expressed as arrays,

\[ \texttt{a} = [1,0,-1,1] \ \text{and}\ \texttt{b} = [1,2,2,1] \]

while the respective polynomials that result from interpolation, should rather be denoted differently, say with, \(P(X)\) and \(Q(X)\), such that for each row index \(i\),

\[ P(g^i) = \texttt{a}[i]\ \ \text{and}\ \ Q(g^i) = \texttt{b}[i] \tag{eqn} \]

But in order to keep the PIL code simple and easily relatable to the execution trace, we replace the \(P\) and \(Q\) with \(\texttt{a}\) and \(\texttt{b}\), respectively. The above \(\text{eqn}\) will therefore be seen written as,

\[ \texttt{a}(g^i) = \texttt{a}[i]\ \ \text{and}\ \ \texttt{b}(g^i) = \texttt{b}[i]. \]

For the sake of convenience, in this particular example, the row index starts at \(0\) just so it syncs with the normal array indexing.

Constraints and cyclicity¶

Observe that the column \(\mathtt{a}\) only takes on the values; \(0\), \(1\) or \(−1\); and these values satisfy the constraint,

\[ (\mathtt{a} + 1)\cdot\mathtt{a}\cdot(\mathtt{a} - 1) = 0, \]

while the values of \(\texttt{b}\) are such that

\[ \texttt{b}' = \texttt{a} + \texttt{b}. \]

This second constraint should be interpreted as,

\[ \texttt{b}'(g^{i}) = \texttt{a}(g^i) + \texttt{b}(g^i). \]

However, this second constraint is satisfied for every row except for the last one. That is, \(\texttt{b}'(g^{3}) \not= \texttt{a}(g^3) + \texttt{b}(g^3)\). Let us proof this inequality.

But we first check one of the other cases. In particular, the case for \(i = 2\).

Recall that \(\texttt{b}'(g^{i}) = \texttt{b}(g\cdot g^{i}) = \texttt{b}(g^{i+1})\) by definition. Then,

\[ \text{LHS} = \texttt{b}'(g^{2}) = \texttt{b}(g\cdot g^{2}) = \texttt{b}(g^3) = b[3] = 1 \ \ \text{and} \\ \text{RHS} = \texttt{a}(g^{2}) + \texttt{b}(g^{2}) = a[2] + b[2] = -1 + 2 = 1 \]

This proves that the second constraints holds true for the case \(i = 2\).

Now for the case \(i = 3\).

Note that \(g^{4} = 1 = g^0\), and again by definition, \(\texttt{b}'(g^{3}) = \texttt{b}(g\cdot g^{3}) = \texttt{b}(g^{4}) = \texttt{b}(g^{0})\). So then,

\[ \text{LHS} = \texttt{b}'(g^{3}) = \texttt{b}(g\cdot g^{3}) = \texttt{b}(g^{0}) = \texttt{b}[0] = 1\ \ \text{and} \\ \text{RHS} =\ \texttt{a}(g^3) + \texttt{b}(g^3) =\ \texttt{a}[3] + \texttt{b}[3] = 1 + 1 = 2. \]

This proves that second constraint is not satisfied for \(i = 3\). And therefore the execution trace is not cyclic.

Introducing cyclicity¶

The execution trace can be made cyclic by introducing a selector polynomial, call it \(\texttt{SEL}\), such that its column values are \(1\) in every row except the last, where it’s \(0\),

i.e., \(\texttt{SEL}[i] = 1\) for all \(i \in \{ 0, 1, 2 \}\), otherwise, \(\texttt{SEL}[3] = 0\).

The above execution trace is now modified to the following:

\[ \begin{aligned} \begin{array}{|l|c|c|c|}\hline \texttt{row} & \ \mathtt{a} & \mathtt{b} & \mathtt{SEL} \\ \hline \ \text{ 0} & \ \texttt{1} & \texttt{1} & \texttt{1} \\ \hline \ \text{ 1} & \ \texttt{0} & \texttt{2} & \texttt{1} \\ \hline \ \text{ 2} & \texttt{-1} & \texttt{2} & \texttt{1}\\ \hline \ \text{ 3} & \ \texttt{1} & \texttt{1} & \texttt{0}\\ \hline \end{array} \end{aligned} \]

Given these adjustments, we note that;

For all \(i \in \{ 0, 1, 2, 3 \}\), the constraint \((\mathtt{a} + 1)\cdot\mathtt{a}\cdot(\mathtt{a} - 1) = 0\) still holds true.
For all \(i \in \{ 0, 1, 2 \}\), the constraint \(\texttt{b}' = \texttt{a} + \texttt{b}\) holds true as before. And, even if the constraint is adjusted to \(\texttt{b}' = \texttt{SEL} \cdot (\texttt{a} + \texttt{b})\), it still holds true for all \(i \in \{ 0, 1, 2 \}\).
For \(i = 3\), we would like to have \(\texttt{b}'(g^3) = \texttt{b}(g^0) = \texttt{b}[0] = 1\). Note that \(\texttt{SEL}[3] = 0\), for this particular case. And hence,

\[ \texttt{SEL} \cdot (\texttt{a} + \texttt{b}) = 0 \cdot (\texttt{a} + \texttt{b}) = 0. \]

All-in-all, the adjusted execution trace attains cyclicity if the second constraint is set to:

\[ \texttt{b}' =\ \texttt{SEL} \cdot (\texttt{a} + \texttt{b})\ +\ (1 - \texttt{SEL}). \]

As seen earlier, for the case \(i = 3\),

\[ \text{LHS} = \texttt{b}'(g^{3}) = \texttt{b}(g\cdot g^{3}) = \texttt{b}(g^{0}) = \texttt{b}[0] = 1 \]

and now,

\[ \text{RHS}\ =\ \texttt{SEL}(g^3)\cdot \big(\texttt{a}(g^3) + \texttt{b}(g^3)\big) +\ \big(1 - \texttt{SEL}(g^3)\big)\ \\ =\ \texttt{SEL}[3] \cdot \big( \texttt{a}[3] + \texttt{b}[3] \big) +\ (1 - \texttt{SEL}[3])\ \text{ } \\ =\ 0\cdot \big( 1 + 1 \big) + \big( 1 - 0 \big) =\ 0 + 1 = 1.\quad \]

The valid PIL code, with all the adjustments, is as depicted below:
```
namespace CyclicExample(4);

pol commit a, b;
pol constant SEL;
pol carry = (a+1)*a;

carry*(a-1) = 0;
b' = SEL*(b+a) + (1-SEL);
```
For implementation purposes, even as alluded to in the previous section, in order to prevent exposing distinguishing features, a configuration file is used to store the exact length of the program \(\%\texttt{N} = 4\) so that only the symbol \(\texttt{N}\) appears in the PIL code.

Last update: January 17, 2024

Authors: avenbreaks