입문자를 위한 영지식 증명 — 2편

Published in

Decipher Media ｜디사이퍼 미디어

36 min readMay 13, 2023

해당 글은 서울대학교 블록체인 학회 디사이퍼(Decipher)에서 ‘입문자를 위한 영지식 증명’을 주제로 Weekly Session에서 발표한 내용입니다. 입문자를 위한 영지식 증명 1편에서는 영지식 증명이 탄생하게 된 과정과 특징을 살펴보았습니다. 본 <영지식 증명 2편>에서는 가장 유명한 영지식 프로토콜 2개에 대해 살펴보고 각 프로토콜을 사용하여 출시된 실제 적용 사례는 어떤 것들이 있는지 살펴보겠습니다.

Author: gganbukim, Min Young Kang

Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)

Reviewed By (박찬우, 하성환, 임요한)

영지식 증명 1편에서는 영지식 증명이 어떠한 문제를 해결하기 위해서 연구되기 시작하였고, 어떠한 맥락에서 솔루션들이 발전해왔는지에 대해 알아보았습니다. 아래의 글에서는 이렇게 발전되어온 영지식 증명이 디지털 세상에서 사용되기 위해 프로토콜로 발전되었고 그 중 가장 중요한 두 가지 프로토콜, zk-SNARK와 zk-STARK에 대해 살펴보겠습니다. 특히 zk-SNARK는 블록체인에서 가장 먼저 사용되고 또한 널리 사용되고 있는 영지식 증명 프로토콜이기 때문에 핵심 작동 원리를 조금 더 깊이있게 살펴보겠습니다.

영지식 증명 분야 입문자도 한번 읽어보면 각 프로토콜이 만들어진 핵심적인 원리와 특징을 알게 되고, 앞으로 영지식 증명에 대한 소식을 접할 때 각종 용어와 개념을 친근하게 느끼며 관련 내용들을 이해할 수 있도록 하는 것에 의의가 있습니다. 따라서 깊이있는 수학적 해석은 최소화하였으며, 세부적인 수학적 이해를 위해서는 아래의 글들을 더 살펴봐주시기 바랍니다.

1. 디사이퍼 ZK-STARK 시리즈
2. 디사이퍼 영지식 증명 이해하기 시리즈

대표적인 영지식 증명 프로토콜(1) zk-SNARK

zk-SNARK는 Zero Knowledge-Succinct Non-interactive ARgument of Knowledge의 줄임말로, 각 단어의 의미를 잠깐 살펴보고 가겠습니다. zk-SNARK는 암호학적 수학 도구를 사용해 증명의 크기를 간결하게(Succinct) 만들고, 증명하고자 하는 주체인 Prover와 증명을 검증하는 주체인 Verifier 사이의 상호 작용이 없도록(Non-interactive) 했으며, Verifier는 Prover가 제시한 증명의 유효성 외에는 아무런 추가 정보도 얻지 못하도록(Zero Knowledge) 했습니다.

이를 기술적으로 구현하기 위해 zk-SNARK에서는 Prover가 특정 조건을 만족하는 다항식을 알고 있음을 Verifier에게 증명하는 것이 핵심입니다. 여기서 다항식을 알고 있다는 말은 다항식의 계수(coefficient)를 알고 있다는 것입니다. 영지식 증명이 되려면 Prover는 다항식의 계수를 모두 알고 있지만 Verifier는 이 다항식을 전혀 알지 못하는 상태에서 Prover가 다항식을 알고 있는지 참 혹은 거짓으로 검증을 해낼 수 있어야 합니다. 이를 위해 zk-SNARK에서는 QAP(Quadratic Arithmetic Program)의 satisfying assignment를 알고 있음을 Prover가 증명하는 것으로 구현해내고 있습니다.

(미디엄에서 수식을 표현하기에 한계가 있어 본문에서는 아래와 같은 규칙으로 표현하였습니다.)

‘다항식을 안다’는 것을 어떻게 증명할까?

일반적인 다항식의 형태 a_0x_0+a_1x_1+…+anxn일 때, 다항식을 안다는 것은 계수인 a_0, a_1, a_2, …, a_n을 안다는 것입니다. 하지만 Prover가 단순히 계수들을 모두 Verifier에게 전달한다면 (1)영지식 성질을 지키지 못하며 (2)다항식의 크기가 커지면 증명의 크기가 커지게 되는 문제점이 존재합니다. 그래서 Prover가 다항식을 공개하지 않고, Verifier가 지정해준 x좌표를 Prover가 다항식에 넣어 값을 계산해서 Verifier에게 보여주는 방식으로 검증합니다. 임의로 선택된 x좌표에서 Prover가 알고 있는 다항식에서 계산한 값과 Verifier가 검증하려 하는 다항식에서 계산한 값이 같다면 높은 확률로 두 다항식이 같다고 말할 수 있습니다. 이를 슈바르츠-지펠 보조정리(Schwartz-Zippel Lemma)에서는 “차수가 n인 서로 다른 다항식이 최대 n개의 점에서 교점이 생길 수 있다.”라고 하며 뒷받침하고 있습니다. n차 다항식에서 n보다 많은 횟수만큼 서로 같은 결과값을 도출한다면 두 다항식은 높은 확률로 서로 같다고 말할 수 있습니다.

여기서 한 가지 문제는, Prover가 만약 Verifier가 선택하려하는 x좌표를 미리 알고 있다면 해당 좌표만 만족하는 임의의 다항식을 만들어 Verifier를 속일 여지가 있습니다. 그래서 선택된 x좌표를 Prover에게 밝히지 않으면서도(숨기고, Hiding) Prover가 해당 x좌표에서 다항식을 계산했다는 걸 확인할 방법이 필요합니다. 이를 위해 Homomorphic Hiding이라는 수학적 방법을 사용합니다. HH(Homomorphic Hiding)은 아래와 같은 세 가지 성질을 만족시키는 암호화 함수입니다.

