Intro

Blob은 저장된 “다수의 데이터가 압축된 데이터”에 “특정 데이터”가 포함되었는지 검증 할 수 있다. Blob이 이러한 “데이터 압축”과 “검증 매커니즘”이 가능한 이유는 SNARK의 성질을 갖는 KZG Polynomial Commitments Scheme(이하 KZG) 때문이다. 이번 시리즈는 KZG의 암호학적 내용과 이더리움이 어떤 목표를 위해 KZG를 사용했는지에 대해 다룰 예정이다.

SNARK

SNARK는 Succintness(간결한) Non-Interactive(비-대화형) Argument Of Knowledge(증명 논쟁)의 약자이다. 각 단어는 사용되는 암호학이 갖는 특징 또는 성질을 의미한다. 하나씩 알아보자

Argument Of Knowledge(증명 논쟁)

_증명 논쟁(Argument Of Knowledge)_은 어떤 행위(또는 데이터)에 대한 옳고 그름을 증명하기 위해 논쟁하는 검증 프로세스를 의미한다. 이때, 어떤 행위(또는 데이터)에 대한 옳고 그름을 증명하는 증명자(Prover)와 이를 검증하는 검증자(Verifier)가 있으며, 이들의 과정에 사용되는 암호학을 “증명 논쟁(Argument Of Knowledge)” 라고한다.

Non-Interactive(비-대화형)

_Interactive(대화형)_에서 검증을 위해 생성하는 증명 데이터는 Prover와 Verifier가 함께 만든다. 먼저 Prover가 증거의 일부를 생성하고, Verifier가 Prover에게 랜덤한 값을 전달하여 동일한 방법으로 증거를 생성하도록 지시한다. 그리고, Prover가 랜덤한 값으로 만든 증명을 다시 Verifier에게 전달하고, Verifier는 두개의 증명을 통해 Prover을 검증한다. 이처럼 Prover와 Verifier가 수 차례 데이터를 주고 받는 과정을 Interactive(대화형)이라고한다.

이에 반대로 _Non-Interactive(비-대화형)_은 Prover와 Verifier의 증명 과정에서 “서로 주고 받는 과정이 없는” 암호학을 의미한다. 즉, 증명자 혼자서 증거를 생성하는 것이다.

Succintness(간결한)

Succintness는 증거의 간결함, 즉 증명과정에 의해 산출되는 증거 데이터의 물리적 크기가 작음을 의미한다. 일반적으로 증명해야하는 데이터가 클수록 계산하는 복잡도가 증가하며, 검증 과정을 시간 또한 길어진다. 시간과 컴퓨터 자원이 충분한 과정에서 크게 문제가 되지 않을 수 있지만, 통신 프로토콜에서 사용하는 암호학인 경우, 전파 속도 및 요청 처리 시간에 영향을 주기에 아주 중요한 요구조건 중 하나이다.

정리하면 SNARK는 어떤 행위(또는 데이터)에 대한 옳고 그름을 증명하는 과정에 활용할 수 있으며, 다루는 데이터가 간결해야하고, 서로 통신을 주고 받는 과정이 없는 성질을 가진 암호학을 의미한다.

쫌더 자세한 내용을 알고 싶으신 분든 Onther에서 작성한 ZKP 기술보고서을 참고하면 좋을 것 같다.

KZG Polynomial Commitments Scheme

이더리움의 덴쿤 업그레이드를 통해 공식적으로 도입된 KZG Polynomial Commitments Scheme(이하 KZG) 또한 SNARK의 성질을 가진 암호학적 프로토콜이다. 다른 SNARK 암호학과 달리 KZG는 큰 데이터를 다항식의 형태(Polynomial)로 만들고, 이를 매우 작은 증명 데이터(Commitments)로 만들어 시간과 비용을 절감하는 특징을 갖는다. 그리고 Commitments에 특정 데이터가 포함되었는지 수학적으로 검증이 가능하다. 이더리움은 이러한 KZG의 특징을 활용하여 “다수의 데이터가 압축된 데이터”에 “특정 데이터”가 포함되었는지 검증 할 수 있다.

