[zk-SNARK 3.] Quadratic Arithmetic Program

DoHoon Kim·2022년 7월 8일

zk-SNARK

목록 보기

3/5

앞선 글들에서 Prover가 Verifier에게 어떤 다항식을 알고 있음을 증명하는 메커니즘에 대해서 살펴보았습니다. zk-SNARK는 이 과정을 수행하기 위해 computational problem을 특정 다항식에 대한 문제로 변환합니다.

이번 글에서는 QAP(Quadratic Arithmetic Program)에 대해서 알아보도록 하겠습니다. 이 글은 Vitalik Buterin의 medium post를 기반으로 작성됐습니다.

NP

zk-SNARK는 NP class에 속하는 모든 computational problem에 대해서 적용이 가능합니다. NP class는 모든 search problem의 집합으로, search problem은 problem의 instance $I$ 와 solution $S$ 가 주어졌을 때 어떤 다항 시간 알고리즘 $C$ 가 존재해, $C(S, I) = true \;or \;false$ 임을 확인할 수 있어야 합니다. zk-SNARK가 NP class에 속하지 않는 문제들에 적용이 가능한지는 알려져 있지 않습니다.

NP class에 속하는 모든 문제들은 특정 search problem들로 reduce가 가능한데, 이러한 search problem들의 집합을 NP-complete하다고 합니다. NP-complete 문제들 중에 circuit satisfiability 문제가 존재하는데, 이는 특정 boolean circuit의 output이 True가 되도록 input을 assign하는 문제입니다. NP class에 속하는 모든 문제들은 circuit의 input assignment를 찾아내는 문제로 reduce될 수 있습니다.

zk-SNARK는 computational problem에 대한 solution을 알고 있음을 증명하는 체계입니다. NP class에 속하는 모든 문제들의 instance가 어떤 circuit으로 변환될 수 있으므로, zk-SNARK는 circuit을 만족하는 input을 알고 있음을 증명하는 것임을 알 수 있습니다. 이 때, circuit을 만족하는 input을 witness라고 부릅니다.

Arithmetic circuit

다음과 같은 computational problem이 존재합니다:

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

qeval(x) == 35 for which x?

Prover는 이 문제에 대한 답( $x$ )을 알고 있음을 증명하려고 합니다. zk-SNARK는 flattening이라는 과정을 통해 문제를 arithmetic circuit으로 변환합니다.

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

위의 결과에서 각 row가 circuit의 gate에 대응됩니다. 예를 들어 y = sym_1 * x 는, wire에 각각 sym_1, x, y가 assign된 multiplication gate에 대응됩니다.

R1CS

Arithmetic circuit의 각 gate들은 두 개의 input wire와 하나의 output wire로 구성되어 있습니다. 그리고 각 gate에는 wire의 값들이 만족해야 하는 조건식이 있습니다. zk-SNARK에서는 먼저 각 gate에 할당된 조건식들을 R1CS(Rank-1 Constraint System) 형태로 변환합니다. R1CS는 일종의 연립방정식으로, 다음과 같은 형태를 가집니다.

s \cdot a_{1} * s \cdot b_{1} - s \cdot c_{1} = 0 \\ s \cdot a_{2} * s \cdot b_{2} - s \cdot c_{2} = 0 \\ \vdots \\ s \cdot a_{n} * s \cdot b_{n} - s \cdot c_{n} = 0

각 $a_{i}, b_{i}, c_{i}$ 는 어떤 $m$ 에 대해 $m \times 1$ column vector이고, $s$ 는 R1CS를 만족하는 solution vector입니다. R1CS의 각 식들은 각 gate에서 wire간에 성립해야 하는 조건식을 나타냅니다. $a_{i}, b_{i}, c_{i}, s$ 벡터들의 각 원소는 flattening 이후 나타나는 모든 변수들에 대응됩니다. 각 벡터의 원소는 다음과 같습니다.

~one, x, ~out, sym_1, y, sym_2

첫 번째 원소인 ~one은 상수 1을 의미하고, 이후 additive gate에서 사용됩니다. R1CS의 solution vector $s$ 는 모든 gate들의 조건식을 만족하도록 각 변수에 값을 assign한 것이 되겠습니다.

그럼 각 gate의 조건식을 R1CS로 변환시켜보겠습니다. 모든 gate를 살펴보지 않고, 첫 번째 gate에 대해서만 확인해 보도록 하겠습니다.

첫 번째 gate의 조건식은 sym_1 = x * x입니다. 조건식을 약간만 변형하면 x * x - sym_1 = 0으로 표현할 수 있습니다.
먼저 벡터 $a$ 는 다음과 같이 표현할 수 있습니다. x를 제외한 나머지 변수들은 0으로 곱해지기 때문에, inner product의 결과로 x가 나오게 됩니다.

a = [ 0, 1, 0, 0, 0, 0 ]

벡터 $b$ 도 $a$ 와 같습니다.

b = [ 0, 1, 0, 0, 0, 0 ]

벡터 $c$ 는 다음과 같습니다. sym_1를 제외한 나머지 변수들은 0으로 곱해지기 때문에, inner product의 결과로 sym_1이 나오게 됩니다.

c = [ 0, 0, 0, 1, 0, 0 ]

각 gate의 조건식을 표현하는 $a, b, c$ 벡터들을 구한 결과는 다음과 같습니다.

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]

QAP

