# Is the permuation check range in the PLONK Paper incorrect?

From the PLONK paper.

On pages 19 & 20, the paper describes the prescribed permutation check in PLONK.

------------------------------------------------------------------------------------------------

My question is about the Step 3 in the protocol which I have marked in red

I am interpreting $$1 \le j < i$$ as $$j =1$$ to $$j = i-1$$

So the $$\prod$$ equation becomes $$Z(\mathbf{g}^i) = \prod_{j=1}^{j=i-1} f'(\mathbf{g}^j)/g'(\mathbf{g}^j)$$

I think this should be $$\prod_{j=1}^{j=i}$$ instead of $$\prod_{j=1}^{j=i-1}$$

My reasoning is as below shown with an example where $$H$$ is a subgroup of 4 elements, so $$n = 4$$ & $$[n] = \{1, 2, 3, 4\}$$ & $$H = \{ \mathbf{g}, \mathbf{g}^2, \mathbf{g}^3, \mathbf{g}^4\}$$

I think the end result in the proof in this case is to prove that

$$f'(\mathbf{g})/g'(\mathbf{g}) \star f'(\mathbf{g}^2)/g'(\mathbf{g}^2) \star f'(\mathbf{g}^3)/g'(\mathbf{g}^3) \star f'(\mathbf{g}^4)/g'(\mathbf{g}^4) = 1$$

This has 4 $$f'/g'$$ terms multiplied with each other.

In the case of $$n=4$$, the prod range becomes So the $$\prod$$ equation becomes $$\prod_{j=1}^{j=4-1}$$ which is $$\prod_{j=1}^{j=3}$$

So $$j=1$$ to $$j=3$$ will get us only 3 terms multiplied by each other. But we need 4 terms so the prod range needs to be $$\prod_{j=1}^{j=i}$$ instead of $$\prod_{j=1}^{j=i-1}$$

Or am I mistaken?

## 1 Answer

The argument in the paper is correct. Verifying (a) confirms that $$Z(g)=1$$, verifying $$Z(a)f'(a)=g'(a)Z(a\mathbf g)$$ for $$a=\mathbf g,\mathbf g^2,\mathbf g^3\ldots \mathbf g^{n-1}$$ then inductively confirms that $$Z(\mathbf g^i)=\prod_{j=1}^{i-1}\frac{f'(\mathbf g^j)}{g'(\mathbf g^j)}$$ for $$i=2,\ldots,n$$.

Finally, verifying $$Z(a)f'(a)=g'(a)Z(a\mathbf g)$$ for $$a=\mathbf g^n$$ confirms that $$Z(\mathbf g^n)f'(\mathbf g^n)=g'(\mathbf g^n)Z(\mathbf g^{n+1})$$ which by the group order and also using the above inductive result confirms that $$f'(\mathbf g^n)\prod_{j=1}^{n-1}\frac{f'(\mathbf g^j)}{g'(\mathbf g^j)}=g'(\mathbf g^n)Z(\mathbf g)$$ which is the same as $$\prod_{j=1}^n\frac{f'(\mathbf g^j)}{g'(\mathbf g^j)}=1$$ as required.

• from your reply - "for $a=\mathbf g^n$ confirms that". However, if we use $\prod_{j=1}^{j=i-1}$, $a$ never becomes $\mathbf g^n$. As you wrote earlier, the values of $a$ which are used in 5(b) are $a=g,g^2,G^3\ldots, g^{n-1}$. Only if we use $\prod_{j=1}^{j=i}$ will 5(b) be tried with $\mathbf g^n$ May 5 at 23:11
• Or are you saying that after 5(a) & 5(b) are done for $\prod_{j=1}^{j=i-1}$, then there is a final step where 5(b) is done for $a = \mathbf g^n$. If so, why is this not a part of the original loop? May 5 at 23:13
• Is $a =\mathbf g^n$ done separately outside the loop? May 5 at 23:23
• Also,I found this in the next page they have this - imgur.com/ICzqPa2.png - In 5(b) - they don't show it for all $i \in [n]$, they show it only for upto $n-1$. So when they say "inductively' does it mean that they are saying because it's true for $i = 2$ to $n-1$, by induction, it's also true for $i = n$? - i.e. they are talking about proof by induction May 6 at 3:06
• In 5 b) the statement $Z(a)f'(a)=g'(a)Z(a\mathbf g)$ is checked for all $a\in H$ which is $a=\mathbf g^i$ for all $i\in[n]$. May 6 at 9:35