이차 산술 프로그램: 제로 지식 증명에 대한 논의

저자: Vitalik Buterin

원제목: 《Quadratic Arithmetic Programs: from Zero to Hero》

발표 시간: 2016년 12월 10일

최근 사람들은 zk-SNARKs(제로 지식 증명) 뒤에 있는 기술에 많은 관심을 보이고 있으며, 많은 사람들이 "달의 수학"이라고 부르는 것의 신비한 베일을 벗기기 위해 점점 더 많은 노력을 기울이고 있습니다. 그 복잡성이 매우 이해하기 어렵다고 여겨지기 때문입니다. zk-SNARKs를 이해하는 것은 실제로 상당히 도전적이며, 특히 전체 시스템이 작동하기 위해 조립해야 하는 이동 부품이 너무 많기 때문입니다. 그러나 이 기술을 하나씩 분해하면 이해하기가 더 쉬워질 것입니다.

이 글의 목적은 zk-SNARKs에 대한 완전한 소개가 아니며, 다음과 같은 배경 지식을 가지고 있다고 가정합니다:

1- 당신은 zk-SNARKs와 그 대략적인 원리를 알고 있습니다;

2- 당신은 기본적인 다항식 지식을 이해할 수 있을 만큼 충분한 수학 지식을 가지고 있습니다. (예: if P(x)+ Q(x)=(P + Q)(x), P와 Q는 다항식을 나타내며, 이러한 다항식 표현 방식에 매우 익숙하다면 계속 읽을 준비가 되어 있는 것입니다).

zk-SNARK 지식 파이프라인 다이어그램, Eran Tromer 작성

위 그림과 같이, 위의 제로 지식 증명은 위에서 아래로 두 단계로 나눌 수 있습니다. 먼저, zk-SNARK는 어떤 계산 문제에도 직접 적용될 수 없습니다; 반대로, 문제를 작동하는 올바른 "형태"로 변환해야 합니다. 이 형태를 "이차 산술 프로그램"(QAP)이라고 하며, 함수의 코드를 이러한 코드로 변환하는 것이 매우 중요합니다. 함수 코드를 QAP로 변환하는 과정과 함께 실행되는 또 다른 과정이 있으며, 이 과정은 코드에 입력이 있을 경우 해당 솔루션(때때로 QAP의 "증인"이라고 불림)을 생성할 수 있도록 합니다. 이것이 이 글에서 다루어야 할 내용입니다.

그 후에는 이 QAP에 대한 실제 "제로 지식 증명"을 생성하는 또 다른 상당히 복잡한 과정이 있으며, 다른 사람이 전달한 증거를 검증하는 별도의 과정이 있지만, 이러한 세부 사항은 이 글의 범위를 벗어납니다.

아래 예제에서는 매우 간단한 문제를 선택하겠습니다:

삼차 방정식의 해를 구하시오: x**3 + x + 5 == 35 (힌트: 답은 3입니다).

이 문제는 간단하지만, 중요하게도 이 사례를 통해 모든 기능이 어떻게 작동하는지를 볼 수 있습니다.

프로그래밍 언어로 위의 방정식을 설명하면 다음과 같습니다:

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

여기서 사용되는 간단한 프로그래밍 언어는 기본 산술(+、-、、、/)과 같은 지수(x7, 그러나 x*y는 아님) 및 변수 할당을 지원하며, 이론적으로는 모든 계산을 수행할 수 있을 만큼 강력합니다(계산 단계의 수가 유한한 경우에 한하여; 루프는 허용되지 않음). 모듈(%) 및 비교 연산자(\<、>、≤≥)는 지원되지 않으며, 유한 순환 군 알고리즘을 직접 비교하거나 모듈을 수행할 수 있는 유효한 방법이 없기 때문입니다(감사합니다; 만약 어떤 방법으로든 이를 수행할 수 있다면, 타원 곡선 암호 해독 속도는 "이진 검색" 및 "중국 잔여 정리"를 초과할 것입니다).

