비탈릭: zk-SNARK의 내부 원리
*참고: 이 글은 2017년 2월에 작성되었습니다.
이 글은 zk-SNARKs 기술의 작동 원리를 설명합니다. 그 전에 2차 연산 프로그램과 타원 곡선 페어링에 대한 글을 읽는 것이 필수입니다. 본문에서는 독자가 이 두 개념과 zk-SNARKs의 기본 지식 및 그 역할을 알고 있다고 가정합니다. 또한 Christian Reitwiessner의 zk-SNARKs 입문서인 글도 함께 참고하시기 바랍니다.
이전 글에서 우리는 2차 연산 프로그램(Quadratic Arithmetic Program, QAP)이라는 계산 문제를 다항식 방정식으로 표현하는 방법을 소개했습니다. 또한 타원 곡선 페어링을 도입하여 매우 제한적이지만 일방향 동형 암호화(one-way homomorphic encryption) 형태를 가능하게 하고, 이를 통해 동등성 검사를 할 수 있음을 보였습니다. 이제 이전까지의 내용을 바탕으로 타원 곡선 페어링과 기타 수학적 기법들을 활용해 증명자가 특정 QAP의 해를 알고 있음을 증명하면서 실제 해에 관한 정보는 전혀 공개하지 않는 방법을 살펴보겠습니다.
본문은 2013년 Parno, Gentry, Howell, Raykova가 제안한 피노키오 프로토콜(Pinocchio Protocol, 일반적으로 PGHR13이라 불림)에 초점을 맞춥니다. 기본 메커니즘에는 일부 변화가 있으므로 실용적인 구현에서 사용되는 zk-SNARK 스킴은 약간 다를 수 있지만, 핵심 원칙은 대체로 유지됩니다.
먼저 중요한 가정 하나를 살펴봅시다. 바로 지수 지식 가정(Knowledge of Exponent Assumption, KEA)입니다. 이 가정은 나중에 보안 메커니즘을 설명할 때 사용됩니다.
KEA1: 어떤 공격자 A가 입력 q, g, g^a를 받아 (C, Y)를 출력하고, Y = C^a 를 만족한다고 하자. 그러면 반드시 추출자(extractor) A'가 존재해서, A와 동일한 입력을 받았을 때 g^c = C 인 c를 반환할 수 있다.
이 가정은 기본적으로 점 P와 Q가 주어졌을 때, P * k = Q 를 만족하고, 또 다른 점 C가 주어졌다고 할 때, k 값은 모르더라도 C * k 에 해당하는 점을 계산하려면 C가 P로부터某种 방식으로 "유도"될 수 있어야 한다는 의미입니다. 이것은 자명해 보일 수 있지만, 실제로 타원 곡선 프로토콜의 보안성을 증명할 때 일반적으로 사용하는 다른 가정들(예: 이산 로그 문제 등)로부터 유도할 수 없습니다. 따라서 zk-SNARKs는 어쨌든 어느 정도, 타원 곡선 암호보다는 약간 더 약한 보안 기반을 갖는다고 볼 수 있습니다. 하지만 여전히 충분히 견고하며 대부분의 암호학자들이 이를 사용할 수 있다고 인정합니다.
자, 이제 이것을 어떻게 활용할 수 있는지 살펴봅시다. 하늘에서 한 쌍의 점 (P, Q)가 떨어졌고, P * k = Q 를 만족한다고 가정합시다. 그러나 누구도 k의 값을 모릅니다. 이제 제가 (R, S)라는 점 쌍을 만들어내며 R * k = S 라고 주장한다고 생각해 봅시다. 그러면 KoE 가정에 따르면, 제가 이 점 쌍을 얻을 수 있는 유일한 방법은 제가 알고 있는 어떤 스칼라 r을 이용해 P와 Q를 곱한 것임을 의미합니다. 또한 타원 곡선 페어링의 특별한 성질 덕분에 R = k * S 인지를 확인하기 위해 k 값을 알 필요조차 없으며, 단순히 e(R, Q) = e(P, S) 를 검사하면 됩니다.
더 흥미로운 상황을 생각해 봅시다. 하늘에서 10쌍의 점이 떨어졌다고 가정합시다: (P_1, Q_1), (P_2, Q_2), ..., (P_10, Q_10). 모든 경우에 대해 P_i * k = Q_i 를 만족합니다. 제가 그런 다음 여러분에게 (R, S) 쌍을 줄테고, R * k = S 를 만족한다고 합시다. 여러분은 무엇을 알게 될까요? 여러분은 R이 P_1 * i_1 + P_2 * i_2 + ... + P_10 * i_10 의 선형 조합이며, 저는 계수 i_1, i_2, ..., i_10 를 알고 있다는 것을 알게 됩니다. 즉, 이런 (R, S) 쌍에 도달하는 유일한 방법은 P_1, P_2, ..., P_10 의 배수를 취해서 더하는 것이며, Q_1, Q_2, ..., Q_10 에 대해서도 동일한 계산을 수행하는 것입니다.
여러분이 임의의 특정 P_1 ... P_10 점 집합에 대해 선형 조합을 검증하고자 할 때, 실제로는 k 값을 알지 못하면 대응하는 Q_1 ... Q_10 점을 만들 수 없다는 점에 주목하세요. 만약 정말로 k 값을 안다면, 선형 조합을 만들지 않고도 원하는 어떤 R에 대해서든 R * k = S 를 만족하는 (R, S) 쌍을 만들 수 있습니다. 따라서 이를 실현하기 위해서는 이러한 점들을 생성하는 사람이 신뢰할 수 있어야 하며, 10개의 점을 생성한 후에는 k 값을 반드시 삭제해야 합니다. 이것이 바로 "신뢰할 수 있는 설정(trusted setup)" 개념의 기원입니다. (역주: 신뢰할 수 있는 설정이란 zkSNARK 시스템 시작 시 한 번만 수행되는 초기 설정을 말합니다.)
QAP의 해란 다항식 A(x), B(x), C(x)가 존재하여 A(x) * B(x) - C(x) = H(x) * Z(x) 를 만족하는 것을 말합니다. 여기서:
A는 다항식 {A_1 ... A_m}의 선형 조합
B는 같은 계수를 가지는 {B_1 ... B_m}의 선형 조합
C는 같은 계수를 가지는 {C_1 ... C_m}의 선형 조합
집합 {A_1 ... A_m}, {B_1 ... B_m}, {C_1 ... C_m} 및 다항식 Z는 문제 정의의 일부입니다.
그러나 대부분의 현실 세계에서 A, B, C는 매우 큽니다. 수천 개의 회로 게이트를 가진 해시 함수와 같은 경우, 다항식(및 선형 조합의 계수)은 수천 항을 가질 수 있습니다. 따라서 증명자가 직접 선형 조합을 제공하는 대신, 위에서 소개한 기술을 사용해 제공된 값이 선형 조합임을 증명하고, 그 외의 정보는 전혀 공개하지 않도록 합니다.
여러분은 위의 기술이 다항식이 아닌 타원 곡선 점에 적용된다는 것을 눈치챘을 것입니다. 따라서 실제로는 아래 값을 신뢰할 수 있는 설정(trusted setup)에 추가합니다:
G * A_1(t), G * A_1(t) * k_a
G * A_2(t), G * A_2(t) * k_a
...
G * B_1(t), G * B_1(t) * k_b
G * B_2(t), G * B_2(t) * k_b
...
G * C_1(t), G * C_1(t) * k_c
G * C_2(t), G * C_2(t) * k_c
...
여기서 t는 다항식을 계산하는 "비밀 점(secret point)"으로 간주할 수 있습니다. G는 "생성기(generator)"입니다(타원 곡선 위의 임의의 점으로, 한 번 결정되면 프로토콜의 일부로 고정됨). t, k_a, k_b, k_c는 "유독 폐기물(toxic waste)"이며, 이 숫자들은 가능한 한 철저히 삭제되어야 하며, 누군가가 이를 확보하면 가짜 증명을 만들 수 있습니다. 이제 누군가가 여러분에게 P, Q 쌍을 주고 P * k_a = Q 를 만족한다고 한다면(기억하세요, k_a를 알 필요 없이 페어링 검사를 통해 확인 가능), 여러분은 그들이 t에서 계산된 A_i 다항식의 선형 조합을 제공했다는 것을 알 수 있습니다.
따라서 지금까지 증명자는 다음과 같은 값을 제공해야 합니다:
π_a = G * A(t), π'_a = G * A(t) * k_a
π_b = G * B(t), π'_b = G * B(t) * k_b
π_c = G * C(t), π'_c = G * C(t) * k_c
증명자가 이 값을 계산하기 위해 t, k_a, k_b 또는 k_c를 실제로 알 필요는 없다는 점에 주목하세요. 오히려 증명자는 우리가 신뢰할 수 있는 설정에 추가한 점들로부터 이 값을 계산할 수 있어야 합니다.
다음 단계는 세 선형 조합 모두가 동일한 계수를 가지고 있는지 확인하는 것입니다. 이를 위해 신뢰할 수 있는 설정에 다음과 같은 값을 추가함으로써 달성할 수 있습니다: G * (A_i(t) + B_i(t) + C_i(t)) * b. 여기서 b는 신뢰 설정 완료 후 폐기되어야 하는 또 다른 "유독 폐기물(toxic waste)"입니다. 그런 다음 증명자에게 이 값들의 선형 조합을 동일한 계수로 생성하도록 하고, 위에서 설명한 것과 동일한 페어링 기술을 사용하여 이 값이 제공된 A + B + C와 일치하는지 검증할 수 있습니다.
마지막으로, A * B - C = H * Z 임을 증명해야 합니다. 다시 한 번 페어링 검사를 사용합니다:
e(π_a, π_b) / e(π_c, G) ?= e(π_h, G * Z(t))
여기서 π_h = G * H(t) 입니다. 이 등식과 A * B - C = H * Z 사이의 연결을 이해하지 못하겠다면, 페어링에 대한 글을 다시 읽어보세요.
위에서 우리는 A, B, C를 타원 곡선 위의 점으로 변환하는 방법을 보았습니다. G는 단지 생성기일 뿐입니다(즉, 이 타원 곡선 점 G는 숫자에서의 1과 같습니다). 우리는 G * Z(t)를 신뢰할 수 있는 설정에 추가할 수 있습니다. H는 계산하기 더 어렵습니다. H는 단지 다항식일 뿐이며, 각 QAP의 해마다 그 계수가 다르기 때문에 미리 예측하기 어렵습니다. 따라서 신뢰할 수 있는 설정에 더 많은 데이터를 추가해야 합니다. 특히 다음과 같은 수열을 추가합니다:
G, G * t, G * t², G * t³, G * t⁴, ...
Zcash의 신뢰 설정에서 이 수열은 약 200만 개 정도입니다. H(t)를 계산하려면 얼마나 큰 컴퓨팅 파워가 필요한지 상상해 보세요. 이를 통해 증명자는 검증자가 최종 검사를 수행하는 데 필요한 모든 정보를 제공할 수 있습니다.
또 하나 논의해야 할 세부 사항이 있습니다. 대부분의 경우 우리는 특정 문제가 해를 가진다는 추상적인 증명만을 원하는 것이 아니라, 특정 해의 정확성을 증명하거나(예: "cow"라는 단어를 SHA3 알고리즘으로 백만 번 해시했을 때 결과가 0x73064fe5로 시작한다는 것을 증명), 일부 매개변수를 제한했을 때 해가 존재함을 증명하고 싶습니다. 예를 들어, 암호화폐 구현에서는 거래 금액과 계좌 잔액이 암호화되어 있으며, 특정 복호화 키 k를 알고 있음을 증명해야 합니다:
decrypt(old_balance, k) ≥ decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
암호화된 old_balance, tx_value, new_balance는 특정 시점에서 우리가 확인해야 하는 구체적인 값이므로 공개되어야 합니다. 오직 복호화 키만 숨겨져야 합니다. 특정 입력에 대한 제약 조건에 해당하는 "맞춤형 검증 키(custom verification key)"를 생성하기 위해 프로토콜에 약간의 수정이 필요합니다.
자, 이제 한 발 물러서서 전체 그림을 살펴봅시다. 먼저, Ben Sasson, Tromer, Virza, Chiesa가 제공한 전체 검증 알고리즘은 다음과 같습니다:
첫 번째 줄은 매개변수화 처리를 수행합니다. 본질적으로 이 기능은 특정 매개변수를 지정한 특정 문제 인스턴스에 대해 "맞춤형 검증 키"를 생성하는 것으로 볼 수 있습니다. 두 번째 줄은 A, B, C의 선형 조합 검사이고, 세 번째 줄은 선형 조합이 동일한 계수를 가지는지 검사하며, 네 번째 줄은 A * B - C = H * Z 인지를 검사합니다.
요약하자면, 검증 과정은 몇 차례의 타원 곡선 곱셈("공개" 입력 변수마다 하나씩)과 다섯 차례의 페어링 검사로 구성되며, 그 중 하나는 추가적인 페어링 곱셈을 포함합니다. 제공되는 증명은 여덟 개의 타원 곡선 점으로 이루어집니다: A(t), B(t), C(t) 각각 하나의 점, b*(A(t)+B(t)+C(t))의 점 π_k, 그리고 H(t)의 점 π_h. 이 중 7개는 F_p 곡선 위에 있으며(y 좌표는 1비트로 압축 가능하므로 각각 32바이트), Zcash 구현에서는 다른 하나의 점(π_b)이 F_p²의 비틀린 곡선 위에 있으므로(64바이트), 증명의 총 크기는 약 288바이트입니다.
증명을 생성하는 데 가장 계산량이 큰 두 부분은 다음과 같습니다:
- (A * B - C)/Z를 수행하여 H를 얻는 작업(FFT 기반 알고리즘으로 준 2차 시간 내에 수행 가능하지만 여전히 계산량이 큼)
- A(t), B(t), C(t), H(t)의 값을 생성하기 위한 타원 곡선 곱셈 및 덧셈, 그리고 이에 대응하는 페어링 계산
증명 생성이 어려운 이유는 우리가 영지식 증명(zero-knowledge proof)을 수행하기 때문에, 원래 계산의 단일 이진 논리 게이트조차 타원 곡선을 통한 암호화 처리 작업으로 바뀌어야 하기 때문입니다. 이 사실과 FFT의 초선형성(superlinearity) 때문에 Zcash 거래에서 증명을 생성하는 데 약 20~40초가 소요됩니다.
또 다른 매우 중요한 질문은: 신뢰할 수 있는 설정을 좀 더... 적은 신뢰를 요구하도록 만들 수 있을까? 안타깝게도 완전히 신뢰를 배제할 수는 없습니다. KoE 가정 자체가 k 값을 모른 상태에서 독립적인 쌍 (P_i, P_i * k)를 형성하는 가능성을 배제하기 때문입니다. 하지만 N-N 다자간 계산(N-of-N multiparty computation)을 사용하여 보안성을 크게 향상시킬 수 있습니다. 즉, N명의 참여자 사이에서 신뢰 설정을 구성하여, 그들 중 최소한 한 명이라도 자신의 유독 폐기물을 삭제한다면 안전하다는 것입니다.
어떻게 할 수 있는지 감을 잡게 해 주기 위해, 기존 집합 (G, G * t, G * t², G * t³, ...)에 자신만의 비밀을 "추가"하여, 당신의 비밀과 이전의 비밀(또는 이전 비밀의 집합)이 모두 있어야 부정행위를 할 수 있도록 하는 간단한 알고리즘을 소개합니다.
출력 집합은 다음과 같습니다:
G, (G * t) * s, (G * t²) * s², (G * t³) * s³, ...
이제부터는 '유독 폐기물'이 t 대신 t * s 가 되었음을 주목하세요. 오직 원래 집합과 s만 알면, 이전 집합과 동일한 기능을 하는 새 집합을 만들 수 있습니다. 여러분과 이전 집합을 생성한 사람(들)이 유독 폐기물을 모두 삭제하지 못하고 이후 공모하지 않는 한, 이 집단은 "안전"합니다.
완전한 신뢰 설정에 대해 이 작업을 수행하는 것은 훨씬 더 어렵습니다. 여러 값이 관련되고 알고리즘이 여러 라운드에 걸쳐 다자간에서 수행되어야 하기 때문입니다. 이는 활발한 연구 분야이며, 다자간 계산 알고리즘이 더 단순화되고, 더 적은 라운드 또는 더 많은 병렬화가 가능해지기를 기대하는 이유입니다. 그렇게 된다면 더 많은 참여자가 신뢰 설정 프로세스에 참여할 수 있게 됩니다. 여섯 명의 참여자가 관여한 신뢰 설정이 일부 사람들에게 불편하게 느껴질 수 있지만, 수천 명이 참여한 신뢰 설정은 거의 무신뢰(de-trust)에 가깝습니다. 만약 정말 괴팍하다면, 직접 참여해서 설정 프로세스에 참여하고 개인적으로 유독 폐기물을 삭제했는지 확인할 수도 있습니다.
다른 활발한 연구 분야는 페어링과 신뢰 설정 없이도 동일한 목표를 달성하는 다른 방법을 찾는 것입니다. Eli Ben Sasson의 최근 프레젠테이션을 참조하세요(수학적으로 SNARKs만큼이나 복잡하다는 점을 기억하세요!).
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@VitalikButerin
