지식 증명이 오랜 기간 동안 지속되면서도 끊임없이 혁신이 나타나는 이유는 무엇일까?

작성자: LambdaClass

번역: mutourend; Yiping, IOSG Ventures

1. 서론

제로지식, 간결하고 비대화형의 지식 증명(zk-SNARKs)은 증명자가 어떤 진술의 정확성을 검증자에게 납득시킬 수 있게 해주는 강력한 암호학적 원시(primitive)이며, 이 과정에서 진술 자체 외에는 아무 정보도 노출하지 않는다. zk-SNARKs는 검증 가능한 프라이빗 컴퓨팅, 컴퓨터 프로그램 실행의 정확성 증명 및 블록체인 확장성 분야에서의 응용 가능성 덕분에 널리 주목받고 있다. 본문에서 설명하듯이 우리는 zk-SNARKs가 세계를 형성하는 데 중대한 영향을 미칠 것이라 믿는다. zk-SNARKs는 다양한 다항식 커밋먼트 방식, 산술화 방식, 대화형 오라클 증명 또는 확률적 검증 가능 증명 등을 사용하는 여러 유형의 증명 시스템을 포함한다. 그러나 이러한 기본 아이디어와 개념들은 1980년대 중반으로 거슬러 올라간다.

비트코인과 이더리움 출시 이후 zk-SNARKs의 발전은 크게 가속화되었으며, 이는 제로지식 증명(일반적으로 특정 용례에서는 유효성 증명이라고 함)을 이용한 확장성이 가능하기 때문이다. zk-SNARKs는 블록체인 확장성에서 핵심적인 역할을 한다. Ben-Sasson이 언급했듯이, 최근 몇 년간 암호 증명(cryptographic proofs)의 캄브리아기 폭발을 목격했다. 각각의 증명 시스템은 장단점을 가지며, 특정한 트레이드오프를 염두에 두고 설계된다. 하드웨어, 알고리즘, 새로운 증명 기법 및 도구들의 발전은 성능을 지속적으로 향상시키며 새로운 시스템의 탄생을 촉진한다. 많은 시스템들이 이미 실제 적용되고 있으며, 우리는 계속해서 한계를 돌파하고 있다. 모든 애플리케이션에 적합한 범용 증명 시스템이 등장할까, 아니면 다양한 요구 사항에 맞는 여러 시스템이 공존하게 될까? 우리는 하나의 증명 시스템이 다른 모든 시스템을 지배할 가능성은 거의 없다고 생각한다. 그 이유는 다음과 같다.

1) 애플리케이션의 다양성.

2) 다양한 제약 조건들 (메모리, 검증 시간, 증명 생성 시간 등).

3) 견고성(Robustness)에 대한 필요성 (만약 한 증명 시스템이 파손되면, 다른 증명 시스템이 대안이 된다).

증명 시스템들이 상당히 변화해왔음에도 불구하고, 모두 중요한 특성 하나를 제공한다: 증명은 신속하게 검증될 수 있다는 점이다. 증명을 검증하고 새로운 증명 시스템에 쉽게 적응할 수 있는 레이어(layer)를 갖추는 것은, 이더리움과 같은 베이스 레이어 변경과 관련된 어려움을 해결한다. 본문은 SNARKs의 다양한 특징들을 개관할 것이다.

1) 암호학적 가정: 충돌 저항성 해시 함수, 타원 곡선 위의 이산 로그 문제, exponent 지식(knowledge of exponent).

2) 투명성 vs 신뢰 설정(trusted setup).

3) 증명 생성 시간: 선형 vs 초선형.

4) 검증자 시간: 상수 시간, 로그 시간, 아예 선형(sub-linear), 선형.

5) 증명 크기(proof size).

6) 재귀성(easy recursion) 용이성.

7) 산술화 방식(arithmeticization scheme).

8) 단일 변수 다항식 vs 다변수 다항식.

