제로 지식 증명의 오랜 시간 동안 변함없이 혁신이 지속적으로 나타나는 진정한 이유 탐구

작성자: LambdaClass

편집: mutourend; Yiping, IOSG Ventures

1. 서론

제로 지식, 간결하고 비상호적 지식 증명(zk-SNARKs)은 증명자가 검증자에게 특정 진술의 정확성을 설득할 수 있게 해주는 강력한 암호학적 원리로, 진술 외의 어떤 정보도 공개하지 않습니다. zk-SNARKs는 검증 가능한 개인 계산, 컴퓨터 프로그램 실행의 정확성 증명 및 블록체인 확장과 같은 응용 분야로 인해 널리 주목받고 있습니다. 우리는 이 글에서 설명하는 바와 같이, zk-SNARKs가 세계를 형성하는 데 중대한 영향을 미칠 것이라고 믿습니다. zk-SNARKs는 서로 다른 유형의 증명 시스템을 포함하며, 다양한 다항식 약속 계획, 산술화 계획, 상호작용 예언자 증명 또는 확률적으로 검증 가능한 증명을 사용합니다. 그러나 이러한 기본 아이디어와 개념은 20세기 80년대 중반으로 거슬러 올라갑니다.

비트코인과 이더리움이 출시된 이후, zk-SNARKs의 발전은 크게 가속화되었습니다. 이는 제로 지식 증명(일반적으로 이 특정 용도의 유효성 증명으로 알려짐)을 사용하여 확장할 수 있기 때문입니다. zk-SNARKs는 블록체인 확장성에서 중요한 역할을 합니다. Ben-Sasson에 따르면, 최근 몇 년 동안 암호 증명의 캄브리아 폭발이 목격되었습니다. 각 증명 시스템은 장단점이 있으며, 설계 시 특정 트레이드오프를 고려했습니다. 하드웨어, 알고리즘, 새로운 증명 및 도구의 발전은 성능을 지속적으로 향상시키고 새로운 시스템의 출현을 촉진했습니다. 이러한 시스템 중 많은 수가 이미 사용되고 있으며, 우리는 지속적으로 한계를 넘어섭니다. 모든 응용에 적합한 범용 증명 시스템을 가질 수 있을까요, 아니면 서로 다른 요구에 적합한 여러 시스템이 존재할까요? 우리는 하나의 증명 시스템이 모든 다른 시스템을 지배할 가능성이 낮다고 생각합니다. 그 이유는 다음과 같습니다:

1) 응용의 다양성.

2) 서로 다른 제한 유형(메모리, 검증 시간, 증명 시간에 대한).

3) 강건성에 대한 요구(하나의 증명 시스템이 손상되면 다른 증명 시스템이 존재함).

증명 시스템이 크게 변화하더라도, 그들은 중요한 특성을 제공합니다: 증명은 빠르게 검증될 수 있습니다. 검증 증명을 보유하고 새로운 증명 시스템에 쉽게 적응할 수 있는 레이어는 이더리움과 같은 기본 레이어 변경과 관련된 어려움을 해결합니다. 본 문서는 SNARKs의 다양한 특성을 개요합니다:

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

2) 투명 vs 신뢰할 수 있는 설정.

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

4) 검증자 시간: 상수 시간, 로그, 서브선형, 선형.

5) 증명 크기.

6) 재귀적 용이성.

7) 산술화 계획.

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

본 문서는 SNARKs의 기원, 몇 가지 기본 구성 요소 및 다양한 증명 시스템의 부상(및 쇠퇴)을 탐구합니다. 본 문서는 증명 시스템에 대한 철저한 분석을 의도하지 않습니다. 오히려 우리에게 영향을 미치는 것들에만 집중합니다. 물론 이러한 발전은 이 분야의 선구자들의 위대한 작업과 아이디어 덕분에 가능했습니다.

2. 기초 지식

제로 지식 증명은 새로운 것이 아닙니다. 정의, 기초, 중요한 정리 및 심지어 중요한 프로토콜은 20세기 80년대 중반부터 제정되었습니다. 현대 SNARKs를 구축하는 데 사용되는 몇 가지 핵심 아이디어와 프로토콜은 20세기 90년대에 제안되었으며(합계 확인 프로토콜), 비트코인이 등장하기 전(2007년의 GKR)에도 존재했습니다. 이를 사용하는 주요 문제는 강력한 사용 사례의 부족(인터넷이 20세기 90년대에 발달하지 않았음)과 필요한 계산 능력과 관련이 있습니다.

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