E(x)로는 hiding된 x의 값을 알아내기는 매우 어렵다.
x≠y이면 E(x)≠E(y)이다.
E(x), E(y)를 통해 x, y의 산술 연산 표현식에 대한 hiding 값, E(x+y)와 같은 값을 계산할 수 있다.

여러가지 함수가 위의 성질을 만족시킬 수 있겠지만 여기서 사용하는 HH는 소수(prime number) p에 대한 E(x) = g^x (mod p) 입니다. 이 콘텐츠에서는 영지식 증명을 개괄적으로 이해하는 것이 목적이므로 왜 하필 이러한 함수가 선택되어야 하는지에 대해서는 탐구하지 않고, 더 깊이있게 이 부분을 탐구하고 싶으신 분들은 HH 성질을 만족하는 함수를 찾아가는 과정을 상세히 기술해둔 디사이퍼 글을 참고해주시기 바랍니다. 우리는 바로 다음 단계인 Blind Evaluation of Polynominal로 넘어가겠습니다.

현재의 조건은, Prover는 다항식의 계수를 모두 알고 있는(혹은 그렇다고 주장하는) 상황이며, Verifier는 Prover에게 물어볼 x좌표를 알고 있는 상황입니다. 이렇게 서로 알고 있는 지식이 다른 상황에서, 더 이상의 불필요한 지식의 소통없이 검증을 해내는 것이 목표입니다. 그 목적으로 사용되는 방법이 Blind Evaluation of Polynominal 입니다. Verifier는 Prover에게 x좌표가 아닌 x좌표를 hiding한 값인 E(x^n), E(x^(n-1)), …, E(x¹), E(x⁰)을 알려줍니다. 만약 Prover가 다항식의 계수를 제대로 알고 있다면 자신이 받은 hiding된 값만 가지고서도, HH함수의 세 번째 성질에 의해 E(a_0x⁰+a_1x¹+…+a_nx^n)를 구할 수 있습니다.

하지만 이렇게 HH방식에서 Prover가 정답을 맞춘다고 해서 정말 다항식을 알고서 정답을 맞췄다고 ‘확신’할 수는 없습니다. 확신하기 위해 Prover에게 계속 퀴즈를 내고 정답을 물어볼 수도 있겠지만 무한히 결과값을 물어볼만큼 Verifier, Prover 모두 리소스가 충분하지 않고 또 그러한 비효율성을 해결하는 것이 이 기술의 목표입니다. 그래서 리소스를 아껴 단 몇 번, 혹은 한 번의 정답 제시만으로도 Prover가 다항식을 알고 있는지에 대해 Verifier가 확신할 수 있는 방법이 필요합니다. 그래서 답을 찍어서는 도저히 맞추기가 힘들 정도로 수학적으로 어렵다고 증명된 방식으로 진화시키게 됩니다.

이를 위해 KCA(Knowledge of Coefficient Assumption)이라는 가정을 사용합니다. KCA는 zk-SNARK에서 가장 중요한 가정입니다. KCA에서는 다음과 같은 사실을 이용합니다. {1, …, p-1} 집합에 속하는 어떤 alpha와 곱셈 연산을 정의한 집합 ℤ_p^*에 속하는 a, b에 대해 b=a^(alpha)를 만족하는 (a, b) 순서쌍을 alpha-pair라고 부르고, ℤ_p^*에서 소수 p가 매우 클 때 log를 취해서 alpha를 구하는 것은 매우 어렵다는 이산 로그 문제(Discrete Logarithm Problem)가 널리 알려져 있습니다. 따라서 Verifier가 임의의 alpha를 골라 Prover에게 alpha-pair (a, b)를 전달할 경우, Prover는 alpha 자체를 알기는 매우 어렵기 때문에 Prover는 alpha가 아닌 Verifier에게 받은 alpha-pair (a, b)만을 이용하여 본인이 갖고 있는 계수(c)를 이용한 a* = a^c, b* = b^c 로 만들어진 새로운 alpha*-pair(a*, b*)를 Verifier에게 보여줍니다.

이를 좀 더 확장해서 Verifier가 Prover에게 한 번에 여러 쌍의 alpha-pair (a_1, b_1), …, (a_n, b_n)을 Prover에게 전달할 경우 Prover는 본인이 알고 있는 계수인 상수 c_0, c_1, c_2, …, c_n를 alpha-pair에 지수 곱을 하여 여러 쌍의 alpha*-pair(a*, b*)를 Verifier에게 보여줄 수 있습니다. 지수 곱을 할 경우 지수 곱을 하는 순서를 바꾸어도 값이 같으므로(예시: a^(alpha)^c = (a^c)^(alpha) = (b*)^(alpha)) alpha를 알고 있는 Verifier는 다항식의 계수인 c를 몰라도 alpha*-pair(a*, b*)를 통해 Prover가 올바르게 계산을 했는지 검증할 수 있습니다. 왜냐하면 b*=b^c=a^(alpha)^c=(a^c)^(alpha)이므로 Verifier는 알고 있는 alpha를 a*에 지수로 곱하여 구한 값과 비교해볼 수 있기 때문입니다.