본문은 SNARKs의 기원, 일부 기본 구성 요소 및 다양한 증명 시스템의 등장(및 쇠퇴)에 대해 살펴볼 것이다. 본문은 증명 시스템에 대한 포괄적인 분석을 목표로 하지 않는다. 오히려 우리에게 영향을 준 시스템들에 초점을 맞출 것이다. 물론 이러한 발전들은 해당 분야의 선구자들이 이루어낸 위대한 작업과 아이디어 없이는 불가능했을 것이다.

2. 기초 지식

제로지식 증명은 새롭지 않다. 정의, 기초, 중요한 정리, 심지어 중요한 프로토콜들조차도 1980년대 중반부터 정립되었다. 현대적 SNARKs 구축에 사용되는 핵심 아이디어들과 프로토콜들은 1990년대에 제안되었다(sumcheck 프로토콜), 심지어 비트코인 등장 이전(2007년 GKR)에도 있었다. 당시 주요 문제점은 강력한 실용 사례의 부족(1990년대 인터넷은 아직 발달되지 않았다)과 필요한 계산 능력이었다.

1) 제로지식 증명: 기원 (1985/1989).

제로지식 증명 분야는 Goldwasser, Micali 및 Rackoff의 논문 <The knowledge complexity of interactive proof systems>가 학계 문헌에 등장하면서 시작되었다. 기원에 대한 논의는 ZKP MOOC Lecture 1: Introduction and History of ZKP (2023년 1월 영상)을 참고하면 된다. 이 논문은 완전성(completeness), 건전성(soundness), 제로지식성(zero-knowledge)의 개념을 도입하였으며, quadratic residuosity와 quadratic non-residuosity에 대한 구성 방법을 제공했다.

2) Sumcheck 프로토콜 (1992).

sumcheck 프로토콜은 Lund, Fortnow, Karloff 및 Nisan이 1992년 <Algebraic Methods for Interactive Proof Systems> 논문에서 제안하였다. 이는 간결한 대화형 증명의 가장 중요한 구성 요소 중 하나이다. 이를 통해 다변수 다항식의 evaluate 합산 요구사항을 임의 선택된 점에서의 단일 evaluation으로 줄일 수 있다.

3) Goldwasser-Kalai-Rothblum (GKR) (2007).

GKR 프로토콜(<Delegating Computation: interactive Proofs for Muggles> 참조)은 증명자가 회로의 게이트 수에 따라 선형 시간에 동작하고, 검증자는 회로 크기에 따라 아예 선형 시간에 동작하는 대화형 프로토콜이다. 프로토콜에서 증명자와 검증자는 깊이 d인 유한 체 위에서 fan-in-two 연산 회로에 대해 합의하며, 여기서 layer d가 입력 레이어(input layer), layer 0이 출력 레이어(output layer)에 해당한다. 프로토콜은 회로 출력에 관한 진술로 시작하여, 이를 바로 앞 레이어 값들에 대한 진술로 단순화한다. 재귀적으로 이를 반복하면 회로 입력에 대한 진술로 변환되며, 이는 쉽게 검사할 수 있다. 이러한 단계 축소(reductions)는 sumcheck 프로토콜을 통해 수행된다.

4) KZG 다항식 커밋먼트 방식 (2010).

Kate, Zaverucha 및 Goldberg는 2010년 <Constant-Size Commitments to Polynomials and Their Applications>에서 쌍선형(bilinear) 매칭 그룹을 사용하는 다항식 커밋먼트 방식을 소개했다. 커밋은 단일 그룹 요소로 구성되며, 커미터는 다항식의 올바른 evaluation 값에 대해 효율적으로 오픈(opening)할 수 있다. 또한 배치(batching) 기술 덕분에 여러 evaluation 값을 동시에 오픈할 수도 있다. KZG 커밋은 Pinocchio, Groth16, Plonk 등의 효율적인 SNARKs에 있어 핵심 구성 요소 중 하나이며, EIP-4844의 핵심이기도 하다. 배치 기술에 대한 직관적 이해는 Mina to Ethereum ZK bridge를 참고하라.

