Zk whiteboard session 3

날짜 : 2024-09-20 16:18

주제: #zk

---

메모:

construct a poly-IOP called Plonk

Plonk + PCS(polynomial commitment scheme) => SNARK

Plonk를 만들기 위한 과정

1. Finite Field p:

   • 유한체 $p$는 소수 $p$를 정의하는 유한체 $\mathbb{F}_p$를 의미합니다. 이 유한체에서 다항식 연산이 이루어집니다. 모든 계산은 $p$로 나눈 나머지(모듈로 연산)로 수행됩니다.

2. $r$는 유한체 $\mathbb{F}_p$에서 선택된 값:

   • $r$는 임의로 선택된 유한체 $\mathbb{F}_p$의 한 원소입니다. 이는 일반적으로 다항식 $f(x)$의 특정 평가를 위해 임의로 선택된 값입니다.

3. $Pr[f(r) = 0] \leq \frac{d}{p}$:

   • 이 수식은 다항식 $f(x)$이 $r$에서 0일 확률이 $\frac{d}{p}$보다 작거나 같다는 의미입니다. 여기서 $d$는 다항식 $f(x)$의 차수입니다.
   • Schwartz-Zippel Lemma에서 유래한 이 식은 다항식의 제로 여부를 검사할 때 자주 사용됩니다. 이 레마에 따르면, 임의의 다항식 $f(x)$가 0이 아닐 경우 $f(x)$이 유한체 $\mathbb{F}_p$에서 임의로 선택된 값 $r$에 대해 0일 확률은 $\frac{d}{p}$보다 작거나 같다는 것을 의미합니다.
   • 쉽게 말하면, $f(x)$가 0이 아닌 다항식이라면, 임의로 선택된 값 $r$에서 $f(r)$이 0이 될 확률이 매우 낮다는 뜻입니다. $d$는 다항식의 차수이고, $p$는 유한체의 크기이기 때문에, 체의 크기가 커질수록 이 확률은 더욱 작아집니다.

4. Zero Test:

   • 다항식이 0인지 아닌지를 확인하는 제로 테스트입니다. 이때 다항식 $f(x)$가 $r$에서 0이라면, 우리는 이를 0으로 평가할 수 있습니다. 반면에, $f(x)$가 0이 아닐 확률은 위 식에서 볼 수 있듯이 매우 낮습니다.
   • 이 기법을 통해 Polynomial Commitment 또는 Polynomial IOP에서 다항식이 실제로 0인지 검증할 수 있습니다. 다항식 커밋 시스템에서, 프로버가 특정 다항식이 0이라고 주장할 때, 검증자는 임의의 값 $r$에서 다항식을 평가하여 그 결과가 0인지 확인합니다. 이 방법은 효율적인 검증을 가능하게 합니다.

$$ Pr[f(r)=0]≤dpPr[f(r) = 0] \leq \frac{d}{p}Pr[f(r)=0]≤pd​ $$

efficient poly-IOPs for the following tasks

zero test, sum-test, prod-test

Zero test

Lemma:

$f(x)$가 집합 $H$에서 0이 되는 것은, $f(x)$가 다항식 $x^k - 1$로 나눠떨어질 때와 같은 조건이다. 즉,

여기서 $H = {1, w, w^2, \dots, w^{k-1}}$이고, $w$는 $k$차 단위근(즉, $w^k = 1$)입니다.

증명:

• 필요조건 (Necessity):
  만약 $f(x)$가 집합 $H$의 모든 원소에서 0이라면, $f(x)$는 다음과 같은 형태로 표현될 수 있습니다:

  $$

  f(x) = (x - 1)(x - w)(x - w^2) \dots (x - w^{k-1}) g(x)

  여기서 $g(x)$는 임의의 다항식입니다. 이는 $f(x)$가 $x^k - 1 = (x - 1)(x - w)(x - w^2) \dots (x - w^{k-1})$로 나눠떨어진다는 의미입니다. 따라서, $f(x)$는 $x^k - 1$로 나눠떨어집니다.

• 충분조건 (Sufficiency):
  반대로, $f(x)$가 $x^k - 1$로 나눠떨어진다면, 우리는 $f(x)$를 다음과 같이 쓸 수 있습니다:

  $$

  f(x) = (x^k - 1) q(x)

  여기서 $q(x)$는 나머지 다항식입니다. $x^k - 1$은 집합 $H$에서 0을 만족하는 다항식이기 때문에, $f(x) = 0$은 $H$의 모든 원소에서 참이 됩니다. 즉, $f(x)$는 $H$의 모든 원소에서 0입니다.