“KZG Polynomial Commitments Scheme”에서 _“Scheme”_는 암호학이나 컴퓨터 과학 분야에서 “특정한 목적을 위해 설계된 알고리즘 또는 프로토콜”을 의미한다. 때문에 이더리움 또한 Blob이라는 저장공간을 설계하기 위해 이더리움 내에서 사용할 수 있는 표준(프로토콜)스킴을 EIP-4844를 통해 정의했다. 이 과정에서 특정 조건을 성립하는 타원 곡선을 선택하고, 다항식의 차수, encoding/decoding 등등 규칙 및 설정 값을 정의하고, 이를 토대로 Trusted Setup, Commit, Challenge, Open, Verify 총 다섯 단계를 거쳐 증명 생성 및 검증 가능한 프로세스를 진행한다. 구체적으로 어떤 내용이 포함되었는지 알아보자.

Trusted Setup

KZG Scheme은 Prover가 증명을 만들고 Verifier가 검증하는 연산 과정에서 공통적으로 사용하는 Global Param(이하 GP)을 설정해야한다. GP안에는 비밀 값 tau(τ)가 포함되는데, τ는 KZG에서 증명 데이터를 만들고 검증하는데 굉장히 중요한 역할을 한다. 만약, τ가 유출되면 악의적인 증명 데이터를 만들고 의도적으로 검증을 통과할 수 있기에, 프로토콜 측면에서 굉장히 치명적인 취약점이 될 수 있다. 때문에 τ는 프로토콜을 설계하는 이더리움을 포함하여, 그 누구도 알면 안되는 “신뢰할 수 있는” KZG Scheme의 초기 설정값이다.

KZG Scheme은 GP의 “신뢰성”를 위해 주로 다수의 참여자들이 선택한 랜덤한 값을 지속적으로 섞어 만드는 “Trusted Setup”라는 과정을 통해 GP를 생성한다.

KZG는 증명과 검증 연산에서 타원 곡선(ECDSA)을 사용한다. 나중에 설명하겠지만, 증명 데이터를 검증하기 위해 타원 곡선의 Pairing 함수를 사용한다. 때문에, 이더리움은 Pairing-based Cryptography 중 하나인 BLS12–381 타원 곡선을 사용하며, GP는 BLS12–381 타원 곡선상의 점으로 구성된다.

Trusted Setup에 참여하는 사람들은 타원 곡선 상의 랜덤한 점를 선택하고, 다른 사람들이 선택한 점에 순차적으로 곱하는 과정을 반복하며 신뢰할 수 있는 GP를 만드는데 기여한다. 이더리움은 Trusted Setup의 참여자를 모으기 위해 KZG Ceremony 이벤트를 진행하였고, 총 141,416명이 GP를 만드는데 참여하였다.

📢 이더리움의 KZG Ceremony는 이미 종료됬지만, 진행 과정이 궁금한 독자는 100y님께서 작성한

“[Research] KZG 세레머니 — 지금 당장 이더리움에 기여하세요!”

Powers-of-tau setup

다수의 참여자가 프로토콜에서 정한 공식을 통해 τ 를 만드는 과정을 Powers of Tau(PoT)라고 하며, 이더리움은 PoT를 통해 보안성이 우수한 GP 만들어 KZG에서 사용하게된다.

[s^0G_1, s^2G_1, s^2G_1,~...~,s^{n1-1}G_1]\\ [s^0G_2, s^2G_2, s^2G_2,~...~,s^{n2-1}G_2]

타원 곡선은 프로토콜에 따라 곡선 상의 생성점(generator:G)이 정해져 있으며, 페어링 기반의(Pairing-based) BLS12–381는 두개의 생성점 G1, G2을 갖는다. GP는 생성점 G1, G2에 대한 두개의 집합으로 구성되어 있다