제로 지식 증명 분야는 Goldwasser, Micali 및 Rackoff의 논문 "The knowledge complexity of interactive proof systems"에서 학술 문헌에 등장했습니다. 기원에 대한 논의는 2023년 1월의 비디오 ZKP MOOC Lecture 1: Introduction and History of ZKP를 시청할 수 있습니다. 이 논문은 완전성, 신뢰성 및 제로 지식성의 개념을 도입하고, 이차 잔여성과 이차 비잔여성의 구성을 제공합니다.

2) 합계 확인 프로토콜 (1992).

합계 확인 프로토콜은 Lund, Fortnow, Karloff 및 Nisan에 의해 1992년 "Algebraic Methods for Interactive Proof Systems" 논문에서 제안되었습니다. 이는 간결한 상호작용 증명의 가장 중요한 구성 요소 중 하나입니다. 이는 다변수 다항식을 평가하여 합산하는 요구를 무작위 선택된 점의 단일 평가로 줄이는 데 도움을 줍니다.

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

GKR 프로토콜(논문 "Delegating Computation: interactive Proofs for Muggles" 참조)은 증명자가 회로의 게이트 수에 따라 선형으로 실행되고, 검증자는 회로의 크기에 따라 아선형으로 실행되는 상호작용 프로토콜입니다. 이 프로토콜에서 증명자와 검증자는 깊이가 d인 두 입력을 가진 유한체의 팬인-투 연산 회로에 대해 합의합니다. 이 프로토콜은 회로 출력에 대한 진술에서 시작되며, 이는 이전 층 값에 대한 진술로 단순화됩니다. 재귀를 사용하여 이를 회로 입력에 대한 진술로 변환할 수 있어 쉽게 검증할 수 있습니다. 이러한 축소는 합계 확인 프로토콜을 통해 이루어집니다.

4) KZG 다항식 약속 계획 (2010).

Kate, Zaverucha 및 Goldberg는 2010년 "Constant-Size Commitments to Polynomials and Their Applications"에서 이중 선형 쌍을 사용하는 다항식 약속 계획을 도입했습니다. 약속은 단일 군 요소로 구성되며, 약속자는 다항식의 모든 올바른 평가에 대한 약속을 효율적으로 열 수 있습니다. 또한 배칭 기술 덕분에 여러 평가를 열 수 있습니다. KZG 약속은 Pinocchio, Groth16 및 Plonk와 같은 몇 가지 효율적인 SNARK의 기본 구성 요소 중 하나입니다. 이는 EIP-4844의 핵심이기도 합니다. 배칭 기술을 직관적으로 이해하려면 Mina to Ethereum ZK bridge를 참조하십시오.

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

SNARKs의 첫 번째 실용적 구성은 2013년에 등장했습니다. 이러한 구성은 증명 및 검증 키를 생성하기 위한 전처리 단계를 필요로 하며, 프로그램/회로에 특화되어 있습니다. 이러한 키는 매우 클 수 있으며, 각 당사자가 알지 못하는 비밀 매개변수에 따라 달라집니다. 그렇지 않으면 증명이 위조될 수 있습니다. 코드를 증명 가능한 코드로 변환하려면 코드를 다항식 제약 시스템으로 컴파일해야 합니다. 처음에는 수동으로 수행해야 했으며, 이는 시간 소모적이고 오류가 발생하기 쉬웠습니다. 이 분야의 발전은 몇 가지 주요 문제를 해결하려고 시도했습니다:

1) 더 효율적인 증명자 보유.

2) 전처리 양 감소.

3) 회로 특정이 아닌 범용 설정.

4) 신뢰할 수 있는 설정을 피하기.

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

현재 타원 곡선을 사용하는 실용 SNARKs 계획은 다음과 같습니다:

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin, 및 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로 변환됩니다. 이 프로토콜은 검증자가 회로 특정 키를 생성하도록 요구합니다. 이는 타원 곡선 쌍을 사용하여 방정식을 검사합니다. 증명 생성 및 키 설정의 점근적 관계는 계산 크기와 선형 관계를 가지며, 검증 시간은 공용 입력 및 출력의 크기와 선형 관계를 가집니다.

3.2 Groth 16 (2016)

