# KZG commitment scheme (PolyCommit\_DL) {% hint style="warning" %} **목표 : 이 문서의 목표는 t-SDH 가정과 쌍선형 페어링 위에서 정의되는 KZG 기반 PolyCommit\_DL 스킴의 전체 흐름을 정리하고, 이 스킴이 어떻게 상수 크기 커밋·증명을 제공하면서도 Correctness·Binding·Hiding 성질을 만족하는지 이해하는 데 있다.** {% endhint %} PolyCommit\_DL scheme은 KZG polynomial commitment scheme으로, 쌍선형 페어링과 t-String Diffie-Hellman(t-SDH) 가정 위에서 정의된다. * 다항식 전체에 대한 커밋 $$C$$는 항상 **1개의 그룹 원소**로 고정되고, * 어떤 점 $$i$$에서의 평가값 $$\phi(i)$$에 대한 증명(witness) $$\omega\_i$$도 **상수 크기**다. * 대신, **trusted setup(SRS 생성자)**와 **t-SDH** 가정이 필요하고, Pedersen 기반 스킴처럼 완전한 hiding은 아니다. 이 페이지에서는 1. **t-SDH 가정**을 정리하고, 2. **KZG PolyCommit\_DL** 스킴의 알고리즘을 정의한 뒤, 3. **Correctness, Binding, Hiding** 성질이 어떻게 보장되는지 살펴본다. #### t-SDH(t-Strong Diffie-Hellman) 가정 t-SDH 가정은 어떤 계산 문제를 다항 시간 내에 푸는 것이 거의 불가능하다는 가정이다. t-DHI(Diffie-Hellman Inversion)의 강화 버전이며, 공격자가 \`"**지수적으로 많은 후보 해**"를 가진 상황에서도 여전히 어렵다는 의미에서 strong을 붙인다. * **랜덤 값** $$\alpha$$ **선택**: * $$\alpha \in \mathbb{Z}\_p^{\*}$$ * **공개값** $$(t+1)$$ **길이의 튜플 공개**: * $$\left\langle g,, g^{\alpha},, \ldots,, g^{\alpha^{t}} \right\rangle \in G^{t+1}$$ * **공격자의 위와 같이** $$t+1$$ **길이의 튜플이 주어질 때 아래와 같이 임의로** $$c$$**를 골라** $$g^{\frac{1}{\alpha + c}}$$**를 계산한다.** * $$\Pr!\left\[A^{t\text{-}SDH}!\left(g,, g^{\alpha},, \ldots,, g^{\alpha^{t}}\right)=\left\langle c,, g^{\frac{1}{\alpha + c}} \right\rangle\right]=\epsilon(\kappa)$$ * 그러나 공격자는 $$\alpha$$를 모르기 때문에, 이 값을 효율적으로 구할 수 있는 확률은 불가능에 가깝다. 즉, t-SDH는 위와 같이 $$(t+1)$$개의 튜플 $$\left\langle g,, g^{\alpha},, \ldots,, g^{\alpha^{t}} \right\rangle \in G^{t+1}$$ 만이 공개값으로 주어질 때, 이러한 튜플과 관련된 대수적 표현 $$g^{\frac{1}{\alpha + c}}$$을 만들어내는 것은 불가능함을 보여준다. (t-DHI에서는 $$c = 0$$이지만 t-SDH에서는 challenge $$c$$를 공격자가 자체부여 해야하므로 더 어렵다.) ### PolyCommit DL PolyCommit DL은 어떤 $$i \in \mathbb{Z}\_p$$에 대해 다항식 $$\phi(x) - \phi(i)$$는 $$(x-i)$$로 나누어 떨어진다는 $$\mathbb{Z}\_p\[x]$$ 상의 $$\phi(x)$$가 갖는 대수적 속성에 기반한다. PolyCommit DL은 **이산로그 문제**를 기반으로 정의된 다항식 커밋먼트 scheme이다. PolyCommit DL은 총 5가지의 과정으로 구성된다. #### Setup $$(1^k, t)$$ Setup 과정은 비밀값을 생성하여 공개 파라미터(SRS, 공개키)를 만드는 단계이다. * **보안 파라미터와 차수 입력**: 보안 파라미터 $$k$$와 다항식 최대 차수 $$t$$를 입력으로 받는다. * **쌍선형 그룹 및 페어링 설정:** t-SDH 가정이 성립하는, 소수 $$p$$를 위수로 갖는 두 그룹 $$\mathbb{G}, \mathbb{G\_T}$$와 이들 사이의 대칭 빌리니어 페어링 $$e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}\_T$$를 설정한다. * $$e(g^a, g^b) = e(g, g)^{ab}$$ 이를 묶어 쌍선형 그룹을 다음과 같이 표기한다. * $$\mathcal{G} = \langle e, G, G\_T \rangle$$ * **비밀 값 생성:** 신뢰가능한 제 3자로부터 $$\alpha \in \mathbb{Z}\_p^\*$$를 무작위로 선택한다. * **SRS 생성:** $$\alpha$$를 이용해 길이 $$t+1$$인 튜플을 생성한다. * $$SRS = \langle g, g^\alpha, \dots, g^{\alpha^t} \rangle \in \mathbb{G}^{t+1}$$ * **공개 키 정의:** * $$PK = \langle \mathcal{G}, g, g^\alpha, \dots, g^{\alpha^t} \rangle$$ Setup 이후에는 비밀 값 $$\alpha$$는 파기되고, $$PK$$(또는 SRS)는 모든 참여자에게 공개된다. #### Commit$$(PK, \phi(x))$$ Committer는 차수가 $$d \le t$$인 다항식 $$\phi(x)$$에 대해 커밋먼트 $$C$$를 다음과 같이 생성한다. 이때, 이상적으로는 $$C = g^{\phi(\alpha)} \in G$$를 계산하고 싶지만, Committer는 $$\alpha$$를 모르기 때문에 Setup 과정에서 제공된 SRS를 사용한다. * **커밋먼트 계산**: 각 계수 $$\phi\_j$$를 공개키에 포함된 $$g^{\alpha^j}$$에 지수로 적용하여 모두 곱해 결합한다. * $$C = \prod\_{j=0}^{\deg(\phi)} (g^{\alpha^j})^{\phi\_j} = g^{\sum\_{j=0}^d \phi\_j \alpha^j} = g^{\phi(\alpha)} \in G$$ 여기서 $$C$$는 전체 다항식 $$\phi(x)$$에 대한 커밋먼트이며, 항상 하나의 그룹 원소 크기를 가진다. #### Open$$(PK, C, \phi(x))$$ * **Open**: 커미터는 커밋먼트 생성에 사용했던 다항식 $$\phi(x)$$를 공개한다. * **VerifyPoly**: 검증자는 공개된 다항식 $$\phi(x) = \sum\_{j=0}^t \phi\_j x^j$$의 계수들과 공개키에 포함된 $$(g, g^\alpha, \dots, g^{\alpha^t})$$를 이용해 $$g^{\phi(\alpha)} = \prod\_{j=0}^{\deg(\phi)} (g^{\alpha^j})^{\phi\_j}$$를 다시 계산해본다. 이 값이 커밋먼트 $$C$$와 일치하는지 확인하여 실패 또는 성공을 판단한다. #### CreateWitness$$(PK, \phi(x), i)$$ CreateWitness는 Committer가 다항식 $$\phi(x)$$를 공개하지 않고, 특정 지점 $$x = i$$에서의 평가값 $$\phi(i)$$만을 증명하는 과정이다. 이 과정에서 PolyCommit\_DL은 "임의의 $$i \in \mathbb{Z}\_p$$에 대해 식 $$\phi(x) - \phi(i)$$는 $$(x-i)$$로 나누어 떨어진다."는 대수적 성질을 이용한다. * **몫 다항식 계산**: * $$\psi\_i(x) = \frac{\phi(x) - \phi(i)}{x - i}$$ * **witness 계산**: 구한 몫 다항식 $$\psi(x)$$을 비밀 지점 $$\alpha$$에서 평가하고, 이를 생성원에 묶어 witness $$w\_i$$를 생성한다. * $$w\_i = g^{\psi(\alpha)}$$ * **출력**: 최종적으로 평가값과 witness를 포함하는 튜플이 출력된다. * $$\langle i, \phi(i), \omega\_i \rangle$$ #### VerifyEval$$(PK, C, i, \phi(i), \omega\_i)$$ VerifyEval은 Committer가 제시한 $$\langle i, \phi(i), \omega\_i \rangle$$가 커밋먼트 $$C$$와 일치하는지 검증하는 절차이다. Verifier는 공개된 값들을 이용해 다음 쌍선형 페어링 식이 성립하는지 검사한다. * **검증 방정식**: 검증은 다음의 페어링 등식이 성립하는 확인하는 방식으로 이루어진다. * $$e(C,g) = e(w\_i, g^{\alpha} / g^i)e(g,g)^{\phi(i)}$$ * **방정식 유도 과정**: 이 검증 방정식은 PolyCommit\_DL과 유사한 과정으로 유도된다. 1. 기본 다항식 항등식 * $$\phi(x) = \psi\_i(x)(x - i) + \phi(i)$$ 2. 비밀 값 $$\alpha$$ 대입 * $$\phi(\alpha) = \psi\_i(\alpha)(\alpha - i) + \phi(i)$$ 3. 커밋먼트 $$C$$를 위 항등식을 이용해 재구성 $$C = g^{\phi(\alpha)}= g^{\psi\_i(\alpha)(\alpha-i)+\phi(i)}$$ * **식 전개:** $$ \begin{aligned} e(w\_i, g^{\alpha} / g^i)e(g,g)^{\phi(i)} &= e(g^{\psi\_i(\alpha)}, g^{(\alpha-i)})e(g,g)^{\phi(i)} \ &= e(g,g)^{\psi\_i(\alpha)(\alpha-i) + \phi(i)} \ &= e(g,g)^{\phi(\alpha)} = e(g^{\phi(\alpha)},g) = e(C,g) \end{aligned} $$ 마지막 등식에서 $$\phi(x) = \psi(x)(x-i) + \phi(i)$$에 $$x=\alpha$$를 대입한 사실을 사용한다. 위 식이 성립하면 Verifier는 $$C = g^{\phi(\alpha)}$$이고, 제시된 $$\phi(i), \omega\_i = g^{\psi\_i(\alpha)}$$가 "$$\phi(x)$$를 알고 있는 누군가가 만들어낼 수 있는 올바른 쌍"이라는 것을 검증할 수 있다. ### **Security properties of PolyCommit\_DL** 이 부분에서는 PolyCommit\_DL 스킴이 **commitment scheme** 으로서 가져야 할 세 가지 보안 성질 **Correctness, Binding, Hiding**을 각각 어떻게 보장하는지 정리한다. #### Correctness Correctness는 **정상적인 알고리즘 흐름으로 생성된 값은 항상 검증에 통과해야 한다**는 성질이다. PolyCommit\_DL에서 Correctness는 다음 두 조건으로 표현할 수 있다. 1. **Polynomial Verify** * Setup을 통해 공개키 $$PK$$를 생성한다. * $$PK \leftarrow \mathit{Setup}(1^{\kappa})$$ * 유효한 다항식 $$\phi(x)$$를 사용하여 Commit 알고리즘으로 $$C$$를 생성한다. * $$C \leftarrow \mathit{Commit}(PK, \phi(x))$$ * 이후 Open 과정에서 공개된 $$\phi(x)$$에 대해 검증자는 다음을 확인한다. * $$\mathit{VerifyPoly}(PK, \phi(x)) = 1$$ 2. **Witness Verify** * 동일한 $$PK, \phi(x)$$, 평가점 $$i$$에 대해 CreateWitness 알고리즘으로 $$\langle i, \phi(i), \omega\_i \rangle$$를 생성 * $$\langle i, \phi(i), \omega\_i \rangle \leftarrow \mathit{CreateWitness}(PK, \phi(x))$$ * 이후 다음이 성립해야 한다. * $$\mathit{VerifyEval}(PK, C, i, \phi(i), \omega\_i) = 1$$ 위 두 조건이 만족된다는 것은, 정상적인 프로토콜을 따르는 한 경우 거짓 음성이 발생하지 않아야 함을 의미한다. #### Binding Binding은 하나의 커밋먼트 $$C$$에 대한 서로 다른 두 다항식 $$\phi(x), \phi'(x)$$를 찾는 것은 불가능하다는 성질이다. PolyCommit\_DL에서는 **Polynomial Binding, Evaluation Binding** 두 조건을 통해 Binding을 평가할 수 있다. **Polynomial Binding** 하나의 다항식 $$\phi(x)$$에 대해 하나의 커밋먼트 $$C$$만 허용하고, 같은 $$C$$에 대해 서로 다른 다항식 $$\phi'(x)$$를 찾는 것은 t-SDH 가정 하에서 불가능해야 한다. 만약 공격자 A가 어떤 $$C$$에 대해 $$\mathit{VerifyPoly}(PK, \phi(x)) = 1, \mathit{VerifyPoly}(PK, \phi'(x)) = 1, \phi(x) \neq \phi'(x)$$를 동시에 만족 시키는 $$\phi, \phi'$$를 찾았다면, 이는 $$\phi(\alpha) = \phi'(\alpha)$$를 만족하는 $$\alpha$$에 대한 비선형 관계를 깨뜨린 것이고, 이를 통해 t-SDH에서 요구하는 형태의 값을 계산할 수 있다. 때문에 모든 공격자 A에 대해 다음이 negligible 해야 한다. $$ \Pr \left( \begin{gathered} PK \leftarrow \mathit{Setup}(1^{\kappa}), (\mathcal{C}, \langle \phi(x), \phi'(x) \rangle) \leftarrow A(PK) : \ \mathit{VerifyPoly}(PK, \mathcal{C}, \phi(x)) = 1 \wedge \ \mathit{VerifyPoly}(PK, \mathcal{C}, \phi'(x)) = 1 \wedge \phi(x) \neq \phi'(x) \end{gathered} \right) = \epsilon(\kappa) $$ **Evaluation Binding** Evaluation Binding은 "특정 평가점 $$i$$에서, 동일한 커밋 $$C$$에 대해 서로 다른 평가값 $$\phi(i), \phi'(i)$$를 동시에 만족할 수 없다"는 성질이다. 공격자가 비밀값 $$\alpha$$를 모르는 상황에서 같은 어떤 $$C$$에 대해 $$\langle i, \phi(i), \omega\_i \rangle, \langle i, \phi(i), \omega'\_i \rangle$$를 모두 통과시키려면, 다음 조건을 동시에 만족해야 한다. * $$\omega\_i = g^{\psi\_i(\alpha)}, \omega'\_i = g^{\psi'(\alpha)}$$ * $$\mathit{VerifyEval}(PK, C, i, \phi(i), \omega\_i) = 1$$ * $$\mathit{VerifyEval}(PK, C, i, \phi(i), \omega'\_i) = 1$$ 검증식을 전개하면 다음과 같다. * $$e(w\_i, g \* \alpha/g^i)e(g, g)^{\phi(i)} = e(w'\_i, g \* \alpha/g^i)e(g, g)^{\phi'(i)}$$ * $$e(g^{\psi\_i(\alpha)}, g^{\alpha-i})e(g, g)^{\phi(i)} = e(g^{\psi'\_i(\alpha)}, g^{\alpha-i})e(g, g)^{\phi'(i)}$$ * $$\frac{e(g^{\psi\_i(\alpha)}, g^{\alpha-i})}{e(g^{\psi'\_i(\alpha)}, g^{\alpha-i})} = \frac{e(g, g)^{\phi'(i)}}{e(g, g)^{\phi(i)}}$$ * $$e\left( \frac{g^{\psi\_i(\alpha)}}{g^{\psi'\_i(\alpha)}}, g^{\alpha-i} \right) = e(g, g)^{\phi'(i)-\phi(i)}$$ * $$e(g^{\psi\_i(\alpha)-\psi'\_i(\alpha)}, g^{\alpha-i}) = e(g, g)^{\phi'(i)-\phi(i)}$$ * $$e(g, g)^{(\psi\_i(\alpha)-\psi'\_i(\alpha))(\alpha-i)} = e(g, g)^{\phi'(i)-\phi(i)}$$ * $$\psi\_i(\alpha) - \psi'\_i(\alpha) = \frac{\phi(i)' - \phi(i)}{\alpha - i}$$ 즉, 공격자는 $$\alpha$$를 모르는 상태에서 $$\frac{1}{\alpha+c}$$ 형태의 값을 구하는 것과 본질적으로 동일하다. 결론적으로, t-SDH 가정 하에서는 공격자가 같은 $$C$$에 대해 서로 다른 평가값 $$\phi(i) \neq \phi'(i)$$를 동시에 정당하다고 속이는 것은 불가능하다. #### Hiding Hiding은 \`"커밋먼트만 보고 원래 메시지(다항식)나 평가값을 알아낼 수 없어야 한다는 성질이다. 일반적으로 commitment scheme의 Hiding 성질은 두 가지로 나눌 수 있다. * Computational Hiding * 공격자가 다항 시간 내에 커밋된 값을 구분/복원할 수 있는 확률이 보안 파라미터 $$k$$에 대해 negligible이어야 한다. * PolyCommit\_DL에서 커밋먼트는 $$C = g^{\phi(\alpha)}$$ 형태이고, $$\alpha$$는 공개되지 않는다. 즉, $$C$$만 보고 $$\phi(\alpha)$$나 $$\phi(x)$$를 구하는 것은 이산 로그 혹은 t-SDH를 풀어야 하므로 계산적으로 숨겨져 있다고 본다. * Unconditional Hiding * 공격자가 무한한 계산 능력을 가진다 하더라도, 커밋먼트의 분포가 메시지에 전혀 의존하지 않아 통계적으로 아무 정보도 누설하지 않아야 한다. * PolyCommit\_DL에서는 같은 공개키, 커밋 구조 아래 서로 다른 $$\phi(x)$$는 서로 다른 $$g^{\phi(x)}$$에 대응하므로, 계산 능력이 무한한다면, 이론적으로는 후보 다항식들을 전부 시도해볼 수 있다고 가정할 수 있다. 때문에 Unconditional 측면의 완전 은닉성은 제공하지 못한다. ### 결론 PolyCommit\_DL은 **t-SDH** 가정과 **쌍선형 페어링**을 바탕으로, 다항식 전체에 대한 커밋과 특정 평가점에서의 증명을 모두 상수 크기로 제공하는 효율적인 polynomial commitment 스킴이다. **Setup–Commit/Open–CreateWitness/VerifyEval** 흐름을 통해 올바르게 생성된 커밋·증명은 항상 검증을 통과(**Correctness**)하고, **t-SDH** 가정 하에서 하나의 커밋에 대해 두 개의 서로 다른 다항식이나 평가값을 동시에 인정시키는 공격은 사실상 불가능하다(**Binding**). **Hiding** 면에서는 기본적으로 계산적 은닉성에 머문다. 즉, 커밋된 다항식에 대한 통계적, 완전한 은닉성(unconditional hiding)을 제공하지는 못한다. 이 한계를 해결하기 위해 KZG 구조에 Pedersen 블라인딩을 결합한 PolyCommit\_Ped 스킴이 존재하며, 이는 별도의 무작위 다항식을 추가함으로써 완전한 은닉성을 달성한다. 다음 문서에서는 PolyCommit\_Ped 스킴이 어떻게 구성되며 DL 스킴과 어떤 점에서 유사하고, 무엇을 보완하는지 살펴본다. ### Reference 1. 2. 3. --- # 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/kzg-commitment-scheme-polycommit_dl.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.