여기까지, HH부터 시작해서 Blind Evaluation of Polynominal과 KCA까지 각각의 쓰임과 목적을 순서대로 이해해보면, 영지식성을 유지하면서 검증하고자 했던 우리의 의도 즉, (1)Prover는 Verifier가 선택한 x좌표를 모르고 (2)Verifier는 Prover가 알고 있는 다항식의 계수를 모르는 조건을 만족하면서도 Verifier는 Prover가 다항식을 알고 있는지를 검증할 수 있게 되었습니다.

QAP를 어떻게 만들까?

앞에서 설명한 ‘다항식을 안다는 것을 어떻게 증명할까?’를 통해 우리는 Prover와 Verifier가 서로가 가진 정보를 노출하지 않고도 True or False를 검증할 수 있는지 이해하게 되었습니다. 그렇다면 실제 코드를 통해 영지식 증명이 적용될 수 있는 다항식을 만들어야 합니다. zk-SNARK 서두에서 말했듯이, zk-SNARK에서는 QAP(Quadratic Arithmetic Program)의 satisfying assignment를 알고 있음을 Prover가 증명하는 것으로 구현해내고 있습니다. 그렇다면 Prover의 메세지를 어떠한 과정을 거쳐 다항식 문제로 만드는지 살펴보겠습니다.

(아래의 각 과정에 대한 자세한 수학적 표현과 정확한 정의에 대해 살펴보고 싶다면 두 가지 문서(문서1, 문서2)를 참고하시기 바랍니다.)

Computational problem을 특정 다항식에 대한 문제로 변환하는 과정: Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK

1. 다음과 같은 computational problem 예시를 살펴보겠습니다. Prover는 아래 문제의 x값을 알고 있음을 증명하려고 합니다.

def qeval(x):
    y = x**3
    return x + y + 5

qeval(x) == 35 for which x?

2. zk-SNARK는 flattening이라는 과정을 통해 문제를 산술회로(Arithmetic Circuit)으로 변환합니다. 산술회로 변환은 문제의 각각의 요소들을 사칙연산으로 단계별 구분하여 나타내는 것이라고 쉽게 이해해주시면 되겠습니다. 이렇게 생겨난 산술회로의 각 행을 ‘Gate’에 대응합니다. 또한 변수 역할을 하는 요소는 각각 ‘wire’에 대응합니다. 예를 들면, ‘~out = sym_2 + 5’라는 Gate는 ‘~out’, ‘sym_2’가 각각 wire에 대응됩니다.

sym_1 = x * x        //Gate1
y = sym_1 * x        //Gate2
sym_2 = y + x        //Gate3
~out = sym_2 + 5     //Gate4

3. 각 Gate에 할당된 조건식들을 R1CS(Rank 1 Constraint System) 형태로 변환합니다. 간단히 말해 R1CS는 1차원 벡터 형태로 변환하는 일종의 연립방정식 입니다. 이렇게 Rank 1인 벡터로 다항식을 표현하면 연산이 용이해진다는 의의가 있습니다. 2번에서 산술회로로 변환된 각 Gate의 식을 s∙a_1*s∙b_1-s∙c_1 =0 형태로 정리합니다. 모든 변수를 대응하여 만든 벡터는 [ ~one, x, ~out, sym_1, y, sym_2 ]이며 ~one은 상수 원소를 나타내기 위해 추가되었습니다. 각 gate 조건식을 표현하는 벡터의 집합을 정리하면 아래와 같습니다.

a_1 = [0, 1, 0, 0, 0, 0]
a_2 = [0, 0, 0, 1, 0, 0]
a_3 = [0, 1, 0, 0, 1, 0]
a_4 = [5, 0, 0, 0, 0, 1]

b_1 = [0, 1, 0, 0, 0, 0]
b_2 = [0, 1, 0, 0, 0, 0]
b_3 = [1, 0, 0, 0, 0, 0]
b_4 = [1, 0, 0, 0, 0, 0]

c_1 = [0, 0, 0, 1, 0, 0]
c_2 = [0, 0, 0, 0, 1, 0]
c_3 = [0, 0, 0, 0, 0, 1]
c_4 = [0, 0, 1, 0, 0, 0]

4. 마지막으로, QAP 다항식으로 변환합니다. R1CS 형태로 변환한 덕분에 연산을 하기에 용이해지기는 했지만 산술회로의 circuit 크기가 커질수록 Gate의 개수 또한 증가해야 합니다. 이러한 R1CS를 보다 간결한 형태로 변환하는 것이 QAP 입니다. 다항식을 만들기 위해 택한 아이디어는, 특정 벡터의 특정 변수 항에서 Gate n에서 특정 변수의 계수는 x일 때의 n과 x를 구하여 (n, x) 좌표를 구합니다.

a벡터의 x 변수 항에서 Gate1에서 x의 계수는 1이다 ⇒ (1, 1)
a벡터의 x 변수 항에서 Gate2에서 x의 계수는 0이다 ⇒ (2, 0)
a벡터의 x 변수 항에서 Gate3에서 x의 계수는 1이다 ⇒ (3, 1)
a벡터의 x 변수 항에서 Gate4에서 x의 계수는 0이다 ⇒ (4, 0)

여기서 특정 x좌표에서 특정 값을 갖는 특정 차수의 다항식을 보간할 수 있는 방법인 라그랑주 다항식(Lagrange Interppolation)을 사용하여 다항식을 만들 수 있습니다. 방금 구한 네 개의 점 (1, 1), (2, 0), (3, 1), (4, 0)을 부드럽게 잇는 함수는 3차 함수로 나타낼 수 있고, 구해진 3차 함수 다항식의 계수를 차수가 높은 항의 계수 순서대로 가져와 [a, b, c, d] 다항함수 벡터로 변형합니다. 이렇게 구해진 A 벡터만 예시로 살펴보면 아래와 같습니다.

