owned this note
owned this note
Published
Linked with GitHub
# KGZ Commitment
###### tags: `Ethereum` `Math` `Polynomial Commitment` `Verkle Tree`
## Commitment
hash 함수도 일종의 commitment
1. for $a$, prover calculate $H(a)$
2. prover send $H(a)$, a commitment, to verifier
3. this commitment **can later be opened** by sending $a$ to verifier
4. verifier checks that the given commitment (step 2) is equal to the computation of hash of given $a$ (step 3)
$Commit = Hash\ Function: string \rightarrow bytes32$
## Vector Commitment
위 예시에서 $a$가 array, vector 일 경우 vector commitment로 분류
1. for given n elements $a_0, a_1, ..., a_{n-1}$, prover compute $Commit(a_0, a_1, ..., a_{n-1}) = C$
2. provder send $C$, a commitment, to verifier
3. this commitment **can later be opened** by sending $a_0, a_1, ..., a_{n-1}$ to verifier
4. verifier checks that the given commitment $C$ (step 2) is equal to the computation of $Commit$ of given $a_0, a_1, ..., a_{n-1}$ (step 3)
## Comparison to Merkle Trees
따라서 Merkle Tree 또한 Vector Commitment라고 볼 수 있음
1. for given n elements $a_0, a_1, ..., a_{n-1}$, prover compute $MerkleRoot(a_0, a_1, ..., a_{n-1}) = Root$
2. provder send $Root$, a commitment, to verifier
3. this commitment **can later be opened at index $i$** by sending **Merkle Proof for index $i$** and **the leaf node $a_i$** to verifier
4. verifier checks that the given Merkle Root $Root$ (step 2) is equal to the computation of Merkle Proof for index $i$ and the leaf node $a_i$ (step 3)
$Commit = MerkleRoot: bytes \rightarrow bytes32$
## Polynomial Commitment
Vector Commitment와 사실상 동일한 개념.
### Vector of length $n$
- n개의 scalar의 집합(?)
### Polynomial $P(x)$ of degree $n$: $P(x) = \sum_{i=0}^{n}{p_ix^i}$
- 마찬가지로 $n+1$개의 $p_i$가 있음
- Polynomial Commitment에서 prover는 $x=z$일 때 $P(z)=y$임을 (주장)함.
- commitment ($C$): $P(z) = y$ (= point ($z$, $y$))
- 모든 $p_i$를 보내서 검증하는것도 가능하겠지만
1. proof size가 O(n)
2. verifier가 수행하는 연산도 O(n)
- 검증 과정에서 필요한 proof size를 constant로 줄이고 succient verification (O(1))을 충족하는 Kate scheme ~ Trade-off: proof creation: O($n^2$)
### Contruction of $P(x)$
$k$개의 elements $a_0,\ ...,\ a_{k-1}$가 있을 때, $k$개의 점 $(0, a_0),\ ...,\ (k-1, a_{k-1})$을 지나는 Polynomial $P(x)$를 만든다. 즉, $P(i) = a_i\ for\ i \in {[0, k-1]}$.
이는 [라그랑주 다항식](https://en.wikipedia.org/wiki/Lagrange_polynomial)으로 $P(x)$를 계산할 수 있다.
물론 이 때 elements의 index는 자연수 $n \in \mathbb{N}$이 아닌 다른 방식으로 한번 mapping을 한다. (자연수는 항상 EC의 domain이 아니기에...)
## Ellitic Curves and Pairings
- Elliptic Curve $\mathbb{G}_1$ where $G$ is a generator of $\mathbb{G}_1$
- Elliptic Curve $\mathbb{G}_2$ where $H$ is a generator of $\mathbb{G}_2$
- $\mathbb{G}_T \subseteq F_p$: Finite field of prime order
- pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$
- pairing은 **bilinear map** 이기에 아래 특징 성립
1. $e(P,Q+R) = e(P,Q) \cdot e(P,R)$
2. $e(P+R,Q) = e(P,Q) \cdot e(R,Q)$
3. $e(2P,Q) = e(P,Q)^2$
4. $e(P,3Q) = e(P,Q)^3$
5. $e(nP,mQ) = e(P,Q)^{nm}$
두 개의 Elliptic Curve Points를 곱해서 하나의 scala를 만드는 연산
### Short Notations for elements in $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ -- $[\ ]_1, [\ ]_2, [\ ]_T$
$\mathbb{G}_1$위의 **점**을 $xG = [x]_1 \in \mathbb{G}_1$로 표현
$\mathbb{G}_2$위의 **점**을 $xH = [x]_2 \in \mathbb{G}_2$로 표현
$\mathbb{G}_T$의 **값**을 $e([a]_1, [b]_2) = e(aG, bH) = e(G, H)^{(ab)} = [ab]_T \in \mathbb{G}_T$로 표현
### Trust Setup
EC Pairing을 위해선 secret $s$와 $s$에서 계산된 $[s^i]_1$, $[s^i]_2$가 필요함
- $s$를 알면 proving scheme 과정에 개입해서 false positive proof를 생성할 수 있기에 $[s^i]_1$, $[s^i]_2$ 계산 이후 폐기 (MPC로 하면 좋음) -- Discrete Logarithm Problem
- $[s^i]_1$, $[s^i]_2$는 public하게 공개되는 값 -- prover, verifier
### Lemma1: $c[s^i]_1 = cs^iG = [cs^i]_1$
Polynomall $P(x) = \sum_{i=0}^{n}{p_ix^i}$에 대해서
- $[p(s)]_1$ 계산 시 $s^i$ 대신 $[s^i]_1$ 이용
- $[p(s)]_2$ 계산 시 $s^i$ 대신 $[s^i]_2$ 이용
$[P(s)]_1 = [\sum_{i=0}^{n}{p_is^i}]_1 = \sum_{i=0}^{n}p_i[s^i]_1$
**secrete point $s$에 대한 $P(s)$ 계산을 public point $[s^i]_1$로 치환할 수 있음**
## Kate scheme
Polynomial Commitment out of Merkle Tree.
$P(z) = y$ 임을 보이고 싶다
- recap: $z$는 child node의 index이고 $y$는 child node의 hash.
### Commitment
**Commitment**: $C = [P(s)]_1$ -- the commitment to the polynomial $P(x)$
- $P(z) = y$ 이기에 $P(x) - y$는 $z$에서 $0$이다 ($P(z) - y = 0$).
- 따라서 다항식 $P(x)-y$는 $x-z$로 나누어진다.
- $x-z$로 나눈 몫 다항식 $Q(x)$가 존재한다
- $Q(x) = {{P(x) - y} \over {x-z}}$
### Proofs
**Proof**: $\pi = [Q(s)]_1$ where $Q(x) = {{P(x) - y} \over {x-z}}$
### Verification Equation
Prover는 Verifier에게 $C$, $\pi$를 전달하고 Verifier는 아래 방정식을 통해 "$C$의 유효성"을 확인한다.
$$
e(\pi, [s-z]_2) = e(C-[y]_1, H)
$$
#### 증명
left-side)
\begin{align*}
e(\pi, [s-z]_2) &= e([Q(s)]_1, [s-z]_2) &\\
&= [Q(s) \cdot (s-z)]_T &\because e([a]_1, [b]_1) = [ab]_T \\
&= [({{P(s) - y} \over {s-z} }) \cdot (s-z)]_T &\because Q(s) = P(s) - y \\
&= [P(s) - y]_T
\end{align*}
right-side)
\begin{align*}
e(C - [y]_1, H) &= e([P(s)]_1 - [y]_1, H) &\\
&= e([P(s) - y]_1, H) &\because [x]_1 - [y]_1 = xG - yG = (x-y)G = [x-y]_1 \\
&= [P(s) - y]_T \\
\end{align*}
위 방정식에서 좌우측 모두 secret $s$에 대한 값으로 귀결되기에 $s$가 prover에게 유출되면 $\pi_{fake} = (C - [y_{fake}]_1)^{1 \over {s-z}}$ 를 만들어 임의의 $y_{fake}$에 대한 proof를 생성할 수 있다.
## Multiproofs
지금까지 논의된 것은 점 $(z,y)$와 다항식 $P(x)$에 대해서 $P(z)=y$임을 verifier가 검증할 수 있는 방법.
만약 점이 여러개라면 점 갯수만큼 $\pi$가 생김.
The interpolation polynomial을 이용해 여러 점에 대해 하나의 proof를 생성할 수 있음.
$$
\text{for given }\ k\ \text{points}\ (z_0, y_0),\ ...,\ (z_{k-1}, y_{k-1}) \\
I(x) = \sum_{i=0}^{k-1}{y_i}\prod_{j=0, j \neq i}^{k-1}\dfrac{x-z_i}{z_i - z_j}
$$
- $P(x)$가 모든 $k$개의 점들을 지나면 $P(x) - I(x)$는 $z_0,\ ...,\ z_{k-1}$에서 항상 0이다.
- 따라서 위 다항식 $P(x) - I(x)$은 $Z(x) = (X-z_0)\cdot(X-z_1)\cdot\cdot\cdot(X-z_{k-1})$로 **나누어진다**.
- 나누어지기 때문에 $Q(x) = \dfrac{P(x) - I(x)}{Z(x)}$가 존재한다.
- **Kate multiproof** for $(z_0, y_0),\ ...,\ (z_{k-1}, y_{k-1})$: $\pi=[Q(s)]_1$
- **Kate multiproof verification equation**: $e(\pi, [Z(s)]_2) = e(C-[I(s)]_1, H)$
### 증명
left-side)
\begin{align*}
e(\pi, [Z(s)]_2) &= e([Q(s)]_1, [Z(s)]_2) &\\
&= [Q(s) \cdot Z(s)]_T \\
&= [\dfrac{P(s) - I(s)}{Z(s)} \cdot Z(s)]_T \\
&= [P(s) - I(s)]_T \\
\end{align*}
right-side)
\begin{align*}
e(C-[I(s)]_1, H) &= e([P(s)]_1-[I(s)]_1, H) &\\
&= [P(s) - I(s)]_T \\
\end{align*}
## Conclusion
지금까지 논의한건 머클 트리로 치면 머클 루트에서 leaf 노드까지 가는게 아니라 parent node - children node 까지의 검증만을 다룬 것
$k$-ary Verkle Tree는 여전히 $d$개의 proof가 필요함
## References
- https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
- https://en.wikipedia.org/wiki/Lagrange_polynomial