3. 타원 곡선을 사용하는 실용적 SNARKs

SNARKs의 첫 번째 실용적 구성은 2013년에 등장했다. 이러한 구성은 증명 및 검증 키를 생성하기 위한 전처리 단계를 필요로 하며, 프로그램/회로에 특화되어 있다. 이러한 키는 매우 클 수 있으며, 모든 당사자가 알지 못하는 비밀 매개변수에 의존한다. 그렇지 않으면 증명을 위조할 수 있다. 코드를 증명 가능한 코드로 변환하기 위해서는 코드를 다항식 제약 시스템으로 컴파일해야 한다. 처음에는 이를 수동으로 수행해야 했으며, 이는 시간 소모적이며 오류 발생 가능성이 높았다. 해당 분야의 발전은 주요 문제들 일부를 제거하려는 시도였다.

1) 보다 효율적인 증명자(prover)를 갖는 것.

2) 전처리 양 감소.

3) 회로 특화(setup)가 아닌 범용(setup) 구현.

4) 신뢰 설정(trusted setup) 회피.

5) 다항식 제약을 수동으로 작성하는 대신 고급 언어로 회로를 기술하는 방법 개발.

현재 타원 곡선을 사용하는 실용적 SNARKs 방식은 다음과 같다.

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin, and Plonk (2019)

5) Lookups (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) Folding schemes (2008/2021)

3.1 Pinocchio (2013)

Pinocchio(<Pinocchio: Nearly Practical Verifiable Computation> 참조)는 첫 번째 실용적이고 사용 가능한 zk-SNARK이다. 이 SNARK는 이차 산술 프로그램(quadratic arithmetic programs, QAP)을 기반으로 한다. 초기 증명 크기는 288바이트였다. Pinocchio의 툴체인은 C 코드에서 산술 회로로의 컴파일러를 제공하며, 이를 더 나아가 QAP로 변환한다. 이 프로토콜은 검증자가 회로 특화 키를 생성하도록 요구한다. 타원 곡선 매칭을 사용하여 방정식을 검사한다. 증명 생성 및 키 설정의 점근적(asymptotic) 복잡도는 계산 크기에 선형 비례하며, 검증 시간은 공개 입력 및 출력 크기에 선형 비례한다.

3.2 Groth 16 (2016)

Groth의 2016년 논문 <On the Size of Pairing-based Non-interactive Arguments>는 R1CS로 기술된 문제의 성능을 향상시킨 새로운 지식 증명을 소개했다. 최소한의 증명 크기(단 세 개의 그룹 요소)와 세 개의 매칭(pairings)을 포함하는 빠른 검증을 제공한다. 또한 구조화된 reference 문자열을 획득하기 위한 전처리 단계를 포함한다. 주요 단점은 증명해야 할 각 프로그램마다 서로 다른 신뢰 설정이 필요하다는 점으로, 이는 매우 불편하다. Groth16은 ZCash에서 사용되었다. 자세한 내용은 블로그 <An overview of the Groth 16 proof system>을 참조하라.

3.3 Bulletproofs & IPA (2016)

KZG PCS의 약점 중 하나는 신뢰 설정이 필요하다는 점이다. Bootle 등은 2016년 <Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting>에서 내적(inner product) 관계를 만족하는 Pedersen 커밋 오프닝에 대한 효율적인 제로지식 증명 시스템을 도입했다. 내적 증명 시스템은 선형 시간 증명자, 로그 통신량 및 대화형 구조를 가지지만, 검증 시간은 선형이다. 또한 신뢰 설정이 필요 없는 다항식 커밋 방식도 개발되었다. Halo 2와 Kimchi 모두 IPA PCS의 아이디어를 채택했다.

3.4 Sonic, Marlin, and Plonk (2019)

Sonic, Plonk 및 Marlin은 범용적이며 갱신 가능한 구조화된 reference 문자열을 도입함으로써 Groth16의 각 프로그램별 신뢰 설정 문제를 해결했다. Marlin은 R1CS 기반의 증명 시스템을 제공하며, Aleo의 핵심이다.

