영지식 증명(Zero Knowledge Proof)이란? 암호학에서 어떤 상태나 문장이 참이라는 것을 증명할 때, 그 문장의 참·거짓 여부를 제외한 어떤 것도 노출하지 않고 정보의 유효성(참·거짓)을 증명할 수 있는 방법이다.

예를 들어, 누군가가 어떤 비밀번호를 안다고 증명하려 할 때, 비밀번호가 'TVCC'라는 문자열인지, 혹은 몇 글자인지 같은 정보는 알리지 않고 오로지 “비밀번호를 안다”는 사실만 증명하는 방법이다.

이것이 어떻게 가능한지에 대해 아래의 알리바바 동굴 예시를 통해 살펴본다.

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

◇Prover: 분홍색 옷
◇Verifier: 초록색 옷
◇Secret: 동굴 내 우측 문을 열 수 있는 비밀
◇Challenge: Verifier가 Prover에게 어느 방향으로 나올지를 요구하는 과정

이 동굴은 A와 B 방향의 두 갈래길이 있고, 가운데(우측)는 문으로 막혀있다. 동굴의 문은 비밀을 알면 열 수 있고, 비밀을 알지 못하면 다른 방향으로 나올 수 없다. Prover는 동굴의 문을 열 수 있는 비밀을 알고 있고, 이를 Verifier에게 알리지 않은채 자신이 비밀을 알고 있다는 것을 증명하고 싶어한다.

이를 위해 Verifier는 동굴 밖에서 기다리고, Prover는 A 또는 B 방향의 길 중에서 가고 싶은 곳으로 먼저 들어간다. 이후 Verifier는 Prover에게 A(또는 B)로 나오라고 한다. 그 다음 Prover는 Verifier가 요구한 A(또는 B)로 나옵니다.

Prover는 동굴 내 잠긴 문(그림의 우측)을 여는 비밀을 알고 있기 때문에, B로 들어갔어도 A로 나올 수 있다. 하지만, 만약 Prover가 비밀을 모른다면 B로 들어갈 경우 A로 나올 수 없고, 이에 따라 Verifier는 Prover가 주문을 모른다고 의심하게 된다.

◆ 영지식 증명의 확률적 확신

그런데 Prover는 주문을 몰라도 Verifier에게 주문을 알고 있다고 속일 수 있다. Prover가 B로 들어갔는데 정말 운이 좋게 Verifier가 B로 나오라고 할 경우, Prover는 주문을 몰라도 B로 나올 수 있기 때문이다.

하지만 이러한 상황은 위 과정을 반복함으로써 해결할 수 있다.

에를 들어 Prover는 주문 없이 Verifier가 요구하는 방향으로 나올 수 있는 확률은 1/2 이며, 이를 20번 반복한다고 가정할 경우 Prover가 비밀을 모른채로 20번 모두 성공할 확률은 (1/2)²⁰ 이다. 이는 1/1048576이며 약 1백만 분의 1이고 0.0001% 확률이다.

즉 반복횟수가 증가하면 할수록 Verifier는 Prover가 비밀을 알고 있다고 ‘확률적’으로 확신할 수 있게 되는 것이다.

여기서 Verifier는 랜덤한 결과값을 요구함으로써 Verifier를 제외한 다른 사람들은 Prover가 증명하는 과정에서 Prover가 어떤 비밀을 갖고 있는지를 알 수 없는 것은 물론이며, 나아가 Secret을 알고 있는지의 여부에 대해서마저 확신할 수 없게 된다.

그리고 이러한 영지식 증명 암호화 방법은 암호화폐 업계에서 유용하게 쓰이게 되는데, 이에 대해서는 다음주의 블록체인 백과사전 '영지식 증명' (2)편에서 이어서 연재된다.

더욱 다양한 정보 및 방송 관련 소식은

공식 SNS 채널을 통해 확인 가능합니다.