Zero-Knowledge proof :: chapter 2. Deep Dive into zk-SNARKs

Published in

Decipher Media ｜디사이퍼 미디어

18 min readMar 18, 2019

Writer: Jihyeok Choy(Jihyeok Choy), Kevin Sohn(Kevin Sohn)
Seoul Nat’l Univ. Blockchain Academy Decipher(Medium)

Reviewed by (Ben)

서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’에서 블록체인 기술에 관한 글을 연재합니다. 이번 주제는 “Zero-Knowledge Proof”이며, chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs, chapter 2. Deep Dive into zk-SNARKs 로 나누어 설명합니다.

지난 글에서 zkp가 무엇인지, 또 non-interactive zkp(특별히 Schnorr Identification Protocol)에서 zk-SNARKs라는 이론이 어떻게 나오게 되었는지 살펴보았다. 이번 글에서는 zk-SNARKs가 어떤 로직으로 정보를 숨기면서 증명을 가능하게 하는지 자세하게 살펴보도록하겠다.

지난 1편의 Alibaba’s Cave [출처] What is zkSNARKs: Spooky Moon Math

zk-SNARKs는 zero-knowledge Succinctness Non-interactive ARguments of Knowledges의 준말로, “간결함을 더한 Non-interactive zkp”라는 뜻이다. 이때 의미하는 간결함이란, 검증자의 간결함을 의미한다. zk-SNARKs는 간결한 증명을 위해 R1CS(Rank 1 Constraint System)과 QAP(Quadratic Assignment Problem)을 이용해 문제를 변환 했으며, 정보를 숨겨 zero-knowledge를 이루기 위해 Elliptic Curve Pairing을 이용했다. 아래의 예시를 통해

원래의 문제 => R1CS => QAP => Elliptic Curve Pairing => ZKP

로 넘어가는 과정을 설명하도록 하겠다.

Public 한 정보: f(x): y= x³+2x²+x+1, y=19
Prover의 목적: 위 식의 해(x=2)를 밝히지 않으면서 알고있음을 증명

R1CS

먼저, 우리는 주어진 방정식(y=x³+2x²+x+1, y=19)을 연산이 용이한 형태인 R1CS 형태로 변환한다. 이를 위해 방정식을 단계적 곱 연산으로 펼친다.

Gate1: x*(x+2) = sym1
Gate2: sym1*x = sym2
Gate3: (sym2 + x +1) * 1 = y

Gate1~Gate3까지의 연산을 수행하면 원래의 식(y=x³+2x²+x+1)이 구해진다. 각각의 Gate들은 곱 연산으로 펼쳐져 A*B=C 의 형태를 띄고 있으며, 중간 산출물 sym1, sym2를 포함한 5가지 수((1(상수), x, sym1, sym2, y))로 이루어져 있다.

A항은 각 Gate에서 x, sym1, sym2 + x + 1이고 이를 [1, x, sym1, sym2, y] 형태로 나타내면

A:     gate1 gate2 gate3
     1   0     0     1
     x   1     0     1
  sym1   0     1     0
  sym2   0     0     1
     y   0     0     0

으로 나타낼 수 있다. 마찬가지로 B, C 항을 다음과 같이 나타낼 수 있다.

이는 주어진 방정식 y=x³+2x²+x+1 의 형태를 변환시킨 것으로, 방정식과 주어진 행렬들은 완벽한 동치이다.

해당 행렬들은 각 Gate에서 사용된 변수(1은 상수이지만 편의상 변수라고 부르겠다)들의 계수 정보를 나타내는 행렬이다.

Prover가 보유하고 있는 private한 정보인 방정식의 해(x=2) 역시 변환한다. Gate1, 2, 3에서 x=2를 대입했을 때 다섯개의 변수들은 각기 고유한 값을 가진다. 따라서 x=2는 다음과 같이 변환된다.

               s 
           1   1
x=2 =>     x   2
        sym1   8
        sym2   16
           y   19