Plonk는 새로운 산술화 방식(나중에 Plonkish라고 불림)을 도입했으며, copy constraints에 대해 grand-product check를 사용한다. Plonkish는 특정 연산을 위해 특수한 게이트(custom gate)를 도입할 수 있도록 한다. Aztec, ZK-Sync, Polygon ZKEVM, Mina의 Kimchi, Plonky2, Halo 2, Scroll 등 여러 프로젝트에서 Plonk의 맞춤형 버전을 사용하고 있다. <All you wanted to know about Plonk> 블로그를 참고하라.

3.5 Lookups (2018/2020)

Gabizon과 Williamson은 2020년 grand product check를 사용하여 특정 값이 미리 계산된 값 테이블에 포함되어 있음을 증명하는 plookup을 도입했다. Arya에서 이전에 lookup arguments가 제안되었으나, 그 구성은 lookups의 중복성을 결정해야 해 효율이 낮았다. PlonkUp 논문은 plookup argument를 Plonk에 어떻게 통합하는지를 보여준다. 이러한 lookup arguments의 문제는 증명자가 조회 횟수와 무관하게 전체 테이블 비용을 부담해야 한다는 점이다. 즉, 큰 테이블은 상당한 비용을 발생시키며, 증명자의 비용을 실제 사용한 조회 수에 비례하도록 낮추기 위한 많은 노력이 이루어졌다.

Haböck은 LogUp을 도입했는데, 이는 로그 미분(logarithmic derivative)을 사용하여 곱셈 검사를 역수들의 합으로 변환한다. LogUp은 전체 테이블을 여러 STARK 모듈로 분할해야 하는 Polygon plonky2 ZKEVM(<Beyond Limits: Pushing the Boundaries of ZK-EVM>)의 성능에 중요하다. 이러한 모듈들은 올바르게 연결되어야 하며, cross-table lookup으로 강화되어야 한다. LogUp-GKR은 GKR 프로토콜을 활용하여 LogUp의 성능을 향상시켰다. Caulk은 테이블 크기에 대해 아예 선형 관계인 prover time을 갖는 첫 번째 lookup argument이며, 전처리 시간은 O(N log N), 저장 공간은 O(N)이다(N은 테이블 크기). 이후 Baloo, flookup, cq, caulk+ 등의 다른 방식들도 등장했다. Lasso는 주어진 구조를 갖는 테이블에 대해 commit하지 않도록 하는 여러 개선점을 제안했다. 또한 Lasso의 증명자는 조회 작업에서 접근한 테이블 항목에 대해서만 비용을 지불한다. Jolt은 Lasso를 활용하여 가상 머신의 실행을 lookup을 통해 증명한다.

3.6 Spartan (2019)

Spartan은 R1CS로 기술된 회로에 대해 IOP를 제공하며, 다변수 다항식과 sumcheck 프로토콜의 속성을 활용한다. 적절한 다항식 커밋 방식과 함께 사용하면, 선형 시간 증명자를 갖는 투명한 SNARK를 생성한다.

3.7 HyperPlonk (2022)

HyperPlonk은 다변수 다항식을 사용하는 Plonk의 아이디어를 기반으로 한다. 제약 조건의 이행 여부를 확인하기 위해 몫(quotient)에 의존하지 않고, sumcheck 프로토콜에 의존한다. 또한 high degree 제약을 지원하면서도 증명자의 실행 시간을 해치지 않는다. 다변수 다항식에 의존하므로 FFT를 수행할 필요가 없으며, 증명자의 실행 시간은 회로 크기에 선형 비례한다. HyperPlonk은 작은 도메인에 적합한 새로운 순열(permutation) IOP와 sumcheck 기반의 배치 오프닝(batch opening) 프로토콜을 도입하여, 증명자의 작업량, 증명 크기, 검증자 시간을 모두 줄였다.

