Groth16 [KOR]

Introduction

Groth16 은 Non-Interactive Zero-Knowledge proof (NIZK) system의 한 종류로, 특히 zk-SNARKs에 사용되는 proof system입니다.

Non-Interactive Zero-Knowledge Proof (NIZK) System

NIZK proof system은 다음과 같은 특징을 가집니다.

• Non-Interactive: Prover와 Verifier가 한 번만 통신하면 됩니다.
• Zero-Knowledge: Prover가 어떤 statement를 증명할 때, statement에 대한 정보 외에는 아무것도 노출되지 않습니다.
• Completeness: Prover가 statement를 올바르게 증명하면, Verifier는 항상 그것을 accept합니다.
• Soundness: Prover가 statement를 틀리게 증명하면, Verifier는 항상 그것을 reject합니다.

Groth16

Groth16은 위의 NIZK proof system을 만족하면서 굉장히 효율적이기 때문에 ZK-SNARKs에 널리 사용됩니다. Groth16은 다음과 같은 특징을 가집니다.

• Succinct Proofs: Prover가 생성하는 proof의 크기가 매우 작습니다.
• Efficient Verification: Verifier가 proof를 검증하는데 필요한 시간이 매우 적습니다.
• Trusted Setup: Groth16은 trusted setup을 필요로 합니다. 이는 신뢰할 수 있는 사람이 한 번만 수행하면 됩니다.

Groth16 protocol의 대략적인 과정은 다음과 같습니다.

1. Computation을 circuit으로서 정의
2. 그것을 R1CS (Rank-1 constraint system)로 변환
3. R1CS에 대한 QAP (Quadratic Arithmetic Program)을 정의
4. Trusted setup을 통해 CRS (Common Reference String)을 생성
5. Prover가 QAP에 대한 proof를 생성
6. Verifier가 proof를 검증

지금부터는 Vitalik Buterin의 글의 예시를 최대한 살려서, Groth16 paper를 읽고 이해한 내용을 정리해보겠습니다.

1. Computation as a Circuit

우리는 다음과 같은 3차식에 $x=3$을 대입 후 잘 계산해서 35가 나왔다는 것을 증명하고 싶습니다.

\[x^3 + x + 5 \vert_{x=3} = 35\]

좌변을 qeval(x)라고 정의합시다. qeval 함수는 다음과 같이 쓸 수 있습니다.

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

위에어 우리가 사용한 프로그래밍 언어는 Python과 닮아 있지만, 실제로는 훨씬 더 간단한 연산만을 지원하는 언어입니다. 예를 들면 사칙연산과(+, -, *, /) 그리 고 상수제곱연산(x**7은 가능하지만 x**y는 불가능)만을 표현할 수 있습니다. 웬만한 계산은 다 할 수 있지만, computational step(계산 단계)는 bound(제한)되어야하 며, 따라서 while같은 unbound loop은 사용할 수 없습니다.

Flattening

Flattening(평탄화)이 뭐냐면, 모든 statement들을 $x = y \;(?)\; z$ 형태로 만드는 것입니다. 예를 들어, 우리는 새로운 변수 $\texttt{sim}_1$, $\texttt{sim}_2$, $\texttt{out}$를 사용해서 qeval 함수를 다음과 같이 flatten할 수 있습니다. (여기서 $\texttt{out}$는 qeval 함수의 결과값을, $\texttt{sim}_1$와 $\texttt{sim}_2$는 중간값을, $\texttt{one}$는 상수 1을 의미합니다.)

\[\begin{align*} \texttt{sim}_1 & = \texttt{x} \ast \texttt{x} & \textrm{gate 1} \\ \texttt{y} & = \texttt{sim}_1 \ast \texttt{x} & \textrm{gate 2}\\ \texttt{sim}_2 & = \texttt{y} + \texttt{x} & \textrm{gate 3}\\ \texttt{out} & = \texttt{sim}_2 + 5\texttt{one} & \textrm{gate 4} \end{align*}\]

코드 상의 statement들이 4개의 gate가 있는 논리 회로로 변했다고 볼 수도 있습니다.

2. Rank-1 Constraint System (R1CS)

이제 우리는 위에서 flatten한 qeval 함수를 R1CS로 변환할 것입니다. R1CS는 세 개의 벡터 $(\vec{a}, \vec{b}, \vec{c})$로 구성되어 있습니다. 그리고 벡터 $\vec{s}$가 다음을 만족하면 이 R1CS의 solution이 됩니다. ($\ast$는 scalar product, $\cdot$은 dot product를 의미합니다.)

\[\vec{a} \cdot \vec{s} \ast \vec{b} \cdot \vec{s} - \vec{c} \cdot \vec{s} = 0\]

