[zk-SNARK 5.] Non-interactive proving system

앞서 Prover가 Verifier에게 특정 QAP의 satisfying assignment를 알고 있음을 interactive하게 증명하는 Pinocchio Protocol에 대해서 살펴 보았습니다. zk-SNARK의 또다른 핵심적인 특징은 Non-interactive하게 동작한다는 것인데, 이를 위해서 CRS (Common Reference String) 모델을 사용합니다.

Common Reference String

기존의 interactive한 protocol에서는 Verifier가 random $x$-좌표 $s$와 random shift 값 $\alpha$를 선택한 후, 다음 값들을 Prover에게 전달했습니다.

위 값들을 이용해 Prover는 QAP를 만족하는 다항식의 hiding 값을 계산할 수 있었습니다. 그런데 만약 $s$와 $\alpha$ 값이 노출된다면, QAP를 만족하는 다항식을 몰라도 valid한 proof를 생성해 낼 수 있습니다. 즉 Prover가 생성한 proof는 Prover와, $s$와 $\alpha$ 값을 제공한 Verifier 사이에서만 유효하고, 다른 Verifier를 convince하기 위해서는 다시 증명 과정을 거쳐야만 합니다. 이는 기존의 protocol이 non-interactive하게 작동할 수 없음을 의미합니다.

Protocol이 non-interactive하게 작동하기 위해서는 신뢰할 수 있는 어떤 third party가 $s$, $\alpha$ 값을 선택해 이들을 hiding한 후, $s$, $\alpha$ 값을 반드시 삭제해야 합니다. 이후 Prover는 다수의 Verifier를 convince하기 위해 third party가 생성한 $s$, $\alpha$ hiding 값들을 이용해 proof를 생성하면 됩니다.

Third party가 생성한 이 값들을 Common Reference String이라고 하고, 생성하는 과정을 Trusted Setup이라고 명명합니다. $s$, $\alpha$ 값들은 hiding된 후 반드시 삭제돼야 하는 값들이기 때문에, toxic waste라고 부릅니다.

Non-interactive Protocol

zk-SNARK는 다음과 같이 non-interactive하게 작동합니다.

먼저, trusted setup은 다음과 같이 이루어집니다. Trusted party가 random한 값 $s$, $\alpha$를 선택한 후에, 다음 값들을 생성합니다. 이 때 사용되는 Homomorphic Hiding 함수는 linear combination에 대해서 homomorphic하고, pairing을 지원합니다.

위 값들이 CRS가 되며, CRS를 publish합니다. 그리고 $s$, $\alpha$ 값은 삭제합니다.

Prover가 QAP에 대한 satisfying assignment $(s_1, \dots, s_n)$을 알고 있다고 하겠습니다. Prover는 CRS를 이용해 다음과 같이 proof를 생성합니다.

Verifier는 다음과 같은 과정을 통해 proof를 검증합니다.

먼저, $\alpha$-pair check를 합니다. 중요한 것은 Verifier는 $\alpha$ 값을 모르지만, pairing을 통해 다음 관계가 성립하는지 확인할 수 있습니다. Pairing 함수를 $e$, 그리고 Homomorphic Hiding 함수가 정의된 타원곡선 상의 group의 generator를 $G$라고 명명하겠습니다.

마지막으로, 다항식들이 QAP의 조건을 만족하는지 확인합니다.

마치며

이번 글에서는 zk-SNARK가 어떻게 non-interactive하게 작동하는지 알아 보았습니다. 이 글을 마지막으로 zk-SNARK 시리즈는 완결하도록 하겠습니다. zk-SNARK의 단점으로는 QAP 별로 CRS가 달라져서 별도의 Trusted Setup이 필요하다는 것인데, 이 문제를 해결하기 위해 universal하고 updatable한 Trusted Setup 과정을 도입합니다. 그리고 어떤 다항식의 evaluation을 증명하기 위해 polynomial commitment라는 방법을 사용합니다. 또한 zk-SNARK에서 사용하는 arithmetization을 개선시킨 새로운 방법인 PLONK가 존재합니다. 추후 시리즈에서 PLONK와, polynomial commitment에 대해서 연재하도록 하겠습니다.