x=2와 동치인 위 벡터를 s라고 지칭하겠다.

QAP

R1CS 형태로 변환된 방정식을 QAP 형태로 다시 한번 변화시킨다. 이 과정은 두 가지 목적을 띈다.

문제의 변형
검증의 간결함 부여

먼저, 1번부터 살펴보자.

A 행렬의 x 항([1,0,1])을 살펴보자. 이것이 의미하는 바는
- Gate1에서 x는 1이란 계수를 가진다. => (1, 1)
- Gate2에서 x는 0이란 계수를 가진다. => (2, 0)
- Gate3에서 x는 1이란 계수를 가진다. => (3, 1)
이다.

위 정보는 기술된 대로 3개의 점으로 나타낼 수 있다. 이를 Lagrange Interpolation을 이용하여 3개의 점을 부드럽게 잇는 함수(3개의 점이므로 여기서는 2차 함수)로 나타내면,
(1,1), (2,0), (3,1) => f(x) = x² - 4x + 4 (자세한 계산은 생략)
이다. 위 다항함수를 각 항의 계수를 따와 [4, -4, 1]이라고 나타내겠다.

같은 방법으로 A, B, C 모두 적용하면 다음과 같이 행렬이 다항함수 벡터로 변형된다.

각 다항함수는 각 게이트에서의 계수 정보를 지나는 함수이다. 따라서 당연히 세 다항식 벡터 A[t], B[t], C[t]는 각 게이트(t=1, t=2, t=3)에서 각각 A, B, C 항의 계수를 반환한다.

마찬가지로, 세 다항식 벡터는y=x³+2x²+x+1와 동치이다.

문제의 변형

R1CS와 QAP를 이용해 원래의 방정식을 세 다항식 벡터로 변환시킨 것은 ‘문제' 자체를 변화시키기 위해서다. 이제 문제가 어떻게 바뀌었나 살펴보도록 하자.
Prover만이 알고 있는 벡터 s와 세 다항식 벡터 중 A[t]를 함께 살펴보도록 하자. 우선 s와 A[t]를 곱(내적)했을 때의 의미를 살펴보자.

s . A[t] (s와 A[t]의 내적)은 왼쪽과 같이 계산한다. s의 인자와 그에 대응하는 A[t]의 다항식을 곱하고 그것들을 모두 더한다.
왼쪽의 예시의 경우 결과값인 A(t)는 [1, -1.5 , 2.5]가 될 것이다.

그렇다면 A(t)가 의미하는 것은 무엇일까?
A 항은 각 게이트에서 x, sym1, sym2 + x + 1 이었으며, s의 값을 실제 대입하면 각각 2, 8, 19가 될 것이다. 이는 A(t)에 1, 2, 3을 대입한 값과 일치한다.

즉, 우리는 A(t)가 각 Gate에서 A 항의 실제 값이란 것을 알 수 있다. 마찬가지로 B(t), C(t)도 각 Gate에서 B 항, C 항의 실제 값이 된다. 이때, 각 Gate에서 A, B, C는 A * B = C 라는 등식을 만족하므로, A(t) * B(t) — C(t) 라는 다항식은 t = 1, 2, 3 에서 0 값을 반환할 것이다. 따라서, A(t) * B(t) — C(t) 는 Z(t) = (t-1)(t-2)(t-3) 이라는 다항식으로 나눠 떨어지게 되고,

A(t) * B(t) - C(t) = H(t) * Z(t), Z(t)=(t-1)(t-2)(t-3), H(t)는 다항식

을 만족하게 된다. (참고로 위 예제에서 A(t), B(t), C(t), H(t)는 각각

A(t) = [1, -1.5, 2.5]
B(t) = [7, -3.5, 0.5]
C(t) = [-5, 15.5, -2.5]
H(t) = [-2, 1.25]

이다) 우리의 문제는 이제,