qeval이 R1CS로 변환될 경우, $\vec{s}$ 벡터는 qeval에 있는 변수들 ($\texttt{one}$, $\texttt{x}$, $\texttt{out}$, $\texttt{sim}_1$, $\texttt{y}$, $\texttt{sim}_2$) 의 값이 각각 얼마인지를 나타내는 길이 6짜리 벡터일 것입니다.

\[\vec{s} : \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix}\]

이제 우리는 이 벡터들을 이용해서 R1CS를 만들어야 합니다. 각각의 gate들은 다음과 같이 표현됩니다.

Gate 1

\[\vec{a}_1 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{b}_1 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{c}_1 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}\]

라고 하면 gate 1이 그대로 표현됩니다.

\[\begin{align*} & \vec{a}_1 \cdot \vec{s} \ast \vec{b}_1 \cdot \vec{s} - \vec{c}_1 \cdot \vec{s} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \texttt{x} \ast \texttt{x} - \texttt{sim}_1 = 0 \end{align*}\]

Gate 2

\[\vec{a}_2 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{b}_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{c}_2 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}\]

라고 하면 gate 2가 그대로 표현됩니다.

\[\begin{align*} & \vec{a}_2 \cdot \vec{s} \ast \vec{b}_2 \cdot \vec{s} - \vec{c}_2 \cdot \vec{s} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \texttt{sim}_1 \ast \texttt{x} - \texttt{y} = 0 \end{align*}\]

Gate 3

\[\vec{a}_3 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \quad \vec{b}_3 = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{c}_3 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}\]

세 번째 gate는 곱셈이 아니라 덧셈이라서 앞 2개랑은 조금 다릅니다. 벡터 $\vec{a}$와의 dot product만으로도 덧셈을 충분히 표현할 수 있기 때문에 $\vec{b}\cdot\vec{s}$는 1을 곱함으로서 아무것도 하지 않습니다.

\[\begin{align*} & \vec{a}_3 \cdot \vec{s} \ast \vec{b}_3 \cdot \vec{s} - \vec{c}_3 \cdot \vec{s} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \texttt{one} - \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \texttt{y} + \texttt{x} - \texttt{sim}_2 = 0 \end{align*}\]

Gate 4

\[\vec{a}_4 = \begin{pmatrix} 5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}, \quad \vec{b}_4 = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \quad \vec{c}_4 = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}\]

gate 4도 gate 3과 비슷합니다.

\[\begin{align*} & \vec{a}_4 \cdot \vec{s} \ast \vec{b}_4 \cdot \vec{s} - \vec{c}_4 \cdot \vec{s} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \ast \texttt{one} - \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \texttt{out} + 5\texttt{one} - \texttt{sim}_2 = 0 \end{align*}\]

Putting Together

위 4개의 constraint들로 구성된 R1CS를 만들었습니다. 행렬 곱셈을 안다면 어렵지 않게 네 개의 constraint들을 가로로 쌓아서 하나로 합칠 수 있습니다.

\[\begin{align*} \mathbf{a} & = \begin{pmatrix} \vec{a}_1^T \\ \vec{a}_2^T \\ \vec{a}_3^T \\ \vec{a}_4^T \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 5 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \\[1em] \mathbf{b} & = \begin{pmatrix} \vec{b}_1^T \\ \vec{b}_2^T \\ \vec{b}_3^T \\ \vec{b}_4^T \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \\[1em] \mathbf{c} & = \begin{pmatrix} \vec{c}_1^T \\ \vec{c}_2^T \\ \vec{c}_3^T \\ \vec{c}_4^T \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} \end{align*}\]

(아래에서 $\circ$는 element-wise product를 의미합니다.)

\[\begin{align*} & \mathbf{a} \cdot \vec{s} \circ \mathbf{b} \cdot \vec{s} - \mathbf{c} \cdot \vec{s} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 5 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \circ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad - \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} \texttt{one} \\ \texttt{x} \\ \texttt{out} \\ \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \end{pmatrix} = 0 \\ \Longleftrightarrow \quad & \begin{pmatrix} \texttt{x} \\ \texttt{sim}_1 \\ \texttt{y} + \texttt{x} \\ 5\texttt{one} + \texttt{sim}_2 \end{pmatrix} \circ \begin{pmatrix} \texttt{x} \\ \texttt{x} \\ \texttt{one} \\ \texttt{one} \end{pmatrix} - \begin{pmatrix} \texttt{sim}_1 \\ \texttt{y} \\ \texttt{sim}_2 \\ \texttt{out} \end{pmatrix} = 0 \\[1em] \Longleftrightarrow \quad & \begin{pmatrix} \texttt{x} \ast \texttt{x} - \texttt{sim}_1 \\ \texttt{sim}_1 \ast \texttt{x} - \texttt{y} \\ \texttt{y} + \texttt{x} - \texttt{sim}_2 \\ 5\texttt{one} + \texttt{sim}_2 - \texttt{out} \end{pmatrix} = 0 \end{align*}\]