라그랑주 방정식으로, 점들을 보간하여 구한 다항식의 계수 벡터 A — 라그랑주 다항식을 사용하여 a벡터 점들을 보간하여 구해진 다항식의 계수로 만들어진 A 벡터

이러한 방식으로 특정 s에 대해 s∙a_1*s∙b_1-s∙c_1 =0 를 만족하는 A벡터, B벡터, C벡터를 Prover가 알고 있음을 보여주면 됩니다.

여기까지 NP에 속하는 computational problem을 QAP로 변환하는 과정을 적당한 깊이의 수학적 원리만을 통해 빠르게 훑어보았습니다. R1CS와 QAP를 통해 computational problem을 벡터의 원소로 표현되는 다항식을 만들어 Verifier가 검증하기에 간결한 구조를 만들어냈습니다. 이 지점에서 zk-SNARK의 간결함(Succinct)이라는 특성을 어떻게 만들어냈는지 이해할 수 있습니다.

Succinct 개념을 근본적으로 이해하기 위해 여기까지 왔습니다. 하지만 이것이 끝이 아니라, 실제로 zk-SNARK는 한 걸음 더 나아가 Prover, Verifier 각각이 가진 정보를 숨기기 위해 QAP에서는 E(x), E(y)를 가지고 E(x*y)를 비교해야만 하는 상황이 됩니다. 하지만 선형 식에서는 E(x), E(y)를 통해 x, y의 산술 연산 표현식에 대한 hiding 값, E(x+y)만을 계산할 수 있습니다. 이 문제를 해결하기 위해 zk-SNARK는 선형식이 아닌 타원곡선과 타원곡선 내 점들의 곱셈 결과를 유한한 다른 군의 원소로 매핑할 수 있는 Elliptic Curve Pairing 함수를 이용합니다. 이 부분은 zk-SNARK의 특성이라기보다는 수학 기술적인 면이라는 생각이 들어 본 글에서는 다루지 않으려 합니다.

zk-SNARK의 non-interactive 특성은 어떻게 작동하는가?

zk-SNARK는 Succinct에 이어 Non-interactive하게 작동하기 위해 CRS(Common Reference String) 모델을 사용합니다. 지금까지의 설명으로 보면 Interactive한 프로토콜에서는 Verifier가 랜덤한 x좌표와 KCA에서 이야기한 alpha-pair(a, b) 를 Prover에게 전달하게 됩니다. 하지만 만약 Verifier가 선택한 x좌표와 alpha-pair(a, b) 값이 Prover에게 노출된다면 QAP를 만족하는 다항식을 몰라도 타당한 증명을 생성할 수 있다는 위험이 계속 존재하게 됩니다. 그래서 Verifier, Prover 사이의 정보 전달을 없애고 Non-interactive하게 작동하기 위해서는 신뢰할 수 있는 어떤 제 3자(third-party)가 x좌표와 alpha-pair(a, b) 값을 선택해 이들을 숨긴(hiding) 후 x좌표와 alpha-pair(a, b)값을 삭제 합니다. 그런 후, Prover는 숨겨진 x좌표와 alpha-pair(a, b) 값들을 이용해 증명을 생성하면 됩니다. 여기서 어떤 제 3자(third-party)가 생성한 값을 CRS라고 하고 생성하는 과정을 Trusted Setup이라고 합니다. 선택된 x좌표와 alpha-pair(a, b) 값들은 숨겨진 후 반드시 삭제되어야 하는 값들이기 때문에 toxic waste라고 부릅니다.

여기까지의 설명을 통해, zk-SNARK는 영지식 증명을 Succinct, Non-interactive하게 구현한 프로토콜이라는 것을 단순히 외우는 것이 아니라, 어떤 흐름과 수학적 근거로 구성되어 있는지를 머릿속에 큰 틀만큼은 그려보실 수 있도록 돕는 것을 목표로 하였습니다.

zk-SNARK에도 단점과 리스크가 존재합니다. 이러한 점들을 보완한 zk-STARK까지 이해하면 영지식 증명의 메인 프로토콜 2가지(zk-SNARK, zk-STARK)를 깊이있게 이해할 수 있을거라 기대합니다. zk-STARK는 수학적 배경에 대한 설명보다도, zk-SNARK의 어떤 단점을 보완했는지 그 차이점을 살펴보는 것으로 아래의 글에서 다뤄보겠습니다.

대표적인 영지식 증명 프로토콜(2) zk-STARK

zk-SNARK 도입부에서도 각 단어의 의미를 살펴봤듯이 zk-STARK도 그 이름에 담겨있는 뜻으로 핵심적인 차이점은 알 수 있습니다. zk-STARK는 Zero Knowledge-Scalable Transparent ARgument of Knowledge의 줄임말로서, 특히 Transparent 단어를 사용한 이유는 SNARK가 Trusted Setup을 기능적으로 필요로 하게 되면서 제 3자에게 의지해야하는 리스크를 zk-STARK에서는 보완하게 되었음을 강조하기 위함입니다.

쟁글(Xangle)에서도 잘 정리해주었듯이 zk-SNARK와 zk-STARK는 몇가지 핵심적인 차이점이 존재합니다. 우리는 앞에서 zk-SNARK에 대해서 상세하게 이해해보았으니 zk-SNARK 대비 zk-STARK가 더 좋아진 점에 대해서만 짚어보겠습니다.

1. Trusted Setup 필요성