“y=x³+2x²+x+1, y=19 의 해가 x=2 인가?” 에서
“세 다항식 벡터 A[t], B[t], C[t]가 주어졌을 때, Z(t) 로 나눠떨어지도록 A(t), B(t), C(t) 를 만드는 벡터가 s = [1, 2, 8, 16, 19]인가?”

로 변형된다.

변형된 문제에서 주어진 값 A[t], B[t], C[t], Z(t) 로 부터 식 A(t) * B(t) — C(t) = H(t) * Z(t) 를 만족하는 A(t), B(t), C(t), H(t) 는 정확한 s를 모른다면 제시할 수 없다. 따라서, Prover가 올바른 A(t), B(t), C(t), H(t) 를 제공한다면 s 를 알고 있다고 판단 가능하다.

여기서 Succinctness를 더하자.

이를 위해 우리는 어떤 특정 점(e.g. t = t_0)을 잡는다. 위 주어진 식에서 양측 다항식이 같음을 증명하는 것 보다 어떤 특정 점에서 증명을 하는 것이 훨씬 간결하다. (이론적으로 무한한 실수 범위에서 서로다른 두 다항식의 교차점은 유한하므로 우연히 겹칠 확률은 0이다. 따라서 어느 랜덤한 한 점에서 증명하더라도 두 다항식이 같음을 납득할 수 있다. 앞의 R1CS를 실수범위의 QAP로 확장시킨 이유가 바로 증명을 위한 임의의 점을 택하기 위함이다.)

주어진 값은 이제 A[t], B[t], C[t], A[t_0], B[t_0], C[t_0], Z(t), Z(t_0) 로 부터 Prover는 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) 를 만족하는 특정 값 A(t_0), B(t_0), C(t_0), H(t_0) 를 제시한다. Verifier는 다음 두 가지를 검사한다.

제시된A(t_0), B(t_0), C(t_0), H(t_0)가 위 식을 만족함을 검증
제시된 A(t_0), B(t_0), C(t_0)가 각각 A[t_0], B[t_0], C[t_0]로 부터
같은 s에 대해 나온 값임을 검증

그렇다면 점 t_0 는 어떻게 정해질까? zk-SNARKs는 이를 위해 Trusted Party를 두었으며, 이 집단이 해당 점을 정해 값들을 생성/공개한다.

Elliptic Curve Pairing

주어진 문제를 변형하고 간결함을 더했지만 아직 정보를 숨기는 것, 즉 Zero-Knowledge를 더하지 못했다. 이를 위해 zkSNARKs에서 이용한 알고리즘이 Elliptic Curve, 타원곡선 암호화 방식이다. (구체적인 타원곡선의 원리는 이곳을 참고바람)

해당 작업은 큰 의미에서 ‘일반적인 계산을 타원 곡선 세계 위로 가져온다’라고 할 수 있다. 즉, 우리가 증명하고자 하는 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) 등식을 타원 곡선 위에서 증명하고자 한다. 타원곡선의 세상에서는 정보를 숨기고 등식만 증명하는 것이 가능하기 때문이다. 이를 위해 짚고 넘어가야할 타원 곡선의 특징은 다음과 같다.

상수 p에 대응하는 타원 곡선위의 점 P가 P = p * G라고 할 때, 점 P로부터 상수 p를 도출해낼 수 없다. (G는 알려진 타원 곡선위의 점)
P = k*Q 라고 할 때, k를 알지 못한다면 R=k*S인 (R, S)를 도출하는 방법은 R=c*P, S=c*Q (c는 임의의 상수)와 같이 (P, Q)에서 도출하는 방법 뿐이다.
e(P,Q)는 타원곡선에서 곱셈과 같은 역할을 한다. 특히,
e(P, S) = e(R, Q) <=> There exists k s.t. P*k=Q, R*k=S

위 세 특징을 이용하여 우리가 증명하고자 하는 문제를 다시 한 번 변형해보자. 원래의 증명식은 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) 이다. 각 항을 공개된 어떤 점 G를 이용해 타원 곡선 위의 점으로 변환 시키면,