Witness and Statement

Statement(우리가 증명하고 싶은 것, 모두가 알아도 되는 것)은 ($\texttt{one}$, $\texttt{x}$, $\texttt{out}$)가 1, 3, 35라는 것입니다. qeval(3)=35를 증명하고 싶다는 것이죠. 그리고 witness(우리가 숨기면서 알고 있다고 증명하고 싶은 계산 과정)는 계산 과정에서 사용된 변수들($\texttt{sim}_1$, $y$, $\texttt{sim}_2$) 에 대한 값들(9, 27, 30)을 의미합니다

편의를 위해서 statement에 해당하는 변수들의 집합을 $V_s \defeq \braces{\texttt{one}, \texttt{x}, \texttt{out}}$로, witness에 해당하는 변수들의 집합을 $V_w \defeq \braces{\texttt{sim}_1, y, \texttt{sim}_2}$로, 그리고 모든 변수들의 집합을 $V \defeq V_s \cup V_w$로 정의하겠습니다.

3. Quadratic Arithmetic Program (QAP)

다음 단계는 R1CS를 QAP로 변환하는 것입니다. QAP는 R1CS가 나타내는 constraint들을 그대로 표현하면서도, dot product 대신 polynomial을 사용합니다.

Lagrange Interpolation

위에서 말한 내용을 가능하게 하려면 우리가 원하는 점을 반드시 지나는 다항식을 만들 수 있어야 합니다. 이걸 해주는 것이 Lagrange Interpolation입니다.

$(1, 2)$ 와 $(3, 4)$를 지나는 다항식을 억지로 만들어보겠습니다.

\[y = c_1 (x - 1) + c_2 (x - 3)\]

$x=1$일 떄는 $c_2$ 만 살아남고, $x=3$일 때는 $c_1$만 살아남습니다. 따라서 $c_1, c_2$를 끼워맞추면 $(1, 2)$와 $(3, 4)$를 지나는 다항식을 만들 수 있습니다. 적당히 $c_1$ 을 선택해서 $x=3$를 대입하면 $y=4$가 나오게 해봅시다.

\[4 = c_1 (3 - 1) + c_2 (3 - 3) = 2c_1 \qquad \therefore c_1 = 2\]

그러면 $c_2$는 $x=1$일 때 $y=2$가 나오게 해야 합니다. $\therefore c_2 = -1$이 됩니다.

우리가 원하는 점이 몇 개든, 이 짓을 반복하면 그 점들을 지나는 다항식을 무조건 만들 수 있습니다. $(1, 2)$와 $(3, 4)$, $(5, 6)$ 를 지나는 다항식을 만들 때는

\[y = c_1(x - 3)(x - 5) + c_2(x - 1)(x - 5) + c_3(x - 1)(x - 3)\]

로 시작하면 됩니다. 점이 $n$ 개라면 $n-1$ 차 다항식이 만들어지게 됩니다. 이것이 Lagrange Interpolation의 전부입니다.

Lagrange Interpolation은 zk-SNARKs에 사용되는 QAP을 만들 때 중요한 역할을 합니다. 그래서 똑똑한 사람들이 이것을 더 빠르게 계산할 수 있는 방법을 찾아냈다고 합니다 ($O(n \log^2 n)$)

Transformation to QAP

앞서 R1CS에서는 gate 1, 2, 3, 4에 대한 constraint들을 $(\vec{a}_1, \vec{b}_1, \vec{c}_1)$, $(\vec{a}_2, \vec{b}_2, \vec{c}_2)$, $(\vec{a}_3, \vec{b}_3, \vec{c}_3)$, $(\vec{a}_4, \vec{b}_4, \vec{c}_4)$ 라고 표현했습니다. 이제 이들을 QAP로 변환할 것입니다.

$\vec{a}, \vec{b}, \vec{c}$에 대해서, 6개의 변수

\[\texttt{one}, x, \texttt{out}, \texttt{sim}_1, y, \texttt{sim}_2\]

마다 3차 다항식을 하나씩 만들어줄 겁니다. 예를 들면, $(\vec{a}, \texttt{one})$에 대응되는 다항식 $A_{\texttt{one}}$이 있고, $(\vec{b}, \texttt{x})$에 대응되는 다항식 $B_\texttt{x}$가 있습니다.

Lagrange Interpolation을 이용해서, 다항식에 $i$를 대입했을 때, $i=1,2,3,4$ 번째 gate의 해당 vector 중 그 변수의 자리의 값이 나오게 만들어줍니다. 예를 들면, $(\vec{a}, \texttt{one})$에 대응되는 다항식 $A_{\texttt{one}}$는 아래를 만족해야 합니다. (여기서 $\vec{a}_1\brackets{\texttt{one}}$는 $\vec{a}_1$의 $\texttt{one}$자리에 있는 값입니다.)