zk-SNARK의 가장 큰 약점으로 항상 지적받는 부분이 Trusted Party의 존재입니다. 특히 증명을 생성하는 것에 있어 Trusted Party의 역할이 결정적이기 때문에, 이들이 fake proof를 생성할 수 있으며, 외부의 다른 집단과 담합하는 것이 가능하다는 리스크입니다.
zk-STARK는 Trusted Party 없이도 Publicly Verifiable Randomness를 차용해서 랜덤하게 만들어진 x좌표와 alpha-pair(a, b) 값을 통해 증명을 생성, 검증할 수 있게 만들었습니다. 물론 이 방식 때문에 zk-STARK는 zk-SNARK에 비해 처리 용량과 소요 시간이 늘어나 효율성은 다소 줄어들고 보안성과 어느정도 trade-off 했다고 이해할 수 있습니다.

2. Scalability

zk-SNARK에서는 증명 데이터와 검증 과정은 획기적으로 간결해졌지만, 저희가 훑어본 것처럼 prover가 증명을 생성할 때 사용하는 함수(ECA)가 어렵기 때문에 증명 생성에 많은 시간이 걸립니다.
반면에 충돌 저항성 해시함수를 사용하는 zk-STARK는 증명 생성이 빠르고 off-chain에서 대부분의 검증을 하기 때문에 on-chain에 올릴 때 드는 비용이 SNARK보다 적습니다. 그래서 transaction이 많고 활발할 때는 zk-STARK가 더욱 비용 효율적입니다.

3. 양자 컴퓨터 저항성

zk-SNARK에서 주요하게 사용되는 알고리즘인 ECDSA는 소인수 분해 기반으로써 충분히 큰 두 개의 소수를 곱하는 것은 쉽지만, 곱의 결과값을 통해 곱해진 소수를 분해하는 것은 계산적으로 매우 어렵다는 것을 바탕으로 암호학에서 사용되었습니다. 여기에 이 곱을 지수 단위로 올려 타원 곡선 상의 이산 대수값을 찾기 위해서는 log를 취해야 하는데, 소수 p가 매우 클 때 log를 취해 alpha를 구하는 것은 매우 어렵다는 이산 로그 문제(Discrete Logarithm Problem)를 통해 더 작은 비트수로도 동일한 보안 강도를 가지도록 만들었습니다.
하지만 소인수 분해를 빠르게 처리할 수 있는 양자 알고리즘인 Shor’s Algorithm에 의해 소인수 분해에 기반한 DSA 방식과 이산 로그 문제(Discrete Logarithm Problem) 모두 단시간에 풀어냄으로써 ECDSA 알고리즘은 양자컴퓨터에 취약한 근원적 구조를 가지게 되었습니다.
zk-STARK가 사용하고 있는 해시 함수는 소인수 분해를 기반으로 하지 않기 때문에 아직까지 다항 시간 안에 풀 수 있는 양자 알고리즘이 발견되지 않았습니다. 하지만 양자 기술 또한 발전되면서 해시 함수의 출력 길이가 짧을 경우에는 양자 컴퓨터로도 풀 수 있기 때문에 단순하게는 해시 함수 출력 길이를 늘이는 방식으로 쉽게 대처하여 아직까지는 양자 컴퓨터 저항성을 가진다고 알려져 있습니다.

여기까지 영지식 증명의 대표적인 프로토콜 2가지를 집중적으로 알아보았습니다. 최대한 수학적 요소는 개념과 쓰임만을 이해하는 정도로 각 프로토콜들이 생겨난 이유를 이해할 수 있게 하려 노력했습니다. 마지막으로, 실제 영지식증명이라는 기술이 어떻게 활용되고 있는지를 살펴보겠습니다.

zk-SNARK 기반 프로젝트

zCash

zk-SNARK의 첫 실활용사례이자 상징적인 존재로 zCash를 빼놓을 수 없습니다. 영지식 증명의 가장 큰 활용성이 프라이버시 보호에 있는 만큼 zCash는 그러한 가치에 충실해서 프라이버시 암호화폐를 구현하였습니다. zCash는 디지털 세상의 현금(Cash)을 만드는 것을 목표로 합니다. 여기서 현금이 뜻하는 것은 거래가 성사되는 것 이외에는 어떤 정보도 공개하지 않아도 되는 특성입니다. 우리가 현금 1만원으로 슈퍼에서 물건을 살 때, 내가 어제 어떤 거래를 했는지, 내가 믿을 수 있는 사람인지를 검증하지 않습니다. 물리적 세상에서 현금은 그것의 가치 저장 기능에 충실합니다. 하지만 디지털 세상으로 넘어오면서 물리적 세상의 현금이 가지는 프라이버시 기능이 사라지고 거래 정보들이 남게 되고 이것이 특정 주체에 의해 집중화되어 관리되어졌습니다. 이러한 특정 주체를 없앤 분산 원장으로써의 블록체인 기술이 등장했지만, 초기의 블록체인은 Transparent로 보안성(Security)을 높이려는 시도를 했습니다. 하지만 영지식 증명 기술의 발달과 도입으로 Transparent하지 않고서도 검증할 수 있게 되었고 그것을 가장 처음 활용한 것이 zCash 입니다.

zCash의 특징은 유저가 지갑을 shielding하여 정보를 가린 z-address를 이용할 수도 있고 일반적인 공개된 지갑인 t-address을 이용할 수도 있어서, 선택적으로 zCash의 화폐인 ZEC를 공개적으로 전송할지, 사적으로 전송할지 선택할 수 있다는 것입니다. 이렇게 zCash는 두 주소 체계의 공존을 통해 자금 흐름의 추적을 불가능하게 만들어 프라이버시 코인의 대표 사례가 되었습니다. 아래는 송신자와 수신자의 z-address, t-address 경우의 수 입니다.