비트 분해를 통해 언어를 모듈 및 비교로 확장할 수 있으며(예: 13 = 2**3 + 2**2 + 1=8+4+1) 보조 입력으로 이러한 분해의 정확성을 증명하고 이진 회로에서 수학적 연산을 수행할 수 있습니다; 유한체 알고리즘에서는 등식(==) 검사를 수행하는 것도 가능하며, 실제로는 더 쉽지만, 이 두 가지 세부 사항은 지금 논의하지 않겠습니다. 우리는 조건문을 지원하기 위해 언어를 확장할 수 있습니다(예: 문장을 if x \< 5: y = 7; else: y = 9;를 산술 형태로 변환: y = 7 * (x \< 5) + 9 * (x >= 5);) 그러나 조건의 두 "경로" 모두 실행해야 하며, 많은 중첩 조건이 있는 경우 이는 상당한 오버헤드를 초래할 수 있습니다.

이제 이 과정을 단계별로 진행해 보겠습니다. 만약 당신이 어떤 코드를 직접 작성하고 싶다면, 저는 여기에서 Python으로 구현한 코드를 제공했습니다(교육 목적으로만; 현실 세계의 zk-SNARK를 위한 QAP는 아직 준비되지 않았습니다!).

첫 번째 단계: 평탄화

첫 번째 단계는 "평탄화" 과정으로, 원래 코드를(임의로 복잡한 문장과 표현을 포함할 수 있음) 가장 간단한 표현으로 분해하는 것입니다. 이러한 표현은 두 가지 형태가 있습니다:

1- x = y (y는 변수 또는 숫자일 수 있음)
2- x = y(op)z (op는 +,-,*,/일 수 있으며, y와 z는 변수, 숫자 또는 하위 표현일 수 있음).

이러한 표현을 회로의 논리 게이트로 볼 수 있습니다. 위의 표현 x**3 + x + 5의 평탄화 과정 결과는 다음과 같습니다:

sym_1 = x * x  
y = sym_1 * x // 이는 y = x\*\*3을 구현한 것과 같습니다.  
sym_2 = y + x  
~out = sym_2 + 5

위의 각 선언은 회로의 논리 게이트로 간주할 수 있으며, 원래 코드와 비교할 때 여기서는 두 개의 중간 변수 sym1과 sym2, 그리고 출력을 나타내는 잉여 변수 ~out이 도입되었습니다. "평탄화"된 선언 시퀀스는 원래 코드와 동등하다는 것을 쉽게 알 수 있습니다.

두 번째 단계: R1CS로 변환

이제 이것을 R1CS(랜덤-1 제약 시스템)이라고 불리는 것으로 변환합니다. R1CS는 세 개의 벡터(a, b, c)로 구성된 시퀀스이며, R1CS의 해는 벡터 s로, 여기서 s는 다음 방정식을 만족해야 합니다:

s . a * s . b - s . c = 0

여기서 .는 내적 연산을 나타냅니다.

예를 들어, 다음은 만족스러운 R1CS입니다:

a = (5,0,0,0,0,1),  
b = (1,0,0,0,0,0),  
c = (0,0,1,0,0,0),  
s = (1,3,35,9,27,30),

（번역자 주: 첫 번째 35=1*5 + 30*1, 두 번째 35=35 * 1）

위의 예는 단지 하나의 제약일 뿐이며, 다음으로 우리는 각 논리 게이트(즉, "평탄화"된 각 선언문)를 제약으로 변환해야 합니다(즉, (a, b, c) 삼중 벡터 그룹). 변환 방법은 선언이 어떤 연산 (+,-,*,/)인지와 선언의 매개변수가 변수인지 숫자인지에 따라 다릅니다. 이 예제에서는 "평탄화"된 다섯 개의 변수('x', '~out', 'sym1', 'y', 'sym2') 외에도 첫 번째 성분 위치에 숫자 1을 나타내기 위해 잉여 변수 ~one을 도입해야 합니다. 따라서 이 시스템에서 하나의 벡터가 대응하는 6개의 성분은(다른 순서일 수 있지만, 일치하기만 하면 됩니다):