3.8 Folding schemes (2008/2021)

Nova는 증분적 검증 가능 컴퓨팅(IVC)을 구현하는 새로운 방법으로 folding scheme의 개념을 도입했다. IVC의 개념은 Valiant까지 거슬러 올라가며, 길이 k의 두 증명을 결합하여 길이 k의 단일 증명을 생성하는 방법을 보여준다. 아이디어는 step i에서 step i+1로의 실행이 올바르다는 것을 재귀적으로 증명하고, step i-1에서 step i로의 전이 증명이 올바르다는 것을 검증함으로써 장시간 실행되는 계산 전체를 증명하는 것이다.

Nova는 uniform computations를 잘 처리할 수 있으며, 이후 Supernova의 도입으로 다양한 유형의 회로 처리로 확장되었다. Nova는 R1CS의 느슨한 버전을 사용하며, 친화적인 타원 곡선 위에서 동작한다. Pickles에서처럼 IVC를 구현하기 위해 Pasta 곡선과 같은 사이클(cycles)을 갖는 우호적인 곡선(friendly curves)이 사용되며, 이는 Mina의 주요 핵심 구성 요소로서 간결한 상태를 달성한다. 그러나 folding의 개념은 재귀적 SNARK 검증과는 다르다. 누산기(accumbulator)의 아이디어는 proofs 배치(batching) 개념과 더 깊은 연관이 있다. Halo는 재귀적 증명 조합의 대안으로서 누산 개념을 도입했다. Protostar는 high-degree gates와 vector lookups를 지원하는 Plonk용 non-uniform IVC 방식을 제공한다.

4. 충돌 저항성 해시 함수를 사용하는 SNARKs

Pinocchio 개발과 거의 동시에, 가상 머신 실행의 정확성을 증명할 수 있는 회로/산술 방식을 생성하는 아이디어들이 등장했다. 특정 프로그램을 위한 전용 회로를 작성하는 것보다 가상 머신의 산술화가 더 복잡하거나 효율이 낮을 수 있지만, 장점은 얼마나 복잡한 프로그램이라도 가상 머신 내에서 올바르게 실행됨을 증명함으로써 검증할 수 있다는 점이다. TinyRAM의 아이디어는 Cairo VM 및 후속된 zk-evms 또는 일반 zkvms와 같은 가상 머신 설계를 통해 개선되었다. 충돌 저항성 해시 함수를 사용하면 신뢰 설정이나 타원 곡선 연산의 필요성을 없애지만, 그 대가로 증명이 더 길어진다.

1) TinyRAM (2013)

<SNARKs for C>에서 C 프로그램 실행의 정확성을 증명하기 위한 PCP 기반의 SNARK가 개발되었으며, 이는 TinyRAM(축소 명령어 세트 컴퓨터)으로 컴파일된다. 이 컴퓨터는 바이트 단위로 주소 지정 가능한 랜덤 액세스 메모리를 갖춘 하버드 아키텍처를 채택한다. 비결정성(nondeterminism)을 활용하여 회로 크기는 계산 크기에 quasi선형(quasilinear) 관계를 가지며, 임의의 데이터 종속 반복문, 제어 흐름, 메모리 접근을 효과적으로 처리한다.

2) STARKs (2018)

STARKs는 Ben Sasson 등이 2018년에 제안했다. 증명 크기는 O(log²n), 빠른 증명자와 검증자를 가지며, 신뢰 설정이 필요 없고 양자 안전(post-quantum secure)으로 간주된다. 처음으로 Starkware/Starknet이 Cairo 가상 머신과 함께 사용했다. 주요 구성 요소는 다음과 같다.

• 대수적 중간 표현 (AIR)

• FRI 프로토콜(Fast Reed-Solomon Interactive Oracle Proof of Proximity)

STARKs는 Polygon Miden, Risc0, Winterfell, Neptune 등의 다른 프로젝트에서도 사용되거나, 그 변형들이 사용된다(ZK-Sync의 Boojum, Plonky2, Starky).