[~s^0 G{\scriptsize 1},s^1G{\scriptsize1},s^2 *G{\scriptsize1}, ...~,s^{4095} *G{\scriptsize1}~] = [A{\scriptsize0},A{\scriptsize1},A{\scriptsize2}, ...,A{\scriptsize{4095}}]

두 집합은 참여자들이 BLS12–381 Field 범위 내 선택한 랜덤한 점 (s : $S~\overset{\$}{\subseteq}~\text{Fr}$ ) 의 거듭 제곱을 G1, G2에 곱한 값들로 이루어져있으며, 연산된 결과 $[A{\scriptsize0},A{\scriptsize1},A{\scriptsize2}, ...,A{\scriptsize{4095}}]$ 는 하나의 정수로 표현되어 보일것이다. 이때, G1 집합의 개수(n1)과 G2 집합의 개수(n2)는 이더리움 프로토콜에서 n1=4096, n2=16로 설정했다.

📢 KZG Ceremoy에서 가장 처음으로 계산된 두 집합은 kzg-ceremoy-specs Github의

initialContribution.json에서 확인 할 수 있다.

~Alice ~: {~s{\tiny 0}}~\overset{\$}{\subseteq}~\text{Fr} \\ [~s{\tiny 0}^0 G{\scriptsize 1},s{\tiny 0}^1G{\scriptsize1},s{\tiny 0}^2G{\scriptsize1}, ...~,s{\tiny 0}^{4095} G{\scriptsize1}~] = [A{\scriptsize0},A{\scriptsize1},A{\scriptsize2}, ...,A{\scriptsize{4095}}]\\ [~s{\tiny 0}^0 G{\scriptsize 2},s{\tiny 0}^1G{\scriptsize2},s{\tiny 0}^2G{\scriptsize2}, ...~,s{\tiny 0}^{15}G{\scriptsize2}~] = [a{\scriptsize0},{a\scriptsize1},{a\scriptsize2}, ...,a{\scriptsize{15}}]

👦🏻 ~Bob ~: {~s{\tiny 1}}~\overset{\$}{\subseteq}~\text{Fr} \\ [~s{\tiny 1}^0A{\scriptsize0},~s{\tiny 1}^1 A{\scriptsize1},~s{\tiny 1}^2 A{\scriptsize2}, ...,~s{\tiny 1}^{4095} A{\scriptsize{4095}}]= [B{\scriptsize0},B{\scriptsize1},B{\scriptsize2}, ...,B{\scriptsize{4095}}]\\ [~s{\tiny 1}^0a{\scriptsize0},~s{\tiny 1}^1a{\scriptsize1},~s{\tiny 1}^2a{\scriptsize2}, ...,~s{\tiny 1}^{15}a{\scriptsize{15}}]= [b{\scriptsize0},b{\scriptsize1},b{\scriptsize2}, ...,b{\scriptsize{15}}]

Trusted Setup 과정은 순차적으로 진행된다. 위 사진의 Alice 처럼 첫번째 참여자는 선택한 랜덤한 점( $s_0$ )의 거듭 제곱을 생성점 G1, G2에 곱하고, 결과에 대한 집합 A와 a를 만들어 Bob에게 전달한다. Bob 또한 선택한 랜덤한 점( $s_1$ )의 거듭 제곱을 Alice에게 전달받은 집합에 곱하여, 결과에 대한 집합 B 와 b를 다음 참여자에게 전달한다.

~Final ~: {s{\tiny 141,416}}~\overset{\$}{\subseteq}~\text{Fr} \\ [~s{\tiny 141,416}^0B{\scriptsize0},~s{\tiny 141,416}^1 B{\scriptsize1},~s{\tiny 141,416}^2 B{\scriptsize2}, ...,~s{\tiny 141,416}^{4095} B{\scriptsize{4095}}]= [X{\scriptsize0},X{\scriptsize1},X{\scriptsize2}, ...,X{\scriptsize{4095}}]=TG_{1} \\ [~s{\tiny 141,416}^0b{\scriptsize0},~s{\tiny 141,416}^1 * b{\scriptsize1},~s{\tiny 141,416}^2 * b{\scriptsize2}, ...,~s{\tiny 141,416}^{4095} * b{\scriptsize{15}}]= [x{\scriptsize0},x{\scriptsize1},x{\scriptsize2}, ...,x{\scriptsize{15}}]=tG\tiny 2

