이차 산술 프로그램: 제로지식 증명에 관한 논고
글: 비탈릭 부테린
발표일: 2016년 12월 10일
최근 zk-SNARKs(제로 지식 증명) 뒤에 있는 기술에 대한 관심이 많아지고 있으며, 많은 사람들이 다수의 사람들이 "달의 수학(moon math)"이라고 부르는 이 기술의 신비를 벗기려 하고 있다. 그 이유는 이 기술이 이해하기 어려울 정도로 복잡하다고 여겨지기 때문이다.
zk-SNARKs를 이해하는 것은 실제로 상당히 도전적인 일이다. 특히 전체 시스템을 작동시키기 위해 결합해야 하는 구성 요소들이 너무 많기 때문이다. 하지만 이 기술을 조각조각으로 분해하면 이해가 훨씬 쉬워진다.
본문은 zk-SNARKs에 대한 완전한 소개가 아니다. 독자가 다음의 배경 지식을 가지고 있다고 가정한다:
1- zk-SNARKs와 그 대략적인 원리를 알고 있을 것;
2- 기본적인 다항식에 대한 수학적 지식이 있어야 한다(P(x)+ Q(x)=(P + Q)(x)처럼 P와 Q가 다항식인 경우, 이런 표현 방식에 익숙하다면 본문을 계속 읽을 수준의 지식을 갖춘 것이다).
zk-SNARK 지식 파이프라인 차트, 에란 트로머(Eran Tromer) 작성
위 그림에서 보듯, 제로 지식 증명은 위에서 아래로 두 단계로 나눌 수 있다. 첫째, zk-SNARK는 어떤 계산 문제에나 직접 적용될 수 없다. 대신 문제를 올바른 "형태"로 변환해야 한다. 이 형태를 "이차 산술 프로그램"(QAP)이라 부르며, 함수 코드를 이러한 형태로 변환하는 과정 자체도 매우 중요하다. 함수 코드를 QAP로 변환하는 과정과 함께, 코드에 입력값이 주어졌을 때 이에 대응하는 해답(때때로 QAP의 "증거(witness)"라고 함)을 생성하는 또 다른 과정이 병행된다. 이것이 본문에서 설명할 내용이다.
그 이후에는 이 QAP에 대해 실제 "제로 지식 증명"을 생성하는 또 다른 상당히 복잡한 과정이 있고, 누군가 당신에게 전달한 증명을 검증하는 별도의 절차도 존재한다. 그러나 이러한 세부 사항은 본문의 범위를 벗어난다.
다음 예시에서는 아주 간단한 문제를 선택하겠다:
세제곱 방정식 x**3 + x + 5 == 35의 해를 구하라(힌트: 답은 3).
이 문제는 매우 간단하지만 중요한데, 이 사례를 통해 모든 기능이 어떻게 작동하는지를 확인할 수 있기 때문이다.
위 방정식을 프로그래밍 언어로 표현하면 다음과 같다:
def qeval(x):
y = x**3
return x + y + 5
여기서 사용하는 간단한 프로그래밍 언어는 기본 산술(+, -, *, /), 항등 거듭제곱(x^7 등, 하지만 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 생성에는 아직 준비되지 않았다!).
첫 번째 단계: 평탄화(Flattening)
첫 번째 단계는 "평탄화(flattening)" 과정으로, 원래의 코드(임의로 복잡한 문장과 표현을 포함할 수 있음)를 가장 단순한 형태의 표현들로 분해하는 것이다. 이러한 표현은 두 가지 형식을 취한다:
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
각 줄의 선언을 하나의 논리 게이트로 생각할 수 있다. 원래 코드와 비교하면 여기서는 두 개의 중간 변수 sym_1과 sym_2, 그리고 출력을 나타내는 여분의 변수 ~out을 도입했다. "평탄화"된 선언 시퀀스가 원래 코드와 동치임을 어렵지 않게 알 수 있다.
두 번째 단계: R1CS로 변환
이제 이것을 R1CS(Rank-1 Constraint System)라 불리는 것으로 변환한다. R1CS는 세 벡터(a, b, c)로 구성된 시퀀스이며, R1CS의 해는 다음 방정식을 만족해야 하는 벡터 s이다:
s . a * s . b - s . c = 0
여기서 .는 내적(dot product) 연산을 의미한다.
예를 들어, 다음은 만족되는 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', 'sym_1', 'y', 'sym_2') 외에도, 첫 번째 성분 위치에 숫자 1을 나타내는 여분의 변수 ~one을 도입해야 한다. 우리 시스템에서 벡터가 대응하는 6개 성분은 다음과 같다(순서는 달라도 상관없으나, 서로 일치해야 함):
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
첫 번째 게이트
sym_1 = x * x, 즉 x*x - sym_1 = 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 = sym_1 * x, 즉 sym_1 * x - y = 0
다음과 같은 벡터 세트를 얻을 수 있다:
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
세 번째 게이트
sym_2 = y + x, 덧셈 게이트는 (x + y) * 1 - sym_2 = 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 = sym_2 + 5, 즉 (sym_2 + 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이라고 가정하자. 첫 번째 게이트에서 sym_1 = 9, 두 번째 게이트에서 y = 27, 세 번째 게이트에서 sym_2 = 30, 네 번째 게이트에서 ~out = 35를 얻는다. 따라서 '~one', 'x', '~out', 'sym_1', 'y', 'sym_2' 순서에 따라 다음과 같이 된다:
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 형식으로 변환하는 것이다. QAP는 내적이 아닌 다항식을 사용한다는 점을 제외하면 동일한 논리를 구현한다. 우리는 이렇게 한다: 길이가 6인 3개 벡터로 구성된 4개 세트에서, 길이가 3인 다항식으로 구성된 6개 세트로 변환한다. 각 x 좌표에서 다항식을 평가하면 하나의 제약 조건을 나타낸다. 즉, x=1에서 다항식을 평가하면 첫 번째 벡터 세트를 얻고, x=2에서 평가하면 두 번째 벡터 세트를 얻는 식이다.
이 변환은 라그랑주 보간법(Lagrange interpolation)을 사용하여 수행할 수 있다. 라그랑주 보간법은 일련의 점들((x, y) 좌표 쌍)이 주어졌을 때, 이 모든 점들을 지나는 다항식을 찾는 문제를 해결한다. 우리는 문제를 분해하여 접근한다: 각 x 좌표마다, 해당 x 좌표에서 원하는 y 좌표를 갖고, 우리가 관심 있는 다른 모든 x 좌표에서는 y 좌표가 0이 되는 다항식을 만들고, 최종 결과는 이 모든 다항식을 더하는 것으로 얻는다.
예를 들어보자. (1,3), (2,2), (3,4)를 지나는 다항식을 원한다고 하자. 먼저 (1,3), (2,0), (3,0)을 지나는 다항식을 만들자. x=1에서 "뻗어나가고", 다른 관심 있는 점에서는 0이 되는 다항식은 다음과 같이 쉽게 만들 수 있다:
y = (x - 2) * (x - 3)
다음과 같다:
그리고 y축 방향으로 "늘이기(stretching)" 위해 다음 식을 사용한다:
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
이것이 우리가 원하는 좌표 방정식이다. 위 알고리즘은n개의 점이 있고, 각 점마다 O(n²) 시간이 필요하므로 O(n³) 시간이 필요하다. 약간의 고민으로 이를 O(n²)로 줄일 수 있고, 더 깊이 고민하면 빠른 푸리에 변환 등의 알고리즘을 사용해 추가로 줄일 수 있다. 이것은 zk-SNARK에서 사용되는 함수가 일반적으로 수천 개의 게이트를 가지기 때문에 중요한 최적화이다.
여기에 바로 라그랑주 보간 공식을 제시하겠다:
n개의 점 (x₁,y₁), (x₂,y₂), (x₃,y₃), ..., (xₙ,yₙ)을 지나는 n-1차 다항식은 다음과 같다:
예를 들어, 점 (1,3), (2,2), (3,4)를 지나는 다항식은 다음과 같다:
이 공식을 사용하는 법을 익히면 다음 단계로 진행할 수 있다. 이제 길이가 6인 세 벡터로 구성된 네 개의 세트를, 각각 세 개의 3차 다항식으로 구성된 여섯 개의 다항식 세트로 변환해야 한다. 우리는 각 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이어야 하는 것은 아니라는 점에 주목할 필요가 있다. 대부분의 경우 실제로 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 * x³ + 38.5 * x² - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x³ - 5 * x² + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x³ - 24.5 * x² + 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]
위 계산 과정여기를 클릭하여 확인
이제 다항식 나눗셈을 계산한다:
h = t / Z = [-3.666, 17.055, -3.444]
h는 나머지 없이 딱 맞아떨어져야 한다.
우리는 QAP의 해를 얻었다. 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 = 14 ≡ 1 mod 13), 3 * 5 = 15 ≡ 2 mod 13 등이다. 유한체 산술을 사용하면 반올림 오차에 대한 걱정이 사라지고, 타원 곡선과 잘 작동하여 궁극적으로 zk-SNARK 프로토콜을 진정으로 안전하게 만들어 준다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@VitalikButerin
