2
$\begingroup$

From the PLONK paper.

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

enter image description here

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

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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$ $\endgroup$
    – user93353
    May 5 at 23:11
  • $\begingroup$ 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? $\endgroup$
    – user93353
    May 5 at 23:13
  • $\begingroup$ Is $a =\mathbf g^n$ done separately outside the loop? $\endgroup$
    – user93353
    May 5 at 23:23
  • $\begingroup$ 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 $\endgroup$
    – user93353
    May 6 at 3:06
  • 1
    $\begingroup$ 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]$. $\endgroup$
    – Daniel S
    May 6 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.