작성자: LambdaClass
편집자: mutourend; Yiping, IOSG Ventures
Zk-SNA RK)는 증명자가 진술 이외의 정보를 공개하지 않고 진술의 정확성을 검증자에게 확신시킬 수 있도록 하는 일종의 강력한 암호화 기본 요소입니다. zk-SNARK는 검증 가능한 개인 계산, 컴퓨터 프로그램 실행의 정확성 증명 및 블록체인 확장에 대한 적용으로 인해 광범위한 주목을 받았습니다. 우리는 기사에서 설명하는 것처럼 zk-SNARK가 세상을 형성하는 데 중요한 영향을 미칠 것이라고 믿습니다. zk-SNARK는 다양한 다항식 약속 체계, 산술 체계, 대화형 오라클 증명 또는 확률론적 테스트 가능 증명을 사용하여 다양한 유형의 증명 시스템을 다룹니다. 그러나 이러한 기본 아이디어와 개념은 1980년대 중반으로 거슬러 올라갑니다.
Zk-SNARK의 개발은 비트코인과 이더리움 출시 이후 영지식 증명(이 특정 사용 사례에 대한 유효성 증명이라고도 함)을 사용하여 확장할 수 있는 능력으로 인해 크게 가속화되었습니다. zk-SNARK는 블록체인 확장성에 중요한 역할을 합니다. Ben-Sasson이 설명했듯이 최근 몇 년 동안 암호화 증명에서 캄브리아기 폭발이 일어났습니다. 각 증명 시스템에는 장점과 단점이 있으며 특정한 장단점을 염두에 두고 설계되었습니다. 하드웨어, 알고리즘, 새로운 증명 및 도구의 발전으로 성능이 지속적으로 향상되고 새로운 시스템이 탄생합니다. 이러한 시스템 중 다수는 이미 사용되고 있으며 우리는 계속해서 한계를 확장하고 있습니다. 모든 애플리케이션에 작동하는 보편적인 증명 시스템을 갖게 될까요, 아니면 다양한 요구에 적합한 여러 시스템이 있을까요? 우리는 다음과 같은 이유로 하나의 증명 시스템이 다른 모든 증명 시스템을 지배할 가능성은 거의 없다고 생각합니다.
1) 애플리케이션의 다양성.
2) 다양한 유형의 제한(메모리, 검증 시간, 증명 시간 관련).
3) 견고성의 필요성(하나의 증명 시스템이 깨지면 다른 증명 시스템이 있음).
증명 시스템은 상당한 변화를 겪을 수 있지만 여전히 중요한 속성, 즉 빠른 증명 검증 가능성을 공유합니다. 이더리움과 같은 기본 레이어 변경과 관련된 어려움은 증명을 검증하고 새로운 증명 시스템에 쉽게 적응할 수 있는 레이어에서 해결됩니다. 이 기사에서는 SNARK의 다양한 특성에 대한 간략한 개요를 제공합니다.
1) 암호화 가정: 충돌 방지 해시 함수, 타원 곡선의 이산 로그 문제, 지수에 대한 지식.
2) 투명함 vs 신뢰할 수 있는 설정.
3) 증명 길이: 선형 대 초선형.
4) 유효성 검사기 시간: 상수 시간, 로그, 하위선형, 선형.
5) 증명사진 사이즈.
6) 재발이 쉽습니다.
7) 산술 체계.
8) 일변수 다항식과 다변수 다항식.
이 기사에서는 SNARK의 기원, 일부 기본 구성 요소, 다양한 증명 시스템의 상승(및 하락)을 살펴보겠습니다. 이 글은 증명 시스템에 대한 철저한 분석을 제공하기 위한 것이 아닙니다. 대신, 우리에게 영향을 미치는 사람들에게만 집중하십시오. 물론 이러한 발전은 해당 분야의 선구자들의 위대한 작업과 아이디어를 통해서만 가능했습니다.
영지식 증명은 새로운 것이 아닙니다. 정의, 기초, 중요한 정리, 심지어 중요한 프로토콜까지 1980년대 중반부터 개발되었습니다. 최신 SNARK를 구축하는 데 사용된 일부 핵심 아이디어와 프로토콜은 비트코인이 존재하기 전(2007년 GKR)인 1990년대(섬체크 프로토콜)에 제안되었습니다. 이를 사용할 때의 주요 문제점은 강력한 사용 사례의 부족(인터넷은 1990년대에 개발되지 않음)과 필요한 컴퓨팅 성능과 관련이 있습니다.
1) 영지식 증명: 기원(1985/1989).
영지식 증명 분야는 Goldwasser, Micali 및 Rackoff의 "대화형 증명 시스템의 지식 복잡성"이라는 논문을 통해 학술 문헌에 등장했습니다. 기원에 대한 논의를 보려면 2023년 1월 비디오 ZKP MOOC 강의 1: ZKP 소개 및 역사를 시청하세요. 본 논문에서는 배수성, 신뢰성 및 영지식의 개념을 소개하고 2차 잔차 및 2차 비잔차의 구성을 제공합니다.
2) Sumcheck 프로토콜(1992).
Sumcheck 프로토콜은 1992년 대화형 증명 시스템을 위한 대수 방법 논문에서 Lund, Fortnow, Karloff 및 Nisan에 의해 제안되었습니다. 이는 간결한 대화형 증명의 가장 중요한 구성 요소 중 하나입니다. 이는 다변량 다항식 평가 합산의 요구 사항을 무작위로 선택된 점에 대한 단일 평가로 줄이는 데 도움이 됩니다.
3) Goldwasser-Kalai-Rothblum(GKR)(2007).
GKR 프로토콜(계산 위임: 머글을 위한 대화형 증명 논문 참조)은 증명자가 회로의 게이트 수에 따라 선형적으로 작동하고 검증자가 회로 크기에 따라 하위선형으로 작동하는 대화형 프로토콜입니다. 프로토콜에서 증명자와 검증자는 깊이가 d dd인 유한 필드의 팬인투(fan-in-two) 연산 회로에 동의합니다. 여기서 레이어 d dd는 입력 레이어에 해당하고 레이어 0 00은 출력 레이어에 해당합니다. 프로토콜은 회로의 출력에 대한 설명으로 시작하며, 이는 이전 계층의 값에 대한 설명으로 축소됩니다. 재귀를 사용하면 이를 쉽게 확인할 수 있는 회로 입력 선언으로 변환할 수 있습니다. 이러한 감소는 sumcheck 프로토콜을 통해 구현됩니다.
4) KZG 다항식 공약 방식(2010).
Kate, Zaverucha 및 Goldberg는 2010 다항식에 대한 상수 크기 약속 및 해당 응용 프로그램에서 이중선형 쌍 그룹을 사용하는 다항식 약속 방식을 도입했습니다. 커밋은 단일 그룹 요소로 구성되며 커미터는 다항식의 올바른 평가에 대한 커밋을 효과적으로 엽니다. 또한 일괄 처리 기술 덕분에 여러 평가를 열 수 있습니다. KZG 약속은 Pinocchio, Groth16 및 Plonk와 같은 여러 효율적인 SNARK를 위한 기본 빌딩 블록 중 하나를 제공합니다. EIP-4844의 핵심이기도 하다. 일괄 처리 기술을 직관적으로 이해하려면 Mina에서 Ethereum ZK 브리지를 참조하세요.
SNARK의 첫 번째 실용적인 구성은 2013년에 나타났습니다. 이러한 구성에는 증명 및 확인 키를 생성하기 위한 전처리 단계가 필요하며 프로그램/회로에 따라 다릅니다. 이러한 키는 매우 클 수 있으며 모든 당사자에게 알려지지 않은 비밀 매개변수에 따라 달라질 수 있습니다. 그렇지 않으면 증거가 위조될 수 있습니다. 코드를 증명 가능한 코드로 변환하려면 코드를 다항식 제약 시스템으로 컴파일해야 합니다. 처음에는 이 작업을 수동으로 수행해야 했기 때문에 시간이 많이 걸리고 오류가 발생하기 쉬웠습니다. 현장의 발전은 몇 가지 주요 문제를 제거하려고 시도합니다.
1) 보다 효율적인 증명자를 확보합니다.
2) 전처리량을 줄여보세요.
3) 특정 회로가 아닌 일반적인 설정을 사용하세요.
4) 신뢰할 수 있는 설정을 피하세요.
5) 다항식 제약 조건을 수동으로 작성하는 대신 고급 언어를 사용하여 회로를 설명하는 방법을 개발합니다.
현재 타원 곡선을 사용한 실용적인 SNARK 솔루션은 다음과 같습니다.
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) 접는 방식(2008/2021)
3.1 Pinocchio (2013)
Pinocchio(Pinocchio: 거의 실용적이고 검증 가능한 계산 논문 참조)는 최초의 실용적이고 사용 가능한 zk-SNARK입니다. SNARK는 QAP(2차 산술 프로그램)를 기반으로 합니다. 증명 크기는 처음에 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에서 사용되었습니다. 자세한 내용은 Groth 16 증명 시스템 개요 블로그를 참조하세요.
3.3 Bulletproofs & IPA (2016)
KZG PCS의 약점 중 하나는 신뢰할 수 있는 설정이 필요하다는 것입니다. Bootle et al.의 2016년 이산 로그 설정의 산술 회로에 대한 효율적인 영지식 인수 논문에서는 내부 제품 관계를 충족하는 Pedersen 공약 개시를 위한 효율적인 영지식 인수 시스템을 소개했습니다. 내부 제품 증명 시스템에는 로그 통신 및 상호 작용이 있지만 선형 기간 검증이 있는 선형 증명자가 있습니다. 또한 신뢰할 수 있는 설정이 필요하지 않은 다항식 약속 체계를 개발했습니다. Halo 2와 Kimchi는 모두 IPA PCS 아이디어를 채택했습니다.
3.4 Sonic, Marlin 및 Plonk(2019)
Sonic, Plonk 및 Marlin은 공통적이고 업데이트 가능한 구조적 참조 문자열을 도입하여 Groth16의 각 프로그램에 대한 신뢰 설정 문제를 해결합니다. Marlin은 Aleo의 핵심인 R1CS 기반의 증명 시스템을 제공합니다.
Plonk는 새로운 산술 체계(나중에 Plonkish라고 함)를 도입하고 복사 제약 조건에 대해 총생산 검사를 사용했습니다. Plonkish는 또한 소위 맞춤형 도어라고 불리는 특정 작업을 위한 특수 도어의 도입을 허용합니다. Aztec, ZK-Sync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 및 Scroll 등 여러 프로젝트에 Plonk의 사용자 정의 버전이 있습니다. 블로그 보기 Plonk에 대해 알고 싶었던 모든 것.
3.5 조회(2018/2020)
Gabizon과 Williamson은 2020년에 plookup을 도입했습니다. 이는 그랜드 제품 검사를 사용하여 값이 미리 계산된 값 테이블에 포함되어 있는지 증명하는 것입니다. 이전에 Arya에서 조회 인수가 제안되었지만 해당 구성에서는 조회의 다양성을 결정해야 했기 때문에 효율성이 떨어졌습니다. PlonkUp 문서에서는 Plonk에 plookup 인수를 도입하는 방법을 보여줍니다. 이러한 조회 인수의 문제점은 증명자가 조회 횟수에 관계없이 전체 테이블에 대한 비용을 지불하도록 강제한다는 것입니다. 이는 대형 테이블의 비용이 상당하며, 증명자 비용을 사용하는 조회 수로 줄이기 위해 많은 노력을 기울였다는 것을 의미합니다.
Haböck은 로그 파생 상품을 사용하여 제품 수표를 역수 합계로 변환하는 LogUp을 소개합니다. LogUp은 전체 테이블을 여러 STARK 모듈로 분할해야 하는 Polygon plonky2 ZKEVM(Beyond Limits: Pushing the Boundaries of ZK-EVM)의 성능에 매우 중요합니다. 모듈은 적절하게 연결되어야 하며 이 작업을 적용하려면 테이블 전체를 조회해야 합니다. LogUp-GKR의 도입은 GKR 프로토콜을 활용하여 LogUp의 성능을 향상시킵니다. Caulk는 증명 시간이 테이블 크기와 하위 선형 관계를 갖는 첫 번째 조회 인수입니다. 전처리 시간은 O(N log N )이고 저장 공간은 O(N )입니다. 여기서 N은 테이블 크기입니다. Baloo, flookup, cq 및 caulk+와 같은 여러 다른 계획이 뒤따랐습니다. Lasso는 특정 구조를 가진 테이블이 커밋되는 것을 방지하기 위해 몇 가지 개선 사항을 제안했습니다. 또한 Lasso의 증명자는 조회 작업을 통해 액세스한 테이블 항목에 대해서만 비용을 지불합니다. Jolt는 Lasso를 활용하여 조회를 통해 가상 머신의 실행을 증명합니다.
3.6 Spartan(2019)
Spartan은 다변수 다항식의 속성과 섬체크 프로토콜을 활용하여 R1CS를 사용하여 설명된 회로에 대한 IOP를 제공합니다. 적절한 다항식 확약 방식을 사용하여 선형 지속 기간 증명을 통해 투명한 SNARK를 생성합니다.
3.7 HyperPlonk(2022)
HyperPlonk는 다변수 다항식을 사용하는 Plonk 아이디어를 기반으로 구축되었습니다. 제약 조건 적용을 확인하기 위해 몫에 의존하지 않고 대신 sumcheck 프로토콜에 의존합니다. 또한 증명자의 실행 시간을 손상시키지 않으면서 높은 수준의 제약 조건을 지원합니다. 다변수 다항식에 의존하기 때문에 FFT를 수행할 필요가 없으며 증명자의 실행 시간은 회로 크기에 따라 선형적으로 확장됩니다. HyperPlonk는 소규모 도메인에 적합한 새로운 순열 IOP와 섬체크 기반 배치 개방 프로토콜을 도입하여 증명 작업, 증명 크기 및 검증 시간을 줄입니다.
3.8 접는 방식(2008/2021)
Nova는 IVC(증분 검증 가능 계산)를 구현하는 새로운 방법인 접는 방식의 아이디어를 소개합니다. IVC의 개념은 길이 k kk 에 대한 2개의 증명을 길이 k kk 에 대한 단일 증명으로 결합하는 방법을 보여준 Valiant로 거슬러 올라갑니다. 아이디어는 재귀 증명을 사용하여 i ii 단계에서 i + 1 i+1i+1 단계로의 실행이 올바른지 증명하고 i − 1 i-1i−1 단계에서 i ii 단계로의 전환을 검증하는 데 사용할 수 있다는 것입니다. 정확하므로 장기 실행 계산의 경우를 입증합니다.
Nova는 균일한 계산을 매우 잘 처리할 수 있으며 나중에 Supernova가 도입되면서 다양한 유형의 회로를 처리하도록 확장되었습니다. Nova는 R1CS의 편안한 버전을 사용하고 친숙한 타원 곡선에서 작동합니다. 친숙한 곡선 사이클(예: 파스타 곡선)을 사용하여 IVC를 구현하는 것은 Mina의 기본 기본 모듈인 Pickles에서도 간결한 상태를 달성하는 데 사용됩니다. 그러나 접는다는 개념은 재귀적 SNARK 검증과 다릅니다. 누산기의 개념은 일괄 증명의 개념과 더 깊은 관련이 있습니다. Halo는 재귀 증명 조합의 대안으로 축적 개념을 도입합니다. Protostar는 높은 수준의 게이트 및 벡터 조회를 지원하는 Plonk용 비균일 IVC 솔루션을 제공합니다.
피노키오가 개발될 무렵, 가상 머신 실행의 정확성을 증명할 수 있는 회로/산술 체계를 생성하기 위한 몇 가지 아이디어가 있었습니다. 가상 머신 개발의 산술은 일부 프로그램에 대한 전용 회로를 작성하는 것보다 더 복잡하거나 덜 효율적일 수 있지만 아무리 복잡하더라도 모든 프로그램이 가상 머신에서 올바르게 실행된다는 것을 입증함으로써 입증될 수 있다는 이점을 제공합니다. TinyRAM의 아이디어는 나중에 Cairo vm 및 zk-evms 또는 일반 zkvms와 같은 후속 가상 머신의 설계로 개선되었습니다. 충돌 방지 해시 함수를 사용하면 신뢰할 수 있는 설정이나 타원 곡선 산술을 사용할 필요가 없지만 증명 시간이 길어집니다.
1) TinyRAM(2013)
C용 SNARK에서는 TinyRAM(Reduced Instruction Set Computer)으로 컴파일된 C 프로그램 실행의 정확성을 증명하기 위해 PCP 기반 SNARK가 개발되었습니다. 컴퓨터는 바이트 수준 주소 지정이 가능한 랜덤 액세스 메모리를 갖춘 Harvard 아키텍처를 사용합니다. 비결정론을 활용하여 회로 크기는 계산 크기에 따라 준선형적으로 확장되므로 임의의 데이터 관련 루프, 제어 흐름 및 메모리 액세스를 효율적으로 처리할 수 있습니다.
2) STARKs(2018)
STARKs는 2018년 Ben Sasson et al.에 의해 제안되었습니다. 구현에는 O(log2n)의 증명 크기가 있고 빠른 증명자와 검증자가 있으며 신뢰할 수 있는 설정이 필요하지 않으며 포스트퀀텀 보안으로 간주됩니다. Starkware/Starknet에서 Cairo 가상 머신과 함께 처음 사용했습니다. 주요 구성 요소에는
대수 중간 표현(AIR)
및 FRI 프로토콜(Fast Reed-Solomon Interactive Oracle Proof of Proximity)이 포함됩니다.
STARK는 다른 프로젝트(Polygon Miden, Risc0, Winterfell, Neptune) 또는 일부 개작(ZK-Sync의 Boojum, Plonky2, Starky)에서도 사용됩니다.
3) Ligero(2017)
Ligero는 증명 크기가 O(root n)인 증명 시스템을 도입합니다. 여기서 n은 회로 크기입니다. 다항식 계수를 행렬 형태로 배열하고 선형 코드를 사용합니다.
Brakedown은 Ligero를 기반으로 하며 도메인 독립적인 다항식 약속 체계의 아이디어를 도입합니다.
생산에서 다양한 증명 시스템을 사용하면 각 방법의 장점을 보여주고 새로운 발전을 가져올 수 있습니다. 예를 들어, plonkish 산술은 사용자 정의 게이트 및 조회 인수를 포함하는 쉬운 방법을 제공합니다. FRI는 Plonky보다 앞서 PCS로서 뛰어난 성능을 보여줍니다. 마찬가지로 AIR에서 최종 제품 검사를 사용하면(전처리를 통해 무작위 AIR가 생성됨) 성능이 향상되고 인수에 대한 메모리 액세스가 단순화됩니다. 해시 함수를 기반으로 한 약속은 하드웨어의 해시 함수 속도 또는 새로운 SNARK 친화적 해시 함수 도입을 기반으로 인기를 끌었습니다.
1) 새로운 다항식 공약 방식(2023년)
다변량 다항식(예: Spartan 또는 HyperPlonk)을 기반으로 하는 효율적인 SNARK의 출현으로 이러한 다항식에 적합한 새로운 커밋 방식에 대한 관심이 높아지고 있습니다. Binius, Zeromorph 및 Basefold는 모두 다선형 다항식 전용의 새로운 형식을 제안합니다. Binius는 데이터 유형을 표현하는 데 오버헤드가 없다는 장점이 있으며(많은 증명 시스템이 단일 비트를 표현하기 위해 최소 32비트 필드 요소를 사용하는 반면) 이진 도메인에서 작동합니다. Binius 커밋은 Brakedown을 기반으로 하며 도메인에 구애받지 않도록 설계되었습니다. Basefold는 FRI를 Reed-Solomon 이외의 코드로 일반화하여 도메인 독립적인 PCS를 생성합니다.
2) 맞춤형 제약 시스템(CCS)(2023)
CCS는 R1CS, Plonkish 및 AIR 산술을 오버헤드 없이 캡처하면서 R1CS를 일반화합니다. CCS와 Spartan IOP를 결합하면 SuperSpartan이 탄생합니다. SuperSpartan은 증명자가 제약 수준에 따라 암호화 비용을 부담하지 않고도 높은 수준의 제약 조건을 지원합니다. 특히 SuperSpartan은 선형 시간 증명을 사용하여 AIR용 SNARK를 생성합니다.
이 글은 1980년대 중반에 도입된 SNARK의 진행 상황을 설명합니다. 블록체인의 도입과 함께 컴퓨터 과학, 수학, 하드웨어의 발전으로 새롭고 효율적인 SNARK가 탄생하여 우리 사회를 변화시킬 수 있는 많은 응용 프로그램의 문이 열렸습니다. 연구원과 엔지니어는 증명 크기, 메모리 사용량, 투명성 설정, 포스트 퀀텀 보안, 증명 시간 및 검증 시간에 중점을 두고 필요에 따라 SNARK에 대한 개선 및 조정을 제안했습니다.
처음에는 두 가지 주요 라인(SNARK 및 STARK)이 있었지만 서로 다른 증명 시스템의 장점을 결합하려고 노력하면서 둘 사이의 경계가 희미해지기 시작했습니다. 예를 들어, 다양한 산술 체계를 새로운 다항식 확약 체계와 결합합니다. 새로운 증명 시스템이 계속 등장하고 성능이 향상될 것으로 예상할 수 있으며, 일부 핵심 인프라를 변경하지 않고 도구를 쉽게 사용할 수 없다면 이러한 개발을 따라잡기 위해 적응하는 데 시간이 필요한 일부 시스템은 어려울 것입니다. .
위 내용은 영지식 증명에서 시대를 초월한 혁신이 등장한 실제 이유를 살펴보세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!