# Pedersen & Polynomial Commitment Scheme {% hint style="warning" %} **이 문서에서는 Pedersen Commitment Scheme와 Polynomial Commitment Scheme에 대해 알아본다.** {% endhint %} ### Commitment의 기본 개념 Commitment(커밋먼트) 스킴은 크게 두 단계로 나뉜다. 1. **Commit 단계** * 커미터(committer)가 비밀 값 $$m$$ 과 랜덤 값 $$r$$(salt)을 골라 $$\text{Com}(m, r)$$를 계산해 Verifier에게 보낸다. * 이때 Verifier는 $$m$$ 이 무엇인지는 알 수 없고, 커밋 값만 본다. 2. **Reveal(Opening) 단계** * 나중에 커미터가 $$(m,r)$$ 을 공개한다. * Verifier는 공개된 $$(m,r)$$ 으로 다시 $$\text{Com}(m, r)$$ 를 계산해, 처음 받은 commitment와 같은지 확인한다. 좋은 commitment 스킴은 두 가지 성질을 만족해야 한다. * **Hiding** * Commit 값만 보고는 $$m$$ 을 추측할 수 없어야 한다. * **Binding** * 커미터가 나중에 $$m \neq m'$$인 두 값을 가지고\ 같은 commit을 만들었다고 주장할 수 없어야 한다. ### Pedersen Commitment Scheme Pedersen commitment는 타원곡선 위에서 정의되는 commitment 스킴이다 * order(원소 개수)가 소수 $$q$$ 인 군 $$G$$ 를 잡는다. * 이 군 위의 점(생성자) $$G,H$$ 를 고른다. * 중요한 조건은, 아무도 $$H=xG$$를 만족하는 $$x$$ 를 모른다는 것이다\ (즉, $$G$$ 와 $$H$$ 사이의 이산 로그 관계를 알 수 없어야 한다). 비밀 값(메시지) $$s \in \mathbb{Z}\_q$$ 랜덤 값(블라인딩) $$t \in \mathbb{Z}\_q$$​ 에 대해 commitment는 다음과 같다. $$E(s, t) = sG + tH$$ * 커미터는 $$E(s,t)$$ 를 Verifier에게 보낸다. * 나중에 $$s,t$$ 를 공개하면, Verifier는 $$sG+tH$$를 다시 계산해 commit 값과 같은지 확인한다.
#### Hiding 성질 고정된 $$s$$ 에 대해 $$t$$ 를 무작위로 뽑으면,\ $$E(s,t)=sG+tH$$는 $$H$$ 방향으로 랜덤하게 섞인 점이 된다. * $$t$$ 를 모르고서는, $$E(s,t)$$ 만 보고 $$s$$ 를 역추적하기 어렵다. * 수학적으로는, 적절한 조건에서 Pedersen commitment는 **완전(정보이론적) Hiding**을 갖는 것으로 알려져 있다. 즉, commit 값만 보고는 비밀 $$s$$ 가 어떤 값인지 알아낼 수 없다. #### Binding 성질 만약 커미터가 같은 commit에 대해 서로 다른 두 쌍 $$(s,t), (s',t')$$를 주장한다면 $$sG+tH=s' G+t'H$$ 이므로 정리하면 $$(s−s')G=(t'−t)H$$이다. \ 양변에 적절한 역원을 곱하면, 결국 $$H = \frac{s - s'}{t' - t},G$$ 라는 관계가 나오게 된다. 이것은 곧 $$H$$ 가 $$G$$ 의 몇 배인지(이산 로그) 를 알아냈다는 뜻이다.\ 하지만 우리는 “아무도 그 값을 모른다”고 가정했기 때문에,\ 이런 식으로 두 개의 서로 다른 opening을 만드는 것은 **계산적으로 불가능**하다고 본다. 그래서 Pedersen commitment는 * **완전 Hiding**, * **DLOG(이산 로그) 가정 하에서 Binding** 을 동시에 만족하는 스킴이다. #### Additively Homomorphic 성질 Pedersen commitment는 군 연산(덧셈)을 사용하기 때문에 자연스럽게 덧셈에 대해 동형(homomorphic)인 성질을 가진다. 두 값 $$s\_1, s\_2$$​ 와 blinding $$t\_1, t\_2$$​ 에 대해, $$E(s\_1,t\_1)=s\_1G+t\_1H, ;E(s\_2,t\_2)=s\_2G+t\_2H$$ 이면, 두 commit을 더하면 $$E(s\_1,t\_1)+E(s\_2,t\_2)=(s\_1+s\_2)G+(t\_1+t\_2)H=E(s\_1+s\_2,  t\_1+t\_2)$$ 이 된다. 따라서 여러 commitment를 한 번에 검증하고 싶은 경우, 1. 개별 값에 대해 각각 commit을 만들고 2. commit들을 더한 뒤 3. 합에 대한 opening을 공개하는 방식으로 한 번에 검증할 수 있다. 이 성질 때문에 Pedersen commitment는 **벡터, 다항식, 집계 증명** 등으로 확장할 때 매우 유용하다.
Pedersen 기반 Vector Commitment 타원곡선 위에서 점을 여러 개 준비하면, 스칼라 곱을 이용해 벡터 전체를 한 번에 commit할 수 있다. 예를 들어, 비밀 벡터 $$\mathbf{s} = (s\_1, s\_2, \dots, s\_n)$$ 를 commit하고 싶다고 가정한다. * 서로 다른 점 $$G\_1, G\_2, \dots, G\_n$$ 과 * blinding용 점 $$H$$ 를 준비한다. 그 다음 commitment를 $$C = s\_1 G\_1 + s\_2 G\_2 + \dots + s\_n G\_n + tH$$ 로 정의한다. * 이때 $$t$$ 는 blinding factor이다. * opening 단계에서는 $$(s\_1, \dots, s\_n, t)$$를 공개하여 Verifier가 같은 $$C$$ 가 나오는지 확인한다. 이 구조는 일반적인 Pedersen commitment를 “메시지를 스칼라 하나 → 스칼라 벡터”로 확장한 형태이다. ### Verifiable Secret Sharing과 Polynomial Commitment Pedersen commitment는 **비대화형 Verifiable Secret Sharing(VSS)** 의 기반 기술로도 쓰인다. #### Shamir Secret Sharing 비밀 $$s$$ 를 n 명에게 나누어 주되, * 어느 한 사람만 갖고는 $$s$$ 를 알 수 없고, 최소 $$k$$ 명 이상이 모였을 때만 $$s$$ 를 복원할 수 있는 구조를 생각한다.
Shamir Secret Sharing에서는 1. $$\phi(0) = s$$를 만족하는 **차수** $$(k−1)$$ 다항식 $$\phi(x)$$를 선택한다. 2. 각 참가자 $$i$$ 에게 **몫**으로 $$\phi(i)$$ 를 나누어 준다. 그 결과, * 한 사람이 가진 $$\phi(i)$$ 만으로는 $$s$$ 를 알 수 없고, * $$k$$ 명 이상이 모이면 라그랑주 보간으로 $$\phi(x)$$ 를 복원하여 $$s = \phi(0)$$을 구할 수 있다.
#### “내 share가 진짜냐?”를 검증하려면 Polynomial Commitment가 필요 각 참가자 입장에서는, 자신이 받은 $$\phi(i)$$ 가\ 정말 같은 다항식 $$\phi(x)$$ 에서 나온 값인지 검증하고 싶다. > “딜러가 마음대로 다른 값을 써서 준 건 아닌가?” 이를 위해서는 “딜러가 특정 다항식 $$\phi(x)$$ 를 알고 있고,\ 각 share $$\phi(i)$$ 가 그 다항식의 평가값이다”를 증명할 수 있어야 한다. 이 문제를 해결하는 구조가 **Polynomial Commitment Scheme** 이다. ### Polynomial Commitment의 기본 아이디어 Polynomial Commitment 스킴에서 커미터가 해야 할 일은 다음과 같다. 1. 어떤 다항식 $$\phi(x) = a\_0 + a\_1 x + \dots + a\_d x^d$$ 을 알고 있다. 2. 이 다항식 전체에 대해 **Commit** 을 한다. (어떤 방법으로든) 3. 나중에 Verifier가 임의의 점 $$u$$ 를 골라 > “$$\phi(u)$$ 를 알려 달라. 그리고 그 값이 commit 한 다항식의 평가값이라는 것을 증명해 달라.” 라고 요구한다. 4. 커미터는 $$v = \phi(u)$$와 함께, “정말로 $$v = \phi(u)$$이다”를 증명하는 **짧은 Proof** 를 보낸다. 5. Verifier는 전체 다항식을 알 필요 없이, “commit 된 다항식에 대해 $$\phi(u) = v$$가 맞다”는 것만 확인한다. 여기서 중요한 조건은 * **Commit은 Hiding** 해야 하고 * 커미터가 **거짓 평가값**을 보내지 못하도록 해야 한다 (Binding + soundness).
### 방법 1: 다항식 전체를 한 번에 string으로 commit 1. 다항식의 계수들$$(a\_0,…,a\_d)$$을 하나의 문자열로 인코딩한다. 2. 이 문자열을 일반 해시 기반 commitment 등으로 commit한다. 3. Eval 단계에서 $$u$$ 가 주어지면, 다항식을 전부 공개하고 Verifier가 직접 $$\phi(u) = a\_0 + a\_1 u + \dots + a\_d u^d$$ 를 계산해 commit과 일치하는지 확인한다. * 장점: Commit 크기가 **상수 크기**(해시 한 개 등)이다. * 단점: Eval 때 **다항식 전체가 노출**된다. * Verifiable Secret Sharing 같은 상황에서는 이는 치명적이다.
### 방법 2: 계수마다 따로 commitment (Coefficient Commitments) 1. 각 계수 $$a\_i$$에 대해 개별 commitment $$C\_i$$를 만든다. 2. Eval 때 $$u$$ 를 받으면, 다항식 평가 값 $$\phi(u)$$ 와, 이를 위한 선형 결합 관계를 이용해 검증한다. 이 방식은 다항식을 바로 문자열로 공개하지 않으므로, 조금 더 구조적으로 다룰 수 있다. 하지만 * commit 개수가 계수 개수(차수 + 1)에 비례하므로, 통신량이 $$O(n)$$ 이 된다.
그래서 “계수마다 Pedersen commitment를 하고, 이것으로 다항식 평가를 증명하는 구조”가 등장한다. ### Pedersen 기반 Polynomial Commitment #### 계수에 대한 Pedersen Commitment 다항식 $$\phi(x) = a\_0 + a\_1 x + a\_2 x^2 + \dots + a\_d x^d$$ 에서 각 계수 $$a\_i$$ 에 대해 **Pedersen commitment** 를 만든다. $$C\_i=a\_iG+r\_iH$$ * $$G,H$$는 Pedersen에서 쓰는 두 점이다 (이산 로그 관계를 모른다고 가정). * $$r\_i$$ 는 각 계수에 대한 blinding factor이다. 전체 다항식에 대한 commit은 “계수 commit들의 리스트” $$(C\_0,C\_1,…,C\_d)$$ 라고 볼 수 있다. Prover는 이 리스트와 $$G,H$$ 를 모두에게 공개한다.
#### Eval 단계: ϕ(u)의 값을 증명 Verifier가 임의의 점 $$u$$ 를 보낸다 커미터(Prover)는 다음을 계산한다. 1. 다항식 평가값 $$v = \phi(u) = \sum\_{i=0}^d a\_i u^i$$ 2. “blinding factor도 마찬가지 형태로 섞은 값” $$\pi = \sum\_{i=0}^d r\_i u^i$$
이제 증명자가 보낸 값을 통해 검증자는 두 가지 벡터를 비교한다.
* 왼쪽: 계수 commit들을 $$u$$ 로 가중합 $$\sum\_{i=0}^d u^i C\_i = \sum\_{i=0}^d u^i (a\_i G + r\_i H) = \left(\sum\_{i=0}^d a\_i u^i\right) G + \left(\sum\_{i=0}^d r\_i u^i\right) H = v G + \pi H$$ * 오른쪽: “값 $$\phi(u)$$ 와 blinding $$\pi$$ 에 대한 Pedersen commit” $$E(\phi(u), \pi) = v G + \pi H$$ 따라서, 항상 $$\sum\_{i=0}^d u^i C\_i = v G + \pi H$$ 가 성립한다. #### Soundness 만약 Prover가 실제 값을 $$v = \phi(u)$$가 아니라, **거짓**인 $$v' \neq \phi(u)$$를 보내려고 한다고 가정한다. 이때 Prover는 검증식을 통과시키기 위해 어떤 $$\pi'$$ 를 만들어서 $$\sum\_{i=0}^d u^i C\_i = v' G + \pi' H$$를 만족시켜야 한다. 하지만 왼쪽 값은 이미 $$\sum\_{i=0}^d u^i C\_i = v G + \pi H$$ 이므로, 두 식을 비교하면 $$v G + \pi H = v' G + \pi' H$$ 즉, $$(v - v') G = (\pi' - \pi) H$$ 입니다. $$v \neq v'$$이므로, 정리하면 $$H = \frac{v - v'}{\pi' - \pi} G$$ 가 된다.\ 이는 곧 $$H$$ 가 $$G$$ 의 몇 배인지(이산 로그)를 찾아낸 꼴이다.
따라서 * **Pedersen의 Binding 가정** (두 점의 이산 로그 관계를 모른다고 가정)을 전제로 할 때, * Prover가 거짓 평가값 $$v'$$ 에 대한 적절한 $$\pi'$$ 를 찾아 검증식을 통과하는 것은 불가능하다. 결과적으로 이 스킴은 * blinding 때문에 **Hiding**을 만족하고, * DLOG 가정 덕분에 **Binding**도 만족한다. ### 한계: 커밋 크기가 O(n) 이 Pedersen 기반 Polynomial Commitment는 계수마다 하나의 commit이 필요하다. * 다항식 차수가 $$d$$ 라면 commit 개수는 $$d+1$$ 개이다. * 따라서 통신량 및 저장 공간이 **다항식 차수에 비례**한다 즉, > commit 크기가 $$O(n)$$ 이고,\ > 보다 큰 규모의 시스템, 특히 온체인에서 쓰기에는 비효율적이다.
이 문제를 해결하기 위해 나온 것이 **KZG Polynomial Commitment** 이다. ### KZG Polynomial Commitment KZG(Kate–Zaverucha–Goldberg) Polynomial Commitment는 **commit 크기와 proof 크기를 상수 크기**로 만드는 것이 목표이다. 1. 어떤 비밀 값 $$\tau$$ 를 골라 아무에게도 알려 주지 않는다. 2. 대신 $$\tau G, \tau^2 G, \dots, \tau^d G$$,같은 값들만 공개한다. * 여기서 $$G$$ 는 타원곡선 상의 생성자이다. * 이 값들은 모두 “타원곡선 점”이다. 3. 다항식 $$\phi(x) = a\_0 + a\_1 x + \dots + a\_d x^d$$ 에 대해, commit 값은 $$C = \phi(\tau) G$$과 같은 꼴이 된다.\ (실제로는 계수와 $$\tau^i G$$ 들의 선형 결합으로 계산할 수 있다.) 이때 중요한 점은, * 아무도 $$\tau$$ 값을 모르기 때문에, commit $$C$$ 는 사실상 “아무도 모르는 점에서 평가한 다항식 값”을 타원곡선 위에 숨겨 놓은 형태이다. 이 구조 덕분에 * **commit 크기는 점 하나(상수 크기)**, * **proof도 상수 크기**, * 여러 평가에 대해 증명해도 통신량이 거의 증가하지 않는 성질을 가진다. ### Eval Proof 커미터가 * 다항식 $$\phi(x)$$ 에 대해 commit $$C$$ 를 만들고, * 임의의 점 $$i$$ 에서 평가값 $$\phi(i) = y$$를 알고 있다. 이제 Prover는 > “이 $$y$$ 가 commit 된 다항식 $$\phi$$ 를 점 $$i$$ 에서 평가한 값이다.” 라는 것을 증명하는 proof $$\omega\_i$$ 를 함께 보낸다. Verifier는 * commit $$C$$, 점 $$i$$, 평가값 $$y$$, proof $$\omega\_i$$ 만 보고 * $$y = \phi(i)$$인지, 고 그 다항식이 commit 시 사용된 다항식과 동일한지 를 pairing 연산을 통해 한 번에 확인한다. 수학적으로는 “$$\phi(x) - y$$가 $$(x−i)$$ 로 나누어 떨어진다”는 사실을\ 다항식 형태가 아니라 **타원곡선 점과 pairing으로 표현**하는 구조이다.
### Pedersen → Polynomial Commitment → KZG 1. **Pedersen Commitment** * $$E(s, t) = sG + tH$$ * 완전 Hiding, DLOG 가정 하에서 Binding 이다. * Additively homomorphic 성질을 가진다. 2. **Vector / Polynomial Commitment via Pedersen** * 여러 점 $$G\_i$$를 사용해 벡터에 commit할 수 있다. * 다항식의 계수들 $$a\_i$$ 를 각각 Pedersen commit하여 $$C\_i = a\_i G + r\_i H$$로 두고\ $$u$$ 에서의 평가 $$\phi(u) = v$$에 대해 $$\sum u^i C\_i = vG + \pi H$$관계를 이용해 증명한다 * hiding + binding 모두 만족하지만, commit 크기가 계수 개수에 비례하여\ 통신량이 $$O(n)$$ 이다. 3. **KZG Polynomial Commitment** * “한 번의 trusted setup으로 만든 파라미터”에 기반하여\ 다항식 전체에 대한 commit을 점 하나(상수 크기)로 줄인다. * 임의의 점에서의 평가 $$\phi(i)$$ 에 대한 증명(Proof $$\omega\_i$$)도 상수 크기이다. * Verifier는 pairing 연산 몇 번으로\ “commit 된 다항식에 대해 $$\phi(i) = y$$가 맞다”를 확인할 수 있다. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-2/kzg-plonk/pedersen-and-polynomial-commitment-scheme.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.