ZKP-4. 영지식 증명: 계산을 다항식 문제로 변환하기

영지식 증명(Zero-Knowledge Proof)의 핵심은 '무언가를 안다’는 사실을, 그 ‘무엇’ 자체는 공개하지 않고 증명하는 것입니다. 이를 실현하기 위해 암호학자들은 아주 독창적인 방법을 고안했습니다. 바로 컴퓨터가 수행하는 복잡한 '계산’을, 간결하고 강력한 '다항식의 관계’로 번역하는 것입니다. 이 번역 과정만 이해하면 영지식 증명의 가장 중요한 원리를 파악할 수 있습니다. 이 문서에서는 간단한 예제를 통해 그 과정을 단계별로 살펴보겠습니다.

우리가 증명하려는 계산은 x³ + x + 5 = 35 입니다. 증명자(Prover)는 이 방정식의 해인 x=3 이라는 비밀값을 알고 있음을 검증자(Verifier)에게 증명하고자 합니다.

1단계: 계산의 평탄화 (Flattening) - 산술 회로로 변환

가장 먼저, 복잡한 계산식을 기본적인 산술 연산(덧셈, 뺄셈, 곱셈)의 연속으로 분해하여 산술 회로(Arithmetic Circuit)로 만듭니다. 각 연산은 하나의 '게이트(gate)'가 됩니다. 이 과정은 컴퓨터가 이해하는 복잡한 로직을 영지식 증명 시스템이 처리할 수 있는 표준화된 형식으로 바꾸는 첫 단계입니다.

x³ + x + 5 식은 다음과 같이 분해할 수 있습니다.

sym_1 = x * x (x²)
sym_2 = sym_1 * x (x³)
sym_3 = sym_2 + x (x³ + x)
~out = sym_3 + 5 (x³ + x + 5)

이제 x=3 이라는 비밀값을 각 단계에 대입하여 중간 결과값을 계산합니다.

x = 3
sym_1 = 3 * 3 = 9
sym_2 = 9 * 3 = 27
sym_3 = 27 + 3 = 30
~out = 30 + 5 = 35

이 산술 회로는 계산의 흐름을 명확하게 보여주는 청사진 역할을 합니다.

위 다이어그램은 각 변수가 게이트를 통해 어떻게 연결되고 변환되는지 시각적으로 보여줍니다.

2단계: R1CS(Rank-1 Constraint System)로 표현

다음으로, 산술 회로의 각 게이트를 R1CS라는 형식의 제약 조건으로 변환합니다. R1CS는 각 제약 조건을 (s · A) * (s · B) - (s · C) = 0 이라는 형태로 표현합니다. 여기서 s는 증인 벡터(witness vector)이고, A, B, C는 각 제약 조건을 정의하는 벡터들이며, '·'는 두 벡터의 내적(dot product)을 의미합니다.

각 제약 조건이 올바르게 충족되었는지 확인하려면, 계산에 사용된 모든 값(비밀 입력값, 중간 결과값, 최종 출력값)을 하나의 긴 목록으로 만들어야 합니다. 이 목록이 바로 증인(witness) 벡터 s입니다. 이는 마치 수학 문제의 '풀이 과정 전체’를 순서대로 적어놓은 것과 같습니다. 증명자는 이 '풀이 과정’을 제출함으로써 계산을 올바르게 수행했음을 증명하는 것입니다.

s = [~one, x, ~out, sym_1, sym_2, sym_3]

~one은 상수 '1’을 나타내는 가상 변수입니다.
x는 비밀 입력값입니다.
~out은 출력값입니다.
sym_1, sym_2, sym_3는 중간값입니다.

x=3일 때의 증인 벡터 s는 다음과 같습니다.

s = [1, 3, 35, 9, 27, 30]

이제 각 게이트를 s와의 내적을 통해 (s · A) * (s · B) - (s · C) = 0 형태로 표현합니다.

게이트 1: sym_1 = x * x

A = [0, 1, 0, 0, 0, 0] (x를 선택)
B = [0, 1, 0, 0, 0, 0] (x를 선택)
C = [0, 0, 0, 1, 0, 0] (sym_1을 선택)
검증: (s · A) * (s · B) - (s · C) = (3) * (3) - (9) = 0

게이트 2: sym_2 = sym_1 * x

A = [0, 0, 0, 1, 0, 0] (sym_1을 선택)
B = [0, 1, 0, 0, 0, 0] (x를 선택)
C = [0, 0, 0, 0, 1, 0] (sym_2를 선택)
검증: (s · A) * (s · B) - (s · C) = (9) * (3) - (27) = 0

게이트 3: sym_3 = sym_2 + x

A = [0, 1, 0, 0, 1, 0] (x + sym_2를 선택)
B = [1, 0, 0, 0, 0, 0] (1을 선택)
C = [0, 0, 0, 0, 0, 1] (sym_3를 선택)
검증: (s · A) * (s · B) - (s · C) = (3 + 27) * (1) - (30) = 0