π_a = A(t_0) * G
π_b = B(t_0) * G
...

로 표현 되며, 증명식은

e(π_a, π_b)/e(π_c, G) = e(π_h, Z(t_0) * G)

로 변형 할 수 있다. (G, Z(t_0) * G는 공개 되어있다.)
t_0 를 정한 후 Trusted Party가 공개하는 정보 역시 A[t_0], B[t_0]… 에서,

A[t_0] * G = [A1(t_0)] * G = [A1(t_0) * G] = [π_a1]
             [A2(t_0)]       [A2(t_0) * G]   [π_a2]
             [A3(t_0)]       [A3(t_0) * G]   [π_a3]
                ...               ...         ...

로, 즉 다시말해 기존에 공개하던 벡터가 타원곡선위로 대응 시킨 점들의 벡터로 변형된다.

Prover는 변형된 식을 증명하기 위해 공개된 정보를 이용해 다음의 세 가지 사항을 보여야한다.

위의 식을 만족하는 π_a, π_b, π_c, π_h 를 제시
제시한 점들이 Trusted Party가 공개한 정보( A[t_0]*G, B[t_0]*G, C[t_0]*G )로 부터 나왔는지 증명
제시한 점들을 도출할 때 사용한 s가 각 세 경우 모두 같은지 증명