Groth의 2016년 논문 "On the Size of Pairing-based Non-interactive Arguments"는 R1CS로 설명된 문제의 성능을 향상시키는 새로운 지식 증명을 도입했습니다. 이는 최소한의 증명 크기(단 3개의 군 요소)와 3개의 쌍을 포함하는 빠른 검증을 제공합니다. 또한 구조화된 참조 문자열을 얻기 위한 전처리 단계를 포함합니다. 주요 단점은 증명할 각 프로그램이 서로 다른 신뢰할 수 있는 설정이 필요하다는 점입니다. 이는 매우 불편합니다. 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" 논문에서 내적 관계를 만족하는 Pedersen 약속 개방의 효율적인 제로 지식 증명 시스템을 도입했습니다. 내적 증명 시스템은 로그 통신 및 상호작용을 가지며 선형 증명자를 보유하지만, 선형 시간 검증을 가지고 있습니다. 또한 신뢰할 수 있는 설정이 필요 없는 다항식 약속 계획을 개발했습니다. Halo 2와 Kimchi는 IPA PCS 아이디어를 채택했습니다.

3.4 Sonic, Marlin, 및 Plonk (2019)

Sonic, Plonk 및 Marlin은 범용적이고 업데이트 가능한 구조화된 참조 문자열을 도입하여 Groth16의 각 프로그램에 대한 신뢰할 수 있는 설정 문제를 해결했습니다. Marlin은 R1CS 기반의 증명 시스템을 제공하며, Aleo의 핵심입니다.

Plonk은 새로운 산술화 계획(후에 Plonkish로 불림)을 도입하고, 복사 제약에 대해 grand-product check를 사용합니다. Plonkish는 특정 작업을 위한 맞춤형 게이트를 도입할 수 있게 해줍니다. 여러 프로젝트는 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년에 plookup을 도입하여 grand product check를 사용하여 특정 값이 미리 계산된 값 표에 포함되어 있는지 증명합니다. 이전에 Arya에서 lookup arguments가 제안되었지만, 그 구조는 lookups의 다중성을 결정해야 하므로 효율성이 떨어졌습니다. PlonkUp 논문은 plookup argument를 Plonk에 도입하는 방법을 보여줍니다. 이러한 lookup arguments의 문제는 증명자가 전체 표에 대한 비용을 지불해야 하며, 이는 그들의 조회 횟수와는 무관하다는 점입니다. 이는 대형 표의 비용이 상당히 크다는 것을 의미하며, 증명자의 비용을 그들이 사용하는 조회 수에 맞게 줄이기 위해 많은 노력이 들어갔습니다.

Haböck은 LogUp을 도입하여 로그 도함수를 사용하여 곱셈 검사를 역수의 합으로 변환합니다. LogUp은 Polygon plonky2 ZKEVM(“Beyond Limits: Pushing the Boundaries of ZK-EVM”)의 성능에 필수적이며, 전체 표를 여러 STARK 모듈로 분할해야 합니다. 이러한 모듈은 올바르게 연결되어야 하며, 표를 가로질러 조회하여 이 작업을 강화해야 합니다. LogUp-GKR의 출시는 GKR 프로토콜을 활용하여 LogUp의 성능을 향상시킵니다. Caulk는 첫 번째 prover time과 table size 간의 아선형 관계를 가진 lookup argument로, 전처리 시간은 O(N log N)이고 저장소는 O(N)입니다. 여기서 N은 table size입니다. 이후 Baloo, flookup, cq 및 caulk+와 같은 다른 몇 가지 계획이 등장했습니다. Lasso는 주어진 구조를 가진 표에 대해 commit하는 것을 피하는 여러 개선을 제안했습니다. 또한 Lasso의 증명자는 조회 작업에 접근하는 표 항목에 대해서만 비용을 지불합니다. Jolt는 Lasso를 활용하여 조회를 통해 가상 머신의 실행을 증명합니다.

3.6 Spartan (2019)

Spartan은 R1CS로 설명된 회로에 대해 IOP를 제공하며, 다변수 다항식과 합계 확인 프로토콜의 속성을 활용합니다. 적절한 다항식 약속 계획을 사용하여 선형 시간 prover를 가진 투명한 SNARK를 생성합니다.

3.7 HyperPlonk (2022)

