편집자 주 : 16z 암호화는 "총포", 우리의 다오 캐논 작년에 우리에게 NFT 캐논 더 일찍 (그리고 그 전에 우리의 원본 크립토 캐논) — 당사에 가입해야 합니다. web3 주간 뉴스레터 추가 업데이트 및 기타 선별된 리소스를 확인하세요.
그래서 below, 우리는 모든 것을 이해하고 더 깊이 이해하고 구축하려는 사람들을 위해 일련의 리소스를 선별했습니다. 제로 지식: 블록체인 확장성의 열쇠를 쥐고 있는 강력하고 기초적인 기술로, 개인 정보 보호 애플리케이션의 미래와 다가올 수많은 혁신을 나타냅니다. 추가할 고품질 조각에 대한 제안 사항이 있으면 @로 알려주십시오.a16zcrypto.
영지식 증명 시스템은 수십 년 동안 존재해 왔습니다. 1985년 Shafi Goldwasser, Silvio Micali 및 Charles Rackoff의 소개는 암호화 분야에 혁신적인 영향을 미쳤으며, Goldwasser와 Micali에게 수여된 ACM Turing Award에서 인정받았습니다. 2012. 오늘날 crypto/web3의 이론에서 실제 및 응용으로의 이동을 포함하여 이 작업이 수십 년 동안 만들어졌기 때문에 우리는 또한 캐논 시리즈 XNUMX부에서 처음으로 공유합니다(현재는 아래에 포함됨). 주석이 달린 읽기 목록 저스틴 탈러, 아래 파트 XNUMX에 이어.
감사의 말: Michael Blau, Sam Ragsdale, Tim Roughgarden에게도 감사드립니다.
기초, 배경, 진화
이 문서 중 일부는 오늘날 제로 지식 증명으로 해결되는 주요 발전 또는 문제의 개요를 포함하여 일반적으로 암호화에 관한 것입니다(모든 제로 지식 자체가 아님).
암호화의 새로운 방향(1976)
Whitfield Diffie 및 Martin Hellman 작성
https://ee.stanford.edu/~hellman/publications/24.pdf
디지털 서명 및 공개 키 암호 시스템을 얻는 방법
Ronald Rivest, Adi Shamir, Leonard Adelman
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf
공개 키 암호 시스템을 위한 프로토콜(1980)
랄프 머클
http://www.merkle.com/papers/Protocols.pdf
안전하지 않은 채널을 통한 보안 통신(1978)
랄프 머클
https://www.merkle.com/1974/PuzzlesAsPublished.pdf
암호화에서 타원 곡선 사용(1988)
빅터 밀러
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf
대화형 증명 시스템의 지식 복잡성(1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf
전산 방음(2000)
실비오 미칼리
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf
추출 가능한 충돌 저항에서 지식에 대한 간결한 비대화형 주장[SNARK], 그리고 다시(2011)
니르 비탄스키, 란 카네티, 알레산드로 키에사, 에란 트로머
https://eprint.iacr.org/2011/443.pdf
셔플의 정확성을 위한 효율적인 영지식 논증(2012)
스테파니 바이엘과 옌스 그로스
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf
von Neumann Architecture(2013)를 위한 간결한 비대화형 영지식
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
https://eprint.iacr.org/2013/879.pdf
확장 가능하고 투명하며 사후 양자 보안 계산 무결성(2018)
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev
https://eprint.iacr.org/2018/046.pdf
(거의) 시간 및 공간 오버헤드가 최소화된 공개 동전 영지식 인수(2020)
Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum 및 Pratik Soni 작성
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645
개요 및 소개
증명, 논증, 영지식 — 검증 가능한 컴퓨팅 및 대화형 증명 및 인수, 영지식(증명이 자신의 유효성 이외의 정보를 공개하지 않는 경우)을 포함하여 증명자가 요청된 계산을 올바르게 수행했다는 보증을 증명자에게 제공할 수 있도록 하는 암호화 프로토콜에 대한 개요 . Zk 인수는 암호학에서 무수히 많은 응용 프로그램을 가지고 있으며 지난 XNUMX년 동안 이론에서 실제로 도약했습니다.
저스틴 탈러
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
영지식 증명을 위한 모델의 진화 — Meiklejohn(University College London, Google)이 개발을 주도하는 애플리케이션, 이러한 새로운 상호 작용을 포착하기 위해 등장한 다양한 모델, 달성할 수 있는 구성 및 작업을 살펴보는 영지식 증명 검토 할 일이 남았습니다.
사라 메이클존
https://www.youtube.com/watch?v=HO97kVMI3SE
ZK 화이트보드 세션 — 입문 모듈
Dan Boneh 외
https://zkhack.dev/whiteboard/
zkps를 사용한 암호화에 대한 보안 및 개인 정보 보호 — 실제로 영지식 증명을 개척합니다. zkps가 무엇이고 어떻게 작동하는지... 라이브 무대 "데모" 포함
주코 윌콕스
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/
주요 기술 주제, 설명 — 일반적으로 제로 지식의 정의 및 의미 포함
조 보노, 팀 러프가든, 스콧 코마이너스, 알리 야히아, 크리스 딕슨
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos
다가오는 개인 정보 보호 계층이 깨진 웹을 수정하는 방법
하워드 우
https://future.com/a-privacy-layer-for-the-web-can-change-everything/
zkSNARK 소개
하워드 우, 안나 로즈와 함께
https://zeroknowledge.fm/38-2/
zk-SNARK가 작동하는 이유와 방법: 확실한 설명
Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf
영지식 증명 소개
프레드릭 해리슨과 안나 로즈
https://www.zeroknowledge.fm/21 [+ 다른 곳에서 요약 작성 여기에서 지금 확인해 보세요.]
Zk-SNARKs: 후드 아래
비탈릭 부테린
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
일부 1, 일부 2, 일부 3
분산 속도 — 영지식 증명, 분산 하드웨어의 발전
엘레나 버거
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/
최첨단 zk 연구 — Ethereum Foundation의 zk 연구원과 함께
메리 말러, 안나 로즈, 코비 구르칸
https://zeroknowledge.fm/232-2/
zk 연구 탐색 — DFINITY의 연구 이사와 함께; Groth16과 같은 발전 뒤에도
Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/
SNARK 연구 및 교육학 — ZCash 및 Starkware의 공동 창립자 중 한 명과 함께
알레산드로 키에사, 안나 로즈
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/
심층 분석, 빌더 가이드
확률 증명의 기초 — 대화식 증명 등의 5개 단원이 포함된 코스
알레산드로 키에사
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC
STARK - 파트 I, II, III
비탈릭 부테린
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html
STARK의 해부학 — STARK 증명 시스템의 역학을 설명하는 XNUMX부로 구성된 튜토리얼
앨런 세피에니에크
https://aszepieniec.github.io/stark-anatomy/
SNARK 디자인, 1부 — 설문 조사, 롤업에서의 사용 등
저스틴 탈러
https://www.youtube.com/watch?v=tg6lKPdR_e4
SNARK 디자인, 2부 — 롤업, 성능, 보안
저스틴 탈러
https://www.youtube.com/watch?v=cMAI7g3UcoI
SNARK 성능 측정 — 프론트엔드, 백엔드 등
저스틴 탈러
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
PLONK 이해하기
https://vitalik.ca/general/2019/09/22/plonk.html
PLONK 영지식 증명 시스템 — PLONK 작동 방식에 대한 12개의 짧은 비디오 시리즈
데이비드 웡
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC
AIR에서 RAP로 — PLONK 스타일 산술이 작동하는 방식
아리엘 가비종
https://hackmd.io/@aztec-network/plonk-arithmetiization-air
PLONK 및 Plookup의 다중 집합 검사
아리엘 가비종
https://hackmd.io/@arielg/ByFgSDA7D
헤일로2 디자인 — ECC에서
https://zcash.github.io/halo2/design.html
플롱키2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf
애플리케이션 및 튜토리얼: 개념 증명, 데모, 도구 등
적용된 zk — 학습 리소스
0xPARC에 의해
https://learn.0xparc.org/materials/intro
zkSNARK를 위한 온라인 개발 환경 — zkREPL, 브라우저 내에서 Circom 도구 스택과 상호 작용하기 위한 새로운 도구 세트
케빈 곽
https://zkrepl.dev (+ 설명 스레드 여기에서 지금 확인해 보세요.)
XNUMX에서 영웅까지의 이차 산술 프로그램
비탈릭 부테린
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
zkEVM에서
Alex Gluchowski와 Anna Rose와 함께
https://zeroknowledge.fm/175-2/
다양한 유형의 zkEVM
비탈릭 부테린
https://vitalik.ca/general/2022/08/04/zkevm.html
ZK 머신 러닝 — 신경망을 SNARK에 넣기 위한 튜토리얼 및 데모
Horace Pan, Francis Ho, Henri Palacci
https://0xparc.org/blog/zk-mnist
ZK 언어에서
Alex Ozdemir와 Anna Rose와 함께
https://zeroknowledge.fm/172-2/
다크 포레스트 — zk 암호화를 게임에 적용 — 완전히 분산되고 지속적인 RTS(실시간 전략) 게임
https://blog.zkga.me/announcing-darkforest
엔지니어를 위한 ZKP — 다크 포레스트 ZKP 살펴보기
https://blog.zkga.me/df-init-circuit
제로 지식에 대한 다이빙
엘레나 나돌링크스키, 안나 로즈, 제임스 프레스위치
https://zeroknowledge.fm/182-2/
zkDocs: 영지식 정보 공유
Sam Ragsdale과 Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/
지식 증명이 전혀 없는 개인 정보 보호 암호화 에어드롭
샘 랙스데일
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/
온체인 신뢰할 수 있는 설정 행사 -
발레리아 니콜라엔코와 샘 랙스데일
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/
암호화폐 규제, 불법 금융, 개인 정보 보호 등 – 규제/준수 맥락에서 제로 지식에 대한 섹션을 포함합니다. "개인 정보 보호"와 난독화 기술의 차이점
Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained
기타 자료
zkMesh 뉴스레터 — 최신 분산형 개인 정보 보호 기술, 개인 정보 프로토콜 개발 및 영지식 시스템을 공유하는 월간 뉴스레터
https://zkmesh.substack.com/
제로 지식 팟캐스트 — 최신 zk 연구 및 zk 애플리케이션 및 암호화 지원 개인 정보 보호 기술 구축 전문가
안나 로즈와 함께
https://zeroknowledge.fm/
...주제 및 연대순으로 주석이 달린 읽기 목록, Justin Thaler:
Linear PCP의 SNARK(회로별 설정이 있는 SNARK라고도 함)
짧은 PCP가 없는 효율적인 주장 (2007)
유발 이샤이, 에얄 쿠실레비츠, 라파일 오스트로프스키
약 2007년 이전에 SNARK는 주로 다음을 통해 설계되었습니다. 킬리안-미 칼리 "짧은" 확률로 확인 가능한 증명(PCP)을 취하고 머클 해싱 및 피아트-샤미르 변환을 통해 이를 간결한 인수로 "암호학적으로 컴파일"하는 패러다임입니다. 불행히도 짧은 PCP는 오늘날에도 복잡하고 비현실적입니다. 이 백서(IKO)는 동형 암호화를 사용하여 "길지만 구조화된" PCP로부터 간결한(투명하지 않은) 대화형 인수를 얻는 방법을 보여주었습니다. 이들은 짧은 PCP보다 훨씬 간단할 수 있으며 결과 SNARK는 훨씬 더 짧은 증거와 더 빠른 검증을 갖습니다. 이러한 주장은 처음에는 실용적인 효율성을 위한 잠재력이 있는 것으로 인식되었고, 후추. 불행히도 IKO의 주장에는 XNUMX차 시간 증명자와 XNUMX차 크기 구조화된 참조 문자열이 있으므로 대규모 계산으로 확장되지 않습니다.
PCP가 없는 XNUMX차 스팬 프로그램 및 간결한 NIZK (2012)
Rosario Gennaro, Craig Gentry, Bryan Parno 및 Mariana Raykova 작성
이 획기적인 논문(GGPR)은 IKO 접근 방식의 증명자 비용을 회로 크기의 XNUMX차에서 준선형으로 줄였습니다. 의 이전 작업을 기반으로 그로스 와 립마, IKO와 같은 대화식 인수가 아닌 페어링 기반 암호화를 통해 SNARK를 제공했습니다. 산술 회로 만족 가능성의 일반화인 현재 순위 1 제약 조건 만족(R1CS) 문제라고 하는 맥락에서 SNARK를 설명했습니다.
이 문서는 또한 상업적 배포(예: ZCash)를 본 최초의 SNARK의 이론적 토대 역할을 했으며 오늘날 인기 있는 SNARK(예: Groth16)로 직접 이어졌습니다. GGPR 주장의 초기 구현이 들어왔습니다. 자 타르 와 피노키오, 이후 변형에는 다음이 포함됩니다. C용 SNARK 와 BCTV. BCIOP 이러한 선형 PCP에서 SNARK로의 변환을 설명하는 일반적인 프레임워크를 제공했습니다(또한 부록 A 참조 자 타르) 다양한 인스턴스화를 설명합니다.
짝짓기 기반 비대화형 인수의 크기에 대하여 (2016)
옌스 그로스
구어체로 Groth16이라고 하는 이 논문은 오늘날에도 최첨단 구체적인 검증 비용을 달성하는 GGPR의 SNARK의 개선을 제시했습니다(증명은 3개의 그룹 요소이고 검증은 적어도 대중을 가정하는 XNUMX개의 페어링 작업에 의해 지배됩니다. 입력이 짧음). 보안은 일반 그룹 모델에서 입증됩니다.
보편적으로 신뢰할 수 있는 설정이 포함된 SNARK
PlonK: 지식의 에큐메니칼 비대화형 논증을 위한 라그랑주 기반의 순열 (2019)
Ariel Gabizon, Zachary Williamson 및 Oana Ciobotaru 작성
Marlin: 범용 및 업데이트 가능한 SRS로 zkSNARK 전처리 (2019)
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely 및 Nicholas Ward 작성
PlonK와 Marlin은 모두 Groth16의 회로별 신뢰할 수 있는 설정을 범용 설정으로 대체합니다. 이것은 4x-6x 더 큰 증명을 희생합니다. PlonK와 Marlin은 Groth16 및 이전 버전의 신뢰할 수 있는 설정 중에 회로별 작업을 수행하여 발생하는 사전 처리 단계로 이동하는 것으로 생각할 수 있습니다. 시간 내에 신뢰할 수 있는 설정과 SNARK 증명 생성 중에.
이러한 방식으로 임의의 회로 및 R1CS 시스템을 처리하는 기능을 홀로그래피 또는 계산 커밋이라고 하며 다음에도 설명되어 있습니다. 스파르타의 (이 편집의 뒷부분에서 논의됨). 증명 생성 중에 더 많은 작업이 발생하기 때문에 PlonK 및 Marlin의 증명자는 주어진 회로 또는 R16CS 인스턴스에 대해 Groth1보다 느립니다. 그러나 Groth16과 달리 PlonK와 Marlin은 R1CS보다 더 일반적인 중간 표현으로 작동하도록 만들 수 있습니다.
SNARK의 주요 암호화 기본 요소인 다항식 약정 체계
다항식 및 해당 응용 프로그램에 대한 일정한 크기 약속 (2010)
Aniket Kate, Gregory Zaverucha 및 Ian Goldberg 작성
이 문서에서는 다항식 확약 방식의 개념을 소개했습니다. 일정한 크기의 약정과 평가 증명이 있는 일변량 다항식(일반적으로 KZG 약정이라고 함)에 대한 계획을 제공했습니다. 이 체계는 신뢰할 수 있는 설정(즉, 구조화된 참조 문자열)과 페어링 기반 암호화를 사용합니다. 오늘날 실제로 매우 인기가 있으며 위에서 논의한 PlonK 및 Marlin을 포함한 SNARK에서 사용됩니다(Groth16은 매우 유사한 암호화 기술을 사용함).
Fast Reed-Solomon Interactive Oracle 근접 증명 (2017)
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev
Reed-Solomon 테스트를 위한 IOP(Interactive oracle proof)를 제공합니다. 즉, 커밋된 문자열이 단변량 다항식의 평가 테이블에 가깝다는 것을 증명합니다. Merkle-hashing 및 Fiat-Shamir 변환과 결합하여 다항식 크기의 평가 증명이 있는 투명한 다항식 확약 체계를 생성합니다(참조 VP19 자세한 내용은). 오늘날 이것은 그럴듯하게 사후 양자 다항식 약속 체계 중에서 가장 짧습니다.
Ligero: 신뢰할 수 있는 설정이 없는 경량 하위 선형 인수 (2017)
Scott Ames, Carmit Hazay, Yuval Ishai 및 Muthuramakrishnan Venkitasubramaniam 작성
FRI와 유사하게 이 작업은 Reed-Solomon 테스트를 위한 IOP를 제공하지만 폴리로그 대신 제곱근 증명 길이를 사용합니다. 이론상의 일 Reed-Solomon 코드를 더 빠른 인코딩으로 다른 오류 수정 코드로 교체함으로써 모든 분야에서 기본적으로 작동하는 선형 시간 증명자를 얻을 수 있음을 보여주었습니다. 이 접근 방식은 다음에서 개선되고 구현되었습니다. 분류 와 오리온, 최첨단 증명 성능을 제공합니다.
Bulletproofs: 기밀 거래 등에 대한 짧은 증거 (2017)
Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille 및 Greg Maxwell
에 의해 이전 작업을 정제 BCCGP, Bulletproofs는 대수 증명 크기이지만 선형 검증자 시간으로 이산 대수를 계산하는 경도를 기반으로 투명한 다항식 확약 방식(사실 내적 인수라고 하는 일반화)을 제공합니다. 이 계획은 투명성과 짧은 증명으로 인해 오늘날에도 여전히 인기가 있습니다(예: ZCash Orchard 및 Monero에서 사용됨).
Dory: 일반화된 내부 제품 및 다항식 약속에 대한 효율적이고 투명한 인수 (2020)
조나단 리
Dory는 Bulletproofs의 검증자 시간을 선형에서 로그로 줄이는 동시에 투명도와 대수 크기 증명(Bulletproof보다 구체적으로 더 큼) 및 투명도를 유지합니다. 페어링을 사용하고 SXDH 가정을 기반으로 합니다.
대화형 증명, 다중 증명자 대화형 증명 및 관련 SNARK
계산 위임: 머글을 위한 대화형 증명 (2008)
Shafi Goldwasser, Yael Tauman Kalai 및 Guy Rothblum 작성
이 문서 이전에는 범용 대화형 증명이 필요했습니다. 초다항 시간 증명자. 이 논문은 효율적인 병렬 알고리즘을 가진 모든 문제에 대해 다항식 시간 증명자와 준선형 시간 확인자를 사용하여 일반적으로 GKR 프로토콜이라고 하는 대화형 증명 프로토콜을 제공합니다(동일하게 대화형 증명은 깊이가 작은 모든 산술 회로에 적용됨).
스트리밍 대화형 증명으로 실제 검증된 계산 (2011)
Graham Cormode, Michael Mitzenmacher, Justin Thaler
이 논문(때때로 CMT라고 함)은 회로 크기의 XNUMX차에서 준선형으로 GKR 프로토콜의 증명자 시간을 줄였습니다. 범용 대화형 증명의 첫 번째 구현을 생성했습니다. 후속 작업 라인(피망, 탈러13, 기린및 천칭) 회로 크기가 준선형에서 선형으로 입증자의 런타임을 더욱 줄였습니다.
vSQL: 동적 아웃소싱 데이터베이스에 대한 임의 SQL 쿼리 확인 (2017)
Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, Charalampos Papamanthou
제목이 특정 응용 프로그램 영역(데이터베이스)을 나타내지만 이 문서의 기여는 더 일반적입니다. 특히, 대화식 증명을 다항식 확약 방식(다선형 다항식의 경우)과 결합하여 회로 만족성에 대한 간결한 인수를 얻을 수 있음을 관찰했습니다.
후 일 렌더링 된 논쟁은 영지식(zero-knowledge)이며 다선형 다항식에 대한 다른 확약 체계를 도입했습니다.
Spartan: 신뢰할 수 있는 설정이 없는 효율적인 범용 zkSNARK (2019)
스리나스 세티
다중 증명자 대화식 증명(MIP)과 다항식 확약 체계를 결합하여 회로 만족 및 R1CS에 대한 SNARK를 얻습니다. 클로버. 그 효과는 위에서 논의한 GKR 프로토콜과 같은 대화식 증명에서 파생된 것보다 짧은 증명으로 SNARK를 얻는 것입니다. PlonK 및 Marlin과 유사하게 Spartan은 사전 처리 및 SNARK 증명 생성을 통해 임의 회로 및 R1CS 시스템을 처리하는 방법도 보여줍니다.
Spartan은 다음의 다항식 확약 방식을 사용했습니다. 하이락스. 라고 불리는 후속 작품들 분류 와 오리온 Spartan의 MIP를 다른 다항식 확약 방식과 결합하여 선형 시간 증명자와 함께 최초로 구현된 SNARK를 생성합니다.
짧은 PCP 및 IOP
Polylog 쿼리 복잡성이 있는 짧은 PCP (2005)
Eli Ben-Sasson과 Madhu 수단
이 이론적인 작업은 검증할 계산 크기에서 준선형 증명 길이와 다대수 쿼리 비용(선형 검증기 시간에도 불구하고)을 가진 최초의 확률적으로 확인 가능한 증명(PCP)을 제공했습니다. PCP에서 SNARK로의 Kilian-Micali 변환에 이어, 이는 준선형 시간 증명자와 다로그 시간 검증자를 사용하여 SNARK를 향한 단계였습니다.
나중에 이론 작업 검증자 시간을 다로그로 줄였습니다. 이후 실제에 초점을 맞춘 작업은 이 접근 방식을 개선했지만 짧은 PCP는 오늘날에도 여전히 비현실적입니다. 실용적인 SNARK를 얻으려면, 후에 일 돌린 에 라고 불리는 PCP의 대화식 일반화 대화형 Oracle 증명 (IOP). 이러한 노력은 무료, 이 편집의 다항식 확약 섹션에서 논의된 인기 있는 다항식 확약 방식.
이 카테고리의 다른 작품은 다음과 같습니다 ZKBoo 그리고 그 후손들. 이것들은 간결한 증명을 달성하지 못하지만 좋은 상수 요인을 가지고 있으므로 작은 진술을 증명하는 데 매력적입니다. 그들은 다음과 같은 포스트 퀀텀 시그니처 제품군으로 이어졌습니다. 피크닉 이 그 된 최적화 in 몇몇의 일. ZKBoo는 MPC-in-head하지만 IOP를 생성합니다.
재귀적 SNARK
점진적으로 검증 가능한 계산 또는 지식 증명은 시간/공간 효율성을 의미합니다. (2008)
폴 발리언트
이 작업은 증명자가 계산을 실행하고 지금까지 계산이 정확했다는 증거를 항상 유지하는 IVC(증분 검증 가능 계산)의 기본 개념을 도입했습니다. SNARK의 재귀 구성을 통해 IVC를 구성했습니다. 여기서, 지식 건전성 SNARK의 속성은 재귀적으로 구성된 비대화형 인수의 건전성을 확립하는 데 필수적입니다. 이 논문은 또한 PCP 파생 SNARK에 대한 매우 효율적인 지식 추출기를 제공했습니다(Kilian-Micali 패러다임에 따라).
타원 곡선 주기를 통한 확장 가능한 제로 지식 (2014)
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
수행원 이론적 연구, 이 문서에서는 GGPR의 SNARK 변형의 재귀 응용 프로그램을 사용하여 간단한 가상 머신(TinyRAM, C용 SNARK 종이).
또한 타원 곡선 암호화를 사용하는 SNARK를 재귀적으로 구성하는 데 유용한 타원 곡선 주기의 개념을 도입했습니다.
신뢰할 수 있는 설정이 없는 재귀적 증명 구성 (2019)
Sean Bowe, Jack Grigg, Daira Hopwood 작성
이 작업(Halo라고 함)은 투명한 SNARK를 재귀적으로 구성하는 방법을 연구합니다. 투명한 SNARK의 검증 절차가 훨씬 더 비쌀 수 있기 때문에 이것은 불투명한 것을 구성하는 것보다 더 어렵습니다.
이것은 다음 촉발 선 of 일 와 같은 시스템으로 절정에 이르렀습니다. 신성 Groth16과 같은 불투명한 SNARK의 구성으로 얻은 것보다 우수한 최첨단 IVC 성능을 달성합니다.
어플리케이션
Zerocash: Bitcoin의 분산된 익명 지불 (2014)
Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza
다음을 포함한 이전 작업을 기반으로 구축 제로 코인 (와 피노키오 코인 동시 작업으로), 이 논문은 GGPR에서 파생된 SNARK를 사용하여 개인 암호 화폐를 설계합니다. ZCash로 이어졌습니다.
Geppetto: 검증 가능한 다목적 계산 (2014)
Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno 및 Samee Zahur 작성
Geppetto는 이더리움이 생성된 지 약 XNUMX년 후에 작성된 개인 스마트 계약 실행에 대한 관심 폭발보다 앞서 있습니다. 따라서 개인 스마트 계약 실행의 맥락에서 제시되지 않습니다. 그러나 SNARK의 제한된 깊이 재귀를 사용하여 신뢰할 수 없는 증명자가 실행 중인 프로그램 또는 실행되는 데이터에 대한 정보를 공개하지 않고 개인 데이터에 대해 개인(커밋/서명된) 컴퓨터 프로그램을 실행할 수 있도록 합니다. 따라서 다음과 같은 개인 스마트 계약 플랫폼에 대한 작업의 전신입니다. 젝스 [아래에서 묘사 되어진].
검증 가능한 ASIC (2015)
Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish
이 글은 신뢰할 수 없는 파운드리(2015년 기준, 최고급 파운드리를 보유한 국가는 XNUMX개국)에서 제조된 ASIC을 어떻게 안전하고 유익하게 사용하는지에 대한 문제를 고려합니다. 접근 방식은 빠르지만 신뢰할 수 없는 ASIC이 느리지만 신뢰할 수 있는 ASIC에서 실행되는 검증자에게 출력의 정확성을 증명하도록 하는 것입니다. 시스템의 총 실행 시간(즉, 증명자와 검증자 런타임의 합계에 데이터 전송 비용을 더한 값)이 순진한 기준선보다 작은 한 솔루션은 흥미롭습니다. -하지만 신뢰할 수 있는 ASIC. GKR/CMT/Allspice 대화식 증명의 변형을 사용하여 이 논문은 숫자 이론 변환, 패턴 일치 및 타원 곡선 연산을 비롯한 여러 근본적인 문제에 대해 순진한 기준선을 실제로 능가합니다. 이 작업은 일부 증명 시스템이 다른 것보다 하드웨어 구현에 더 적합함을 시사합니다. 하드웨어 구현을 위한 최적화된 증명 시스템이 현재 수신 중입니다. 많은 주의, 그러나 탐구해야 할 것이 많이 남아 있습니다.
증명할 수 있는 지연 기능 (2018)
Dan Boneh, Joseph Bonneau, Benedikt Bünz 및 Ben Fisch 작성
예를 들어 지분 증명 합의 프로토콜의 가능한 조작을 완화하는 것과 같이 블록체인 애플리케이션에서 널리 유용한 암호화 기본 형식인 검증 가능한 지연 기능(VDF) 표기법을 도입했습니다. SNARK(특히 증분 검증 가능한 계산의 경우)는 최신 VDF로 가는 경로를 제공합니다.
Zexe: 분산된 개인 컴퓨팅 활성화 (2018)
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, Howard Wu
Zexe는 개인 스마트 계약 플랫폼을 위한 디자인입니다. Zexe는 위에서 설명한 Zerocash의 확장으로 볼 수 있습니다. Zerocash를 사용하면 단일 응용 프로그램을 체인에서 실행할 수 있으며(사용자가 토큰을 전송할 수 있음) 사용자 데이터의 개인 정보(예: 토큰을 보내는 사람, 토큰을 받는 사람, 전송된 토큰 양 등)를 보호할 수 있습니다. Zexe는 많은 동일한 블록체인에서 실행되고 서로 상호 작용하기 위해 서로 다른 애플리케이션(스마트 계약). 트랜잭션은 오프체인에서 실행되고 올바른 실행의 증거는 체인에 게시됩니다. 데이터 개인 정보가 보호될 뿐만 아니라 기능 개인 정보도 보호됩니다. 이것은 각 거래와 관련된 증명이 거래가 속한 애플리케이션을 밝히지 않는다는 것을 의미합니다. Zexe의 보다 일반적인 엔지니어링 기여는 페어링 기반 SNARK의 효율적인 깊이 12 구성에 유용한 타원 곡선 그룹인 BLS377-1을 도입했다는 것입니다.
복제된 실행이 없는 복제된 상태 머신 (2020)
Jonathan Lee, Kirill Nikitin 및 Srinath Setty 작성
이것은 블록체인 확장성을 위한 롤업에 관한 몇 안 되는 학술 논문 중 하나입니다. 그것은 롤업이라는 용어를 사용하지 않습니다. 왜냐하면 그것이 학술 문헌 외부에 도입된 개념보다 선행하거나 동시대이기 때문입니다.
프런트 엔드(컴퓨터 프로그램에서 회로 만족, R1CS 등과 같은 중간 표현으로의 효율적인 변환)
RAM에서 위임 가능한 간결한 제약 조건 만족 문제로의 빠른 감소 (2012)
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer
현대적인 관점에서 이것은 가상 머신(VM) 추상화를 위한 실용적인 컴퓨터-프로그램-회로-SAT 변환에 대한 초기 작업입니다. 1970년대 후반부터 1990년대까지의 작업(예: 롭슨) 이 논문은 T 단계에 대한 VM 실행에서 크기 O(T*polylog(T))의 회로의 만족까지 결정론적 감소를 설명합니다.
후속 논문, 예: C용 SNARK 와 BCTV, VM 추상화를 통해 프론트 엔드를 계속 개발했으며 최신 인스턴스화에는 다음과 같은 프로젝트가 포함됩니다. 카이로, RISC 제로및 폴리곤 메이든.
증명 기반의 검증된 계산을 통해 실용성에 몇 걸음 더 다가갑니다. (2012)
Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg 및 Michael Walfish 작성
Ginger라고 하는 이 문서는 실용적인 프론트 엔드 기술에 대한 또 다른 초기 공헌입니다. Ginger는 조건부 및 논리 표현식, 비교 및 비트 분할을 통한 비트 산술, 기본 부동 소수점 산술 등과 같은 일반 프로그래밍 기본 요소를 위한 가젯을 도입했습니다. 이 가제트를 사용하여 고급 언어에서 저급 언어에 이르기까지 최초로 구현된 프론트 엔드를 제공했습니다. SNARK 백엔드가 적용될 수 있는 중간 표현(IR)인 산술 제약(현재 R1CS로 알려진 것과 유사).
"Fast Reductions" 논문과 그 후손들은 IR을 생성할 때 "CPU 에뮬레이터" 접근 방식을 사용하는 반면(즉, IR은 증명자가 지정된 단계 수에 대해 CPU의 전환 기능을 적용하여 특정 프로그램을 올바르게 실행하도록 강제합니다) , Ginger와 그 후손들은 보다 ASIC과 유사한 접근 방식을 취하여 증명자가 올바르게 실행한다고 주장하는 컴퓨터 프로그램에 맞게 조정된 IR을 생성합니다.
예를 들어, 뷔페 는 이러한 제어 흐름을 실행 중인 프로그램에 맞게 조정된 유한 상태 기계로 전환함으로써 ASIC 모델에서 복잡한 제어 흐름을 처리하는 것이 가능하고 이 접근 방식이 범용 CPU 에뮬레이터를 구축하는 것보다 훨씬 더 효율적일 수 있음을 보여줍니다. xJsnark 다중 정밀도 산술, RAM 및 ROM 최적화를 위한 효율적인 구성을 제공하고 Java와 유사한 고급 언어를 프로그래머에게 제공합니다. 이는 오늘날에도 여전히 널리 사용됩니다. 원 컴퓨터 프로그램을 R1CS로 컴파일하는 것은 프로그램 분석의 잘 알려진 기술과 밀접하게 관련되어 있으며 두 커뮤니티의 아이디어를 통합하는 컴파일러 구성 툴킷을 구축한다는 사실을 관찰했습니다("회로와 유사한 표현을 위한 LLVM"). ASIC 스타일 프런트 엔드에 기여한 초기 작업에는 다음이 포함됩니다. 피노키오 와 제페토.
"Fast-Reductions" 논문은 소위 "라우팅 네트워크"라고 하는 복잡하고 값비싼 구성을 사용했습니다. 기억력 검사 (즉, 정확성이 입증되고 있는 VM이 실행되는 동안 신뢰할 수 없는 증명자가 VM의 랜덤 액세스 메모리를 올바르게 유지하고 있는지 확인). 이 선택은 이와 같은 초기 작업이 프론트 엔드가 필요했던 PCP를 얻으려고 했기 때문에 이루어졌습니다. 두 비대화형 및 정보 이론적으로 안전합니다. 나중에 작업이라고 식료품 저장실 (전작의 뷔페 위에서 언급한 작업) 라우팅 네트워크 대신 Merkle-trees를 사용하여 대수적(즉, "SNARK 친화적") 해시 함수를 컴파일하여 효율성을 달성했습니다. 아즈타이, 제약 조건으로. 그 결과 "계산적으로 안전한" 프론트엔드가 탄생했습니다. 오늘날 SNARK 친화적인 해시 함수에 대한 대규모 연구 문헌이 있습니다. 포세이돈, 미엠씨, 철근 콘크리트, 구출수록.
증명자가 RAM을 올바르게 유지하고 있는지 확인하기 위한 최첨단 기술은 적어도 립톤 (1989)에 의해 메모리 검사에 사용 Blumet al. (1991). 이러한 기술은 본질적으로 증명자와 검증자 간의 상호 작용을 포함하지만 Fiat-Shamir 변환과 상호 작용하지 않게 렌더링할 수 있습니다. 우리가 아는 한, 그들은 실용적인 SNARK 프론트 엔드에 대한 문헌에 라는 시스템에 의해 소개되었습니다. vRAM.
순열 불변 핑거프린팅 기술은 이제 예를 들어 가상 머신 추상화를 위한 많은 프런트 엔드 및 SNARK에서 사용됩니다. 카이로. 밀접하게 관련된 아이디어는 오늘날 실제로 널리 사용되는 아래 두 작품에서 관련 맥락에서 다시 나타납니다.
정확한 프로그램 실행을 위한 거의 선형에 가까운 영지식 증명 (2018)
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen 및 Mary Maller 작성
Plookup: 조회 테이블을 위한 단순화된 다항식 프로토콜 (2020)
아리엘 가비종과 재커리 윌리엄슨
프론트 엔드에 대한 초기 작업은 필드 요소를 비트로 나누고 이러한 비트에 대한 작업을 수행한 다음 "패킹"하여 회로 및 관련 IR 내부에서 "비산술" 연산(예: 범위 검사, 비트 연산 및 정수 비교)을 나타냅니다. 결과를 단일 필드 요소로 되돌립니다. 결과 회로의 크기 측면에서 이것은 연산당 대수 오버헤드를 초래합니다.
위의 두 가지 작업(BCGJM 및 Plookup)은 상각된 의미에서 회로 내에서 이러한 작업을 보다 효율적으로 표현하기 위한 영향력 있는 기술(소위 "룩업 테이블"을 기반으로 함)을 제공합니다. 대략적으로 말하자면, 프론트엔드 설계자가 선택한 일부 매개변수 B의 경우, 이는 증명자가 암호학적으로 추가 작업을 수행하는 비용으로 B의 대수 인수만큼 회로의 각 비산술 연산을 나타내는 데 필요한 게이트 수를 줄입니다. 길이가 대략 B인 "advice" 벡터.
