STARK: 다항식 증명
ZK-SNARKS는 검증 가능한 컴퓨팅부터 프라이버시 보호가 필요한 암호화폐에 이르기까지 다양한 분야에 적용될 수 있는 일반적이고 간결한 제로지식 증명 기술로, 많은 사람들이 들어봤을 것이다. 그러나 아마도 당신은 아직 ZK-SNARK에 새로운 형제가 생겼다는 것을 모를지도 모른다. 바로 ZK-STARK이다. 여기서 T는 "transparent(투명한)"을 의미하며, ZK-STARK는 ZK-SNARK의 주요 단점 중 하나인 '신뢰할 수 있는 초기 설정(trusted setup)'에 의존한다는 문제를 해결한다. 또한 ZK-STARK는 타원 곡선, 쌍(pairings), 지수 지식 가정(the knowledge-of-exponent assumption)과 같은 복잡한 암호학적 가정을 피하고, 해시와 정보 이론에만 기반하여 훨씬 더 간단한 암호학적 가정을 사용한다. 즉 양자 컴퓨터를 사용하는 공격자에게조차 안전하다는 의미이다.
물론 이것은 대가를 치러야 한다. 증명 크기가 288바이트에서 수백 킬로바이트(kb)로 증가하게 되는 것이다. 어떤 경우에는 이러한 비용이 가치 있지 않을 수 있지만, 높은 수준의 신뢰 최소화가 요구되는 블록체인 응용 프로그램에서는 충분히 가치 있을 수 있다. 그리고 만약 타원 곡선 암호가 깨지거나 양자 컴퓨터가 실현된다면, 이 대가는 반드시 치를 만한 가치가 있을 것이다.
그렇다면 이 새로운 제로지식 증명 기술은 정확히 어떻게 작동하는가? 이를 설명하기 전에 먼저 간결하고 일반적인 제로지식 증명이 무엇을 하는지 다시 상기해보자. 지금 당신은 (공개된, public) 함수 f, (비공개인, private) 입력 x, 그리고 (공개된, public) 출력 y가 있다고 하자. 우리는 x의 내용을 드러내지 않고, f(x) = y가 되도록 하는 x가 존재함을 증명하고자 한다. (역주: 마치 금고가 있고, 비밀번호를 알려주지 않으면서 그 비밀번호를 알고 있다는 사실을 입증하는 것과 같다.) 게다가 이 증명은 간결해야 하며, f 자체를 계산하는 것보다 훨씬 빠르게 검증될 수 있어야 한다.
몇 가지 사례를 살펴보자.
-
f는 일반 컴퓨터에서 2주가 걸리는 계산이지만, 데이터센터에서는 2시간만에 완료할 수 있다. 당신은 이 계산 작업(f 코드 실행)을 데이터센터에 보내고, 데이터센터는 계산을 수행한 후 결과 y와 증명을 반환한다. 이후 당신은 몇 밀리초 안에 검증을 완료하고, y가 진짜 답임을 확신할 수 있다.
-
암호화된 거래가 있으며, 형식은 "X1은 나의 이전 잔액, X2는 너의 이전 잔액, X3은 나의 새 잔액, X4는 너의 새 잔액"이라고 하자. 이 거래가 유효함을 증명하고 싶다. 구체적으로 말하면, 이전 및 새 잔액이 모두 음수가 아니며, 내 잔액 감소량이 너의 잔액 증가량과 정확히 일치함을 증명해야 한다. 이때 x는 한 쌍의 암호화 키일 수 있고, f는 내장된 공개 입력 거래를 포함하는 함수이며, 키를 입력받아 거래를 복호화하고 유효성을 검사한 후 성공 시 1, 실패 시 0을 반환한다. 그러면 y는 반드시 1이어야 한다.
-
이더리움과 같은 블록체인이 있으며, 최신 블록을 다운로드했다고 하자. 이 블록이 유효하며 체인의 최신 블록임을 증명하고 싶다. 또한 이 체인의 모든 블록이 유효함을 증명하고 싶다. 이를 위해 알려진 풀 노드에 이러한 증명을 제공해 달라고 요청한다. x는 전체(또는 일부) 블록체인이고, f는 각 블록을 처리하여 유효성을 검증하고 직전 블록의 해시를 출력하는 함수이며, y는 방금 다운로드한 블록의 해시값이다.
그렇다면 이러한 모든 사례들의 어려움은 어디에 있는가? 사실 다음과 같다.
제로지식(즉, 개인정보 보호)를 보장하는 것은 (상대적으로!) 비교적 쉬운 편이다. 기존의 전통적인 제로지식 증명 프로토콜을 사용하여, 어떤 계산을 삼색 그래프 문제와 유사한 형태로 변환하고, 원래 문제의 해법과 관련된 그래프 색칠 문제를 만들어 낸 후, 실제 색칠 방법을 드러내지 않은 채 유효한 색칠이 가능함을 증명하는 여러 방법이 존재한다. Matthew Green이 2014년에 쓴 훌륭한 글에서 이러한 세부 사항을 잘 설명하고 있다.
훨씬 더 어려운 것은간결성이다. 직관적으로 말해, 계산과 관련된 내용을 간결하게 증명하는 것은 매우 어렵다. 계산은 극도로 민감하기 때문이다. 아주 길고 복잡한 계산이 있다고 가정하자. 계산 도중 어느 한 비트(bit)라도 0에서 1로 바꿀 수 있다면, 많은 경우 단지 한 비트만 바꿔도 전혀 다른 결과를 낳게 된다. 따라서 무작위로 계산 경로를 샘플링하여 올바름을 확인하는 등의 방법으로는 쉽게 '악랄한 한 비트(one evil bit)'를 놓치게 될 수 있다. 그러나 정교한 수학적 방법을 통해 이것이 실제로 가능함을 증명할 수 있다.
일반적으로 이 프로토콜이 어떻게 작동하는지에 대한 고차원적인 직관은 오류 정정 코드(error-correcting code)에서 사용하는 수학과 유사하다. 이는 데이터에 내구성을 부여하는 데 자주 사용된다. 예를 들어, 어떤 데이터가 있고 이를 직선 위의 점들로 인코딩한다고 하자. 이 선 위에서 네 개의 점을 선택할 수 있다. 이 네 점 중 임의의 두 점만으로도 직선을 재구성할 수 있으므로, 나머지 두 점도 알 수 있게 된다. 더욱이 데이터를 아주 미세하게 변경하더라도 최소한 세 개 이상의 점은 반드시 달라진다. 동일한 원리를 확장하여, 데이터를 1,000,000차 다항식으로 인코딩하고, 이 다항식 위에 2,000,000개의 점을 선택할 수 있다. 그러면 임의의 1,000,001개 점만으로도 원래 데이터를 복원할 수 있으며, 원래 데이터의 어떤 작은 변화라도 최소한 1,000,000개의 점을 변경하게 된다. 여기서 설명하는 알고리즘은 이러한 방식을 활용하여 다항식을 통해 오류를 크게 증폭(error amplification)한다.
간단한 예제
어떤 다항식 P가 있어서, x가 1에서 100만 사이일 때 P(x)가 정수이며 0 ≤ P(x) ≤ 9임을 증명하고 싶다고 하자. 이것은 매우 흔한 '범위 검사(range check)'의 간단한 예이다. 예를 들어, 거래가 실행된 후에도 여전히 계좌 잔고가 양수인지 확인하는 검증 절차로 생각할 수 있다. 만약 1 ≤ P(x) ≤ 9라면, 이는 스도쿠 퍼즐의 정답을 검증하는 과정의 일부일 수도 있다.
이 문제를 '전통적'으로 해결하는 방법은 100만 개의 점을 하나씩 순회하며 값을 검증하는 것이다. 하지만 우리가 궁금한 것은, 100만 단계보다 적은 시간 안에 검증 가능한 증명을 구성할 수 있느냐는 것이다. 단순히 P를 무작위로 샘플링해서 검증하는 것은 불가능하다. 악의적인 증명자가 999,999개의 위치에서는 조건을 만족하지만 마지막 하나에서는 만족하지 않는 P를 만들 수 있기 때문에, 소수의 샘플만으로는 항상 그 잘못된 값을 놓치게 된다. 그렇다면 우리는 무엇을 할 수 있을까?
이 문제를 수학적으로 변환해보자. C(x)를제약 조건 검사 다항식(constraint checking polynomial)이라고 하자. 0 ≤ x ≤ 9일 때 C(x) = 0이고, 그렇지 않으면 0이 아니다. C(x)를 구성하는 간단한 방법은 x * (x-1) * (x-2) * ... * (x-9)이다.
이제 문제는 1에서 1,000,000까지의 모든 x에 대해 C(P(x)) = 0임을 증명하는 것으로 바뀐다. 이제 Z(x) = (x-1) * (x-2) * ... * (x-1000000)이라고 하자. 이미 알려진 수학적 사실에 따르면, 1에서 1,000,000까지의 모든 x에서 0이 되는 다항식은 반드시 Z(x)의 배수이다. 따라서 문제는 다시 다음과 같이 변환된다. 모든 x에 대해 C(P(x)) = Z(x) * D(x)를 만족하는 P와 D를 알고 있음을 증명하라. (참고로, 적절한 C(P(x))를 알고 있다면 Z(x)로 나누어 D(x)를 계산하는 것은 그리 어렵지 않다. 다항식 장제법(polynomial long division)이나 더 빠르고 실용적인 FFT 기반 알고리즘을 사용하면 된다.) 이제 원래 명제를 수학적으로 더 명확하고 증명하기 쉬운 형태로 전환한 것이다.
그렇다면 어떻게 증명할 수 있을까? 이를 증명자(prover)와 검증자(verifier) 사이의 3단계 교환 프로세스로 생각할 수 있다.
- 증명자가 일부 정보를 전송한다
- 검증자가 일부 요청을 전송한다
- 증명자가 추가 정보를 전송한다
먼저 증명자는 1에서 10억(맞다, 10억) 사이의 모든 x에 대해 P(x)와 D(x)의 값을 제출한다. 여기에는 100만 개의 점(0 ≤ P(x) ≤ 9를 만족)과 나머지 9억 9900만 개의 점(상태가 불분명할 수 있음)이 포함된다.
검증자는 모든 점에서 Z(x)의 값을 이미 알고 있다고 가정하자. 이 방식에서 Z(x)는 공개 검증 키와 같으며, 모두가 사전에 알고 있어야 한다. (클라이언트는 Z(x) 전체를 저장할 공간이 없으므로, 단순히 Z(x)의 Merkle 루트만 저장하고, 검증자가 조회를 요청하는 각 Z(x) 값에 대한 분기를 증명자로부터 동시에 제공받을 수 있도록 한다. 또는 특정 x에 대해 Z(x)를 매우 쉽게 계산할 수 있는 방법이 있을 수도 있다.) Merkle 루트를 수신한 후, 검증자는 1에서 10억 사이에서 무작위로 16개의 x 값을 선택하고, 해당 위치에서의 P(x)와 D(x)에 대한 Merkle 분기를 요청한다. 증명자가 값을 제공하면, 검증자는 다음을 확인한다.
-
분기가 이전에 제공된 Merkle 루트와 일치하는지
-
모든 16개 경우에 대해 C(P(x))가 Z(x) * D(x)와 같은지
우리는 이 증명이완전성(completeness)을 개선했다는 것을 알고 있다. 즉, 적절한 P(x)를 알고 있고, D(x)를 올바르게 계산하여 증명을 구성하면, 16개의 검사를 모두 통과할 수 있다. 하지만신뢰성(soundness)은 어떨까?
즉, 악의적인 증명자가 잘못된 P(x)를 제출했을 때, 적어도 얼마나 높은 확률로 그것이 발견될까? 다음과 같이 분석할 수 있다. C(P(x))는 1,000,000차 다항식이므로, 차수는 최대 10,000,000이다.
일반적으로 서로 다른 두 개의 N차 다항식은 최대 N개의 점에서만 일치할 수 있다. 따라서 어떤 x에 대해, 1,000,000차 다항식과 Z(x) * D(x)와 항상 일치하는 임의의 다항식이 다르다면, 최소한 9억 9천만 개의 점에서 달라져야 한다. 따라서 단 한 번의 검사만으로도 잘못된 p(x)가 발견될 확률은 99%이며, 16번의 검사를 거치면 발견될 확률은 1 - 10^-32로 높아진다. 즉, 이 방식은 해시 충돌을 찾는 것만큼이나 속이기 어렵다.
우리가 방금 분석한 것은 무엇인가? 우리는 다항식을 이용해 '나쁜 해법'에 존재하는 오류를 증폭시켰다. 즉 원래 100만 번의 직접 검사가 필요했던 문제를, 단 한 번의 검사로도 오류를 99% 식별할 수 있는 검증 프로토콜로 전환한 것이다.
이러한 3단계 메커니즘을 비대칭 증명(non-interactive proof)으로 전환할 수 있다. Fiat-Shamir 휴리스틱(Fiat-Shamir heuristic)을 활용하면, 증명자가 이를 방송하고 누구나 검증할 수 있게 된다. 증명자는 먼저 P(x)와 D(x) 값들의 Merkle 트리를 구성하고, 그 루트 해시를 계산한다. 이 루트 자체가 엔트로피의 원천이 되어, 증명자가 어떤 분기를 제공해야 할지 결정한다. 이후 증명자는 Merkle 트리 루트와 분기를 함께 증명으로 방송한다. 모든 계산은 증명자 측에서 이루어진다. 데이터로부터 Merkle 트리 루트를 계산하고, 이를 사용해 감사를 위한 분기를 선택함으로써, 상호작용형 검증자의 필요성을 효과적으로 대체한다.
유효한 P(x)를 모르는 악의적인 증명자가 할 수 있는 유일한 일은 Merkle 트리 루트 분기를 계속 생성하면서 운 좋게 통과할 수 있는 증명을 찾는 것이다. 그러나 신뢰성이 1 - 10^-32(즉, 주어진 잘못된 증명이 검사를 통과할 확률은 최대 10^-32)이므로, 이를 찾는 데 수십억 년이 걸릴 수 있다.
더 깊이 탐구하기
이 기술의 강력함을 설명하기 위해, 조금 특이한 일을 해보자. 즉, 당신이 백만 번째 피보나치 수를 알고 있다는 것을 증명하는 것이다. 이를 위해 우리는 계산 테이프를 나타내는 다항식을 알고 있음을 증명할 것이다. 여기서 P(x)는 x번째 피보나치 수를 나타낸다. 이제 제약 조건 검사 다항식은 3개의 x좌표를 아우른다. C(x1, x2, x3) = x3 - x2 - x1. (모든 x에 대해, P(x)가 피보나치 수열을 나타내면 C(P(x), P(x+1), P(x+2)) = 0이 성립한다.)
-피보나치-
변환된 문제는 C(P(x), P(x+1), P(x+2)) = Z(x) * D(x)가 되도록 P와 D를 알고 있음을 검증하는 것이다. 16개의 각 감사 케이스마다 증명자는 P(x), P(x+1), P(x+2), D(x)에 대한 Merkle 분기를 제공해야 한다. 또한 증명자는 P(0) = P(1) = 1임을 보여주기 위해 추가로 Merkle 분기를 제공해야 한다. 그 외의 절차는 동일하다.
실제로 이를 구현하려면 두 가지 문제를 해결해야 한다. 첫째, 일반 숫자를 사용한다면 이 방식은 효율적이지 않다. 숫자 자체가 너무 커질 수 있기 때문이다. 예를 들어 백만 번째 피보나치 수는 208,988자리이다. 실제로 간결성을 달성하려면 일반 숫자가 아닌 유한체(finite field)에서 다항식을 계산해야 한다. 유한체란 a*(b+c)=(a*b)+(a*c), (a²-b²)=(a-b)*(a+b)와 같은 기본적인 수학 법칙을 따르면서도, 각 숫자가 일정한 크기의 공간만 차지하도록 보장하는 수 체계이다. 백만 번째 피보나치 수를 증명하려면 이 유한체 기반의 수학 위에서 큰 수 연산을 구현하는 더 복잡한 설계가 필요하다.
가장 간단하고 가능성 있는 유한체는 모듈러 산술(modular arithmetic)이다. 즉, 어떤 소수 N에 대해 모든 a + b를 a + b mod N로 대체하는 것이다. 뺄셈과 곱셈에도 동일한 연산을 적용하고, 나눗셈의 경우 모듈러 역수(modular inverses)를 사용한다. (예: n=7이라면, 3+4=0, 2+6=1, 3*4=5, 4/2=2, 5/2=6). 이런 수 체계에 대해서는 여기서 (페이지 내에서 "prime field" 검색) 내가 소개한 소수체(prime field)에 대한 글을 참고하거나, 모듈러 산술에 관한 위키백과("finite fields", "prime fields" 검색)에서 더 자세히 알아볼 수 있다. 복잡해 보이고 추상대수학과 관련되어 있지만, 깊이 파고들 필요는 없다.
둘째, 앞서 언급한 신뢰성 증명 개요에서 나는 한 가지 공격을 간과했다. 공격자가 100만 차수의 P(x)와 900만 차수의 D(x) 대신, 저차 다항식에서 유래하지 않은 다른 값을 제출하는 경우 말이다. 이 경우 잘못된 C(P(x))는 모든 유효한 C(P(x))와 최소 9억 9천만 개의 점에서 달라져야 하므로, 더 많은 공격이 가능할 수 있다. 예를 들어, 공격자는 각 x에 대해 임의의 값 p를 생성하고 d = C(p)/Z(x)를 계산한 후, 이를 P(x)와 D(x) 대신 제출할 수 있다. 이 값들은 어떤 저차 다항식에서도 유래하지 않았지만,테스트는 통과할 수 있다.
사실 이 가능성은 사용되는 도구가 매우 복잡할 수 있지만 효과적으로 방어할 수 있으며, 이를 통해 STARK의 수학적 혁신이 실제로 완성된다. 그러나 이 해결책에도 한계가 있다. 즉, 100만 차 다항식과 크게 다른 데이터(예: 모든 값의 20%를 변경해야 저차 다항식이 되는 경우)는 배제할 수 있지만, 단지 한두 좌표만 다른 다항식 데이터는 배제할 수 없다. 따라서 이러한 도구는근접성 증명(proof of proximity)— 즉 P와 D의 대부분의 점이 동일한 다항식과 관련되어 있음을 — 제공한다.
따라서 두 가지 '예외(catches)'가 있지만, 여전히 증명을 구성하는 데 충분하다. 첫째, 검증자는 자신의 제한으로 인해 발생할 수 있는 오류를 고려하여 더 많은 검사를 수행해야 한다. 둘째, '경계 제약 조건 검사(boundary constraint checking)'를 수행할 경우(예: 위의 피보나치 예제에서 P(0)=P(1)=1임을 증명), 근접성 증명을 확장하여 대부분의 점들이 동일한 다항식 위에 있을 뿐 아니라, 특정 두 점(또는 검사하고자 하는 임의의 점들)도 그 다항식 위에 있음을 증명해야 한다.
이 시리즈의 다음 부분에서는 이 근접성 검사 문제의 해결책을 계속 다룰 것이다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@VitalikButerin
