완전 영지식 증명 대 계산적 영지식 증명: 이 구분이 실제로 의미하는 것

크립토 분야에서 "영지식 증명"이라는 말이 나올 때, 사람들이 떠올리는 것은 거의 항상 한 가지 구체적인 개념입니다. 바로 입력값을 공개하지 않으면서 특정 연산이 올바르게 수행되었음을 증명하는 SNARK 또는 STARK입니다. 이 정도의 이해는 대부분의 엔지니어링 논의에서 충분합니다. 그러나 이 관점은 보안이 실제로 무엇을 보장하는가를 따지는 순간 중요해지는 구분 하나를 감춰 버립니다.

영지식 증명에는 공식적으로 세 가지 유형이 있습니다. 완전(perfect), 통계적(statistical), 계산적(computational) 영지식 증명이 그것이며, 세 유형은 검증자가 무한한 자원을 가지고 있더라도 알 수 있는 것이 무엇인가라는 점에서 서로 다릅니다. 여러분이 실제로 배포하는 시스템은 거의 확실히 계산적 영지식 증명입니다. 그 이유와 그것이 의미하는 바를 이해할 필요가 있습니다.

영지식 증명의 구조

고전적인 설정은 이렇습니다. *증명자(prover)*는 *검증자(verifier)*에게 어떤 명제가 참임을 납득시키되, 검증자가 그 이상의 정보를 얻지 못하도록 해야 합니다. 여기서 "참"이란 "나는 H(x) = y를 만족하는 x를 알고 있다"거나 "나는 이 그래프에서 경로를 알고 있다"거나 "나는 비공개 입력으로 이 프로그램을 올바르게 실행했다"와 같은 명제를 말합니다.

어떤 증명 시스템이 영지식이려면, 비공식적으로 말해서 검증자가 비밀 없이도 스스로 증명을 생성할 수 있어야 합니다. 이를 형식적으로 포착하는 것이 바로 **시뮬레이터(simulator)**의 존재입니다. 시뮬레이터는 공개 명제만 주어졌을 때(증인 없이), 실제 증명 트랜스크립트와 구별할 수 없는 트랜스크립트를 생성하는 다항 시간 알고리즘입니다.

영지식의 세 유형은 "구별할 수 없다"는 것이 무엇을 의미하는가에 따라 나뉩니다.

완전 영지식(Perfect Zero-Knowledge)

시뮬레이터의 출력이 실제 증명과 동일하게 분포합니다. 어떤 통계적 검정으로도, 양자 컴퓨터로도, 10^100년을 돌려도 시뮬레이터와 실제 증명자를 구별할 수 없습니다. 수학적으로 두 분포는 동일합니다.

이것이 최고 기준입니다. 시간 제한이나 계산 가정 없이도, 무한한 능력을 가진 적대자조차 증명으로부터 아무것도 알 수 없다는 뜻입니다.

통계적 영지식(Statistical Zero-Knowledge)

시뮬레이터의 출력이 실제 증명과 통계적으로 가깝습니다. 두 분포 사이의 전체 변동 거리(total variation distance)가 무시할 수 있는 수준입니다. 무한한 능력의 적대자가 원칙적으로는 무언가를 알아낼 수도 있지만, 알아낼 수 있는 양은 보안 매개변수에 따라 지수적으로 줄어듭니다.

실용적 관점에서 통계적 ZK는 완전 ZK만큼 훌륭합니다. 시뮬레이터는 실제 분포와 정확히 일치할 필요가 없으며, 어떠한 연산도 그 차이를 증폭시킬 수 없을 만큼 충분히 가깝기만 하면 됩니다.

계산적 영지식(Computational Zero-Knowledge)

시뮬레이터의 출력이 실제 증명과 계산적으로 구별 불가능합니다. 다항 시간 알고리즘은 둘을 구별할 수 없습니다. 무한한 능력의 적대자, 즉 기반이 되는 해시 함수를 무차별 대입하거나 기반이 되는 어려운 문제를 풀 수 있는 사람이라면 이론적으로 둘을 구별하고 증인을 알아낼 수 있습니다.

세 가지 중 형식적 의미에서 가장 약한 유형이며, 현대의 거의 모든 시스템이 실제로 제공하는 수준이 바로 이것입니다.

