ZKP 직관: 알리바바의 동굴

영지식 증명(ZKP)은 증명자가 비밀을 알고 있거나 어떤 명제가 참이라는 사실을 비밀 자체를 공개하지 않고 검증자에게 납득시킬 수 있게 합니다. 세 가지 성질은 완전성, 건전성, 영지식성입니다.

증명자가 비밀을 알고 있다면 항상 검증자를 납득시킬 수 있습니다. 프로토콜을 따르는 정직한 증명자는 확률 1(또는 압도적으로 높은 확률)로 성공합니다. 검증자는 유효한 증명을 거부하지 않습니다.

비밀을 모르는 부정직한 증명자는 무시할 수 있을 정도로 작은 확률을 제외하면 검증자를 납득시킬 수 없습니다. 상호작용을 한 라운드 진행할 때마다 부정행위의 확률이 줄어듭니다. k라운드 후 부정직한 증명자의 성공 확률은 최대 2^{-k}입니다.

검증자는 명제가 참이라는 사실을 넘어서는 어떤 것도 알 수 없습니다. 형식적으로는 비밀을 알지 못하면서도 실제 증명자와 검증자의 상호작용에서 얻은 실행 기록과 구별할 수 없는 기록을 생성하는 시뮬레이터가 존재합니다. 검증자가 얻는 추가 지식은 전혀 없습니다.

동굴에는 가운데에 마법의 문이 있는 고리 모양 통로가 있습니다. 증명자 앨리스는 자신이 비밀번호를 안다고 주장합니다. 검증자 밥은 밖에서 기다립니다. 앨리스는 동굴에 들어가 왼쪽이나 오른쪽으로 갑니다. 밥은 어느 쪽으로 나와야 하는지 외칩니다. 앨리스가 비밀번호를 알고 있다면 항상 올바른 쪽으로 나올 수 있습니다. 라운드마다 부정행위가 성공할 확률은 1/2입니다.

20라운드 후 부정직한 증명자가 성공할 확률은 2^{-20}, 즉 약 백만 분의 1입니다. 비밀번호를 아는 앨리스는 매번 성공합니다. 밥은 비밀번호를 절대 알 수 없으며, 요청한 쪽에서 앨리스가 나오는 것만 봅니다. 이것이 영지식성입니다.

상호작용형 ZKP는 증명자와 검증자가 서로 여러 번 주고받아야 합니다. 비상호작용형 ZKP(NIZK)는 Fiat-Shamir 변환을 사용합니다. 검증자의 무작위 도전값을 커밋 값의 해시로 대체하는 방식입니다(해시 = 무작위 오라클). 그 결과 누구나 검증할 수 있는 하나의 증명 문자열이 생성됩니다.

증명자의 전략으로부터 증명자가 비밀을 추출할 수 있음이 도출된다면 해당 ZKP는 지식 증명(PoK)입니다. 이는 단순히 명제가 참이라고 증명하는 것보다 강한 개념입니다. ECDSA와 Schnorr 서명은 개인 키를 알고 있다는 사실에 대한 비상호작용형 지식 증명입니다.

비밀번호를 보내지 않고 비밀번호를 인증할 수 있습니다. 생년월일을 공개하지 않고 나이를 인증할 수 있습니다. 급여를 공개하지 않고 급여가 특정 범위에 있다는 범위 증명을 할 수 있습니다. 블록체인에서는 거래 내용을 공개하지 않고 유효한 거래를 알고 있음을 증명할 수 있습니다.

완전한 영지식: 시뮬레이터의 출력이 실제 대화 기록과 동일합니다. 통계적 ZK: 무시할 수 있는 확률을 제외하면 서로 구별할 수 없습니다. 계산적 ZK: 다항 시간 검증자에게 서로 구별할 수 없습니다. 더 약한 보장은 더 효율적인 증명을 의미합니다.

동굴은 커밋먼트 → 도전 → 응답의 3단계 프로토콜입니다. 형식적으로는 시그마 프로토콜이라고 합니다. 대부분의 실용적인 ZKP(Schnorr, Pedersen, Fiat-Shamir)는 시그마 프로토콜이거나 그 구성입니다. 이 이름은 메시지 흐름도에서 메시지가 이루는 Σ 모양에서 유래했습니다.

ZKP는 비밀을 공개하지 않고 비밀을 알고 있음을 증명합니다. 세 가지 특성은 완전성, 건전성, 영지식입니다. 알리바바 동굴은 대화형 ZKP를 보여 줍니다. 다음 주제: 시그마 프로토콜과 Schnorr 식별