3) Ligero (2017)

• Ligero는 증명 크기가 O(√n)인 증명 시스템을 도입했다(n은 회로 크기). 다항식 계수를 행렬 형태로 배열하고 선형 코드(linear codes)를 사용한다.

• Brakedown은 Ligero를 기반으로 하며, 도메인 독립적인 다항식 커밋 방식의 아이디어를 도입했다.

5. ZKP의 새로운 발전들

다양한 증명 시스템을 생산 환경에서 사용해보면서 각 방법의 장점이 드러났으며, 새로운 발전을 이끌어냈다. 예를 들어, plonkish 산술화는 사용자 정의 게이트와 lookup arguments를 포함하는 간단한 방법을 제공한다. FRI는 PCS로서 뛰어난 성능을 보이며 Plonky를 앞질렀다. 또한 AIR에서 grand product check를 사용함으로써(사전 처리된 randomized AIR을 유도) 성능을 향상시키고 메모리 접근 arguments를 단순화했다. 해시 함수 기반의 커밋이 인기를 끌었는데, 이는 하드웨어에서 해시 함수의 속도 혹은 새로운 SNARK 친화적 해시 함수 도입 때문이었다.

1) 새로운 다항식 커밋 방식 (2023)

Spartan이나 HyperPlonk과 같이 다변수 다항식 기반의 효율적인 SNARK의 등장으로, 이러한 다항식에 적합한 새로운 커밋 방식에 대한 관심이 높아지고 있다. Binius, Zeromorph, Basefold는 모두 다중 선형(multilinear) 다항식을 위한 새로운 형태를 제안했다. Binius는 데이터 유형을 표현하는 데 추가 비용이 없으며(많은 증명 시스템은 단일 bit를 표현하기 위해 최소 32비트 도메인 요소를 사용함), 이진 도메인(binary field)에서 동작한다. Binius 커밋은 Brakedown 기반으로, 도메인 독립적 설계를 목표로 한다. Basefold는 FRI를 리드-솔로몬 코드 이외의 코드들로 확장하여 도메인 독립적 PCS를 형성한다.

2) Customizable Constraint Systems(CCS) (2023)

CCS는 R1CS를 일반화하면서도 R1CS, Plonkish, AIR 산술을 추가 비용 없이 모두 포괄한다. CCS를 Spartan IOP와 결합하면 SuperSpartan이 되며, 이는 high-degree 제약을 지원하면서도 증명자가 제약 차수(degree)에 따라 증가하는 암호화 비용을 부담하지 않는다. 특히, SuperSpartan은 선형 시간 증명자를 갖는 AIR용 SNARK를 생성한다.

6. 결론

본문은 SNARK가 1980년대 중반 등장한 이후의 발전 과정을 설명한다. 컴퓨터 과학, 수학, 하드웨어의 발전과 더불어 블록체인의 도입은 새로운, 더욱 효율적인 SNARK를 탄생시켰으며, 사회를 변화시킬 수 있는 많은 애플리케이션의 문을 열었다. 연구자들과 엔지니어들은 자신의 요구에 따라 SNARKs의 개선과 조정을 제안하며, 증명 크기, 메모리 사용량, 투명 설정, 양자 안전성, 증명자 시간, 검증자 시간에 초점을 맞췄다.

처음에는 두 가지 주요 흐름(SNARK와 STARK)이 있었지만, 이제 그 경계는 흐려지고 있으며 서로 다른 증명 시스템의 장점을 결합하려는 시도가 진행 중이다. 예를 들어, 다양한 산술 방식을 새로운 다항식 커밋 방식과 결합하는 것이다. 앞으로도 새로운 증명 시스템이 계속 등장하며 성능이 향상될 것이며, 일부 시스템은 적응에 시간이 걸릴 수 있으므로, 핵심 인프라를 변경하지 않고도 이러한 도구들을 쉽게 사용할 수 있어야 따라잡을 수 있을 것이다.