\[\begin{align*} A_{\texttt{one}}\prths{1} & = \vec{a}_1\brackets{\texttt{one}} = 0 \\ A_{\texttt{one}}\prths{2} & = \vec{a}_2\brackets{\texttt{one}} = 0 \\ A_{\texttt{one}}\prths{3} & = \vec{a}_3\brackets{\texttt{one}} = 0 \\ A_{\texttt{one}}\prths{4} & = \vec{a}_4\brackets{\texttt{one}} = 5 \end{align*}\]

이제 이런 조건을 $x, \texttt{out}, \texttt{sim}_1, y, \texttt{sim}_2$에 대해서도 적용해서 Langrange Interpolation을 통해 다항식들을 만들어줍니다.

\[\begin{align*} A_{x}\prths{1} & = \vec{a}_1\brackets{\texttt{x}} = 1 \\ A_{x}\prths{2} & = \vec{a}_2\brackets{\texttt{x}} = 0 \\ & \vdots \\ A_{\texttt{sim}_2}\prths{4} & = \vec{a}_4\brackets{\texttt{sim}_2} = 1 \end{align*}\]

이제 우리는 각각의 변수에 대한 3차 다항식

\[A_{\texttt{one}}, A_\texttt{x}, A_{\texttt{out}}, A_{\texttt{sim}_1}, A_\texttt{y}, A_{\texttt{sim}_2}\]

을 만들었습니다. $\vec{b}$와 $\vec{c}$에 대해서도 같은 방식으로 다항식을 만들어줍니다. 그러면 $B_{\texttt{one}}, B_\texttt{x}, B_{\texttt{out}}, \dots C_{\texttt{one}}, C_\texttt{x}, C_{\texttt{out}}, \dots$ 이런 식으로 총 18개의 다항식이 만들어집니다. 이 18개의 다항식들은 R1CS에서 만들었던 constraint들을 그대로 표현하고 있습니다.

참고로, 실제로 Lagrange Interpolation을 이용해서 18개의 polynomial들을 구해보면 다음과 같습니다.

\[\begin{align*} A_{\texttt{one}}(x) & = 0.833x^3 - 5.0x^2 + 9.166x - 5.0 \\ A_{\texttt{x}}(x) & = -0.666x^3 + 5.0x^2 - 11.333x + 8.0 \\ A_{\texttt{out}}(x) & = 0 \\ A_{\texttt{sim}_1}(x) & = 0.5x^3 - 4.0x^2 + 9.5x - 6.0 \\ A_{\texttt{y}}(x) & = -0.5x^3 + 3.5x^2 - 7.0x + 4.0 \\ A_{\texttt{sim}_2}(x) & = 0.166x^3 - x^2 + 1.833x - 1.0 \\ B_{\texttt{one}}(x) & = -0.333x^3 + 2.5x^2 - 5.166x + 3.0 \\ B_{\texttt{x}}(x) & = 0.333x^3 - 2.5x^2 + 5.166x - 2.0 \\ B_{\texttt{out}}(x) & = 0 \\ B_{\texttt{sim}_1}(x) & = 0 \\ B_{\texttt{y}}(x) & = 0 \\ B_{\texttt{sim}_2}(x) & = 0 \\ C_{\texttt{one}}(x) & = 0 \\ C_{\texttt{x}}(x) & = 0 \\ C_{\texttt{out}}(x) & = 0.166x^3 - 1.0x^2 + 1.833x - 1.0 \\ C_{\texttt{sim}_1}(x) & = -0.166x^3 + 1.5x^2 - 4.333x + 4.0 \\ C_{\texttt{y}}(x) & = 0.5x^3 - 4.0x^2 + 9.5x - 6.0 \\ C_{\texttt{sim}_2}(x) & = -0.5x^3 + 3.5x^2 - 7.0x + 4.0 \end{align*}\]

Checking the QAP

도대체 왜 이 다항식 18개를 만든걸까요. 누군가 constraint의 solution을 들고 왔을 떄, constraint의 solution이 맞는지 확인하는게 R1CS보다 더 쉬워집니다. R1CS에서는 모든 gate 각각의 constraint를 확인해야 했지만, QAP에서는 한 번에 모든 constraint를 확인할 수 있습니다.

아래 solution이 constraint를 만족하는지 확인해봅시다.

\[\vec{s} = \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix}\]

원래는(R1CS에서는) 총 4개의 constraint를 확인해야 합니다.

