“Updatable and Universal CRS with applications to zk-SNARK” 정리
Nov 3 · 3 min read
Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, Ian Miers, in Crypto 2018.
문제 정의
- 기존의 zk-SNARK 시스템에서 CRS는 Relation에 종속되어 생성되기 때문에 매번 새롭게 Setup이 필요하다. → Universal Setup이 필요
- CRS를 Trusted Party가 생성한다. → Subvertible Setup이 필요
* Proof들은 공유된 CRS를 이용해서 생성 및 검증되는데, zero knowledge를 만족하기 위해 CRS를 생성할 때 simulation trapdoor를 생성하고, 버리게 된다. 만약 Setup을 한 주체가 honest하지 않아 trapdoor를 버리지 않고 저장해놓는다면 false proof를 언제나 생성할 수 있게 된다.
Subvertible Setup
Setup generator가 직접 setup하지 않고, Adversary로부터 CRS를 받고, 이를 verify한 뒤 사용한다. 따라서, Subvertible Setup이 가장 이상적이나, subversion soundness와 standard zero-knowledge는 동시에 만족될수 없다.
따라서 이 논문에서는 Updatable Setup을 제안하고, 이러한 updatable soundness는 subversion zero-knowledge와 동시에 만족될수 있기 때문에, updatable zero-knowledge와도 동시에 만족될 수 있다.
Updatable Setup


- Monomial 기법을 이용해서 updatably sound한 scheme을 만드는 것은 어렵지 않으나[Gro10b], 이렇게 하기 위해서는 quadratic-sized reference string이 필요하고, 즉, quadratic prover complexity를 야기한다.
- 따라서 이 논문에서는 quadratic-sized universal CRS에서 linear-sized relation-dependent CRS를 derive해서 사용하는 scheme을 제안하고 있고, 그렇기 때문에 본 논문에서 prover는 linear complexity를 가진다.


