영지식 증명: 알리바바 동굴

우연히 영지식 증명에 대해 접하게 되었다. 이게 너무 흥미로운 주제라 아주 자세하게 알아보고자 한다. 제대로 이해할 때 까진 계속해서 이 주제에 대해서만 작성할 것이다.

 

영지식 증명이란 정말정말 쉽게 한 문장으로 말하면, "본인의 정보를 공개하지 않고도 거래를 검증할 수 있는 기술"이다. 이게 무슨 뚱단지 같은 소리일까? 우선 그 전에, 영지식 증명을 가장 직관적으로 설명하는 알리바바 동굴에 대해 알아보겠다. 

알리바바 동굴

출처: https://xangle.io/research/detail/1612

1. 동굴을 들어가면 A,B 두 갈래로 길이 나뉜다.
2. 이 두 길은 안쪽에서 다시 연결이 되는데,그 전에 잠겨진 문을 먼저 해제해야 한다.
3. 이 문은 비밀번호를 알아야지만 통과할 수 있다. 
4. 이 동굴에는 비밀번호를 아는 사람(증명자) 과 검증하는 사람(검증자)가 2명이 있다. 
5. 증명자가 먼저 동굴로 들어가고 검증자는 동굴 밖에 뒤돌아 서 있다. 
6. 증명자는 혼자 동굴 안으로 들어가서 A를 선택 하고 비밀의 문까지 걸어간다. 
7. 이제 검증자가 동물 입구로 와서 안을 향해 외친다. "B로 나오세요"
8. 이때 검증자는 증명자가 처음에 A로 갔는지 B로 갔는지 모른느 상태에서 B로 나오라고 명령을 한 것이다. 왜냐면 검증자는 뒤돌아 서 있었기 때문
9. 여기서 이제 비밀번호를 아는 사람과 몰랐던 사람(사기꾼) 2가지 경우로 나뉜다.
   • 증명자가 진짜 비밀번호를 아는 경우: "증명자는 지금 A에 서 있지만 검증자가 B로 나오라"고 했으므로 비밀의 문을 열고 통과해서 B길로 나온다. 검증자가 A로 나오라 하든, B로 나오라 하든 문을 자유롭게 잠그고 열면서 이동할 수 있으니 항상 성공한다
   • 증명자가 비밀번호를 모르는 사기꾼인 경우: 운 좋게 어쩌다 한번은 맞을 수 있어도 B로 나오라고 하면 문을 못 열어서 명령한 방향으로 나오지 못하고 들통나게 된다. 

이 과정을 1번만 수행한다면 검증자는 확신하기 어렵다. 왜? 2분의 1 확률이니 운 좋게 맞을 수도 있기 때문이다. 근데 이 실험을 여러 번 반복한다면? 몇 번만 반복해도 우연히 연속으로 맞출 가능성은 점차 줄어들 것이다. 따라서 매번 정확히 요구에 응답하는 모습을 보면 검증자는 증명자가 비밀번호를 알고 있는지 모르는지 확신을 가질 수 있다. 중요한 것은!! 이 모든 과정에서 비밀번호 자체는 한 번도 공개되지 않는 것이다.