R1CS는 arithmetic circuit의 각 gate에서 wire에 assign된 값들 간에 성립하는 조건식들을 나타냅니다. Prover의 목표는, R1CS의 해인 $s$ 벡터를 알고 있음을 증명하는 것입니다. R1CS는 꽤나 근사한 형태를 가지고 있지만, circuit의 크기가 커질수록 constraint의 개수 또한 증가합니다. zk-SNARK에서는 R1CS를 QAP라는 훨씬 더 간결한 형태로 변환합니다.

R1CS의 각 constraint들은 다음과 같은 형태를 가집니다.

a_i \cdot s \;* \;b_i \cdot s \;- \;c_i \cdot s = 0

여러 개의 constraint들을 한꺼번에 다루기 위해 다항식을 도입합니다. 아이디어는 간단합니다. 각 gate들을 특정 $x$ 좌표에 대응시킵니다. 그리고 각 constraint의 $a, b, c$ 벡터들의 원소를 (해당 gate에 대응되는) $x$ 좌표에서 값으로 갖는 다항식들을 생성합니다.

예를 들면,
다항식 $a_1(x)$ 는 $x = 1$ 일 때 첫 번째 gate의 $a$ 벡터의 첫 번째 원소를 값으로 가지고, $x = 2$ 일 때 두 번째 gate의 $a$ 벡터의 첫 번째 원소를 값으로 가지고, ...
다항식 $a_2(x)$ 는 $x = 1$ 일 때 첫 번째 gate의 $a$ 벡터의 두 번째 원소를 값으로 가지고, $x = 2$ 일 때 두 번째 gate의 $a$ 벡터의 두 번째 원소를 값으로 가지고, ...
다항식 $b_1(x)$ 는 $x = 1$ 일 때 첫 번째 gate의 $b$ 벡터의 첫 번째 원소를 값으로 가지고, $x = 2$ 일 때 두 번째 gate의 $b$ 벡터의 첫 번째 원소를 값으로 가지고, ...

이런 식으로 해서 $a, b, c$ 벡터들의 각 원소에 대응되는 다항식을 만들어낼 수 있습니다.

특정 $x$ 좌표에서 특정 값을 갖는 특정 차수의 다항식을 생성하는 방법은 Lagrange Interpolation에 의해 이루어집니다.

R1CS의 constraint들을 다음과 같이 다항식에 대한 statement로 변형시킬 수 있습니다.

다음과 같은 벡터 $A, B, C$ 에 대해,

A = [ a_1(x), a_2(x), a_3(x), a_4(x), a_5(x), a_6(x) ]
B = [ b_1(x), b_2(x), b_3(x), b_4(x), b_5(x), b_6(x) ]
C = [ c_1(x), c_2(x), c_3(x), c_4(x), c_5(x), c_6(x) ]

a_i(x)는 x = n에서 n번째 gate의 a 벡터의 i번째 원소를 값으로 가지는 다항식
b_i(x)는 x = n에서 n번째 gate의 b 벡터의 i번째 원소를 값으로 가지는 다항식
c_i(x)는 x = n에서 n번째 gate의 c 벡터의 i번째 원소를 값으로 가지는 다항식

$A \cdot s \;* \;B \cdot s \;- \;C \cdot s = 0$ 이 각 gate들의 $x$ 좌표에서 성립해야 합니다. $A \cdot s \;* \;B \cdot s \;- \;C \cdot s = 0$ 의 결과 또한 다항식이기 때문에, 각 gate들의 $x$ 좌표에서 0이 됨을 다음과 같이 표현할 수 있습니다.

다항식 $Z(x) = \prod_{j = 1}^{4}(x - x_j)$ 에 대해서, 다음을 만족하는 어떤 다항식 $H(x)$ 가 존재합니다. ( $x_j$ 는 $j$ 번째 gate에 대응되는 $x$ 좌표입니다)

A \cdot s \;* \;B \cdot s \;- \;C \cdot s = H(x) \;* \;Z(x)

$s = (s_1, s_2, ..., s_6)$ 일 때, 다음과 같이 나타낼 수도 있습니다.

(\sum_{i=1}^{6}s_i * a_i(x))(\sum_{i=1}^{6}s_i * b_i(x)) \;- \;(\sum_{i=1}^{6}s_i * c_i(x)) = H(x) \;* \;Z(x)

$s$ 가 $(1, 3, 35, 9, 27, 30)$ 임을 쉽게 확인할 수 있습니다.

Generalization

QAP의 일반적인 형태는 다음과 같이 정의됩니다. degree가 최대 $d - 1$ 인 다항식 $a_1(x), ..., a_m(x), b_1(x), ..., b_m(x), c_1(x), ..., c_m(x)$ 가 존재하고 degree가 $d$ 인 다항식 $Z(x)$ 가 존재할 때, 어떤 $(s_1, ..., s_m)$ 에 대해서 다음을 만족합니다.

(\sum_{i=1}^{m}s_i * a_i(x))(\sum_{i=1}^{m}s_i * b_i(x)) \;- \;(\sum_{i=1}^{m}s_i * c_i(x)) = H(x) \;* \;Z(x)

이 때 $(s_1, s_2, ..., s_m)$ 을 QAP의 satisfying assignment라고 명명합니다.

zk-SNARK의 core는 Prover가 Verifier에게 특정 QAP의 satisfying assignment를 알고 있음을 증명하는 것으로 귀결됩니다. Satisfying assignment로부터 $(\sum_{i=1}^{m}s_i * a_i(x))(\sum_{i=1}^{m}s_i * b_i(x)) \;- \;(\sum_{i=1}^{m}s_i * c_i(x))$ 을 계산할 수 있어야 합니다.