Zero Test에서의 활용:

이 레마는 Zero Test에서 매우 유용하게 사용됩니다. Zero Test는 다항식 $f(x)$가 특정 집합 $H = {1, w, w^2, \dots, w^{k-1}}$에서 0인지 확인하는 과정입니다. 만약 $f(x)$가 $x^k - 1$로 나눠떨어진다면, 우리는 $f(x)$가 집합 $H$의 모든 원소에서 0이라고 신뢰할 수 있습니다.

• Prover는 $f(x)$가 $x^k - 1$로 나눠떨어진다는 증명을 Verifier에게 제시합니다.
• Verifier는 이를 확인하여 $f(x)$가 실제로 $H$의 모든 원소에서 0인지 검증할 수 있습니다.

$q(x)$의 역할:

주어진 다항식에서 $q(x)$는 다음과 같이 정의됩니다:
$$ q(x) = \frac{f(x)}{x^k - 1} $$

이 다항식은 $f(x)$가 $x^k - 1$로 나눠떨어질 때의 몫입니다. 만약 $f(x)$가 $x^k - 1$로 정확하게 나눠떨어지면, 나머지가 0이므로 $q(x)$는 나눗셈의 결과로 얻어진 몫이 됩니다.

---

Plonk (a poly-IOP for a general circuit)

step 1 : compile circuit to a computation trace (gate fan-in : 2)

encode all inputs, encodes all wires
prover과 위 과정을 수행해야 하는데, 여기서 FFT를 씀

step 2 : proving validity of P

Prover needs to prove that P is a correct computation trace :
1) P가 인풋을 제대로 인코딩 했는지
2) 모든 게이트가 정확히 작동 하는지(and면 and연산, mul이면 mul연산)
3) 와이어링이 제대로 되었는지(input이 두번 들어갈 수 도 있고, output이 input이 될 수 있음)
4) 마지막 게이트의 아웃풋은 0이다

KZG Polynomial 순서

1. 다항식 커밋

프로버가 다항식 $P(x) = 2 + 3x$을 커밋한다고 가정해 봅시다.

다항식 $P(x) = 2 + 3x$는 차수 1의 다항식입니다.
신뢰 설정(CRS): $g$와 $g^s$가 주어집니다.
예를 들어, $g = 5$, $s = 4$라고 하겠습니다.
그러면 CRS는 $\{g = 5, g^s = 5^4 = 625\}$입니다.

이제 다항식 $P(x)$의 커밋 값을 계산합니다.

여기서:

• $a_0 = 2$ (상수항),
• $a_1 = 3$ (x의 계수).

따라서 커밋 $C$는 다음과 같습니다:

이제 계산을 해보면:

따라서 커밋 $C$는:

따라서 프로버는 다항식 $P(x) = 2 + 3x$에 대한 커밋 $C = 6103515625$를 생성합니다.

---

2. 열람 요청

이제 베리파이어가 $P(x)$에서 특정한 지점 $z = 2$에서의 값을 알고 싶다고 요청합니다.
프로버는 $z = 2$에서 $P(2)$의 값을 계산합니다:

따라서 프로버는 $P(2) = 8$이라는 값을 베리파이어에게 보냅니다.

---

3. 열람 증명 생성

베리파이어가 이 값이 실제 다항식 $P(x)$에서 계산된 것인지 확인할 수 있도록 프로버는 잉여 다항식 $H(x)$를 생성해야 합니다. 잉여 다항식 $H(x)$는 다음과 같이 정의됩니다:

$P(x) = 2 + 3x$이므로, $P(2) = 8$을 대입해 잉여 다항식을 계산합니다:

따라서 $H(x) = 3$은 상수 다항식입니다. 이제 프로버는 $H(x) = 3$을 커밋합니다.

커밋 값은:

따라서 $H = 125$입니다.

---

4. 검증

베리파이어는 $P(2) = 8$이 정확한지 검증해야 합니다. 이를 위해 검증식:

를 사용합니다. 각 항을 계산해 봅시다:

• $g^{P(2)} = 5^8 = 390625$,
• $s - z = 4 - 2 = 2$,
• $g^{s - z} = g^2 = 5^2 = 25$,
• $H = 125$이므로 $(g^{s - z})^H = 25^3 = 15625$.

따라서 좌변은:

우변은:

좌변과 우변이 일치하므로, 베리파이어는 $P(2) = 8$이 정확한 값임을 확신할 수 있습니다.

연결문서