게이트 4: out = sym_3 + 5

A = [5, 0, 0, 0, 0, 1] (5*~one + sym_3를 선택)
B = [1, 0, 0, 0, 0, 0] (1을 선택)
C = [0, 0, 1, 0, 0, 0] (~out을 선택)
검증: (s · A) * (s · B) - (s · C) = (5 + 30) * (1) - (35) = 0

이렇게 모든 계산 과정을 벡터 연산으로 구성된 제약 조건 시스템으로 변환했습니다.

[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

3단계: R1CS를 QAP(Quadratic Arithmetic Program)로 변환

R1CS는 계산을 여러 개의 개별적인 제약 조건으로 표현합니다. 하지만 수백만 개의 게이트가 있는 복잡한 계산에서는 제약 조건의 수도 그만큼 많아져 하나씩 확인하는 것이 현실적으로 불가능합니다. QAP 변환의 진정한 목적은 이 수많은 벡터 제약 조건들을 단 하나의 다항식 등식으로 '압축’하여, 검증자가 단 한 번의 확인만으로 전체 계산의 정당성을 검증할 수 있게 만드는 데 있습니다. 이를 위해 라그랑주 보간법(Lagrange Interpolation)과 같은 기법을 사용합니다.

각 게이트(1, 2, 3, 4)를 다항식을 평가할 x좌표(예: x=1, x=2, x=3, x=4)로 간주합니다. 그리고 각 변수 위치에 해당하는 다항식을 만듭니다. 예를 들어, A 벡터들의 첫 번째 요소 [0, 0, 0, 5]를 가져와봅시다. 이 값들은 각각 x=1, 2, 3, 4에서의 다항식의 결과값입니다. 즉, (1,0), (2,0), (3,0), (4,5)를 지나는 다항식을 찾는 것입니다.

이 과정을 모든 변수 위치(6개)와 모든 벡터(A, B, C)에 대해 반복하면, 아래와 같은 다항식의 집합을 얻게 됩니다.

$A_{polynomials} = [A_1(x), A_2(x), ..., A_6(x)]$
$B_{polynomials} = [B_1(x), B_2(x), ..., B_6(x)]$
$C_{polynomials} = [C_1(x), C_2(x), ..., C_6(x)]$

이 다항식들은 R1CS 제약 조건을 다항식 형태로 인코딩한 결과물입니다.

4단계: 다항식 결합 및 최종 검증 문제 생성

마지막으로, 3단계에서 만든 다항식들과 증인 벡터 s를 결합하여 단 하나의 다항식 방정식을 만듭니다.

먼저, 각 다항식 집합을 증인 벡터 s와 내적하여 세 개의 대표 다항식 A(x), B(x), C(x)를 만듭니다.

$A(x) = s[0]*A_1(x) + s[1]*A_2(x) + ... + s[5]*A_6(x)$
$B(x) = s[0]*B_1(x) + s[1]*B_2(x) + ... + s[5]*B_6(x)$
$C(x) = s[0]*C_1(x) + s[1]*C_2(x) + ... + s[5]*C_6(x)$

여기서 이 변환 과정의 마법이 드러납니다. 만약 증명자가 올바른 증인 s를 사용했다면, 이 다항식들을 조합한 P(x) = A(x) * B(x) - C(x)는 우리의 모든 제약 조건에 해당하는 지점(x=1, 2, 3, 4)에서 정확히 0이 됩니다. 즉, 증명자의 계산이 올바를 때만 P(x)가 이 특정 지점들에서 0이 되는 것입니다.

다항식이 특정 지점에서 0이 된다는 것은, 그 지점들을 근으로 갖는다는 의미입니다. 즉, P(x)는 (x-1), (x-2), (x-3), (x-4)를 인수로 가져야 합니다. 이 인수들을 모두 곱한 다항식을 타겟 다항식 Z(x)라고 합니다.

$Z(x) = (x-1)(x-2)(x-3)(x-4)$

따라서, 증명자가 올바른 계산을 수행했다면 아래의 등식이 반드시 성립해야 합니다.

$A(x) * B(x) - C(x) = H(x) * Z(x)$

여기서 H(x)는 P(x) / Z(x)의 몫에 해당하는 다항식입니다.

이처럼 복잡한 계산의 정당성을 단 하나의 다항식 관계로 압축하여 증명하는 것이 이 과정의 핵심입니다. 정리하자면, 우리는 'x=3’이라는 구체적인 비밀값을 아는지를 증명하는 문제를, 수많은 제약 조건을 거쳐 최종적으로는 '두 다항식이 특정 관계를 만족하는가’라는 단 하나의 문제로 변환한 것입니다. 이것이 바로 영지식 증명의 정수입니다.

천천히, 제대로

이 블로그 검색