이 글은 Verkle Tree에서 사용되는 KGZ Commitment을 다룹니다.
TLDR;
- KGZ Commitment는 PCS(Polynomial Commitment Scheme)로서 “데이터에 (라그랑주) 보간법을 이용해 생성한 다항식”을 commit할 경우 Vector Commitment로서 기능한다.
- 다항식 P(x)에 대한 KGZ Commitment는 [P(s)]₁로 정의되며 이에 대한 proof의 사이즈는 O(1)이다. 이 때
s는 Trust Setup으로 생성된 비밀값이다. - multiopenings: 모든 점을 한번에 reveal하기 위한 multiproofs를 생성할 수 있으며 multiproofs의 사이즈는 O(1)이다.
KGZ Commitment는 Polynomial Commitment로서 Merkle Tree의 Merkle Root를 만드는 과정을 대체할 수 있습니다. 이는 Proof 사이즈를 줄여 p2p 통신에 사용되는 네트워크 대역폭을 크게 줄일 수 있으며 stateless client까지의 가능성도 제공합니다.
이 글은 KGZ Commitment의 핵심 동작 방식을 설명하기 위해 디테일한 요소(엄밀한 수학적 정의와 보안 요소)는 다소 생략됨을 알립니다.
Commitment Scheme
Commitment Scheme은 데이터를 숨긴 후 그에대한 Commitment만 제출하고 이후에 실제 데이터를 드러내는 방식입니다. 가장 이해하기 쉬운 예시는 해시 함수를 이용한 commit-reveal scheme입니다.
- 유저는 본인이 가진 데이터
input을 해시하여commit = sha256(input)을 계산합니다. - 유저는 프로토콜에
commit을 제출하며 이후 필요할 경우input을 드러냅니다. - 프로토콜은 유저가 제출한
input이 (2)에서 제출한commit에 대응하는지sha256(input) == commit로 확인합니다. 일치하지 않을 경우 유저가 제출한input을 거부합니다. - 프로토콜은 제한된 시간 안에 유저가
input을 드러내지 않으면 패널티를 부여합니다.
(reveal이란 단어 보다 opening이란 표현을 자주 사용하지만 동일한 의미를 가집니다. 마찬가지로 proof-of-membership 또한 동일한 의미를 가지며 이 글에선 세 단어를 혼용합니다.)
Vector Commitment
해시 함수는 임의의 길이의 인풋을 고정된 사이즈의 아웃풋으로 변환합니다. 만약 인풋의 사이즈가 크다면 해시 함수는 여러 라운드를 반복하기에 해시 함수의 연산 시간은 인풋 사이즈에 비례합니다. 위와 같은 commit 과정 뿐만 아니라 reveal(=opening) 과정에서도 인풋 사이즈에 비례해 컴퓨팅 자원들이 필요합니다.
“인풋 사이즈가 크니 이를 나눠서 배열로 처리하자”는 아이디어를 적용하면 위에서 언급한 문제들을 해결할 수 있습니다. 이제는 인풋의 정의역이 “하나의 값”(scalar)이 아닌 “배열”(vector)이기에 이러한 Commitment Scheme은 Vector Commitment Scheme이라고 불립니다.
가장 명확한 예시는 Merkle Tree입니다. 길이가 n인 배열에 Merkle Tree를 이용해 Commitment를 생성한다면 이 Commitment는 결국 Merkle Root가 됩니다. Binary Merkle Tree의 경우 Merkle Root를 만들기 위해 O(n)번의 해시 함수를 실행해야 하며 i번째 노드를 reveal하기 위해선 (proof-of-membership) 사이즈가 O(log(n)/log(2))인 proof가 필요합니다. 만약 모든 노드를 reveal하기 위해선 proofs의 총 사이즈는 O(n log(n)/log(2)) 가 될것입니다.
Commitment Scheme을 개선하는 목적은 proof 사이즈를 줄여 네트워크 대역폭을 더 효율적으로 사용하기 위함입니다. 물론 그를 위해 관련 자료구조를 만들고 proof를 계산하는 시간(e.g., Merkle Tree 구성 및 Merkle Path 생성)을 trade-off 합니다.
Polynomial Commitment
Vector Commitment가 인풋의 정의역이 배열(=vector)인 것이라면 Polynomial Commitment는 인풋의 정의역이 다항식입니다.
다항식을 아래와 같은 방식으로 구성하면 Polynomial Commitment를 Vector Commitment로 사용할 수 있습니다.
- 길이가
n인input: Array<Bytes32>에 대해n개의 점(i, input[i])를 생성합니다. - 라그랑주 보간법을 이용해 다항식 P(x)를 생성합니다. 즉, P(i) = input(i) for 0 ≤ i < n 입니다. (이 때 P(x)의 차수는 최대
n입니다) - Polynomial Commitment를 이용해 다항식 P(x)를 commit합니다.
- 추후 필요할 경우
i번째 점을 reveal(=proof-of-membership)합니다.
여기서 3번은 Merkle Root에 대응하고 4번에서 생성된 proof는 Merkle Path에 대응합니다.
또한 i번째 점을 reveal 한다는 것은 P(i) = input[i] 임을 보이는 것과 동일합니다.
KGZ Commitment는 다항식 P(x)를 commit하는 Polynomial Commitment 입니다.
지금까지는 다소 생소할 수 있는 Commitment 와 관련 용어들을 설명했습니다. 마지막으로 KGZ Commitment에서 사용하는 2가지 수학적 요소(Polynomial Divisibility, Elliptic Curve Pairings)를 간략하게 이해하고 나면 KGZ Commitment을 이해할 재료는 모두 갖춰집니다.
Polynomial Divisibility: Factor Theorem
방적식 f(x) = 0이 x=a를 해로 가질 때 다항식 f(x)는 (x-a)를 인수(factor)로 가집니다. f(x) = (x-a) * Q(x) 를 만족하는 다항식 Q(x)가 존재하기 때문에 f(x)는 x-a로 나눌 수 있습니다. 그 나눗셈에서 몫 다항식은 Q(x)가 됩니다.
EC Pairings (Elliptic Curve Pairings)
EC 위의 점들로 할 수 있는 기존의 연산들은
a) 하나의 EC 위의 두 점 P, Q에 대한 덧셈 (P+Q), 뺄셈 (P-Q)
b) EC 위의 한 점 P와 자연수 n의 곱셈 (nP)
뿐이었습니다. EC Pairings이 가지는 수학적 의미는 2개의 ECs 위에 있는 각각의 점 (P in G1, Q in G2)에 대해 곱셈(P*Q)과 같은 연산을 제공한다는 점입니다.
EC Pairings은 두 개의 EC를 정의역으로 가지고 치역은 자연수(정확히는 finite field Fₚ) 입니다. 즉, function pairing(pointA: Point_on_EC1, pointB: Point_on_EC2): Fₚ 와 같은 function signature를 가집니다.
또한 EC Pairing은 아래와 같은 특징(Bilinearity)을 가집니다
EC Pairings를 더 자세히 이해하고 싶으시다면 이 글을 읽는 것을 추천합니다.
Short Notations for elements in G₁, G₂, G_T — [ ]₁,[ ]₂,[ ]_T
앞으로 다룰 수학적 표현에서 G₁, G₂, G_T에 속하는 각 원소들을 아래와 같은 방식으로 표기합니다.
KGZ Commitment
KGZ Commitment는 악의적인 prover가 false positive proof를 생성할 수 있기 때문에 Trust Setup이 필요합니다. 즉, 특정한 secret s를 생성한 후 이를 기반으로 [sⁱ]₁, [sⁱ]₂ 를 생성해야합니다. 이 과정은 MPC(e.g., KGZ Ceremony) 방식으로 생성하는 것이 안전하며 s는 유출되어선 안됩니다.
[sⁱ]₁, [sⁱ]₂는 퍼블릭하게 공유하며 앞으로 필요한 연산에 사용될 것입니다. 예를 들어 다항식 P(x) = ∑ᵢⁿpᵢxⁱ을 알고있는 사람(즉, pᵢ를 아는 사람)은 s 에서의 결과인 P(s)를 계산할 수 없지만, [P(s)]₁와 [P(s)]₂를 계산 할 때는 sⁱ 대신 [sⁱ]₁, [sⁱ]₂를 이용해 계산할 수 있습니다.
이제 Commitment Scheme의 3가지 정의(Commitment, proof, verification equation)을 다룹니다. Prover가 Commitment, proof 를 만들어 Verifier에게 전달하고 Verifier는 verification equation를 확인해 “Commitment의 유효성”을 확인합니다.
Commitment
다항식 P(x)에 대한 Commitment C는 아래와 같이 정의합니다.
이는 Merkle Tree의 Merkle Root와 동일한 의미를 가집니다. Merkle Tree의 proof-of-membership에는 (1) Merkle Root, (2) Merkle Path, (3) i번째 노드의 값(해시)이 필요합니다. proof-of-membership의 재료가 되는 (1)은 C에 대응하니 (2)와 (3)이 필요합니다.
(2)는 앞으로 설명할 proof입니다.
(3)은 우리가 P(x)를 생성하기 위해 사용했던 점 (i, input[i])입니다. 즉, P(i) = input[i]이고 Prover는 이를 Verifier에게 점 (z, y) 형태로 전달합니다. (z = i, y = input[i])
Proof
다항식 P(x)는 x=z 일 때 y입니다. 즉, 다항식 “P(x)-y”는 x=z 일 때 0입니다. 따라서 다항식 “P(x)-y”는 다항식 “x-z”로 나눌 수 있습니다. 이는 곧 어떠한 “몫 다항식 Q(x)”가 아래 형태로 존재함을 의미합니다.
다항식 P(x)에 대한 Commitment C에 대한 proof π는 아래와 같이 정의합니다.
재미있는 점은 Commitment와 Proof 모두 단순히 특정 다항식을 G₁로 옮겨놓은 것이 불가하단 것입니다. 물론 Verifier가 “C의 유효성”을 올바르게 확인하기 위해서는 아래 방정식을 확인합니다.
Verification Equation
Prover는 Verifier에게 C, π, (z, y) 를 전달합니다. Verifier는 아래 방정식을 통해 “C의 유효성”을 확인합니다.
[s-z]₂ = (s-z)H = sH-zH = [s]₂-[z]₂ 이기에 Verifier는 [s]₂와 z를 이용해 모든 연산을 수행할 수 있습니다.
지금까지 다룬 Commitment Scheme은 1개의 점 (z,y)에 대해 1개의 proof가 필요합니다. proof는 𝔾₁ 위의 점이기에 사이즈가 O(1)입니다.
KGZ Commitment — multiproofs
우리는 하나의 다항식 P(x)에 여러 점이 지나는 것을 알고 있습니다. n개의 점이면 n개의 π가 생깁니다. 하지만 이를 1개의 π로 압축할 수 있습니다.
Commitment C 는 이전과 동일하게 [P(s)]₁를 사용합니다.
Proof — multiproofs
P(x)는 k개의 점을 지나고 이는 라그랑주 보간법을 이용해 생성되었습니다. 마찬가지로 라그랑주 보간법을 이용해 I(x)를 생성합니다.
(라그랑주 보간법을 이용해 P(x)와 I(x)를 생성한다면 P(x) = I(x) 일 수 있습니다. 따라서 이를 피하기 위해 P(x)를 생성할 때 추가적인 항 (e.g., x∏₀ᵏ(x-xᵢ))을 붙인다면 k개의 점들을 동일하게 지나면서 두 다항식이 다르게 생성할 수 있습니다.)
다항식 P(x)와 다항식 I(x) 모두 k개의 점을 지납니다. 즉, 다항식 “P(x)-I(x)”는 x=zᵢ 일 때 항상 0입니다. 따라서 다항식 “P(x)-I(x)”는 다항식 “Z(x)=∏₀ᵏ(x-xᵢ)”로 나누어집니다. 이는 곧 “몫 다항식 Q(x)”가 아래 형태로 존재함을 의미합니다.
이제 k개의 점에 대한 multiproofs π는 아래와 같이 정의됩니다.
Verification Equation — multiproofs
Prover는 Verifier에게 C, π, (zᵢ, yᵢ) 를 전달합니다. Verifier는 아래 방정식을 통해 “C의 유효성”을 확인합니다.
Verifier는 (zᵢ, yᵢ)를 이용해 Z(x)와 I(x)를 계산할 수 있습니다.
multiproofs π 또한 𝔾₁ 위의 점이기에 사이즈가 O(1)입니다.
Conclusion
지금까지 Verkle Tree에서 사용될 Polynomial Commitment Scheme(PCS)인 KZG Commitment를 살펴봤습니다. 주어진 데이터 셋(input: Array<Bytes32>)을 2차 평면위의 점으로 표현해 라그랑주 보간법을 사용한다면 PCS를 Vector Commitment Scheme으로도 이용할 수 있습니다. Commitment Scheme이기에 기존의 Merkle Tree의 기능을 대체할 수 있습니다.
단점으로는 Trust Setup이 필요하고 연산 시간이 O(n)에서 O(n²)로 늘어납니다. 장점으로는 proof 사이즈가 O(log(n))에서 O(1)으로 줄어들고 multiproofs를 사용한다면 여러 데이터를 한번에 reveal할 수 있습니다.
지금 논의한 내용만으로 구성한 Verkle Trie의 Proof 사이즈가 O(1)이 아닙니다. k-ary Verkle Trie에서 동일한 parent node에 속하는 여러 children nodes에 대해 크기가 O(1)인 proof를 가지는 것 뿐입니다. 즉, π 하나는 depth 하나 올라갈 때 사용되는 것으로 depth가 2이상일 경우 더 많은 π가 필요합니다.
실제 Verkle Tree(Trie)에는 더 많은 최적화 요소들이 들어갑니다. 이러한 내용들은 다음 글에서 설명하도록 하겠습니다.