\[\begin{align*} \vec{a}_1 \cdot \vec{s} \ast \vec{b}_1 \cdot \vec{s} - \vec{c}_1 \cdot \vec{s} = 0 \\ \vec{a}_2 \cdot \vec{s} \ast \vec{b}_2 \cdot \vec{s} - \vec{c}_2 \cdot \vec{s} = 0 \\ \vec{a}_3 \cdot \vec{s} \ast \vec{b}_3 \cdot \vec{s} - \vec{c}_3 \cdot \vec{s} = 0 \\ \vec{a}_4 \cdot \vec{s} \ast \vec{b}_4 \cdot \vec{s} - \vec{c}_4 \cdot \vec{s} = 0 \end{align*}\]

여기서 첫 번째 constraint만 방금 만든 polynomial을 이용해서 표현해보겠습니다.

\[\begin{pmatrix} A_{\texttt{one}}(1) \\ A_\texttt{x}(1) \\ A_{\texttt{out}}(1) \\ A_{\texttt{sim}_1}(1) \\ A_\texttt{y}(1) \\ A_{\texttt{sim}_2}(1) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} \ast \begin{pmatrix} B_{\texttt{one}}(1) \\ B_\texttt{x}(1) \\ B_{\texttt{out}}(1) \\ B_{\texttt{sim}_1}(1) \\ B_\texttt{y}(1) \\ B_{\texttt{sim}_2}(1) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} - \begin{pmatrix} C_{\texttt{one}}(1) \\ C_\texttt{x}(1) \\ C_{\texttt{out}}(1) \\ C_{\texttt{sim}_1}(1) \\ C_\texttt{y}(1) \\ C_{\texttt{sim}_2}(1) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} = 0\]

두번째부터 네 번째 constraint도 같은 방식으로 표현할 수 있습니다. 다시 말해 $x = 1, 2, 3, 4$에 대해서 아래가 성립해야 합니다.

\[\begin{pmatrix} A_{\texttt{one}}(x) \\ A_\texttt{x}(x) \\ A_{\texttt{out}}(x) \\ A_{\texttt{sim}_1}(x) \\ A_\texttt{y}(x) \\ A_{\texttt{sim}_2}(x) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} \ast \begin{pmatrix} B_{\texttt{one}}(x) \\ B_\texttt{x}(x) \\ B_{\texttt{out}}(x) \\ B_{\texttt{sim}_1}(x) \\ B_\texttt{y}(x) \\ B_{\texttt{sim}_2}(x) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} - \begin{pmatrix} C_{\texttt{one}}(x) \\ C_\texttt{x}(x) \\ C_{\texttt{out}}(x) \\ C_{\texttt{sim}_1}(x) \\ C_\texttt{y}(x) \\ C_{\texttt{sim}_2}(x) \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{pmatrix} = 0\]

그런데 각각의 dot product의 결과도 polynomial이므로, $A(x), B(x), C(x)$를 다음과 같이 정의하면

\[\begin{align*} A(x) & \defeq 1\cdot A_{\texttt{one}}(x)+3\cdot A_\texttt{x}(x)+35\cdot A_{\texttt{out}}(x)+9\cdot A_{\texttt{sim}_1}(x)+27\cdot A_\texttt{y}(x)+ 30\cdot A_{\texttt{sim}_2}(x) \\ B(x) & \defeq 1\cdot B_{\texttt{one}}(x)+3\cdot B_\texttt{x}(x)+35\cdot B_{\texttt{out}}(x)+9\cdot B_{\texttt{sim}_1}(x)+27\cdot B_\texttt{y}(x)+ 30\cdot B_{\texttt{sim}_2}(x) \\ C(x) & \defeq 1\cdot C_{\texttt{one}}(x)+3\cdot C_\texttt{x}(x)+35\cdot C_{\texttt{out}}(x)+9\cdot C_{\texttt{sim}_1}(x)+27\cdot C_\texttt{y}(x)+ 30\cdot C_{\texttt{sim}_2}(x) \end{align*}\]

위의 constraint들은 다음과 같이 표현할 수 있습니다.

\[A(x) \ast B(x) - C(x) = 0 \quad \forall x \in \braces{1, 2, 3, 4}\]

이 말은, 좌변의 다항식이 $Z(x)\defeq(x-1)(x-2)(x-3)(x-4)$로 나누어 떨어진다는 것을 의미합니다.

\[A(x) \ast B(x) - C(x) = H(X) \ast Z(x) \quad \text{for some polynomial } H(x)\]

따라서 좌변이 $Z(x)$로 나누어 떨어지는지만 확인하면 $\vec{s}$가 constraint를 만족하는지 확인할 수 있습니다. 우리는 18개의 polynomial들을 모두 알고 있기 때문에, $A(x), B(x), C(x)$도 쉽게 계산할 수 있고, 좌변 $A(x) \ast B(x) - C(x)$ 또한 계산할 수 있습니다.