HyperPlonk는 다변수 다항식을 사용하는 Plonk 아이디어를 기반으로 구축되었습니다. 이는 제약의 실행을 검사하기 위해 상을 사용하지 않고 합계 확인 프로토콜에 의존합니다. 또한 증명자의 실행 시간을 손상시키지 않으면서 높은 차수 제약을 지원합니다. 다변수 다항식에 의존하기 때문에 FFT를 실행할 필요가 없으며, 증명자의 실행 시간은 회로 크기와 선형 관계를 가집니다. HyperPlonk는 작은 도메인에 적합한 새로운 permutation IOP와 sumcheck 기반의 배치 개방 프로토콜을 도입하여 증명자의 작업량, 증명 크기 및 검증자의 시간을 줄입니다.

3.8 Folding schemes (2008/2021)

Nova는 증분 검증 가능한 계산(IVC)을 구현하는 새로운 방법으로 folding 계획의 아이디어를 도입했습니다. IVC의 개념은 Valiant로 거슬러 올라가며, 이는 길이가 k인 두 개의 증명을 길이가 k인 하나의 증명으로 병합하는 방법을 보여줍니다. 이 아이디어는 재귀 증명을 통해 step i에서 step i + 1로의 실행이 올바르다는 것을 증명하고, step i - 1에서 step i로의 전환 증명이 올바르다는 것을 검증하여 장시간 실행되는 계산을 증명할 수 있습니다.

Nova는 균일 계산을 잘 처리하며, 이후 Supernova의 도입으로 다양한 유형의 회로를 처리하도록 확장되었습니다. Nova는 R1CS의 느슨한 버전을 사용하며, 친화적인 타원 곡선에서 작동합니다. 친화적인 곡선 사이클(예: Pasta 곡선)을 사용하여 IVC를 구현하는 것도 Pickles에서 사용되며, Pickles는 Mina의 주요 기본 모듈로 간결한 상태를 구현합니다. 그러나 folding의 아이디어는 재귀 SNARK 검증과는 다릅니다. 누산기의 아이디어는 배치 증명의 개념과 더 깊은 연관이 있습니다. Halo는 재귀 증명 조합의 대안으로 누산기의 개념을 도입했습니다. Protostar는 Plonk에 대해 비균일 IVC 계획을 제공하며, 높은 차수 게이트와 벡터 조회를 지원합니다.

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

Pinocchio 개발과 동시에, 가상 머신 실행의 정확성을 증명할 수 있는 회로/산술 계획을 생성하는 몇 가지 아이디어가 등장했습니다. 특정 프로그램을 위한 전용 회로를 작성하는 것보다 가상 머신의 산술을 개발하는 것이 더 복잡하거나 비효율적일 수 있지만, 모든 프로그램이 얼마나 복잡하든 가상 머신에서 올바르게 실행되었음을 증명함으로써 증명할 수 있는 장점이 있습니다. TinyRAM의 아이디어는 이후 Cairo vm 및 후속 가상 머신(예: zk-evms 또는 범용 zkvms)의 설계로 개선되었습니다. 충돌 저항 해시 함수를 사용하면 신뢰할 수 있는 설정이나 타원 곡선 연산의 필요성이 제거되지만, 대신 더 긴 증명이 필요합니다.

1) TinyRAM (2013)

"SNARKs for C"에서, C 프로그램 실행의 정확성을 증명하기 위해 PCP 기반의 SNARK가 개발되었으며, 이 프로그램은 TinyRAM(정밀 명령 집합 컴퓨터)으로 컴파일됩니다. 이 컴퓨터는 하버드 아키텍처를 채택하고 있으며, 바이트 수준으로 주소 지정 가능한 랜덤 액세스 메모리를 가지고 있습니다. 비결정성을 활용하여 회로의 크기는 계산 크기와 준선형 관계를 가지며, 이는 임의의 데이터 관련 루프, 제어 흐름 및 메모리 접근을 효과적으로 처리합니다.

2) STARKs (2018)

STARKs는 Ben Sasson 외에 2018년에 제안되었습니다. 그 구현의 증명 크기는 O(log2n)이며, 빠른 증명자와 검증자를 가지고 있으며, 신뢰할 수 있는 설정이 필요하지 않으며, 후량자 안전으로 간주됩니다. 이는 처음에 Starkware/Starknet와 함께 Cairo 가상 머신과 함께 사용되었습니다. 그 핵심 구성 요소는:

대수 중간 표현 (AIR)

