ZK 기술의 역사적 발전 흐름 정리
작성자:Lambda Class
번역: 백정, Faust, Nickqiao
영문 원본 게시일: 2024년 2월 17일
제로지식 증명(ZK Proofs)은 강력한 암호학적 원시 기능으로, 한 당사자(증명자)가 특정 진술이 참임을 다른 당사자(검증자)에게 믿게 하면서도 어떠한 비공개 정보도 노출하지 않도록 해줍니다. 최근 들어 ZK는 검증 가능한 비밀 계산, 컴퓨터 프로그램에 대한 유효성 증명 및 블록체인 분야에서 널리 주목받고 있으며, 세계 발전에 긍정적인 영향을 미치고 있습니다.
ZK는 신기술이지만 그 기본 개념과 아이디어는 1980년대로 거슬러 올라갑니다. 비트코인과 이더리움 같은 블록체인과 결합된 이후 ZK 기술의 발전 속도는 가파르게 증가하였으며, SNARK와 STARK를 통해 블록체인의 확장성을 극대화할 수 있게 되었기 때문에 ZK는 블록체인 분야에서 각광받고 있습니다.
Starkware 창립자 Eli Ben-Sasson이 말했듯이, 최근 우리는 암호학적 증명 시스템의 '캄브리아기 폭발'을 목격했습니다.각 증명 시스템은 고유한 장점과 단점을 가지며 설계상 여러 트레이드오프가 존재합니다. 하드웨어의 발전, 더 나은 알고리즘, 새로운 논증 방식 및 주변 도구들은 ZK 시스템의 성능 향상과 새로운 시스템의 탄생을 촉진하고 있습니다. 많은 증명 시스템들이 이미 실제 적용되고 있으며, ZK의 경계는 계속해서 확장되고 있습니다.
이는 다음과 같은 질문을 제기하게 합니다:모든 응용 분야에 적합한 보편적인 ZK 증명 시스템이 존재할 수 있을까? 이에 대해 우리는 가능성은 낮다고 생각하며, 그 이유는 세 가지입니다:
-
응용 프로그램의 다양성;
-
다양한 종류의 제약 조건(메모리, 검증 시간, 증명 생성 시간 등);
-
회복탄력성(Robustness) 요구사항(만약 어떤 증명 시스템이 해킹당하더라도 다른 시스템으로 전환해 대비할 수 있어야 함).
위와 같은 이유들로 인해 ZK 증명 시스템은 다양성이 필요합니다.하지만 증명 시스템의 종류가 많다 하더라도 중요한 공통점 하나는 존재합니다. 즉, ZK 증명은 빠르게 검증될 수 있다는 점이며, 새로운 증명 시스템에도 쉽게 적응할 수 있는 검증 계층을 갖추고 있어 기반 플랫폼(예: 이더리움)의 문제들을 해결하는 데 유리합니다.
ZK 분야에서는 자주 zk-SNARK이 언급됩니다. 이는 복잡한 수학적 도구(쌍선형 연산 및 산술 회로 등)를 활용하여 효율적인 제로지식 증명을 구현하는 방식 중 하나입니다. zk-SNARK의 특징은 증명 과정이 간결하고 비대화적이며, 증명자와 검증자 사이의 통신이 단 한 번만 이루어진다는 것입니다. 또한,zk-SNARK의 증명 크기는 매우 작고 검증 효율이 뛰어나 제한된 자원 환경에서도 잘 동작합니다.
반면, zk-STARK는 zk-SNARK의 일부 한계를 극복하기 위해 개발된 또 다른 형태입니다. zk-STARK는 신뢰할 수 있는 설정(trusted setup)을 필요로 하지 않으며, 다항식 커밋, 유한 체 연산, 해시 충돌 등의 더 투명한 수학적 구성 방식을 사용하여 증명을 생성하고 검증합니다.zk-STARK는 zk-SNARK보다 확장성이 뛰어나고 대규모 계산에 적합하며 증명 생성 속도가 빠릅니다. 하지만 증명 자체의 크기가 일반적으로 큽니다.
즉, zk-SNARK와 zk-STARK 모두 제로지식 증명에서 흔히 사용되는 방식이지만 투명성, 확장성, 증명 크기 등의 면에서 서로 다릅니다.
전반적으로,ZK 증명 시스템은 일반적으로 PIOP(다항식 대화형 오라클)와 PCS(다항식 커밋 방식) 두 부분으로 구성됩니다. 대표적인 PIOP 방식에는 PLONKish, GKR 등이 있고, PCS 방식으로는 FRI, KZG, IPA 등이 있습니다. 예를 들어, Zcash 버전의 Halo2는 Plonkish+IPA 방식을 사용하며, 사실상 zk-STARK는 FRI 기반의 특수한 형태의 zk-SNARK로 볼 수 있습니다.
좀 더 상세히 설명하면, 다양한 증명 시스템은 서로 다른 다항식 커밋 방식(PCS), 산술화 방식, 대화형 오라클 증명(IOP), 혹은 확률적 검사 가능 증명(PCP)을 사용합니다.
또한,다른 ZK 증명 시스템은 일반적으로 다음 지표들에서 차이를 보입니다:
-
암호학적 가정: 충돌 저항성 해시 함수, 타원 곡선 위의 이산 로그 문제, 지식의 지수 문제
-
투명 설정 vs 신뢰할 수 있는 설정
-
증명 생성 시간: 선형 vs 초선형
-
검증 시간: 상수 시간, 로그 시간, 아름다운 선형(sub-linear), 선형
-
증명 크기
-
재귀성의 용이성
-
산술화 방식
-
단일 변수 vs 다중 변수 다항식
다음 내용에서는 ZK 기술의 기원을 간략히 살펴보고, 핵심 구성 요소를 탐색하며 다양한 ZK 증명 시스템의 부상과 쇠퇴 과정을 개관하겠습니다. 본 글은 증명 시스템 자체의 심층 분석보다는 해당 분야에 큰 영향을 미친 인물들에 초점을 맞춥니다. 어쩌면 모든 산업의 발전은 선구자들의 위대한 아이디어와 실천을 통해서만 가능하기 때문입니다.
zk-SNARK의 역사적 발전
기원: 1980~1990년대
앞서 언급했듯이 제로지식 증명은 새로운 개념이 아니며, 정의, 기초, 중요한 정리 및 관련 주요 프로토콜은 이미 1980년대 중반에 등장하였습니다.최초로 Goldwasser, Micali(Algorand 창립자), Rackoff의 논문 《The Knowledge Complexity of Interactive Proof Systems》에서 소개되었습니다.
또한,현재 우리가 ZK-SNARK 기술을 구성하는 데 사용하는 핵심 아이디어와 프로토콜은 1990년대에 이미 제안되었습니다. 예를 들어 Sumcheck 프로토콜은 다변수 다항식의 값을 합산하는 진술을 타원 곡선 상의 임의 선택된 점에서 단일 평가로 줄여내는 방식으로, ZK 기술의 중요한 기반이 되었습니다.
따라서 ZK 사상의 발아는 비트코인 출현보다 훨씬 이전부터 시작되었지만, 당시에는 적절한 사용 사례가 부족했고, ZK 증명 시스템에 필요한 막강한 컴퓨팅 파워를 제공할 수 없었습니다. 1990년대 인터넷과 하드웨어 기술은 아직 발달하지 않았기 때문입니다.
GKR 프로토콜 (2007)
GKR(Goldwasser-Kalai-Rothblum)는 대화형 프로토콜로, 증명자의 실행 시간은 회로 내 논리 게이트 수에 비례하고, 검증자의 시간은 회로 크기에 비해 아름다운 선형(sub-linear) 관계를 가집니다. GKR 프로토콜에서는 증명자와 검증자가 유한 체 상의 이중 입력 산술 회로의 결과에 동의해야 하며, 회로 깊이는 d이고, d번째 층이 입력층, 0번째 층이 출력층입니다. 프로토콜은 회로 출력에 관한 진술로 시작하여 재귀적으로 상위 계층의 진술로 줄여갑니다. 결국 출력에 관한 진술을 회로 입력 값에 관한 진술로 변환할 수 있으며, 이를 검증하기 쉽습니다.즉, GKR 프로토콜은 앞서 언급한 Sumcheck 프로토콜을 기반으로 크게 단순화한 것입니다.
KZG 다항식 커밋 방식 (2010)
2010년, 독일 MPI-SWS 소속의 Kate, 캐나다 암호학 회사 Certicom Research의 Zaverucha, 그리고 워털루 대학교의 Goldberg라는 세 명의 ZK 전문가가 공동으로 《Constant-Size Commitments to Polynomials and Their Applications》라는 논문을 발표했습니다. 이 논문은쌍선형 연산을 사용하는 다항식 커밋 방식인 KZG를 제안했습니다.
이 커밋은 단일 군 원소로 구성되며, 제출자는 다항식의 올바른 값을 효율적으로 공개할 수 있고, 배치 처리 기술을 통해 여러 다항식의 값을 동시에 공개할 수 있습니다.KZG 커밋은 halo2(이더리움 PSE 팀이 사용)와 같은 유명한 ZK 증명 시스템의 핵심 구성 요소 중 하나가 되었으며, 특히 이더리움 EIP-4844에서 중심 역할을 했습니다. 배치 처리 기술에 대한 직관적인 이해를 위해서는 Mina-Ethereum 브릿지 관련 글을 참고하시기 바랍니다.
참고자료: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
타원 곡선 기반 실용적 ZK-SNARK 시스템 (2013)
실용적인 ZK-SNARK 구조는 2013년 처음 등장하였으며, 사전 처리 과정을 통해 증명 키와 검증 키를 생성해야 하고, 프로그램 또는 회로에 특화되어 있었으며 일반화되지 않았습니다. 이러한 키들의 크기는 매우 클 수 있으며, 비밀 매개변수 자체에 따라 달라질 수 있습니다. 만약 이 비밀성이 유출되면 공격자는 위조된 증명을 만들 수 있습니다.이러한 실용적인 ZK-SNARK 시스템에서는 코드를 증명 가능한 형식으로 변환하기 위해 코드를 일련의 수학적 다항식 제약으로 컴파일해야 합니다.
처음에는 이러한 과정이 수동으로 수행되어야 했으며, 시간이 많이 걸리고 오류가 발생하기 쉬웠습니다. 이후 이 분야의 기술 발전은 주로 다음 핵심 문제 해결에 집중되었습니다:
-
더 효율적인 증명 제공
-
사전 처리 횟수 감소
-
회로 특화가 아닌 일반화된 설정 구현
-
신뢰할 수 있는 설정 피하기
-
다항식 제약을 수동으로 작성하는 대신 고급 언어로 회로를 설명하는 방법 개발
Pinocchio 프로토콜 (2013)
Pinocchio 프로토콜은 최초의 실용적인 zk-SNARK 시스템입니다. 이는 2차 산술 프로그램(QAP)을 기반으로 하며, 초기 증명 크기는 288바이트였습니다. Pinocchio의 도구 체인은 C 언어를 산술 회로로 컴파일하는 컴파일러를 제공하며, 이는 다시 QAP로 변환될 수 있습니다. Pinocchio 프로토콜은 검증자가 키를 생성하도록 요구하며, 이 키들은 일반적이지 않고 회로에 특화되어 있습니다. 이 증명 시스템의 증명 생성 및 키 설정의 점근적 시간 복잡도는 계산 규모에 비례하며, 검증 시간은 공개 입력 및 출력의 크기에 비례합니다.
Groth16 (2016)
Groth는 R1CS(일계 제약 시스템) 처리에서 더 높은 성능을 가지는 새로운 ZK 증명 알고리즘을 도입했습니다. R1CS는 zk-SNARK에서 사용되는 다항식 제약 형식 중 하나입니다.Groth의 증명은 데이터 규모가 가장 작으며(단 세 개의 군 원소 포함), 검증 속도도 매우 빠릅니다. 세 번의 쌍선형 연산만 수행하면 되며, 구조화된 참조 문자열을 위한 사전 처리 단계도 포함됩니다. 그러나 Groth의 주요 단점은 각각의 증명 대상 프로그램마다 별도의 신뢰할 수 있는 설정이 필요하다는 점이며, 이는 실제 적용에서 상당히 불편합니다.
이후 Groth16은 ZCash에 채택되었으며, ZCash는 유명한 개인정보 보호 블록체인 프로젝트로 Starkware 창립자 Eli도 참여했습니다.
Bulletproofs 및 IPA (2016)
앞서 언급한 KZG 다항식 커밋 방식의 주요 약점 중 하나는 신뢰할 수 있는 설정이 필요하다는 점입니다. Bootle 등은 Pedersen 커밋의 내적 관계를 만족하는 오픈을 검사하는 효율적인 제로지식 증명 시스템을 제안했습니다. 내적 증명은 선형 복잡도의 증명 시간을 가지며, 증명자와 검증자 간의 상호작용 횟수는 로그 차원이지만 검증 시간은 선형입니다. 또한 Bootle 등은 신뢰할 수 있는 설정이 필요 없는 다항식 커밋 방식도 개발했습니다. 이러한 아이디어는 이후 Halo2 및 Kimchi 등에서 채택되었습니다.
Sonic, Marlin 및 Plonk (2019)
Sonic, Plonk, Marlin은 Groth16 알고리즘에서 각 프로그램마다 신뢰할 수 있는 설정이 필요하다는 문제를 해결하고, 일반적이며 업데이트 가능한 구조화된 참조 문자열을 도입하여 단 한 번의 신뢰 설정만으로도 가능하게 했습니다. 여기서,Marlin은 R1CS 기반의 증명 시스템을 제공하며 Aleo의 핵심 기술이 되었습니다.
Plonk는 새로운 산술 방식(나중에 Plonkish라고 알려짐)과 복사 제약을 확인하기 위한 grand-product 기법을 도입했습니다. Plonkish는 특정 작업을 위한 전용 회로 게이트(이른바 '사용자 정의 게이트')를 도입할 수 있도록 허용합니다.Aztec, zkSync, Polygon zkEVM, Mina, 이더리움 PSE 팀, Scroll 등 많은 유명 블록체인 프로젝트들이 Plonk의 맞춤형 버전을 사용하고 있습니다.
Spartan (2019)
Spartan은 R1CS로 설명된 회로에 대해 IOP(Interactive Oracle Proof)를 제공하며, 다변수 다항식과 Sumcheck 프로토콜의 특성을 활용합니다. 적절한 다항식 커밋 방식을 사용함으로써 투명성을 갖춘 zk-SNARK 시스템을 구현하며, 증명 생성 시간 복잡도는 선형입니다.
Lookups (2020)
2020년 Gabizon과 Williamson은 plookup을 제안하며, grand-product를 이용해 어떤 값이 미리 계산된 참조 테이블에 포함되어 있음을 증명하고, 이를 Plonk 알고리즘에 어떻게 도입할 수 있는지를 보여주었습니다.
하지만 이러한 lookup argument들은 증명자가 완전한 참조 테이블을 구성하는 데 큰 비용이 든다는 공통된 문제를 가지고 있으며, 따라서 이전 연구들은 주로 증명 비용을 줄이는 데 집중했습니다.
이후 Haböck은 LogUp을 논문에서 소개하였으며, 이는 로그 도함수를 사용해 grand-product 검사를 역수의 합으로 변환합니다. LogUp은 Polygon zkEVM의 성능 향상에 중요했는데, 전체 참조 테이블을 여러 STARK 모듈로 분할해야 했기 때문입니다. 이러한 모듈들은 올바르게 연결되어야 하며, cross-table lookup은 이를 강제할 수 있습니다. 이후 LogUp-GKR은 GKR 프로토콜을 통해 LogUp의 성능을 더욱 향상시켰습니다.
Caulk은 증명 시간이 참조 테이블 크기에 대해 아름다운 선형(sub-linear) 관계를 갖는 최초의 방식입니다. 사전 처리 시간 복잡도는 O(NlogN), 저장 공간 복잡도는 O(N)이며, N은 참조 테이블 크기입니다. 이후 Baloo, flookup, cq, caulk+ 등의 다른 방식들도 등장했습니다. 또한 Lasso는 참조 테이블이 특정 구조를 가질 때 이를 커밋하지 않도록 하는 여러 개선안을 제시했습니다.
HyperPlonk (2022)
HyperPlonk은 논문 《HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates》에서 제안되었습니다. HyperPlonk은 Plonk의 아이디어를 기반으로 하며 다변수 다항식을 사용합니다. 제약 조건 검사를 위해 나눗셈을 사용하지 않고 Sumcheck 프로토콜에 의존합니다. 또한 고차 제약을 지원하면서도 증명 생성 시간에 영향을 주지 않습니다.
다변수 다항식을 사용함으로써 FFT(고속 푸리에 변환)가 필요 없으며, 증명 생성 시간은 회로 규모에 비례합니다. HyperPlonk은 작은 필드에 적합한 새로운 순열 IOP를 도입하고, Sumcheck 기반 프로토콜을 사용해 증명자의 작업량, 증명 크기, 검증 시간을 모두 줄였습니다.
충돌 저항성 해시 함수를 사용하는 ZK 증명 시스템
2013년 Pinocchio가 제안된 동시에, 가상 머신의 명령어 실행 결과가 올바름을 증명할 수 있는 회로/산술화 방안에 대한 연구도 진행되었습니다. 가상 머신을 위한 산술화 방안 개발은 특정 프로그램을 위한 전용 회로를 작성하는 것보다 더 복잡하거나 덜 효율적일 수 있지만 중요한 장점이 있습니다. 즉, 프로그램이 얼마나 복잡하든 간에 그 실행이 가상 머신 내에서 올바르게 이루어졌음을 증명하기만 하면 된다는 점입니다.
TinyRAM의 일부 아이디어는 이후 Cairo 가상 머신 설계에서 개선되었으며, 이후 zk-evm과 일반 zkvm 등이 등장했습니다. 증명 시스템에서 충돌 저항성 해시 함수를 사용하면 신뢰할 수 있는 설정이나 타원 곡선 연산이 필요 없지만, 그 대가로 증명 시간이 더 길어집니다.
TinyRAM (2013)
「SNARKs for C」에서는 PCP를 기반으로 C 언어로 작성된 프로그램의 실행 결과가 올바름을 증명하는 시스템을 개발했습니다. 이 프로그램은 TinyRAM이라는 단순화된 VM으로 컴파일됩니다. 이 VM은 바이트 단위로 주소 지정 가능한 랜덤 메모리를 가지며, 회로 크기는 계산 규모에 대해 준선형(quasi-linear)으로 증가하며, 반복문, 제어 흐름, 메모리 접근 등을 효율적으로 처리할 수 있습니다.
여기서,PCP는 Probabilistically Checkable Proof(확률적 검사 가능 증명)를 의미하며, 검증자는 증명의 일부를 무작위로 읽기만 해도 매우 높은 신뢰도로 증명의 유효성을 검사할 수 있습니다. 기존 증명 시스템에서 검증자가 전체 증명을 검사해야 하는 것과 달리, PCP는 제한된 무작위성만으로도 효율적인 검증이 가능합니다.
Ligero (2017)
Ligero는 O(√￣n) 크기의 증명을 제공하는 증명 시스템을 도입했습니다(n은 회로 크기). 다항식 계수를 행렬 형태로 배열합니다. Brakedown은 Ligero를 기반으로 구축되었으며, 분야 독립적(dimension-independent) 다항식 커밋 방식의 개념을 도입했습니다.
STARKs (2018)
STARKs(Scalable Transparent ARguments of Knowledge)는 Eli Ben-Sasson 등이 2018년에 제안했습니다. 이는 𝑂(log²𝑛) 증명 복잡도를 달성하며, 빠른 검증 속도를 가지며, 신뢰할 수 있는 설정이 필요 없고 양자 안전(post-quantum security)으로 추정됩니다. 이는 Starkware/Starknet과 Cairo 가상 머신에서 함께 사용되고 있습니다. 핵심 혁신으로는 대수적 중간 표현(AIR)과 빠른 리드-솔로몬 대화형 오라클 근접 증명(FRI) 프로토콜이 있습니다. 또한 STARKs는 Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync 등 많은 유명 블록체인 프로젝트에서도 사용되고 있습니다.
새로운 발전 방향
다양한 증명 시스템의 실제 적용은 서로 다른 접근 방식의 장점을 보여주며 ZK의 발전을 이끌고 있습니다. 예를 들어, Plonkish 산술화 방식은 사용자 정의 게이트와 lookup argument를 포함하는 간단한 방법을 제공하며, FRI는 PCS로서 뛰어난 성능을 보여 Plonky의 탄생을 가능하게 했습니다. 또한 AIR에서 grand-products를 사용한 검사는(사전 처리된 랜덤 AIR로 이어짐) 성능을 향상시키고 메모리 접근 매개변수를 단순화했습니다. 증명 생성 효율이 우수하고 점점 더 많은 ZK 친화적 해시 함수가 도입됨에 따라 zk-STARK는 점점 더 인기를 얻고 있습니다.
새로운 다항식 커밋 방식 (2023)
Spartan이나 HyperPlonk과 같이 다변수 다항식 기반의 고효율 SNARK가 등장함에 따라, 그러한 다항식에 적합한 새로운 커밋 방식에 대한 관심이 증가하고 있습니다. Binius, Zeromorph, Basefold는 모두 다중 선형 다항식을 위한 새로운 커밋 방식을 제안했습니다. Binius의 장점은 데이터 유형 표현에 추가 오버헤드가 없다는 점이며(다른 많은 증명 시스템은 단일 비트를 표현하기 위해 최소 32비트 필드 요소를 사용함), 이진 체 위에서 동작합니다. 이 커밋 방식은 brakedown을 기반으로 하며, 이는 분야 독립적 설계를 위해 고안되었습니다. Basefold는 Reed-Solomon 외의 경우에도 FRI를 일반화하여 분야 독립적 다항식 커밋 방식(PCS)을 실현했습니다.
분야 독립성(dimension independence)은 다항식 커밋 방식의 성질로, 커밋 과정이 특정 분야의 고유 속성에 의존하지 않는다는 것을 의미합니다. 즉, 유한 체, 타원 곡선, 정수환 등 어떤 대수 구조의 다항식에도 커밋할 수 있음을 나타냅니다.
맞춤형 제약 시스템 (2023)
CCS는 R1CS를 일반화하면서도 R1CS, Plonkish, AIR의 산술화를 추가 오버헤드 없이 포괄합니다. CCS를 Spartan IOP와 결합하면 SuperSpartan이 생성되며, 이는 고차원 제약을 지원하지만 증명자는 제약 차수에 비례하는 암호학적 비용을 부담하지 않습니다. 특히 SuperSpartan은 AIR에 대해 선형 시간 증명을 제공하는 SNARK입니다.
결론
본 글은 1980년대 중반 이후 ZK 기술의 발전을 개괄합니다. 컴퓨터 과학, 수학, 하드웨어의 발전과 더불어 블록체인의 도입은 새로운, 더 효율적인 ZK 증명 시스템의 탄생을 이끌었으며, 사회를 변화시킬 수 있는 다양한 응용 분야를 열어주었습니다.
연구자들과 엔지니어들은 증명 크기, 메모리 사용량, 투명성, 양자 저항성, 증명 시간, 검증 시간 등의 요소에 초점을 맞춰 ZK 시스템의 개선안을 제안해왔습니다. 오랫동안 ZK의 주류 구현 방식은 SNARK와 STARKs 두 가지로 나뉘었지만, 이 둘의 경계는 점점 모호해지고 있으며, 다양한 산술화 방식과 새로운 다항식 커밋 방식이 결합되고 있습니다.
새로운 ZK 증명 시스템은 계속해서 등장할 것이며, 성능은 계속해서 향상될 것입니다. 이러한 증명 시스템을 사용하는 응용 프로그램 입장에서는 최신 기술 발전을 따라가지 못하고 현재의 알고리즘에 머무른다면, 지금의 선두 위치도 일시적일 뿐입니다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@class_lambda
