<aside> 🏎️ Formula Zero 는 Nonce Open Source Lab 소속으로, Tezos Foundation 의 지원을 받아 PoS 기반 블록체인의 Light Client를 연구하는 프로젝트입니다.
</aside>
여기서 지식이라 함은 보통 $R(x,w)$ 로 나타낸다. $x$ 는 공개 입력이며, $w$ 는 witness 라 하여 prover 만 아는 비공개 입력이다. 이 두 입력간의 특정한 관계 $R$ 을 만족한다는 것이 위에서 말하는 '지식', statement 라 한다. 비공개 입력인 $w$ 에 대해서 verifier 가 알 수 없기 때문에 Zero Knowledge 가 성립된다. $R$ 은 보통 NP 속성을 가지는데, 이는 $R$을 만족하는 $x,w$ 를 찾기 어렵지만, $x,w$ 를 알고 있으면 $R$을 만족하는지 평가하는 것은 쉽다는 것을 의미한다. (프로그래밍 관점에서 $R$ 은 하나의 함수, 연산이라고 보면 된다.) Prover 는 Verifier 에게 $w$ 를 직접 전달하는 대신, 해당 주장에 대한 증명 proof 를 생성하며 전달하면, Verifier 는 $w$ 자체는 모르지만, Prover 가 $R(x,w)$를 만족하는 $w$ 를 알고 있음을 파악할 수 있는 것이다.
일반 연산을 위한 zk-SNARK 구성을 생각해보자. 먼저 입력들에 대한 연산을 NP Statement(Language)로 변환해야한다. 가장 널리쓰이는 방식이 해당 연산에 대한 circuit 을 구축하는 것이며, circuit 을 이루는 원소들의 종류에 따라 arithmetic (+,*) 또는 boolean (AND,OR) circuit 으로 나뉘게 된다. 주어진 입력값이 해당 circuit을 만족하는지를 보이기 위해 circuit 을 constraint system 으로 변형하고 이를 information-theoretic compilation을 통해 proof system 으로 나타낼 수 있다. Contraint system 에는 R1CS 뿐만 아니라 최근에는 Polynomial 로 변환시키는 scheme 도 존재하다. (ex. Sonic, Marlin, Plonk) 이러한 Polynomial 을 짧은 값의 interaction 을 통해 증명하는 scheme 으로 Kate Pairing, DARK, FRI 등이 있다. 각 scheme 들의 조합으로 다양한 Proof system 구축이 가능하다.
이러한 Proof System을 구축하여 실제 Proof 를 생성하는 것은 Prover 입장에서 매우 비싼 연산이다. 영지식증명이 최근까지도 Practical 하지 않다고 여겨진 점이 바로 이 때문이다. 이 연산의 오버헤드를 줄이기 위해 연산에 필요한 파라미터들을 '전처리 pre-processing' 하는 방식을 생각할 수 있다. 바로 Trusted Setup 단계이다. 즉 믿을만한 제 3자에 의해 관계 $R$ 의 proof 생성에 필요한 CRS (common reference string)을 구축하고 이를 Prover 및 Verifier 가 서로 공유함으로써, Proof System 에서 필요한 연산을 줄일 수 있는 개념이다. 다만 Trusted Setup 은 특정 $R$ 에 의존적으로 생성되기에 $R$ 이 바뀔때 마다 새로운 CRS 생성이 필요하다는 한계가 존재하였다. 이를 극복하기 위해 Universal, 즉 범용적이고, Updatable, 즉 필요에 따라 갱신해서 쓸 수 있는 CRS 를 생성하는 scheme 또한 제안되었다. 한번의 Trusted Setup 으로 여러 $R$ 에서 범용적으로 쓰이며 필요에 따라 갱신해서 쓸 수 있는 것이다. 다만 누구를 'Trusted'하는 것 또한 Security Assumption 이므로 이 조차 필요로 하지 않는 Proof system 이 STARK (Succinct 'Transparent' ARgument of Knowledge) 계열이다.
관계 $R$ 은 매우 복잡한 연산으로 구성될 수 있으며 Heterogeneous 한 성격의 연산 조합일 가능성이 크다. 예를 들어 $H,A,B$ 가 입력으로 주어졌을 때, $R(H,A,B) : H=sha256(A \cdot B)$ 이라면 이는 sha256이라는 해시함수와 곱셈의 조합이다. 물론 위에서 언급한 하나의 Proof system 으로 해당 $R$ 을 구축할 수 있다. 하지만 이는 최적의 상태가 아니다. 왜냐하면 해시함수는 arithmetic circuit 보다는 boolean circuit 기반의 proof system 에서 proof 생성이 더 효율적인 반면, 곱셉은 boolean 보다는 arithmetic 으로 구축하는 것이 더욱 효율적이다. $R$ 에 하나의 Proof System 을 적용하는 것이 아닌 $R$ 내의 존재하는 각 연산들의 종류에 따라 최적화된 Proof System 을 구축하고 이들을 연결할 수 있다면 Proof 생성에 필요한 연산에 있어서 성능 향상을 꾀할 수 있다. 즉 위 예에서 곱셈의 arithmetic circuit 의 출력값과 해쉬 함수의 boolean circuit의 입력값이 동일하다는 '증명'이 존재하면 된다. 이러한 scheme 이 바로 Commit-and-Prove SNARK 이다. 동일해야하는 각 circuit 의 입출력값에 대해 값 자체를 노출하는 것이 아는 해당 값의 commitment 를 활용함으로써 두 값이 동일함을 증명하고, 이를 통해 heterogeneous 한 연산의 연결고리를 구축하는 것이다.
그래서 CP-SNARK는 관계 $R(x,w)$를 만족하는 지식을 알고 있음을 증명하는 것에 더하여 한가지 조건이 추가된 SNARK로 볼 수 있다.