zk-SNARK: 간결한 비대화형 논증

zk-SNARK(영지식 간결 비대화형 지식 논증)는 다음 특성을 갖는 증명입니다. (1) 영지식입니다. (2) 간결합니다(증명이 매우 작고 계산 크기와 무관하게 검증이 빠름). (3) 비대화형입니다(단일 증명 문자열).

시그마 프로토콜은 간단한 명제(이산 로그를 알고 있다는 사실)에 사용할 수 있습니다. 복잡한 계산, 즉 "비공개 입력에 대해 이 함수를 올바르게 실행했다"는 사실을 증명하려면 범용 증명 시스템이 필요합니다. SNARK는 O(1)의 검증 시간으로 임의의 계산을 증명합니다.

계산은 먼저 유한체 위의 덧셈 및 곱셈 게이트로 이루어진 방향성 비순환 그래프인 산술 회로로 표현합니다. 예를 들어 x=3을 공개하지 않고 x^3 + x + 5 = 35를 만족하는 x를 알고 있음을 증명할 수 있습니다. 이 회로에는 약 5개의 게이트가 있습니다.

산술 회로는 z가 모든 와이어 값으로 이루어진 벡터일 때 (A*z)*(B*z) = C*z를 만족하는 제약 집합인 R1CS로 변환됩니다. 각 곱셈 게이트는 하나의 제약이 됩니다. 증명자는 비공개 와이어를 공개하지 않고 모든 제약을 만족하는 z를 찾아야 합니다.

R1CS는 A(x), B(x), C(x)라는 다항식을 사용하는 QAP로 변환됩니다. 제약이 만족될 때에 한해 A(x)*B(x)-C(x)가 목표 다항식 t(x)로 나누어집니다. 증명자는 증인을 공개하지 않고 다항식 몫 H(x)를 알고 있음을 보여 줍니다.

Groth16(2016)은 가장 효율적인 범용 SNARK입니다. 신뢰 설정(CRS 생성) 후 증명자는 3개의 군 원소로 이루어진 증명을 출력합니다(BLS12-381에서 약 192바이트). 검증에는 3회의 페어링 연산이 필요합니다. 회로 크기와 무관하게 증명 크기는 일정합니다.

Groth16은 회로마다 신뢰 설정이 필요합니다. 독성 폐기물(무작위 비밀)을 생성하고, 공통 참조 문자열을 계산한 다음 독성 폐기물을 폐기합니다. 폐기물이 남아 있으면 공격자가 증명을 위조할 수 있습니다. 다자간 의식(Powers of Tau)은 신뢰를 분산합니다.

PLONK(2019)는 범용 신뢰 설정을 사용합니다. 하나의 의식으로 크기 제한 이하의 모든 회로를 처리할 수 있으므로 회로별 설정이 필요하지 않습니다. 절충점은 Groth16보다 증명이 약간 더 크다는 것입니다. ZK-EVM 구현(Polygon Hermez, zkSync Era)에 사용됩니다.

STARK(확장 가능한 투명 지식 논증)는 신뢰 설정이 필요 없고 해시 함수를 사용하며 양자 내성을 갖습니다. 절충점은 증명이 더 크다는 것입니다(200바이트에 비해 수십 KB). StarkWare/StarkNet과 Cairo 언어에 사용됩니다. SNARK는 더 작고 STARK는 양자에 안전합니다.

Groth16은 쌍선형 페어링을 사용합니다. e: G1 × G2 → GT이며, e(a*P, b*Q) = e(P,Q)^{ab}입니다. 이를 통해 값을 공개하지 않고 지수에서 다항식 항등식을 확인할 수 있습니다. BLS12-381 곡선은 효율적인 Groth16 페어링에 맞게 최적화되었습니다.

10^6개 게이트로 이루어진 회로에서 Groth16 증명을 생성하는 데 최신 CPU로 약 10초가 걸립니다. 검증에는 약 1ms가 걸립니다. 이러한 비대칭은 의도된 것입니다. 무거운 계산을 수행한 증명자가 작업을 맡고, 검증자(블록체인 노드)는 거의 작업하지 않습니다.

zk-SNARK는 일정한 크기의 증명으로 임의의 계산을 증명합니다. 처리 파이프라인: 계산 → 산술 회로 → R1CS → QAP → SNARK 증명. Groth16은 가장 효율적이지만 회로마다 신뢰 설정이 필요하고, PLONK는 범용 설정을 사용합니다. 다음 주제: 블록체인에서의 ZKP 응용