및 FRI 프로토콜(빠른 Reed-Solomon 상호작용 오라클 근접 증명).

STARKs는 Polygon Miden, Risc0, Winterfell, Neptune와 같은 다른 프로젝트에서 사용되거나 그 일부 변형에서 사용됩니다(예: ZK-Sync의 Boojum, Plonky2, Starky).

3) Ligero (2017)

Ligero는 증명 크기가 O(√n)인 증명 시스템을 도입했으며, 여기서 n은 회로 크기입니다. 이는 다항식 계수를 행렬 형태로 배열하고 선형 코드를 사용합니다.

Brakedown은 Ligero를 기반으로 하여 필드에 독립적인 다항식 약속 계획의 아이디어를 도입했습니다.

5. ZKP의 몇 가지 새로운 발전

생산에서 다양한 증명 시스템을 사용하는 것은 각 방법의 장점을 보여주고 새로운 발전을 가져왔습니다. 예를 들어, plonkish 산술화는 사용자 정의 게이트와 lookup arguments를 포함하는 간단한 방법을 제공합니다. FRI는 PCS로서 뛰어난 성능을 보여주며, Plonky를 앞서갑니다. 마찬가지로 AIR에서 grand product check를 사용하여(전처리가 있는 무작위화된 AIR을 초래함) 성능을 향상시키고 메모리 접근 arguments를 단순화했습니다. 해시 함수 기반의 약속이 인기를 얻고 있습니다—하드웨어에서 해시 함수의 속도 또는 새로운 SNARK 친화적 해시 함수를 도입함으로써.

1) 새로운 다항식 약속 계획 (2023)

다변수 다항식을 기반으로 하는 효율적인 SNARK(예: Spartan 또는 HyperPlonk)의 출현과 함께, 이러한 다항식에 적합한 새로운 약속 계획에 대한 관심이 높아지고 있습니다. Binius, Zeromorph 및 Basefold는 다중 선형 다항식에 전념하는 새로운 형태를 제안했습니다. Binius는 데이터 유형을 표현하는 데 제로 오버헤드를 가지며(많은 증명 시스템이 단일 비트를 표현하기 위해 최소 32비트 필드 요소를 사용함) 이진 필드에서 작동합니다. Binius 약속은 Brakedown을 기반으로 하며, 설계 목적은 필드에 독립적입니다. Basefold는 FRI를 Reed-Solomon 이외의 코드로 확장하여 필드에 독립적인 PCS를 형성합니다.

2) 사용자 정의 제약 시스템 (CCS) (2023)

CCS는 R1CS를 요약하며, R1CS, Plonkish 및 AIR 산술을 오버헤드 없이 포착합니다. CCS와 Spartan IOP를 결합하면 SuperSpartan이 생성되어 높은 차수 제약을 지원하며, 증명자가 제약 차수에 따라 증가하는 암호 비용을 부담하지 않아도 됩니다. 특히 SuperSpartan은 선형 시간 prover를 가진 AIR에 대해 SNARK를 생성합니다.

6. 결론

본 문서는 20세기 80년대 중반 이후 SNARK의 발전을 설명합니다. 컴퓨터 과학, 수학 및 하드웨어의 발전과 블록체인의 도입은 새로운, 더 효율적인 SNARK를 탄생시켰으며, 이는 우리 사회를 변화시킬 수 있는 많은 응용 프로그램의 문을 열었습니다. 연구자와 엔지니어는 자신의 요구에 따라 SNARKs에 대한 개선 및 조정을 제안하며, 증명 크기, 메모리 사용, 투명한 설정, 후량자 안전성, 증명자 시간 및 검증자 시간에 중점을 두고 있습니다.

처음에는 두 가지 주요 경로(SNARK과 STARK)가 있었지만, 두 시스템 간의 경계는 점차 흐려지고 있으며, 서로 다른 증명 시스템의 장점을 결합하려고 시도하고 있습니다. 예를 들어, 서로 다른 산술 계획을 새로운 다항식 약속 계획과 결합하는 것입니다. 새로운 증명 시스템이 계속해서 등장하고 성능이 향상될 것으로 예상되며, 일부 시스템은 이러한 발전을 따라잡기 어려울 것입니다. 이는 이러한 도구를 쉽게 사용할 수 있도록 하여 일부 핵심 인프라를 변경하지 않고도 가능할 것입니다.