[Note] A batched version of the [KZG10] scheme

DoHoon Kim·2022년 10월 11일
KZG10MBKM19
0

PLONK

목록 보기
3/5

PLONK protocol의 더러운 식을 이해하기 위해 알아야 하는 KZG PCS의 batched version에 대해서 정리해봤다.

두 개의 distinct한 evaluation point를 각각 z,z′z, z'라고 하고, zz에서 evaluate되는 polynomial들을 {fi}i∈[t1]\{f_i\}_{i \in [t_1]}, z′z'에서 evaluate되는 polynomial들을 {fi′}i∈[t2]\{f'_i\}_{i \in [t_2]}라고 하겠다. open protocol은 다음과 같다. (srs는 미리 생성되어 있다고 가정) PPCP_{PC}가 증명하고자 하는 것은 fi(z)=si,fi′(z′)=si′f_i(z) = s_i, f'_i(z') = s'_i 이다.

open({cmi}i∈[t1],{cmi′}i∈[t2],{z,z′},{si,si′})open(\{cm_i\}_{i \in [t_1]}, \{cm'_i\}_{i \in [t_2]}, \{z, z'\}, \{s_i, s'_i\})

(a) VPCV_{PC}가 random field element γ,γ′\gamma, \gamma'을 PPCP_{PC}에게 보낸다.

(b) PPCP_{PC}가 다음과 같은 polynomial을 계산한다.

h(X):=∑i=1t1γi−1fi(X)−fi(z)X−zh′(X):=∑i=1t2γ′i−1fi′(X)−fi′(z′)X−z′h(X) := \sum_{i=1}^{t_1}\gamma^{i-1}{{f_i(X) - f_i(z)} \over {X - z}} \\ h'(X) := \sum_{i=1}^{t_2}\gamma'^{i-1}{{f'_i(X) - f'_i(z')} \over {X - z'}}

그냥 각 polynomial들의 evaluation proof를 random linear combination한 다항식이다. 위 다항식에 대한 commitment를 계산한다.

W:=[h(x)]1,W′:=[h′(x)]1W := [h(x)]_1, W' := [h'(x)]_1

(c) VPCV_{PC}가 random field element r′r'를 선택한다.

(d) VPCV_{PC}가 다음과 같은 G1G_1 element를 계산한다.

F:=(∑i∈[t1]γi−1⋅cmi−[∑i∈[t1]γi−1⋅si]1)+r′(∑i∈[t2]γ′i−1⋅cmi′−[∑i∈[t2]γ′i−1⋅si′]1)F := (\sum_{i \in [t_1]}\gamma^{i-1} \cdot cm_i - [\sum_{i \in [t_1]}\gamma^{i-1} \cdot s_i]_1) \\+ r'(\sum_{i \in [t_2]}\gamma'^{i-1} \cdot cm'_i - [\sum_{i \in [t_2]}\gamma'^{i-1} \cdot s'_i]_1)

더럽게 복잡해 보이지만 γi−1,γ′i−1\gamma^{i-1}, \gamma'^{i-1}의 계수를 살펴보면 (b)에서 계산한 W,W′W, W'의 γi−1,γ′i−1\gamma^{i-1}, \gamma'^{i-1}의 계수의 분자와 대응됨을 알 수 있다.

마지막으로 다음과 같은 pairing check를 하고, protocol은 종료된다.

e(F+z⋅W+r′z′⋅W′,[1]2)⋅e(−W−r′⋅W′,[x]2)=1e(F + z \cdot W + r'z' \cdot W', [1]_2) \cdot e(-W - r' \cdot W', [x]_2) = 1

마지막에 pairing check도 보자마자 뇌절 와서 그러려니 하고 넘어가고 싶지만 약간 중요하다.(내 생각엔?)

[KZG10] 논문을 읽은 사람이라면 pairing check의 우변을 약간 변형하겠다.

e(W+r′⋅W′,[x]2)=e(W,[x]2)⋅e(r′⋅W′,[x]2)=e(W,[x−z+z]2)⋅e(r′⋅W′,[x−z′+z′]2)=e(W,[x−z]2)⋅e(W,[z]2)⋅e(r′⋅W′,[x−z′]2)⋅e(r′⋅W′,[z′]2)=e(F,[1]2)⋅e(z⋅W+r′z′⋅W′,[1]2)=e(F+z⋅W+r′z′⋅W′,[1]2)e(W + r' \cdot W', [x]_2) \\[5pt] = e(W, [x]_2) \cdot e(r' \cdot W', [x]_2) \\[5pt] = e(W, [x - z + z]_2) \cdot e(r' \cdot W', [x - z' + z']_2) \\[5pt] = e(W, [x - z]_2) \cdot e(W, [z]_2) \cdot e(r' \cdot W', [x - z']_2) \cdot e(r' \cdot W', [z']_2) \\[5pt] = e(F, [1]_2) \cdot e(z \cdot W + r'z' \cdot W', [1]_2) \\[5pt] = e(F + z \cdot W + r'z' \cdot W', [1]_2)

지금은 식을 왜 이렇게 변형해서 헷갈리게 만드는 건지 모르겠지만, 추후 proof aggregation에서 유용한 등식이 된다.

자, 이제 PLONK protocol의 더러운 식을 이해해보자.

profile
DoHoon Kim
Researcher & Developer
이전 포스트

[PLONK 2.] KZG polynomial commitment

다음 포스트

[Note] PLONK algorithm - Prover

0개의 댓글