\[\begin{multline*} A(x) \ast B(x) - C(x) = -3.444x^6 + 51.5x^5 - 294.777x^4 \\ + 805.833x^3 - 1063.777x^2 + 592.666x - 88.0 \end{multline*}\]

$Z(x)$ 도 쉽게 구할 수 있습니다.

\[Z(x) = x^4 - 10x^3 + 35x^2 - 50x + 24\]

$\vec{s}$가 실제로 constraint를 만족하기 때문에, 다항식의 나눗셈을 이용해서 확인해 보면 잘 나누어 떨어집니다.

\[\frac{A(x) \ast B(x) - C(x)}{Z(x)} = -3.444x^2 + 17.055x - 3.666\]

만약 $\vec{s}$가 constraint를 만족하지 않는다면, 좌변이 $Z(x)$로 나누어 떨어지지 않을 것입니다.

4. Trusted Setup

Trusted Setup 단계에서는 위에서 만든 QAP을 이용해서 CRS(Committed Reference String)을 만들어냅니다. CRS란 믿을 수 있는 제 3자가 만들어낸 값들로, 이 값들을 이용해서 prover와 verifier가 서로간에 증명과 검증을 할 수 있게 됩니다.

Preliminaries

시작하기 전에, 우리의 연산이 이루어지는 finite field를 $\Z_p$라고 하겠습니다. 또 $\G_1, \G_2$는 각각 prime order $p$를 가지는 cyclic group들이고 (generator는 각각 $g_1, g_2$라고 하겠습니다), $\G_T$는 $e(\;\cdot\;,\;\cdot\;) : \G_1 \times \G_2 \rightarrow \G_T$인 bilinear map을 가지는 multiplicative group입니다. 편의를 위해서 어떤 $(X_1, \dots , X_k)\in\Z_p^k$가 있을 때,

\[\begin{align*} \brackets{(X_1, \dots , X_k)}_1 & \defeq (g_1^{X_1}, \dots , g_1^{X_k}) \\ \brackets{(X_1, \dots , X_k)}_2 & \defeq (g_2^{X_1}, \dots , g_2^{X_k}) \end{align*}\]

이라고 하겠습니다 (집합, 벡터, 행렬 등에 대해서도 같은 방식으로 정의할 수 있습니다).

또한 이전 섹션에서 구한 QAP 식 $ A(x) \ast B(x) - C(x) = H(X) \ast Z(x) $ 을 일반적으로 표현해보도록 하겠습니다. Solution vector가 다음과 같이 주어졌다고 했을 때,

\[\vec{s} = \begin{pmatrix} s_{\texttt{one}} \\ s_{\texttt{x}} \\ s_{\texttt{out}} \\ s_{\texttt{sim}_1} \\ s_{\texttt{y}} \\ s_{\texttt{sim}_2} \end{pmatrix} \in \Z_p^6\]

QAP는 다음과 같이 표현됩니다.

\[\sum_{v\in V} s_v A_v(x) \ast \sum_{v\in V} s_v B_v(x) = \sum_{v\in V} s_v C_v(x) + H(x) \ast Z(x)\]

여기서 $Z(x)$의 차수를 $n$이라고 하겠습니다.

Setting CRS

$\Z_P^*$에서 무작위로 5개의 원소를 선택합니다.

\[\alpha, \beta, \gamma, \delta, u \leftarrow \Z_p^*\]

제 3자가 CRS를 만들어줄 때 생성되는 이 다섯 개의 원소를 trapdoor information이라고 부릅니다. Trapdoor information의 값은 그대로는 절대로 공개되어서는 안되고, CRS를 만들어낸 직후에는 폐기되어야 합니다. 왜 그런지에 대해서는 7장에서 설명하겠습니다. ($g^{\alpha}, g^{\beta}, g^{\gamma}, g^{\delta}, g^u$는 공개되어도 상관없습니다.)

어쨌든 이 다섯 개의 원소를 이용해서 다음과 같은 값들을 계산합니다.

\[\begin{align*} \boldsigma_1 & \defeq \begin{pmatrix} \alpha, \beta, \delta, \braces{u}_{i=0}^{n-1}, \braces{\frac{\beta a_v(x)+\alpha b_v(x)+c_v(x)}{\gamma}}_{v\in V_s}, \\ \braces{\frac{\beta a_v(x)+\alpha b_v(x)+c_v(x)}{\delta}}_{v\in V_w}, \braces{\frac{u^i Z(x)}{\delta}}_{i=0}^{n-2} \end{pmatrix} \\ \boldsigma_2 & \defeq \prths{ \beta, \gamma, \delta, \braces{u}_{i=0}^{n-1}, } \end{align*}\]

CRS는 $\boldsigma_1, \boldsigma_2$를 각각 $\G_1,\G_2$로 exponentiation한 값들로 구성됩니다.

\[\boldsigma = \prths{ \brackets{\boldsigma_1}_1, \brackets{\boldsigma_2}_2 }\]