왜 사실상 모든 프로덕션 ZK 시스템은 계산적인가

여기에는 숨겨진 정리가 있습니다. NP-완전 언어에 대해서는 완전 영지식이 존재할 가능성이 낮습니다. 다항 계층이 붕괴하지 않는 한 그렇습니다 (Goldreich and Krawczyk, 1996). 달리 말하면, 임의의 명제—"나는 이 프로그램을 올바르게 실행했다"처럼 표현력이 높은 명제—를 영지식으로 증명하고 싶다면, 증명 자체가 증명되지 않은 복잡도 가정에 의존하지 않고서는 완전 영지식을 실현할 수 없습니다.

임의의 NP 명제에 대해 가질 수 있는 것:

계산적 영지식 증명: 일방향 함수가 존재하면 존재합니다. (Goldreich, Micali, Wigderson 1991.)
제한된 명제 클래스에 대한 통계적 영지식: 임의 자기 환원 가능 문제, 그래프 동형 문제 등이 해당되지만, 일반적인 NP에는 해당되지 않습니다.

따라서 실제 시스템—Groth16, PLONK, Halo2, STARK, Bulletproofs—이 "영지식"이라고 말할 때, 이는 사실상 항상 계산적 영지식을 의미합니다. 증명은 타원 곡선, 해시 함수, 또는 기타 암호학적 기본 요소에 대한 가정을 전제로, 다항 시간 검증자에게 아무것도 드러내지 않습니다.

만약 그 가정이 깨진다면—예를 들어, 미래의 알고리즘이 어떤 스킴이 의존하는 곡선의 이산 로그 문제를 푼다면—영지식 논거는 소급하여 약화될 수 있습니다. 무엇이 가능해지는지는 구체적인 구성 방식에 따라 다릅니다. 공격자는 실제 트랜스크립트와 시뮬레이션된 트랜스크립트를 구별하거나, 증명을 위조하거나, 이전에 보호되었던 정보를 추출할 수 있게 될 수도 있습니다. 기반이 되는 가정이 무너진 이후에도 과거의 계산적 ZK 트랜스크립트가 동일한 프라이버시 마진을 유지한다고 가정해서는 안 됩니다.

실제 예시: 커밋먼트 스킴

커밋먼트 스킴은 이 구분을 구체적으로 보여줍니다.

커밋먼트란 대략 이런 것입니다. "나는 값 v를 봉인된 봉투 c에 넣고 봉투를 건네줍니다. 나중에 v를 공개하면 당신은 내가 원래의 값을 공개했는지 확인할 수 있지만, 공개 전에는 v를 볼 수 없습니다."

두 가지 보안 속성이 있습니다.

은닉성(Hiding) — 봉투는 v에 대해 아무것도 드러내지 않습니다.
결합성(Binding) — 나는 처음 커밋한 값 이외의 값으로 봉투를 열 수 없습니다.

이 두 가지를 모두 완전하게 갖출 수는 없습니다. 완전 은닉 커밋먼트는 계산적으로 결합적입니다(충분한 연산력으로 공격자가 두 번째 열기를 찾아낼 수 있음). 완전 결합 커밋먼트는 계산적으로 은닉적입니다(충분한 연산력으로 공격자가 커밋된 값을 추출할 수 있음).

Pedersen 커밋먼트는 완전 은닉이며 계산적으로 결합적입니다. 무한한 능력의 공격자에게도 커밋된 값에 대해 아무것도 드러내지 않지만, 미래에 이산 로그가 풀리면 결합성을 속일 수 있게 됩니다. 해시 기반 커밋먼트(c = H(v || r))는 계산적으로 은닉이며 (해시가 충돌 저항성을 가질 때) 계산적으로 결합적입니다.

어떤 유형을 원하는지는 시간이 지나면서 어떤 속성이 약화되어도 괜찮은지에 달려 있습니다. 투표나 입찰의 장기 프라이버시를 위해서는 결합성이 계산적이더라도 완전 은닉을 선호하는 것이 일반적입니다. 이산 로그 가정이 깨지기 전에 결합성을 재증명할 수 있지만, 유출된 투표를 소급하여 익명화하는 것은 불가능하기 때문입니다.

ZK 롤업과 L2 시스템에서 이것이 중요한 이유