그렇다면 zCash에서는 zk-SNARK가 어떤 부분에서 쓰이는지를 살펴보겠습니다. zk-SNARK는 Trusted Setup을 둬서 랜덤한 x좌표와 alpha-pair(a, b) 값을 만들었습니다. zCash에서는 Trusted Setup 기능을 하는 Sprout, Sapling이라는 public parameter ceremony를 통해 증명키(proving key)와 검증키(verifying key)를 만들어 냅니다. Sender는 증명키를 이용해 증명을 만들어내고 Miner는 검증키를 이용해 Prover의 증명이 zCash 합의 알고리즘을 따랐는지를 검증할 수 있습니다.

zCash도 비트코인, 이더리움처럼 합의 알고리즘, 토큰 발행량 등의 토크노믹스를 가지고 있습니다. 본 콘텐츠는 영지식 증명에 집중하기 위해 관련있는 부분만 간단히 소개했지만 zCash 자체를 조금 더 이해하고 싶으신 분은 zCash documentation을 참고해보시길 바랍니다.

Loopring

Loopring은 zk-SNARK 기술을 토대로 만들어진 non-custodial DEX를 만들 수 있는 zk-Rollup 레이어2 프로토콜입니다. 기존의 CEX의 오더북 형태 거래 경험이 가능하며 기본적인 스왑, 스테이킹, NFT 민팅 기능도 제공합니다. 항상 DEX에는 확장성을 어떻게 확보할 것인가가 주된 숙제였었는데, Loopring 1.0, 2.0 버전에서는 off-chain에서 order-messaging을 받고 거래 체결은 on-chain에서 되는 방식으로 확장성을 갖추려 하였습니다. Loopring 3.0에서는 zk-SNARK 기술을 활용하여 사용자의 지갑, 잔액, 거래 히스토리를 off-chain 상에서 머클 트리(Merkle Tree)로 저장하고, 거래 체결까지 off-chain 머클 트리를 업데이트하는 방식으로 진행하게 되었습니다. Loopring은 이더리움에 off-chain 상의 머클 트리가 모두 올바르게 연산되었다는 증거만 업데이트하면 되어 확장성을 크게 늘린 것입니다. on-chain 상에는 머클 트리 루트(root)만 저장하는 것만으로도 유저들은 DEX에서 본인들이 얼마만큼의 토큰을 가지고 있는지를 증명할 수 있습니다. Loopring의 버전에 따라 성능이 얼마나 좋아졌는지는 아래의 표를 참고해주시기 바랍니다.

zkSync 1.0 / 2.0

Matter Labs는 2019년에 시작되어 zk-SNARK 기술을 이용한 확장성 솔루션인 zkSync를 만든 팀입니다. 2020년에 출시된 zkSync 1.0은 Smart Contract 기능 없이 이더리움 상의 zk-Rollup이 가능한 형태로 빠른 지불 시스템과 큰 처리량을 주요 기능으로 컴팩트하게 만들어졌습니다. 그 다음 업데이트된 zkSync 2.0은 EVM 호환성을 갖춰 개발자들이 여러가지 언어로 이더리움 Smart Contract를 만들 수 있게 하였고 첫 활용 사례로 Curve Finance가 zkSync 2.0 위에서 런칭하였습니다.

위 도표는 zkSync 2.0이 Volition 구조를 갖게 된 모습을 그려놓은 것입니다. zkSync 2.0 출시와 함께 zkPorter를 출시하여 기존 zk-Rollup으로 트랜잭션 데이터를 on-chain에 올리던 것과 다르게 off-chain인 zkPorter에도 올릴 수 있게 하여 zkSync가 Rollup 또는 Validium 구조 중 선택할 수 있는 Volition 디자인이 되도록 만들었습니다.

zkSync 2.0을 이해할 때 중요한 부분은, 여러 기술적 장벽이 있음에도 불구하고 zkSync가 높은 수준의 EVM 호환성을 제공한다는 것입니다. zk-Rollup은 특히 기술적으로 보안이 강화되어 있고 확장성있는 우위를 갖고 있지만 EVM 호환성 문제로 실제 대중들에게 빠르게 확장되지 않는 어려움이 있습니다. EVM 확장성 문제는 간단하게 설명하면, zk-Rollup 위에서 dApp을 개발할 때 이더리움의 Smart Contract 로직을 사용할 수 없는 것이 원인입니다. EVM에는 거래의 유효성을 입증하는 증명을 생성하는 기능이 없는데 이 부분을 zkEVM이 보완해줄 수 있습니다. 하지만 영지식 증명을 생성하는 로직은 복잡한 연산을 필요로 하는데 비해 EVM은 가스비, 용량 등 많은 제한 사항이 있고, 기존 이더리움은 영지식 증명 연산에 친화적이지 않은 해시 함수를 쓰는 등 zkEVM이 처한 기술적 장벽은 많습니다. 그럼에도 불구하고 zkSync는 TinyRam, Recursive Aggregation, Heterogeneous Mixing과 같은 방법을 사용하여 높은 확장성의 zkEVM을 설계했습니다. 각 방법에 대한 구체적인 내용은 디사이퍼의 이 글을 추가적으로 참고해보시기 바랍니다.

Mina Protocol

미나 프로토콜은 지분 증명 방식(PoS)을 합의 알고리즘으로 하고, 영지식 증명을 통해 블록 사이즈를 22KB로 제한하여 경량화된 노드를 운영할 수 있도록 하는 zk-Monolitic 레이어 1 블록체인 입니다. 가장 큰 특징은, zk-SNARK를 재귀적으로, 곧 생성된 증명을 모아 또 다시 그 증명들을 검증하는 하나의 증명을 생성하는 방식으로 적은 용량의 증명을 만들어 냅니다.