이더리움 KZG Ceremony 참여자 기준으로, 이와 같은 과정을 총 141,416 번 반복하여, 마지막 참여자가 선택한 랜덤한 점( $s_{141416}$ )까지 계산이 끝났을 때, Global Param는 $TG\tiny 1$ 와 $tG\tiny 2$ ( 두 결과를 통합적으로 *τ * G)*의 라는 결과를 얻을 수 있다.

\tau * G = (s_0 * s_1*s_2~...~s_{141,416}) * G

τ는 “Powers of Tau”의 “Tau”를 가르키며, 각 라운드를 반복적으로 거쳐 만들어진 강력한(Power) 무작위 값을 의미한다. τ를 풀어서 보면 141,416명이 선택한 랜덤한 숫자가 반복적으로 곱해진 값이기에, 이는 충분한 무작위성을 갖는 강력한 비밀(secret) 값이라고 할 수 있다.

\tau *G{\scriptsize 1} => A \\ \dfrac {A}{G{\scriptsize 1}} => \xcancel \tau

또한 PoT는 타원곡선 상의 점과 점의 덧셈을 반복하여 만들어진다. 때문에 타원 곡선 이상 대수 문제(ECDLP)로 인해 G를 알고 있다고 해도 Alice가 만든 집합 A와 α를 보고 Bob은 절때 Alice의 비밀값(s)를 역산해 낼 수 없다. Bob이 보는 A와 α는 하나의 정수 집합으로만 보일것이다. 즉, Trusted Setup에 참여한 사람 중, 단 한명만 정직하다면 절때 τ를 알 수 없는 구조이다.

Commit

KZG Scheme의 첫번째 단계인 Trusted Setup은 말 그대로 KZG Scheme를 구현하기 위한 GP를 set up(준비)하는 단계이다. 이더리움의 Blob은 “다수의 데이터가 압축한 데이터”를 저장하기 위해 설계된 저장공간이며, KZG를 활용하여 암호학적으로 다수의 데이터를 압축하는데, 이 과정을 Commit라고 한다.

라그랑주 보간법(Lagrange interpolation)은 주어진 데이터 포인트(좌표 상의 점)들을 통해 이들 사이의 다항식 f(x)을 구하는 보간법 중 하나이며, n+1개의 점을 지나는 n차 다항식을 구할 수 있다. Blob은 타원곡선 BLS12–381 상의 점 4096개로 구성된 저장공간이다. Blob의 점 4096개가 정해지면, 먼저 라그랑주 보간법(lagrange interpolation)을 활용하여 점 4096개를 지나는 다항식(Polynomial) f(x)를 만들어 낸다.

f(X) = \textcolor{blue}{f_{4095}}X^{4095}+ \textcolor{blue}{f_{4094}}X^{4094} +~...~+ \textcolor{blue}{f_{1}}X^{1} + \textcolor{blue}{f_{0}}

(1) 다항식 f(x)가 만들어지면 모든 항의 계수( $f$ )를 추출한다.

f_{4095}*(\tau^{4095}G_1)+f_{4094}(\tau^{4094}G_1)+~...~+f_{1}(\tau^{1}G_1)+f_{0}(\tau^{0}*G_1)

(2) 추출한 모든 계수는 Trusted setup에서 만든 τ*G1 집합에 곱한다. *τ는 이때 활용하기 위해 G1 집합의 개수(n1)을 4096개로 정한것이다.

