블록체인하는 만두아빠

영지식 증명(Zero-Knowledge Proof)

영지식 증명의 개념

영지식 증명은 한 사람이 다른 사람에게 어떤 문장(Statement)이 참(True)임을 증명할 때, 그 문장 자체의 참/거짓 여부를 제외하고는 어떠한 정보도 노출하지 않는 증명 방법을 말합니다. 이 때, 문장을 증명하고자 하는 사람을 증명자(Prover)라고 하고, 증명자의 문장을 검증하는 사람을 검증자(Verifier)라고 합니다. 상대방을 속일 목적을 가진 경우 해당자는 부정직하다(Dishonest)고 합니다.

영지식 증명의 개념은 Shafi Goldwasser와 Silvio Micali의 1985년 논문 "The Knowledge Complexity of Interactive Proof System"에서 처음으로 제안되었습니다. 영지식(Zero knowledge)는 Shafi Goldwasser의 한 궁금증에서 출발합니다. 암호학에서 공격자(Adversary)가 암호문 전체를 해독하지는 못했지만, 부분 부분을 해독했거나, 어떠한 내용인지는 알 수 없지만 해당 암호문의 원본 평문이 영어로 작성되었다는 사실을 알 수 있었다거나하는 등의 일부 속성을 알아냈다면 이는 암호문의 해독으로 봐야하는 것인가라는 문제입니다. Shafi Goldwasser는 암호문을 통해서 공격자가 어떠한 형태의 정보도 얻을 수 없는 Case를 영지식으로 보아야한다고 했습니다. 종합하면, 영지식 증명은 다음의 3가지 성질을 충족하는 경우가 됩니다.

영지식 증명의 3가지 성질

1. 완전성 (Completeness) : 문장이 참일 경우, 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.

2. 건전성 (Soundness) : 문장이 거짓인 경우, 어떠한 부정직한 증명자라도 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.

3. 영지식성 (Zero-knowledgeness) : 문장이 참이면, 검증자는 문장의 참/거짓 외의 어떠한 정보도 알 수 없어야 한다.

ZKP for Kids

어려운 영지식 증명을 어떻게 하면 쉽게 설명할 수 있을까에 대한 고민의 결과로 나온 논문이 있습니다. "How to explain zero-knowledge protocols to your children"이라는 제목의 논문인데, 우리가 영지식 증명에 대해 알아볼 때 가장 많이 접하는 '알리바바의 동굴 예시'가 바로 이 논문에서 나온 것입니다.

증명자인 Peggy는 검증자인 Victor에게 알리바바 동굴 가운데의 문을 통과할 수 있는 방법을 알고 있다는 점을 증명하고 싶어합니다. 하지만 알리바바 동굴 문을 통과하는 방법에 대해서는 어떠한 정보도 알려주고 싶지는 않습니다. 이런 경우 다음과 같은 방법으로 진행하면 안전하게 Victor에게 Peggy의 지식을 증명할 수 있습니다. 영지식 증명에서 이 증명 과정을 Challenge라고 합니다.

1. 먼저 Peggy가 A, B의 두 갈림길 가운데 한 곳으로 들어갑니다. 이 때 Victor는 Peggy가 어느 방향으로 간지 알 수 없어야 합니다.

2. Peggy가 무사히 들어가고 나면, Victor는 동굴의 입구에서 Peggy에게 A/B 중 한 곳으로 나오라고 외칩니다.

3. Peggy는 Victor가 외친 방향의 통로로 나옵니다.

Peggy가 문을 통과할 수 있는 방법을 알고 있다면 문제없이 나올 수 있겠지만, 방법을 모른다면 나올 수 없을 것입니다.

만약 Peggy가 부정직한 증명자라서 Victor를 속일 목적을 가지고 있다고 하더라도 50%의 확률로 위의 Challenge를 통과할 수 있을 것입니다. 그렇다면 어떻게 하면 Peggy는 Victor에게 '확신'을 줄 수 있을까요?

간단하게, 여러번 이 과정을 반복하면 됩니다. Challenge를 단 1회 시행했을 경우 방법을 모르더라도 맞출 확률이 50%가 되지만, 계속 반복할수록 이 확률은 급격히 낮아지게 됩니다. 20번만 반복하더라도 확률은 100만분의 1로 줄어들며, 40회 반복하면 1조분의 1로 줄어듭니다. 방법을 모르는 상태에서 40번 연속으로 이 Challenge를 성공할 확률은 사실상 없다고 볼 수 있습니다. 영지식 증명에서는 이렇게 '수학적으로 증명가능'하여야 한다는 것이 중요합니다.

이 Challenge를 관찰하는 다른 제 3자의 경우에는 이 Challenge의 내용을 신뢰하기가 어렵습니다. 제 3자의 시각에서 보면, 증명자와 검증자가 사전에 미리 나올 통로의 순서를 준비했는지 아닐지 알 수 없기 때문입니다. 영지식 증명은 이와 같이 해당 증명 과정에 참여한 증명자와 검증자만이 이 사실을 확인할 수 있다는 특징이 있습니다.

알리바바의 동굴 예시는 어려운 수식과 용어, 암호학적 지식 없이도 쉽게 영지식 증명에 대한 이해를 돕는다는 측면에서 훌륭하지만 영지식 증명에 대한 공부를 알리바바의 동굴 예시로만 그쳐서는 안될 것입니다.

개념을 이해하기에는 위의 알리바바 동굴 예시의 도움으로 어렵지 않을 수 있지만, 실제 구현하는 과정에 있어서는 매우 복잡하고 까다로운 것이 영지식 증명입니다. 실제 수식으로 사용되는 ZKP의 경우 검증이 쉽도록 하기 위해 p np문제에 해당하는 모듈러 연산을 사용하는 경우가 많은데, 이 연산식이 난해할수록 보안성이 증가하기 때문에 일반적으로 아주 큰 소수(Prime number)를 사용합니다. 많은 컴퓨팅 파워를 사용하기 때문에 그동안 실제 프로토콜로 사용되는 경우가 많지 않았는데 영지식 증명을 실용적으로 할 수 있도록 고안된 zk-SNARK 프로토콜이 알려지면서 최근 개인정보보호 이슈가 대두된 블록체인 쪽에서 많이 사용되고 있습니다.