KZG Polynomial Commitment

날짜 : 2024-09-21 02:37

주제: #zk

---

메모:

1. 커밋 값 생성 (Recap)

프로버는 다항식 $P(x)$를 커밋했을 때, 아래와 같은 다항식 커밋 $C$를 생성했습니다:

여기서 다항식 $P(x)$는

의 형태로 주어졌습니다. $g$는 생성자, $s$는 신뢰 설정 과정에서 선택된 비밀 값입니다.

---

2. 열람 요청 (Opening Request)

이제 베리파이어가 다항식 $P(x)$의 특정한 지점 $z$에서의 값을 열람하고자 합니다. 예를 들어, 베리파이어는 $P(z)$를 알고 싶어 합니다.

• 프로버의 작업: 프로버는 다항식 $P(x)$의 값 $P(z)$을 계산하고, 그 결과를 베리파이어에게 보냅니다. 그러나 이 값만으로는 베리파이어가 그것이 정말 다항식 $P(x)$에서 계산된 값인지를 알 수 없습니다. 따라서 프로버는 열람 증명(Opening Proof)이라는 추가 정보를 제공해야 합니다.

---

3. 증명 생성 (Proof Generation)

프로버는 $P(z)$의 정확성을 증명하기 위해 잉여 다항식 $H(x)$를 생성합니다. 잉여 다항식 $H(x)$는 다음과 같이 계산됩니다:

여기서 $P(x)$는 프로버가 알고 있는 원래의 다항식이고, $P(z)$는 프로버가 방금 계산한 $z$에서의 값입니다. $H(x)$는 $P(x)$가 실제로 $P(z)$에서 값을 만족하는지 증명하는 역할을 합니다.

이 잉여 다항식 $H(x)$는 다항식의 차수가 $d-1$이 되며, 이를 사용해 베리파이어가 $P(z)$를 검증할 수 있습니다. 프로버는 이 잉여 다항식 $H(x)$의 커밋을 생성하여 베리파이어에게 보냅니다.

---

4. 검증 (Verification)

베리파이어는 프로버가 보낸 $P(z)$와 $H(x)$의 커밋을 검증하여, 프로버가 실제로 $P(x)$를 알고 있는지 확인합니다.

• 검증식: 베리파이어는 다음 검증식을 사용하여 $P(z)$의 정확성을 확인합니다:

이 식에서:

• $g^{P(z)}$는 프로버가 제시한 $P(z)$에서의 값을 대입한 결과입니다.
• $g^{s - z}$는 설정 단계에서 생성된 CRS 중 $g^s$에서 $z$만큼 뺀 값입니다.
• $H$는 프로버가 보낸 잉여 다항식 $H(x)$의 커밋입니다.
• $C$는 초기 다항식 커밋입니다.

---

5. 성공적인 검증

베리파이어는 위 검증식을 계산하여 양쪽이 일치하면, 프로버가 정확한 $P(z)$ 값을 제시했음을 확신하게 됩니다. 이로써 프로버는 $P(z)$가 실제로 다항식 $P(x)$에서 나온 값임을 증명한 것이 됩니다.

---

요약

• 프로버: 다항식 $P(x)$의 특정한 지점 $z$에서 $P(z)$ 값을 계산하고, 잉여 다항식 $H(x)$을 생성하여 열람 증명(Opening Proof)을 만듭니다.
• 베리파이어: 검증식 $g^{P(z)} \cdot (g^{s - z})^H = C$를 사용해, 프로버가 제시한 값 $P(z)$가 실제로 다항식 $P(x)$에서 계산된 것인지를 확인합니다.

1. 커밋 값 생성 (Recap)

프로버는 다항식 $P(x)$를 커밋했을 때, 아래와 같은 다항식 커밋 $C$를 생성했습니다:

여기서 다항식 $P(x)$는

의 형태로 주어졌습니다. $g$는 생성자, $s$는 신뢰 설정 과정에서 선택된 비밀 값입니다.

---

2. 열람 요청 (Opening Request)

이제 베리파이어가 다항식 $P(x)$의 특정한 지점 $z$에서의 값을 열람하고자 합니다. 예를 들어, 베리파이어는 $P(z)$를 알고 싶어 합니다.

• 프로버의 작업: 프로버는 다항식 $P(x)$의 값 $P(z)$을 계산하고, 그 결과를 베리파이어에게 보냅니다. 그러나 이 값만으로는 베리파이어가 그것이 정말 다항식 $P(x)$에서 계산된 값인지를 알 수 없습니다. 따라서 프로버는 열람 증명(Opening Proof)이라는 추가 정보를 제공해야 합니다.

---

3. 증명 생성 (Proof Generation)

프로버는 $P(z)$의 정확성을 증명하기 위해 잉여 다항식 $H(x)$를 생성합니다. 잉여 다항식 $H(x)$는 다음과 같이 계산됩니다:

여기서 $P(x)$는 프로버가 알고 있는 원래의 다항식이고, $P(z)$는 프로버가 방금 계산한 $z$에서의 값입니다. $H(x)$는 $P(x)$가 실제로 $P(z)$에서 값을 만족하는지 증명하는 역할을 합니다.

이 잉여 다항식 $H(x)$는 다항식의 차수가 $d-1$이 되며, 이를 사용해 베리파이어가 $P(z)$를 검증할 수 있습니다. 프로버는 이 잉여 다항식 $H(x)$의 커밋을 생성하여 베리파이어에게 보냅니다.

---

4. 검증 (Verification)

베리파이어는 프로버가 보낸 $P(z)$와 $H(x)$의 커밋을 검증하여, 프로버가 실제로 $P(x)$를 알고 있는지 확인합니다.

• 검증식: 베리파이어는 다음 검증식을 사용하여 $P(z)$의 정확성을 확인합니다:

이 식에서:

• $g^{P(z)}$는 프로버가 제시한 $P(z)$에서의 값을 대입한 결과입니다.
• $g^{s - z}$는 설정 단계에서 생성된 CRS 중 $g^s$에서 $z$만큼 뺀 값입니다.
• $H$는 프로버가 보낸 잉여 다항식 $H(x)$의 커밋입니다.
• $C$는 초기 다항식 커밋입니다.

---

5. 성공적인 검증

베리파이어는 위 검증식을 계산하여 양쪽이 일치하면, 프로버가 정확한 $P(z)$ 값을 제시했음을 확신하게 됩니다. 이로써 프로버는 $P(z)$가 실제로 다항식 $

출처(참고문헌)

연결문서