<aside> 🏎️ Formula Zero 는 Nonce Open Source Lab 소속으로, Tezos Foundation 의 지원을 받아 PoS 기반 블록체인의 Light Client를 연구하는 프로젝트입니다.

</aside>

zk-SNARK의 종류

zk-SNARK 는 Prover가 특정 Statement 가 True 임을 증명하는 Proof 를 생성하고 Verifier가 이를 검증하는 데 있어서 Prover 와 Verifier 간에 사전에 공유하는 방식에 따라 3가지로 분류할 수 있다

• Trusted Setup : 믿을 만한 제 3자에 의해 CRS (Common Reference String, 공용키) 생성하고 이를 기반으로 Proof 를 생성한다. 일종의 사전처리(Pre-Processing) 과정이며, 사전 처리로 인해 실제 증명과 검증 단계가 간소화되는 효율을 얻는다. 이 과정에서 사용된 비밀 정보(Toxic waste)는 제 3자가 아무도 알 수 없도록 파기해야 하는데, 만약 누설이 될 경우 Prover 는 실제 맞지 않는 연산값으로 Proof 를 생성할 수 있게 된다. (False Positive) Pinocchio, Groth16 등이 이에 기반하며, Statement가 변경되면 Trusted Setup은 새로 진행해야 한다. 여기서 CRS는 SRS (Structured Reference String) 으로도 불린다.
• Universal (and Updatable) : Trusted Setup 을 진행하는 제 3자는 "믿을 만 하다"는 것을 공개적으로 증명하기 위해 복잡한 Ceremony 등을 거치게 된다. 이로 인해 Statement 변경 마다 Setup을 매번 진행하는 것은 실질적으로 무리가 있다. 이런 단점을 해결하기 위해 이미 생성된 CRS 를 업데이트 하여 변경된 Statement 에서 활용할 수 있도록 하는 것이 바로 Universal Setup 이다. 업데이트라 함은 임의의 수를 적용하여 새로운 CRS 를 만들어 내는 것이다. sonic, marlin, plonk 가 이 setup 에 기반하며 유연성, 자유도 및 적용성을 높였다.
• Transparent : 위에서 언급한 두 방식과는 달리 CRS 자체가 존재하지 않는다. Proof 생성을 위해 해시함수만을 활용하며 대표적으로 zk-STARK 가 있다. 여기서 CRS 는 URS (Uniform Random String) 또는 RRS (Random Reference String)으로도 불린다.

특정 Statement, 즉 일반적으로 함수에서 SNARK 를 기반으로 Proof 를 생성하는 과정은 다음과 같다.

• Arithmetization : 함수 f() 를 +, x 의 게이트로 이뤄진 회로 Circuit 으로 변환한다. (Computation ⇒ Constraint System)
• Information-Theoretic Compilation : Circuit 을 다항식 (Polynomial) 형태로 변환한다. (Constraint System ⇒ (Unconditionally sound) Proof System)
  • Sonic, Marlin, Plonk 가 이 단계에 해당하며, Proof System 에서 Front-End 라 할 수 있다.
  • Plonk 가 다항식을 제일 적게 사용한다.
• Cryptographic Compilation : 다항식을 SNARK, 즉 간결한(Succinct) 증명으로 변환한다. (Proof System ⇒ SNARK)
  • 긴 길이의 다항식을 짧은 값의 interaction 을 통해서 증명하는 것으로 Polynomial Commitment 를 수행하는 Kate Pairing, DARK, FRI 가 이 단계에 해당한다. Back-end 로 볼 수 있다.
  • Kate Pairing 은 Universal Trusted Setup 기반으로 Proof size 가 제일 작으며, DARK 는 Transparent 기반이다. FRI 는 해시함수만 사용하기에 퀀텀 저항성을 갖는 특징이 있다.

위에서 언급된 Front-end 와 Back-end 의 조합으로 다양한 Proof System 이 가능하다. 예를 들어, 최근 Starkware 에서 발표한 Cairo 의 경우 Plonk와 FRI 의 조합이다.

Polynomial Commitment

Prover가 Verifier 에게 특정 Statement 가 True 임을 증명하는 방법은 간단하게 해당 Statement 를 표현하는 다항식들을 다 전달하면 된다. 하지만 이럴 경우 효율적이지 않으므로, 다항식을 짧은 숫자로 표현하면서도 긴 다항식을 나타내는 것이 맞다는 것을 보장하는 증명 방법이 Polynomial Commitment 이다. 보통 Interactive Proof, 즉 Prover 와 Verifier 간에 메시지들을 주고 받음으로써 증명하게 된다. Prover 가 다항식 f(X)에 대한 Polynomial Commitment 를 Verifer 에게 전달하고 Verifier 는 임의의 z 값에 대한 다항식의 Evaluation f(z) 를 요청한다. Prover 는 f(z) 를 계산하고, f(z) 가 정확하다는 Proof 를 Verifier 에게 제공한다. 처음 전달한 Polynomail Commitment 는 f(z)에 대한 Proof 검증시에 필요한 정보를 전달하기에 일종의 오라클 (Oracle) 역할을 한다. 이와 같은 과정을 Polynomial IOP (Interfactive Oracle Proof) 라고 하며 요즘 대부분의 SNARK 가 이를 기반으로 한다.