영지식 증명 (Zero Knowledge Proof)

영지식 증명(Zero Knowledge Proof)은 증명자가 검증자에게 어떤 명제가 참이라는 사실을 납득시키면서, 그 명제가 참이라는 사실 외에는 어떤 정보도 알려 주지 않는 암호학적 증명 방식입니다. 비밀 키나 비밀번호를 안다는 사실을, 그 값을 드러내지 않고 증명하는 것이 대표적인 예입니다.

자세히 알아보기

이 개념은 골드바서(Goldwasser), 미칼리(Micali), 래코프(Rackoff)가 1985년 발표한 논문에서 처음 정식화했습니다. 이들은 증명 과정에서 검증자가 얻는 지식의 양을 따졌고, 명제가 옳다는 것 외에 추가 지식을 전혀 주지 않는 증명을 영지식 증명으로 정의했습니다. 영지식 증명은 보통 세 가지 성질로 설명합니다. 첫째, 명제가 참이고 증명자가 정직하면 검증자는 받아들입니다(완전성). 둘째, 명제가 거짓이면 속이려는 증명자가 검증자를 통과할 확률이 무시할 만큼 작습니다(건전성). 셋째, 검증자는 증명을 거친 뒤에도 명제가 참이라는 사실 말고는 새로 알게 되는 것이 없습니다(영지식성).

초기의 영지식 증명은 상호작용 방식이었습니다. 검증자가 무작위 질문을 던지고 증명자가 답하는 과정을 여러 번 되풀이하며, 반복할수록 속임수가 통할 확률이 급격히 줄어듭니다. 이후 증명자가 메시지 하나만 보내면 누구나 검증할 수 있는 비상호작용 영지식 증명(NIZK)이 나왔습니다. 블록체인에서 널리 쓰이는 zk-SNARK는 증명이 짧고 검증이 빠른 비상호작용 방식의 한 종류입니다. 따라서 "상호작용이 필요 없다"는 것은 영지식 증명 전체의 성질이 아니라 일부 방식의 특징입니다.

영지식 증명은 일부 정보를 보여 주는 것과 다릅니다. 답의 일부를 잘라 보여 주는 방식은 그 일부만큼 정보를 드러내므로 영지식이 아닙니다.

블록체인·암호화폐에서는

대표적인 사례는 Zcash(ZEC)입니다. Zcash의 차폐(shielded) 거래는 zk-SNARK를 사용해 송신자, 수신자, 금액을 공개하지 않고도 거래가 규칙에 맞는다는 것을 증명합니다. 증명 시스템은 Sprout에서 BCTV14, Sapling에서 Groth16, Orchard에서 Halo 2로 바뀌어 왔고, Halo 2는 이전 방식에 필요했던 신뢰 설정(trusted setup) 절차를 없앴습니다. 다만 Zcash에서 차폐 거래는 선택 사항이며, 투명 주소를 쓰는 거래는 일반 블록체인처럼 공개됩니다.

이더리움의 zk-롤업도 같은 계열의 기술을 씁니다. 롤업은 레이어 2에서 처리한 많은 거래가 올바르다는 유효성 증명을 메인넷에 제출하고, 메인넷은 거래를 하나하나 다시 실행하지 않고 증명만 검증합니다. 이 경우에는 정보를 숨기는 것보다 검증을 짧게 만드는 데 초점이 있는 경우가 많습니다. 증명 생성에 많은 연산이 필요하고, 구현이 복잡해 오류가 생기기 쉽다는 점은 한계로 꼽힙니다.

쉽게 말하면

색을 구별하지 못하는 친구에게 빨간 공과 초록 공이 서로 다른 색이라는 것을 증명하는 상황을 생각해 볼 수 있습니다. 친구가 두 공을 등 뒤로 숨겨 바꾸거나 그대로 둔 뒤 다시 보여 주면, 나는 바뀌었는지 아닌지를 맞힙니다. 계속 맞히면 친구는 두 공의 색이 다르다는 것을 믿게 되지만, 어느 공이 무슨 색인지는 끝내 알 수 없습니다.

예시

위 과정에서 색을 구별하지 못하는 사람이 한 번 맞힐 확률은 1/2입니다. 20번 연속으로 맞힐 확률은 1/2²⁰, 약 105만분의 1입니다. 반복 횟수를 늘릴수록 속임수가 통할 가능성은 계속 작아지며, 이것이 건전성이 확률로 표현되는 이유입니다.