1번의 π_a, π_b, π_c 는 Trusted Party가 공개한 정보 A[t_0]*G, B[t_0]*G, C[t_0]*G 에 각각 해답인 s 를 곱하여 계산할 수 있다. (Prover는 t_0 를 모르기 때문에 s를 사용할 수 밖에 없다.

π_h 의 경우, 앞의 세 점처럼 구할 수 없다. 이때, Prover는 원래의 식 A(t) * B(t) — C(t) = H(t) * Z(t)을 계산하여 H(t) 식 자체를 알수 있다. (위의 예시에서 H(t) = [-2, 1.25] = 1.25t — 2) Trusted Party는 증명을 위해 G*t_0, G*(t_0)^2, G*(t_0)^2... 를 제공한다. Prover는 원식을 알고 있기 때문에 제시된 값들로 부터 π_h 를 만들 수 있다.
앞선 예제로 예를 들면, π_h = G * H(t_0) = G * (1.25 * t_0 — 2) = (G * t_0) * 1.25 + G * (-2) 의 방법으로 구할 수 있다. (G * t_0, G 가 공개 되어있다)

2번의 경우, 위에 기술한 타원곡선의 두 번째 성질을 이용한다. Trusted Setup은 어떤 비밀스러운 임의의 값 k_a, k_b, k_c 를 생성한 후 (해당 값은 공개되지 않는다),

A[t_0] * G * k_a
B[t_0] * G * k_b
C[t_0] * G * k_c

를 공개한다. Prover는
π_a' = π_a * k_a, π_b' = π_b * k_b, π_c' = π_c * k_c 인
π_a', π_b', π_c' 를 제시하여야 한다.
Prover는 k_a, k_b, k_c를 모르지만 타원곡선 2번 성질에 의해 공개된 A[t_0] * G * k_a 를 s 와 를 곱하여 π_a' 를 만들 수 있다. 왜냐하면,

π_a' = π_a * k_a = (s . (A[t_0] * G)) * k_a = s . (A[t_0] * G * k_a)

이기 때문이다.
두 번째 성질을 다시 살펴보면:

P = k*Q 라고 할 때, k를 알지 못한다면 R=k*S인 (R, S)를 도출하는 방법은 R=c*P, S=c*Q (c는 임의의 상수)와 같이 (P, Q)에서 도출하는 방법 뿐이다.

이를 통해 Prover가 증명하는 사항은 k_a, k_b, k_c를 알지 못할때, A(t_0) * G, B(t_0) * G, C(t_0) * G 가 공개된 A[t_0] * G, B[t_0] * G, C[t_0] * G 로부터 도출 되었다는 것이다.

이제 3번을 증명하자. 이를 위해 Trusted Party는 새로운 값 b 를 생성하여(이번에도 b 는 숨긴다),

(A[t_0] + B[t_0] + C[t_0]) * G * b

를 공개한다. Prover는 기존에 공개했던 π_a, π_b, π_c 와 함께
π_s' = (π_a + π_b + π_c) * b 를 만족하는 π_s' 를 b 없이 증명해야 한다. 올바른 Prover는 s . (A[t_0] + B[t_0] + C[t_0]) 를 통해 쉽게 π_s' 를 생성 할 수 있다. 왜냐하면,

π_s' = (π_a + π_b + π_c) * b
     = (s . A[t_0] * G + s . B[t_0] * G + s . C[t_0] * G) * b
     = (s . (A[t_0] + B[t_0] + C[t_0]) * G) * b

이기 때문이다. 이를 통해 증명하는 것은 ‘Prover가 π_a, π_b, π_c 를 도출할 때 사용한 s가 모두 같은가?’이다. 다른 s 를 사용했다면 바로 위의 식 line2 => line3로 넘어갈때 하나의 s로 묶이지 않는다.

정리하면,

Prover는 A[t], B[t], C[t] 를 공개한다.
Trusted Party는 t_0, k_a, k_b, k_c, b를 정한 후, Prover의 증명을 위해
-A[t_0] * G, B[t_0] * G, C[t_0] * G한
-A[t_0] * G * k_a, B[t_0] * G * k_b, C[t_0] * G * k_c
-(A[t_0] + B[t_0] + C[t_0]) * G * b
-G, t_0 * G, t_0^2 * G, ...
를 공개한다.
Prover는 식 A * B — C = H * Z 를 만족하는 π_a, π_b, π_c, π_h 와 이것들이 Trusted Party가 제시한 정보로부터 나왔음을 증명하는 π_a', π_b', π_c', π_s' , 총 8개의 점을 제시한다.

흥미로운 점은 Prover가 증명을 위해 제시해야 하는 proof가 단 8개의 점(=288 bytes)이며, 이는 문제의 크기와 상관없이 일정하다. 또한, Verifier 역시 8개의 점들로 간단한 연산을 통해 옳음을 납득할 수 있다. zkSNARKs의 큰 장점 중 하나가 바로 이 증명의 간결함이다.

vs zk-STARKs

zk-SNARKs 이후 해당 이론의 단점을 보완하기 위해 나온 영지식 증명 이론이 zk-STARKs이다. zk-STARKs는 세 가지 측면에서 zk-SNARKs 보다 강점을 가진다. 이 글에서는 각각에 대해 간단히만 짚고 넘어가도록 하겠다.

Trusted Setup

zk-SNARKs의 가장 큰 약점은 Trusted Party의 존재이다. 프로토콜 내에서 Trusted Party의 역할이 큰 비중을 차지하고 있으며, proof 생성에 있어 많은 비중을 차지한다. 이들은 공개되면 안될 정보 t_0, k_a, k_b, k_c, b 를 통해 fake proof를 생성할 수 있으며, 외부의 다른 집단과 collusion이 가능하다.

zk-STARKs의 T는 Transparent(투명한)이다. 해당 이론은 Trusted Setup 단계에서 만들어지는 휘발성 정보들이 비트코인 마이닝과 비슷한 방법으로 random하게 생성되도록 설계하였다. 중요한점은 이를 통해 Trusted Party의 존재가 불필요해졌다는 것이다.

Proof 생성 시간

zk-SNARKs에서는 증명 데이터와 검증 과정은 획기적으로 간결해졌지만 prover가 proof를 생성하는 시간은 매우 느리다. zk-STARKs 논문에 따르면 해당 proof 생성 작업이 다음과 같이 빨라진다고 한다.

y축이 proof 생성 시간이고, x축은 문제의 복잡성이다.

그래프에서 알 수 있는 사실은 zk-STARKs(초록색)에서의 proof 생성 시간이 zk-SNARKs(파란색)에 비해 빠르다는 점이다.

Quantum Computers Resistance

zk-SNARKs에서 주요하게 사용되는 알고리즘인 ECDSA는 양자 컴퓨터에 취약하다고 알려져있다. Shor’s Algorithm(소인수 분해를 빠르게 처리할 수 있는 양자 알고리즘)과 같은 방식을 통해 공개키로부터 비밀키를 추출해 낼 수 있기 때문이다. 반면 zk-STARKs는 ECDSA와 같은 key pair 알고리즘에 기반하지 않기 때문에 양자 컴퓨터 공격으로 부터 안전하다.

Application

zk-SNARKs의 특징 중 하나는 증명을 생성하는데 걸리는 시간과 검증하는데 걸리는 시간이 비대칭적이라는 것이다. 위 예시에서 f(x)=19의 해가 x=2라는 것을 zk-SNARKs 사용하지 않고 증명할 경우 그것을 검증하기 위해서는 f(x)에 x=2를 대입하여 그 값이 19와 일치하는지 직접 계산해야할 것이다. 마찬가지로, 블록체인의 맥락에서, 일반적으로 한 명의 채굴자가 생성한 블록이 올바르다는 것을 증명하기 위해서는 모든 채굴자들이 해당 블록을 직접 실행해보아야 한다. 반면 zk-SNARKs에서 검증자는 원본을 직접 검증할 필요 없이 그것보다 훨씬 간결한 proof만 검증하는 것으로 충분하다.

이러한 특성을 블록체인의 확장성에 활용한 예시로 코다 프로토콜(Coda Protocol)이 있다. 일반적인 블록체인과 달리 코다에서는 채굴자들이 트랜잭션의 원본 데이터 대신 자신들이 올바른 블록을 생성했다는 증명만을 블록에 담는 것으로 확장성 문제를 해결하고자 한다. 이더리움의 플라즈마 사이드체인 관련 연구 중에도 zk-SNARKs를 활용한 사례가 등장하고 있다. 그동안 일반상태 플라즈마 체인의 가장 큰 걸림돌 중 하나는 사이드체인의 정합성을 온체인에서 간결하게 증명하기가 어렵다는 것이었는데, zk-SNARKs가 해결의 실마리를 제공해준 것이다. 비탈릭이 제안한 이더리움의 온체인 스케일링 솔루션 중 하나인 롤업(roll up) 또한 zk-SNARKs를 활용하여 이론적으로 하드포크 없이 이더리움의 TPS를 10~30배 확장하는 기술이다.

이러한 인프라 기술 뿐만이 아니라 어플리케이션에서도 활용 사례들이 있다. STARKWARE는 zk-STARKs를 활용하여 유저의 자산을 보관하지 않는 거래소(Non-custodial Exchange) 솔루션을 제작하고 있으며 현재 제로엑스 프로토콜(0x protocol)과 긴밀히 협력하고 있다. 예측마켓 프로토콜로 잘 알려진 노시스(Gnosis)에서도 디퓨젼(dFusion)이라는 이름의 탈중앙화 거래소(DEX)를 개발하고 있는데, 이것 역시 zk-SNARKs를 활용하여 탈중앙화 거래소의 낮은 거래속도를 개선하고자 하는 프로젝트이다.

Conclusion

이번 글에는 zk-SNARKs의 자세한 과정을 수학적 이론에 기반하여 설명하였다. 더불어 zk-SNARKs의 주요한 특징과 zk-STARKs 이론의 배경이 된 zk-SNARKs의 한계점을 짚었다. 추후의 글에서는 zk-SNARKs 이후의 이론인 zk-STARKs, Bulletproof 같은 이론들을 다룰 예정이다.