이 $\boldsigma$로 proof 만들고 verify 하고 다 합니다.

5. Proof Generation

Supplies

Prover는 statement

\[s_{\texttt{one}}=1, s_{\texttt{x}}=3, s_{\texttt{out}}=35\]

와 witness

\[s_{\texttt{sim}_1}=9, s_{\texttt{y}}=27, s_{\texttt{sim}_2}=30\]

그리고 QAP에서 만든 polynomial

\[A_{\texttt{one}}(x), A_\texttt{x}(x), \dots B_{\texttt{one}}(x), B_\texttt{x}(x), \dots C_{\texttt{sim}_2}(x)\]

마지막으로 CRS $\boldsigma$를 가지고 있습니다.

Proof Generation

위 재료들을 가지고 아래와 같이 3개의 element를 가진 proof를 만들어냅니다.

\[\pi = \prths{\brackets{\calA}_1, \brackets{\calC}_1, \brackets{\calB}_2}\]

여기서 $\calA, \calB, \calC$는 다음과 같이 정의됩니다. 일단 $\mu, \nu \leftarrow \Z_p$를 무작위로 선택합니다.

\[\begin{align*} \calA & \defeq \alpha + \sum_{v\in V} s_v A_v(x) + \mu \delta \\ \calB & \defeq \beta + \sum_{v\in V} s_v B_v(x) + \nu \delta \\ \calC & \defeq \frac{ \sum_{v \in V_w} s_v \prths{ \beta A_v(x) + \alpha B_v(x) + C_v(x) } + H(x) \ast Z(x) }{\delta} + \calA \nu + \calB \mu - \mu \nu \delta \end{align*}\]

참고로, $\boldsigma$ 만 가지고서는 $\calA, \calB, \calC$를 바로 계산할 수는 없습니다. 하지만 $\prths{\brackets{\calA}_1, \brackets{\calC}_1, \brackets{\calB}_2}$는 계산 가능하도록 똑똑한 Groth 선생님께서 $\boldsigma$를 알차게 구성해놨겠지요.

6. Verification

Supplies

Verifier는 statement

\[s_{\texttt{one}}=1, s_{\texttt{x}}=3, s_{\texttt{out}}=35\]

와 QAP에서 만든 polynomial

\[A_{\texttt{one}}(x), A_\texttt{x}(x), \dots B_{\texttt{one}}(x), B_\texttt{x}(x), \dots C_{\texttt{sim}_2}(x)\]

그리고 CRS $\boldsigma$, 마지막으로 proof $\pi$를 가지고 있습니다.

Verification

정말 놀랍게도, verifier는 오직 statement, CRS, proof만 가지고서도 다음 등식이 성립하는지만 확인하면 prover가 constraint를 지키는 witness를 가지고 있다는 것을 확신할 수 있습니다.

\[\begin{multline*} e\prths{\brackets{\calA}_1, \brackets{\calB}_2} = e\prths{\brackets{\alpha}_1, \brackets{\beta}_2} + e\prths{ \sum_{v\in V_s} s_v \brackets{ \frac{\beta A_v(x) + \alpha B_v(x) + C_v(x)}{\gamma} }_1, \brackets{\gamma}_2 } \\ + e\prths{ \brackets{\calC}_1, \brackets{\delta}_2 } \end{multline*}\]