'~one', 'x', '~out', 'sym1', 'y', 'sym2'

첫 번째 게이트

sym1 = x * x, 즉 x*x - sym1 = 0

다음과 같은 벡터 그룹을 얻을 수 있습니다:

a = [0, 1, 0, 0, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 1, 0, 0]

해 벡터 s의 두 번째 스칼라가 3이고, 네 번째 스칼라가 9라면, 다른 스칼라가 무엇이든 성립합니다. 왜냐하면: a = 3 * 1, b = 3 * 1, c = 9 * 1, 즉 a * b = c입니다. 마찬가지로, s의 두 번째 스칼라가 7이고 네 번째 스칼라가 49일 경우에도 검사를 통해 확인할 수 있습니다. 첫 번째 검사는 단지 첫 번째 게이트의 입력과 출력의 일관성을 검증하기 위한 것입니다.

두 번째 게이트

y = sym1 * x, 즉 sym1 * x - y = 0
다음과 같은 벡터 그룹을 얻을 수 있습니다:

a = [0, 0, 0, 1, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 0, 1, 0]

세 번째 게이트

sym2 = y + x, 즉 (x + y) * 1 - sym2 = 0
다음과 같은 벡터 그룹을 얻습니다:

a = [0, 1, 0, 0, 1, 0]  
b = [1, 0, 0, 0, 0, 0] // 상수 1에 해당, ~one 위치  
c = [0, 0, 0, 0, 0, 1]

네 번째 게이트

~out = sym2 + 5, 즉 (sym2 + 5) * 1 - ~out = 0
다음과 같은 벡터 그룹을 얻습니다:

a = [5, 0, 0, 0, 0, 1]  
b = [1, 0, 0, 0, 0, 0]  
c = [0, 0, 1, 0, 0, 0]

이제 x = 3이라고 가정하면, 첫 번째 게이트에 따라 sym1 = 9를 얻고, 두 번째 게이트에 따라 y = 27을 얻고, 세 번째 게이트에 따라 sym2 = 30을 얻고, 네 번째 게이트에 따라 ~out = 35를 얻습니다. 따라서, '~one', 'x', '~out', 'sym1', 'y', 'sym2'에 따라:

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

다른 x를 가정하면 서로 다른 s를 얻을 수 있지만, 모든 s는 (a, b, c)를 검증하는 데 사용할 수 있습니다.

이제 우리는 네 개의 제약의 R1CS를 얻었으며, 전체 R1CS는 다음과 같습니다:

A

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

B

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

C

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

세 번째 단계: R1CS에서 QAP로

다음 단계는 이 R1CS를 QAP 형태로 변환하는 것입니다. 이는 완전히 동일한 논리를 구현하지만 내적 대신 다항식을 사용합니다. 우리는 이렇게 합니다: 4개의 길이가 6인 3개의 벡터에서 6개의 길이가 3인 다항식으로, 각 x 좌표에서 다항식이 제약 조건을 나타내도록 평가합니다. 즉, x=1에서 다항식을 평가하면 첫 번째 벡터 그룹을 얻고, x=2에서 다항식을 평가하면 두 번째 벡터 그룹을 얻는 식입니다.

우리는 라그랑주 보간법을 사용하여 이 변환을 수행할 수 있습니다. 라그랑주 보간법이 해결하는 문제는: 점 집합(즉, (x, y) 좌표 쌍)이 있을 때, 이 점들을 통과하는 다항식을 만드는 것입니다. 우리는 문제를 분해하여 각 x 좌표에 대해 필요한 y 좌표의 x 좌표와 y 좌표 0을 다른 모든 x 좌표에서 관심 있는 것과 함께 생성한 다음, 최종 결과를 모든 다항식을 함께 추가하여 얻습니다.

예를 들어 보겠습니다. (1,3), (2,2) 및 (3,4)를 통과하는 다항식을 원한다고 가정해 보겠습니다. 우리는 먼저 (1,3)(2,0) 및 (3,0)을 통과하는 다항식을 만듭니다. 사실, 다항식은 "x = 1"과 0의 다른 관심 지점을 쉽게 만들 수 있으며, 다음과 같은 다항식을 만들면 됩니다:

y = (x - 2) * (x - 3)

아래 그림과 같이:

그런 다음 y축 방향으로 "늘리기" 위해 다음 방정식을 사용합니다:

y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

정리하면:

y = 1.5 * x**2 - 7.5 * x + 9

이것은 (1,3), (2,0) 및 (3,0) 세 점을 모두 통과합니다. 아래 그림과 같이:

(2,2) 및 (3,4) 두 점을 위 식에 대입하면:

y = 1.5 * x**2 - 5.5 * x + 7

이것이 우리가 원하는 좌표 방정식입니다. 위 알고리즘은 O(n3) 시간이 필요합니다. 왜냐하면 n개의 점이 있고 각 점마다 O(n2) 시간이 필요하기 때문입니다. 조금 생각해 보면, 이는 O(n**2) 시간으로 줄일 수 있으며, 더 생각해 보면 빠른 푸리에 변환 알고리즘 등을 사용하여 더욱 줄일 수 있습니다. 이는 zk-spuks에서 사용되는 함수가 일반적으로 수천 개의 게이트를 가질 때 중요한 최적화입니다.

여기에서 라그랑주 보간 공식은 다음과 같습니다:

n개의 점 (x1,y1), (x2,y2), (x3,y3), … , (xn,yn)의 n-1차 다항식은:

예를 들어 위 예에서 (1,3), (2,2), (3,4)를 통과하는 다항식은:

이 공식을 사용하는 방법을 배우면 우리의 단계를 계속 진행할 수 있습니다. 이제 네 개의 길이가 6인 세 벡터 그룹을 여섯 개의 다항식으로 변환해야 하며, 각 다항식은 세 개의 삼차 다항식을 포함하고, 각 x 점에서 서로 다른 제약을 평가합니다. 여기서 우리는 총 네 개의 제약이 있으므로, 각각의 다항식에서 x = 1, 2, 3, 4에서 이 네 개의 벡터 그룹을 평가합니다.

이제 우리는 라그랑주 보간 공식을 사용하여 R1CS를 QAP 형태로 변환합니다. 우리는 먼저 네 개의 제약에 해당하는 각 a 벡터의 첫 번째 값의 다항식을 구합니다. 즉, 라그랑주 보간 정리를 사용하여 점 (1,0), (2,0), (3,0), (4,0)을 통과하는 다항식을 구합니다. 유사하게 나머지 네 개의 제약에 해당하는 각 벡터의 i번째 값의 다항식을 구할 수 있습니다.

여기에서 직접 답을 제시합니다:

A 다항식
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B 다항식
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C 다항식
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

이러한 계수는 오름차순으로 정렬되어 있습니다. 예를 들어, 위의 첫 번째 다항식은 0.833 * x**3 - 5 * x**2 + 9.166 * x - 5입니다. 만약 우리가 x=1을 위의 18개 다항식에 대입하면 첫 번째 제약의 세 개의 벡터를 얻을 수 있습니다:

(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
…
유사하게 x = 2, 3, 4를 위의 다항식에 대입하면 R1CS의 나머지 부분을 복원할 수 있습니다.

네 번째 단계: QAP 검증

R1CS를 QAP로 변환함으로써 우리는 다항식의 내적 연산을 통해 모든 제약을 동시에 검증할 수 있습니다. R1CS처럼 각 제약을 개별적으로 검증하는 것이 아닙니다. 아래 그림과 같이:

이 경우 내적 검증은 일련의 다항식의 덧셈과 곱셈이며, 결과 자체가 다항식입니다. 만약 얻어진 다항식이 우리가 위에서 논리 게이트를 나타내기 위해 사용한 각 x 좌표에서의 값이 0이라면, 모든 검증이 통과한 것입니다. 만약 결과 다항식이 적어도 하나의 비제로 값을 가지면, 이는 논리 게이트의 입력과 출력 값이 일치하지 않음을 의미합니다.

주목할 점은, 얻어진 다항식 자체가 반드시 0일 필요는 없으며, 사실 대부분의 경우 그렇지 않습니다; 이는 특정 논리 게이트의 점에서 어떤 행동을 할 수 있지만, 특정 게이트의 점에서 결과가 0이면 됩니다. 정확성을 검증하기 위해, 우리는 다항식 t = A . s * B . s - C . s를 각 점에서 해당 게이트에 대해 계산하지 않습니다; 대신, 우리는 t를 다른 다항식 Z로 나누고, Z가 t를 균일하게 나누는지 확인합니다. 즉, 나눗셈 t / Z는 나머지가 없습니다.

Z는 (x - 1) * (x - 2) * (x - 3)…로 정의됩니다. 이는 모든 해당 논리 게이트의 점에서 0이 되는 가장 간단한 다항식입니다. 이는 대수학의 기본 사실로, 어떤 다항식이 이러한 점에서 0이라면 반드시 이 최소 다항식의 배수여야 합니다. 만약 어떤 다항식이 Z의 배수라면, 이는 이러한 점에서의 값이 0입니다; 이러한 동등성은 우리의 작업을 훨씬 쉽게 만듭니다.

이제 위의 다항식을 사용하여 내적 검증을 수행해 보겠습니다.

먼저, 우리는 중간 다항식을 얻습니다:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]
（번역자 주: 위의 계산 과정:
43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30，
-73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30,
…
-3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
…)

위의 다항식은 A . s * B . s - C . s 계산 후 다음과 같습니다:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
（번역자 주: 계산 과정:
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 * x3 + 38.5 * x2 - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x3 - 5 * x2 + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x3 - 24.5 * x2 + 71.666 * x - 41.0
A . s * B . s - C . s는 위의 다항식의 계산이며, 계산 후, 차수에 따라 낮은 것부터 높은 것까지 계수를 정렬하여 얻습니다: [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

최소 다항식은:

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

즉:

Z = [24, -50, 35, -10, 1]

위의 계산 과정은 여기를 클릭하여 확인%20%5Ccdot%20%5Cleft(x%20-%203%5Cright)%20%5Ccdot%20%5Cleft(x%20-%204%5Cright)).

이제 다항식 나눗셈을 계산합니다:

h = t / Z = [-3.666, 17.055, -3.444]

h는 나머지 없이 정수 나눗셈이어야 합니다.

여기를 클릭하여 확인할 수 있습니다%20%5Ccdot%5Cleft(x%20-%203%5Cright)%20%5Ccdot%5Cleft(x%20-%204%5Cright)%5Ccdot%5Cleft(-3.444x%5E%7B2%7D%2B17.055x-3.666%5Cright)).

우리는 QAP의 해를 얻었습니다. 만약 우리가 R1CS의 변수를 위조하려고 한다면, 이 R1CS는 QAP 솔루션을 도출합니다. 예를 들어, s의 마지막 숫자를 30이 아닌 31로 설정하면, 우리는 t 다항식이 검증에 실패할 것입니다(특정 경우에, x = 3에서 1이 아닌 0이 됩니다), 그리고 Z의 배수가 아닐 것입니다; 반대로, t / Z를 나누면 [-5.0, 8.833, -4.5, 0.666]의 나머지를 얻게 됩니다.

위의 예는 매우 간단한 예일 뿐입니다; 현실 세계에서는 덧셈, 뺄셈, 곱셈 및 나눗셈이 일반적으로 비정규 숫자와 함께 수행되므로, 우리가 알고 사랑하는 모든 대수 법칙은 여전히 유용하지만, 모든 답변은 어떤------의 크기의 요소이며, 일반적으로 0에서 n - 1 범위 내의 정수 n입니다. 예를 들어, n = 13이라면, 1 / 2 = 7(7 * 2 = 1), 3 * 5 = 2 등입니다. 유한체 알고리즘을 사용하면 반올림 오차에 대한 걱정을 없애고 시스템이 타원 곡선과 잘 작동하도록 하여, 궁극적으로 zk-SNARK 프로토콜을 진정으로 안전하게 만드는 데 기여합니다.