미나 프로토콜은 Snarketplace라는 개념을 만들어서 ‘블록 생성자’들과 ‘SNARK 작업자’들이 생태계 내에서 역할을 하도록 만들었습니다. Snarketplace에서는 미나 토큰이 네이티브 토큰으로 사용되고, 블록 생성자들이 블록을 생성하기 위해 작업들의 목록을 Snarketplace에 내어놓으면 SNARK 작업자들이 각자 수수료를 제시하며 작업들에 대한 zk-SNARK 증명을 생성하게 됩니다. 생성된 증명을 블록 생성자는 미나 토큰을 소비하며 SNARK 작업자들에게 사오게 되고, 이렇게 SNARK-ed한 블록을 미나 프로토콜 네트워크에 업데이트하게 됩니다. 이처럼 미나 프로토콜은 zk-SNARK 기술이 가지는 간결함(Succinct)을 최대한으로 활용하여 경량화된 노드를 발전시키고 있고 이를 통해 성능이 낮은 하드웨어에서도 노드를 운영할 수 있어 탈중앙화를 보다 완전하게 구현하려 하고 있습니다.

zk-STARK 기반 프로젝트

zk-STARK을 이용한 프로젝트들은 대부분 Starkware 회사에서 만든 제품들을 통해 최종 제품인 dApp으로 만들어지고 있습니다. 따라서 Starkware 회사의 대표 제품인 StarkEx와 StarkNet에 대해 알아보겠습니다.

StarkEx

StarkEx는 이더리움 레이어2 확장 솔루션으로, DEX와 같은 dApp들이 올라갈 수 있도록 설계된 것입니다. StarkEx는 범용 솔루션 형태는 아니기 때문에 프로젝트를 의뢰하면 Starkware 개발자들이 해당 프로젝트에 맞는 영지식증명을 맞춤형으로 직접 설계하고 있습니다. 또한 Smart contract를 지원하지 않기 때문에 다양한 dApp을 개발자들이 자발적으로 만들어 올리기에는 제한적인 제품입니다. StarkEx는 기본적으로 이더리움과 ERC-20, ERC-721, ERC-1155 토큰, EVM 호환성 있는 토큰을 지원하며 BTC와 같은 비이더리움 토큰 중 주요 토큰은 wrapped로도 지원합니다. StarkEx에는 크게 두 가지 버전, Spot Trading과 Perpetual Trading이 있는데, Spot Trading은 자산의 즉각적인 거래 기능을 주요하게 지원하고, Perpetual Trading은 현재 담보 자산이 없어도 미래 가치에 대해 거래를 할 수 있는 선물 거래 기능을 주요하게 지원합니다. 이러한 이유로 StarkEx는 DEX, NFT 거래소, 파이낸싱 분야의 dApp에 주로 활용되었습니다. StarkEx의 작동 원리를 큼직하게 이해해보면 아래와 같습니다.

(Off-chain) Application 단에서 발생한 거래들이 수행된 다음, StarkEx Service로 거래들을 모두 보냅니다.
(Off-chain) StarkEx Service에서 받은 거래들을 batch로 나누고 서로 공유된 Prover인 SHARP에 보내어 증명을 만들어 냅니다.
(On-chain) 만들어낸 증명을 On-chain 상에 있는 Verifier가 받아 검증을 합니다.
(On-chain) 검증 결과가 True라면 StarkEx Contract에 보내어 State를 업데이트 합니다.

활용 사례 — dApp

StarkEx의 기본적인 구조와 특징을 알고서 활용 사례 dApp을 살펴보면 self-custody 기반의 탈중앙화거래소, NFT 거래소, 민팅 서비스, DeFi 서비스가 많은 것을 이해할 수 있습니다. 결국 이 서비스들은 zk-STARK 기술을 활용하여 높은 거래처리량(9,000+ TPS)을 탑재할 수 있게 되었고 이러한 이점을 활용해 체결 속도가 빠른 DEX, 선물 거래, 보안성 높은 NFT 거래 등의 end-user단의 서비스로 만들었음을 이해할 수 있습니다.

StarkNet

방금 살펴본 StarkEx라는 테스트베드를 통해 zk-STARK이 잘 작동한다는 것을 확인했으니, 이제는 L1처럼 누구나 dApp을 자유롭게 구축할 수 있는 오픈소스 범용 zk-Rollup을 개발할 필요가 있었습니다. 이에 따라 2021년 11월 29일 Starkware는 zk-STARK 기술을 사용하여 이더리움 상에서 zk-Rollup 기반으로 Smart Contract를 배포할 수 있는 튜링 완전 STARK L2솔루션인 StarkNet을 런칭하게 됩니다.

StarkNet의 작동 원리를 이해하기 위해 핵심적인 특징은 두 가지로 (1)카이로(Cairo; CPU Algebraic Intermediate Representation)와 (2)SHARP(Shared Prover)입니다.

1. 카이로(Cairo)

카이로는 STARK 프로그램을 지원하는 프로그래밍 언어로 카이로를 사용하면 어떤 카이로 기반 프로그램도 검증할 수 있습니다. 특히나 카이로는 범용 검증자 컨트랙트를 사용하기 때문에 기존처럼 디앱마다 신규 검증자 컨트랙트를 구축할 필요가 없어졌습니다. 여기에 StarkNet은 비동기 메시지 전달 방식을 통해 이더리움 컨트랙트와도 상호 작용할 수 있어 이더리움 디앱과도 상호 작용 가능한 장점이 있습니다. 카이로 언어를 바이트 코드로 전환해주는 자체 컴파일러부터 카이로 전용 가상머신, 디버거, 통합 개발 환경(IDE)가 존재하기 때문에 간편한 개발 환경을 제공해주고 있다고 볼 수 있습니다.