식의 모양새가 좀 복잡해 보이지만, [다음 장]{#nizk}에서 이게 왜 되는지 대강 설명하겠습니다. (물론 이 등식도 똑똑하신 Groth 선생님께서 CRS를 구성할 때 계산 가능하도록 해놓으셨을거라 믿습니다.)

7. NIZK properties

Trusted Setup, Proof generation, Verification 과정이 말이 되는건지 아닌지 어떻게 알 수 있을까요? 이 글의 맨 처음 introduction에서 언급했듯이, NIZK의 3가지 property를 만족하는지 알아보면 됩니다.

Non-Interactivity

제일 알아보기 쉬운 성질입니다. Prover가 verifier에게 딱 한번 $\pi$를 보내고, verifier는 그것을 받아서 한번에 검증을 합니다.

Zero-Knowledge

Zero-Knowledge는 verifier가 statement가 참이라는 것을 알아도 witness에 대한 어떤 정보도 얻지 못한다는 것을 의미합니다. 그럼 우리가 여기에서 걱정해야 할 점은 다음과 같습니다.

아, prover가 제출한 증명 $\pi = \prths{\brackets{\calA}_1, \brackets{\calC}_1, \brackets{\calB}_2}$ 안에 witness에 대한 정보가 들어있으면 어쩌지?

그런데 사실 $\pi$ 안에는 witness에 대한 정보가 전혀 들어있지 않습니다. CRS ($\boldsigma$) 를 setting할 때 trapdoor information $\boldtau \defeq \alpha, \beta, \gamma, \delta, u$ 을 갖다 버렸지만, 만약 $\tau$를 알고 있다면 witness 없이도 proof를 만들어낼 수 있습니다.

$\calA^\prime, \calB^\prime \leftarrow \Z_p$를 무작위로 선택하고, $\calC^\prime$를 다음과 같이 계산하면

\[\calC^\prime = \frac { \calA^\prime \calB^\prime - \alpha \beta -\sum_{v\in V_s} s_v \prths{\beta A_v(x) + \alpha B_v(x) + C_v(x)} }{\delta}\]

verifier를 감쪽같이 속일 수 있습니다. Verifier는 절대 (다항 시간 안에) $\prths{\brackets{\calA^\prime}_1, \brackets{\calC^\prime}_1, \brackets{\calB^\prime}_2}$ 가 실제 witness를 가지고 만들어낸 proof인지 아닌지 알 수 없습니다. Verification 과정을 그냥 통과할 뿐입니다.

Proof을 만들어내는데 witness가 필요하지 않다는 말은, proof 안에 witness에 대한 정보가 들어있지 않다는 것을 의미합니다. 즉, Zero-Knowledge property를 만족한다는 것입니다. 그러나, 만약 trapdoor information $\boldtau$ 이 CRS가 만들어진 직후에 믿을만한 제 3자에게 의해 잘 폐기된다면, 그때부터는 proof를 만들어내는데 witness가 필요하게 될 것입니다. 자세한 내용은 soundness에서 다루겠습니다.

Completeness

Completeness는 statement가 참일 때, 즉 prover가 constraint를 지키는 witness를 가지고 있을 때 verifier가 항상 accept해야 한다는 것을 의미합니다. 그 말은, prover가 제대로 $\pi = \prths{\brackets{\calA}_1, \brackets{\calC}_1, \brackets{\calB}_2}$를 만들면 verifier는 아까 그 복잡한 등식이 성립하는것을 확인할 수 있어야 한다는 것입니다.

Completeness에 대한 설명은 다음과 같은 대수적인 팩트에서 시작할 수 있습니다. 다음 등식이 성립하는건 팩트입니다.

\[\calA \cdot \calB = \alpha \cdot \beta + \frac{ \sum_{v \in V_s} s_v \prths{ \beta A_v(x) + \alpha B_v(x) + C_v(x) } }{\gamma} \cdot \gamma + \calC \cdot \delta\]

찜찜하다면, $\calA, \calB, \calC$의 정의들과 아래 QAP 식을 대입해서 열심히 전개하다보면 위 등식이 성립하는 것을 확인할 수 있을 겁니다.

\[\sum_{v\in V} s_v A_v(x) \ast \sum_{v\in V} s_v B_v(x) = \sum_{v\in V} s_v C_v(x) + H(x) \ast Z(x)\]

근데 위 식을 잘 보면, 아까 그 복잡한 등식 과 상당히 닮아있죠. $e(\;\cdot\;,\;\cdot\;)$이 bilinear map이라는 성질이 있기 때문에, 아까 그 복잡한 등식이 성립한다면 이 등식도 성립할 수밖에 없을 것입니다.

그래서 verifier는 $\pi$가 제대로 만들어졌다면 항상 accept할 것입니다.

Soundness (Why pairing is needed)

Soundness는 statement가 거짓일 때, 즉 prover가 constraint를 지키지 않는 witness를 가지고 있을 때 verifier가 항상 reject해야 한다는 것을 의미합니다.

아까 이야기했듯이, trapdoor information $\boldtau$을 숨기는 것은 soundness를 보장하기 위해 필수적입니다. 만약 $\boldtau$이 공격자에게 노출된다면, 공격자는 위에서 설명한 방법으로 witness 없이도 proof를 만들어낼 수 있습니다.

그런데 group exponential과 group pairing이 없이는 CRS $\boldsigma$ 안에 trapdoor information $\boldtau = \alpha, \beta, \gamma, \delta, u$을 넣을 수 밖에 없습니다. $\alpha, \beta, \gamma, \delta, u$에 대한 정보는 proof generation과 verification을 할 때 꼭 필요하기 때문입니다.

그래서 soundness를 보장하기 위해서는 trapdoor information을 숨길 수 있는 group exponential과 group pairing을 이용해서 $g^{\alpha}, g^{\beta}, g^{\gamma}, g^{\delta}, g^u$ 등을 CRS $\boldsigma$를 구성해야 합니다.

이렇게 trapdoor information을 숨기면, 공격자가 valid한 witness 없이도 verifier를 속일 수 있는 확률이 통계적으로 0이라고 합니다.

8. Conclusion

이상 Groth16 protocol에 대해서 간단히 알아보았습니다. 감사합니다.