(f_{4095}\tau^{4095}+ f_{4094}\tau^{4094} +~...~+ f_{1}\tau^{1} + f_{0}\tau^{0})*G1 = \textcolor{#0000FF}{f(\tau) *G1} = Commit_f

(3) τ*G1와 다항식의 계수(f)는 공개되거나 구할 수 있는 값이기에, (2)식을 계산하여 하나의 결과를 도출해낼 수 있다. 이때 도출된 값이 KZG의 Commitments가된다. (3)식을 다시 보면, 이는 맨 처음에 구한 다항식 f(x)에 τ를 대입한 f(τ) G1과 같다. 이는, Blob의 타원곡선 점이 Commitments에 포함되었는지를 증명하는 아주 중요한 정보가 될 예정이다.

KZG Scheme의 데이터 압축과정을 정리하자면 라그랑주 보간법을 통해 Blob에 저장된 4096개의 점을 하나의 다항식(Polynomial)을 만든다. 그리고 Trusted setup에서 만든 GP의 G1 집합에 곱하여 하나의 값으로 도출된 Commitments를 구한다. 이 과정을 통해 다수의 데이터가 모여있는 Blob이 하나의 Commitments로 “압축” 되었다고 표현하는 것이다.

Challenge

Commitment는 blob의 원본 데이터를 KZG 암호학으로 압축해 48바이트 길이의 값으로 표현한 것이다. 때문에 마땅히 포함되어야하는 데이터가 blob 데이터에 포함되었는지 Commitment만 보고 확인할 수 없다. 따라서 이를 증명해야하는 blob 생성자(provder)는 “특정 데이터의 포함 여부에 대한 증명”을 할 수 있도록 proof를 생성해 검증자(verifier)함께 전달해야 하며, 이 과정의 첫 번째 단계가 Challenge이다.

verifier는 Commitment에 데이터(u)가 포함되었는지 검증하고 싶다. 즉, 다항식(=블롭 데이터) 안에 u가 존재하는지를 보이려는 것이다. 첫번째 단계인 Challenge는 verifier가 prover에게 보간법으로 만든 다항식 위의 한점 u를 전달하는것으로 부터 시작된다.

Open

f(u) = v

prover는 challenge과정에서 전달 받은 점(u)를 라그랑주 보간법으로 만든 $f(x)$ 에 대입하여 $v$ 를 구한다. 이때 v는 _evaluation_라 부른다.

(u)-v = 0

그리고 그 식을 다시 해석해 보자면 위와 같은 식이 성립된다.

f(x)-v=(x-u)Q(x)

해당 식을 풀어보면 x = u일 때, $f(x) -v = 0$ 을 만족한다. 이는 다시 말해, $f(x) -v$ 라는 다항식이 (x-u)를 인수로 포함하고 있다는 의미이기도 하기에, 위와 같은 식이 성립된다.

\dfrac {f(x)-v}{x-u}= Q(x) \\

\dfrac {f(x)-f(u)}{x-u}= Q(x)

인수 (x-u)를 오른쪽으로 넘겨 나눈 Quotient 다항식 Q(x)의 방정식을 구할 수 있다.

Q(\tau)G_1 = Q_{com}

Q(x)에서도 Commitment를 생성할 때와 마찬가지로 다항식의 계수를 추출하여, Trusted setup에서 생성된 τ·G1 집합에 곱한다. 이 과정을 통해 생성된 데이터가 바로 Proof이며, prover는 이 Proof를 통해 verifier에게 특정 데이터(u)가 포함되었는지 검증할 수 있도록 전달한다.

f(\tau)G_1~,~u~,~v~,~Q(\tau)G_1

지금까지 생성된 파라미터들은 모두 prover와 verifier가 공유하는 공개 파라미터다. 이 파라미터들을 바탕으로 어떻게 데이터(u)의 포함 여부를 검증하는지 다음 Verify 단계에서 확인해보자.

Verify

이를 알아보기 전에, 우리는 먼저 pairing 함수에 대해 알아야한다.

Bilinear Pairing Function

G1 X G2 → GT

Bilinear Pairing 함수는 두 타원곡선 그룹의 생성점(G)를 입력 받아서 하나의 값(scalar)을 출력하는 함수이다. 수학적으로 두 타원곡선 그룹, G1과 G2의 원소를 입력 받아 제3의 그룹 GT로 매핑하는함수를 의미한다.

이더리움의 KZG에서 사용하는 BLS12–381 타원 곡선 역시 Pairing Function(e)을 지원하는 Pairing-based Cryptography 계열에 속하며, Trust Setup에서 생성한 파라미터들도 두 타원곡선 그룹에서 나온 값임을 알 수 있다. Pairing Function(e)는 아래와 같은 성질을 갖는다.

e(aG_1, bG_2) = S

두 타원곡선 상의 두점 $(G_1, G_2)$ 를 Pairing Function(e)의 파라미터에 넣으면 값 Scalar(S)가 도출되는데,

S = e(G_1,bG_2)^a =e(aG_1, G_2)^b = e(bG_1,aG_2) = e(G_1,G_2)^{ab}

이때 S는 위와 같은 식을 모두 성립한다. 이러한 성질을 Bilinearity라 부르며, verifier는 해당 성질을 이용하여 prover를 검증한다.

(1)~~~f(\tau)-v\overset{?}=(\tau-u)Q(\tau)

verifier는 알고 있는 변수를 통해 위 공식을 활용하면 데이터(u)가 Commitment( $f(\tau)G_1$ )에 포함되었는지 검증할 수 있다. 이를 증명해보자.

(2)~~~(~f(\tau)-v~)G_1=(\tau-u)Q(\tau)G_1

먼저 두 변에 생성점 (G_1)을 곱하여 타원곡선 상의 한점으로 만든다.

(3.1)~~~e(~(f(\tau)-v)G_1, G_2)=e(~(\tau-u)Q(\tau)G_1~,G_2)

(3.2)~~~e(G_1, G_2)^{f(\tau)-v}\overset{?}=e(G_1,G_2)^{(\tau-u)Q(\tau)}

그리고 페어링 함수를 이용하여 위와 같은 공식 (3.2)을 성립시킬 수 있으며, 공식(1)을 두 변이 같다는것을 증명할 수 있다. 다시 공식(3.1)로 돌아가서 페어링 함수에 들어가는 파라미터를 구하여, 두 식이 같은지를 증명해보자.

e(~(f(\tau)-v)G_1, G_2)

(f(\tau)-v~)G_1 \to f(\tau)G_1 - vG_1

(3.1)의 왼쪽 식을 풀이하면 위와 같다. verifier는 $f(\tau)G_1$ $, v$ , $G_1$ 모두 알고있으니 충분이 계산할 수 있고, $G_2$ 또한 알고 있으니 왼쪽 식의 파라미터는 모두 구할 수 있다.

e(Q(\tau)G_1, (\tau-u)G_2) \\ (\tau-u)G_2 \to \tau G_2-uG_2

(3.1)의 오른쪽 식은 위와 같이 Bilinearity을 활용하여 재정의가 된다. verifier는 $Q(\tau)G_1$ , $u$ , $G_2$ 를 알고 있고 trust setup에서 생성한 $\tau G_2$ 도 알고 있으니, 마찬가지로 파라미터로 전달하는 두 값을 구할 수 있다.

마무리

이더리움은 Blob 데이터를 검증하기 위해 프로토 댕크샤딩에서 KZG Polynomial Commitments Scheme을 도입했다. 하지만 이는 현재보다는 미래의 생태계를 대비한 사전 업데이트(pre-update)로 볼 수 있다. Blob은 하나에 131,072 바이트의 대용량 데이터를 담고 있는데, 블록체인 특성상 모든 노드가 다수의 Blob 데이터를 전부 보유해야 한다면 확장성에 큰 제약이 발생한다. 이를 해결하기 위해, 모든 노드가 Blob 전체를 저장하지 않고, 일부만 분산 저장하면서 필요한 경우 각 노드가 자신이 해당 데이터를 가지고 있음을 KZG Proof로 증명하는 DAS(Data Availability Sampling) 방식을 도입할 계획이다.

이더리움의 KZG Polynomial Commitments Scheme