재귀 SNARKs 설명: 증명이 다른 증명을 검증하는 방법

Source: Dev.to

증명이 다른 증명을 검증할 수 있다면?

대부분의 영지식 시스템에서는 검증자가 하나의 증명을 하나의 명제에 대해 검증합니다. Recursive SNARK는 이 모델을 깨뜨립니다: 증명이 스스로 다른 증명을 검증할 수 있어, 검증된 연산의 체인—또는 심지어 트리—를 만들 수 있습니다.

이는 단순한 이론적 호기심이 아닙니다. 재귀적 구성은 수천 개의 트랜잭션을 하나의 온‑체인 증명으로 배치하는 zkRollup의 핵심 메커니즘이며, Nova, Halo 2, SP1과 같이 점진적으로 검증 가능한 연산(IVC)을 구현하는 시스템의 핵심이기도 합니다.

작동 원리

표준 SNARK는 다음을 증명합니다:

"I know a witness w such that C(x, w) = true."

재귀 SNARK는 더 강력한 것을 증명합니다:

"I know a witness w **and** a valid proof π of a prior statement, and both check out."

핵심은 검증 회로를 증명 회로 안에 인코딩하는 것입니다. 증명자는 이전 검증자를 하위 연산으로 실행한 뒤, 새로운 연산과 이전 검증이 모두 올바름을 증명합니다.

이 과정은 비용이 많이 듭니다. SNARK 검증은 타원곡선 페어링이나 다항식 평가를 포함하는데, 이를 산술 제약으로 인코딩하면 회로 크기가 급격히 늘어납니다. (2019년 Halo에서 시작된) 축적 스킴(accumulation schemes) 이라는 획기적인 아이디어는 비싼 페어링 검사를 연기하고, 여러 단계에 걸쳐 축적한 뒤 마지막에 한 번만 검증하도록 했습니다.

왜 중요한가

압축

zkRollup이 10 000개의 트랜잭션을 처리한다고 가정합니다. 재귀가 없으면 증명은 10 000개 전체를 한 번에 커버해야 하므로 회로가 거대해집니다. 재귀를 사용하면 각 블록 증명이 이전 블록 증명과 새로운 트랜잭션을 검증합니다. 최종 증명은 히스토리 길이에 관계없이 일정한 크기를 유지합니다.

병렬성

재귀 트리를 이용하면 독립적인 가지를 동시에 증명한 뒤 병합할 수 있습니다. 이것이 SP1과 RISC Zero가 대규모 프로그램에 대해 실용적인 증명 시간을 달성하는 방식입니다.

상호운용성

증명 시스템이 다른 증명 시스템의 증명을 검증할 수 있습니다. 이를 통해 체인 A가 체인 B에서 생성된 증명을 체인 B의 검증자를 신뢰하지 않고도 검증하는 교차‑체인 브리지를 구현할 수 있습니다.

트레이드‑오프

재귀 회로는 비재귀 회로에 비해 크기가 크고 단계당 증명 속도가 느립니다. 각 재귀 단계마다 검증자를 삽입하는 오버헤드가 발생합니다. 이 이점은 많은 단계가 존재해 오버헤드를 상쇄할 수 있을 때 비로소 나타납니다—즉 롤업, 장시간 실행되는 연산, 점진적 상태 머신 등에 정확히 해당합니다.

현재 분야는 폴딩 스킴(Nova, ProtoStar, HyperNova)으로 수렴하고 있습니다. 이 스킴은 전체 재귀 검증을 더 저렴한 “폴딩” 연산으로 대체해 작업을 더욱 적극적으로 연기합니다. 2027년까지 이는 프로덕션 ZK 시스템의 기본 아키텍처가 될 것으로 예상됩니다.