# 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