대부분의 ZK 롤업은 계산적 영지식을 갖춘 SNARK를 사용합니다. 실질적인 함의는 다음과 같습니다.

현재, 증명들은 어떠한 현실적인 공격자에게도 아무것도 드러내지 않습니다. 프라이버시 보장은 강합니다.
장기적으로, 증명들은 기반이 되는 가정이 보호하는 것만큼만 드러내지 않습니다. 만약 롤업이 BN254 이산 로그에 보안이 의존하는 SNARK를 사용하는데, BN254가 2050년에 깨진다면, 그 이전에 게시된 모든 증명은 잠재적으로 익명성이 해제될 수 있습니다.
포스트 양자 고려 사항이 중요합니다. 이산 로그 기반 SNARK(표준 페어링 곡선 위의 Groth16, PLONK)는 포스트 양자 보안을 갖추지 못합니다. 해시 충돌 저항성에만 의존하는 STARK는 갖추고 있습니다. (StarkWare, STARK 약어를 확립한 논문.)
통계적 또는 완전 ZK는 제한된 설정(예: 특정 대수적 관계를 증명하는 경우)에서 가능하며, 장기 프라이버시 예산이 표현력보다 중요할 때 사용되기도 합니다.

익명 투표, 내부고발 채널, 그리고 트랜스크립트가 수십 년간 보관될 수 있는 시스템과 같은 응용 분야에서, 계산적 ZK와 통계적 ZK 사이의 선택은 단순히 학문적인 문제가 아닙니다. 이는 내일의 적대자에 맞서 유지되는 프라이버시와 어떤 적대자에게도 유지되는 프라이버시의 차이입니다.

간단한 의사결정 트리

프로덕션용 ZK 시스템을 선택한다면:

검증자 전용 프라이버시, 단기 데이터, 성능이 가장 중요한 경우: 검증된 SNARK나 STARK의 계산적 ZK로 충분합니다. 대부분의 롤업, 대부분의 ZK-KYC, 대부분의 ZK 로그인이 여기에 해당합니다.
장기 프라이버시, 감사/법적 민감성: 해시 기반 시스템(STARK)이나 내부에 Pedersen 스타일 커밋먼트를 사용하는 방식을 선호하십시오. 가정을 문서화하십시오.
계산 가정과 무관한 증명 가능한 프라이버시: 제한된 명제 클래스에 대한 완전 또는 통계적 ZK를 원하는 것입니다. 어느 정도의 표현력이나 상호작용성을 포기해야 함을 예상하십시오.

공짜 점심은 없습니다. ZK의 유형들은 서로, 그리고 효율성과 상충 관계에 있습니다. 중요한 것은 어떤 상충 관계를 의식적으로 선택하는가입니다.

Namefi의 관점

도메인 소유권 흐름에서 ZK의 가장 흥미로운 활용은, 어떤 이름인지 드러내지 않으면서 해당 이름을 소유하고 있음을 증명하는 것입니다. 온체인 레지스트리에 대한 소유권 증명은 성숙한 도구(Groth16, PLONK)를 활용한 계산적 ZK로 구현할 수 있으며, 오늘날 프로덕션 시스템이 실제로 사용하는 방식이 바로 이것입니다. 더 민감한 흐름—예를 들어, 어느 것인지 공개하지 않고 도메인이 신뢰할 수 있는 엔터티의 집합에 속한다는 것을 증명하는 경우—에는 제한된 명제에 대한 통계적 또는 완전 ZK 스킴이 적합할 수 있습니다. 이 글의 목적은 상충 관계를 명확하게 하는 것입니다. 실제로 필요한 것을 선택하고, 채택하는 가정을 명문화하십시오.

출처 및 추가 읽을거리

Goldreich, Micali, Wigderson — Proofs that yield nothing but their validity (J. ACM 1991).
Goldreich and Krawczyk — On the composition of zero-knowledge proof systems (1996).
Pedersen — Non-interactive and information-theoretic secure verifiable secret sharing (1991).
Ben-Sasson, Bentov, Horesh, Riabzev — Scalable, transparent, and post-quantum secure computational integrity (STARK paper, 2018).
a16z crypto — Justin Thaler의 "Proofs, Arguments, and Zero-Knowledge", 현대의 표준 교재.