이렇게 Starkware는 자체적인 언어인 카이로 생태계 구축을 통해 zkEVM을 최종 목표로 삼고 있지 않는 모습인데, 그 이유는 (1)이들은 높은 확장성을 달성하려면 EVM을 표방하는 것이 아니라 zk-Rollup에 최적화된 언어와 가상머신(VM)을 구축해야 하고 (2) 몇 년 뒤면 모든 디앱들이 L2 위에서 구동될 것이기 때문에 EVM의 중요성과 영향력은 시간이 지날수록 점점 퇴색할 것이라고 믿고 있기 때문입니다. 몇 십년 후에 뒤돌아 보았을 때 어떠한 믿음이 세상을 지배하게 되는지 궁금해지는 지점입니다.

2. SHARP(Shared Prover)

카이로와 함께 StarkNet의 중요한 특징은 범용 연산을 위한 STARK의 증명 생성 엔진, SHARP 입니다. SHARP는 한 종류의 트랜잭션에 대해서만 STARK 증명을 생성하는 StarkEx와 달리 복수의 dApp에서 발생하는 다양한 종류의 트랜잭션을 모두 처리한다는 점입니다.

여기서 한 발 더 나아가 STARK 증명들을 합쳐서 다시 증명하여 하나의 STARK 증명으로 합치는 재귀적 증명(Recursive Proving) 방식 또한 StarkNet에 도입되었습니다. 이러한 재귀적 증명은 각 트랜잭션들을 연산하는 데 소요되는 시간은 선형적으로 증가하는 반면, STARK 증명을 생성하는 데 소요되는 시간은 log(T)의 관계를 갖는 로그화 압축(Logarithmic Compression) 특성이 있기 때문입니다. 따라서 재귀적 증명이 도입된다면 확장성이 크게 향상되고 비용 또한 낮아져 레이어3이 더욱 활성화될 수 있다는 비전이 있습니다.

StarkNet 생태계가 완성되기 위해서는 완벽히 탈중앙화된 네트워크를 구축해야한다고 Starkware는 생각합니다. 이를 위해 STARK 증명 생성자인 오퍼레이터(Prover)를 완전히 탈중앙화 해야하며, 누구나 StarkNet 검증자가 될 수 있도록 풀 노드를 도입해야 합니다. Starkware는 Erigon, Nethermind, Equilibrium과 협력하여 풀 노드 시스템을 준비하고 있으며 오퍼레이터 소프트웨어 또한 Public 출시할 예정입니다. 앞으로 남은 StarkNet의 발자취를 통해 Starkware의 비전이 이뤄지는지 지켜보는 것도 블록체인 생태계의 굵직한 줄기를 이해하는 좋은 접근이 될 것입니다.

나가며: 영지식 증명의 가치

본 글에서 영지식 증명이 풀려고 한 문제부터 영지식 증명이 암호학에서 개념화되고 솔루션으로 발전한 순서대로 살펴보았습니다. 그리고 프라이버시와 확장성의 한계를 균형있게 해결하고자 하는 기술로서 영지식 증명이 사용되고 있고, 대표적인 프로토콜로 zk-SNARK, zk-STARK가 있음을 이해했습니다. 대표적으로 zk-SNARK가 암호학에서 이론적으로 도출해낸 여러 수학적 도구들을 어떻게 코드와 연산으로 녹여냈는지 알아보았습니다. 그리고 나서 zk-STARK가 가진 차이점을 통해 zk-STARK 또한 이해해보았습니다.

영지식 증명은 블록체인만을 위해 발전된 기술이 아니라는 점을 독자 분들께서 이해하시면 좋겠습니다. 영지식 증명이 풀고 싶은 문제는 프라이버시와 확장성이고, 이러한 문제가 부각되는 분야가 블록체인이었기 때문에 영지식 증명이 문제 해결을 위한 도구이자 기술로서 활용되고 있는 것입니다. 구체적인 활용 사례들을 통해 영지식 증명의 왜(Why)를 요약해보자면, zCash는 프라이버시를 지키기 위해, Loopring은 비수탁형, 곧 유저가 ‘본인의 자금을 가지고서도’ 금융 시스템을 이용할 수 있도록, zkSync는 ‘간결함’을 최대한으로 활용해 확장성있는 레이어2 솔루션을 제공하기 위해, Mina Protocol은 노드 ‘경량화’된 레이어1을 제시하기 위해 zk-SNARK 기술을 활용하고 있습니다. StarkEx와 StarkNet 또한 같은 Why를 가지고 zk-STARK 기술을 활용하여 블록체인 생태계를 고도화시키고 있습니다.

영지식 증명 기술처럼, 현재의 기술 선구자들이 치열한 연구, 개발을 통해 우리가 도달할 수 있는 ‘한계 지점’를 부수고 블록체인으로 할 수 있는 범위를 확장해주고 있다 생각합니다. 그 후에 우리가 할 수 있는 일은, 영지식 증명 기술이 주는 혜택을 제대로 활용한 dApp들을 개발하여 기술 선구자들이 닦아놓은 길 위를 풍요롭게 장식하는 것이라 생각합니다. Mass adoption의 미래에 대해 zkEVM과 Starkware의 접근법이 다르듯 미래를 예견하는 시각은 모두 다르지만 결국 목적은 더 빠르고 효율적인 블록체인 생태계를 만드는 방향으로 나아가고 있다는 것은 이번 영지식 증명 탐구를 통해 확실하게 확인할 수 있었습니다.