Zero-knowledge

영지식 증명이란 ?

영지식 증명이 무엇인가?

영지식 증명은 암호학에서 누군가가 상대방에게 어떤 상태가 참이라는 것을 증명할 때, 그 문장의 참 거짓 여부를 제외한 어떤 것도 노출되지 않도록 하는 절차이다.

영지식 증명을 활용한 프로토콜의 가장 큰 특징은 정보를 공개하지 않고 정보의 ‘유효성'을 증명할 수 있는 방법이라는 것이다.

내가 어떤 정보를 알고 있을 때, 정보를 알려주지 않으면서 내가 알고있다는 사실만을 증명하는 것.

영지식 증명에는 어떤 상태의 유효성(참 혹은 거짓)을 증명하고자 하는 Prover와 이를 검증하고자 하는 Verifier가 참여합니다.

Prover

Prover는 자신이 가지고 있는 정보가 무엇인지 공개하지 않고, Verifier에게 ‘정보를 알고 있다'는 것을 증명하고 싶은 참여자

Verifier

Prover가 해당 정보를 가지고 있음을 검증하고 싶은 참여자

Secret

Prover가 가지고 있음을 증명하고 싶은 정보이며, 모두에게 숨기고자 하는 정보

Challenge

Verifier가 Prover가 Secret을 가지고 있는지 확인하기 위해 문제를 내는 과정

Statement is true

Verifier가 Prover가 Secret을 가지고 있음을 검증한 상태

영지식 증명에서 Prover는 Secret을 그 누구에게도 공개하지 않고, 오직 Verifier에게 자신이 secret을 알고 있다는 것을 증명하고 싶다.

The Ali Baba Cave

간단한 예시를 통해 Prover가 secret을 공개하지 않고 Verifier에게 이를 알고 있다는 것을 어떻게 증명할 수 있는지 알아보자.

이 동굴은 A와 B 방향의 두 갈래길이 있고, 가운데는 문으로 막혀있다.

동굴의 문은 주문을 통해 열 수 있고, 주문을 알지 못하면 다른 방향으로 나올 수 없다.

Prover는 동굴의 문을 열 수 있는 주문을 알고 있고, 이를 Verifier에게 알리지 않은채 자신이 주문을 알고 있다는 것을 증명하고 싶다.

Prover는 자신의 주문(secret)을 Verifier에게 알리지 않고, 주문을 알고 있다는 것을 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로 나올 수 있고, 이에 따라 Verifier를 속일 수 있다.

우리는 이러한 불상사를 막기 위해 위 과정을 반복한다.

Prover는 주문 없이 Verifier가 요구하는 방향으로 나올 수 있는 확률은 1/2 이다.

이 확률은 Verifier가 Prover가 들어간 방향으로 나오라고 요구할 확률과 일치한다.

이 과정을 20번 정도 계속 반복한다. Prover가 주문을 모른채 20번 모두 성공할 확률은 (1/2)²⁰ 이다.

이 성공 확률은 시행 횟수에 따라 줄어들게 된다.

하지만 우선 성공하면 Verifier는 Prover가 주문을 알고 있다고 확률적으로 확신할 수 있게 된다.

대화형 증명 시스템(Interactive Proof System)

High-Level 대화형 증명 시스템은 Prover와 Verifier의 메시지 교환을 통해,

Prover의 증거가 옳다면, Verifier가 옳다고 판단하고, Prover의 증거가 옳지 않다면, Verifier도 옳지 않다고 판단하는 시스템을 의미한다.

이를 좀 더 체계적으로 정리해보자. 대화형 증명 시스템이 되기 위해서는 두 가지 조건을 만족해야 한다.

두 가지 조건은 완전성(completness)과 건전성(soundness)이다.

완전성: Prover의 증거가 옳다면, Verifier는 이를 옳다고 판단해야함

건전성: Prover의 증거가 옳지 않다면, Verifier는 이를 옳지 않다고 판단해야함

어떻게 보면, 증거를 검증할 때 완전성과 건전성의 조건은 너무나 당연한 것이라 생각할 수 있다.

여기서 핵심은 ‘너무나 당연한 이 두가지 조건을 모두 만족하는 시스템을 만들기 위해서는 어떻게 해야하는가’ 이다.

대화형 증명 시스템은 Prover와 Verifier의 대화(Interactive)의 반복을 통해 이 조건을 만족한다.

예시는 다음과 같다.

예제

Prover는 과일 두 개를 가지고 있다다. 한 개는 사과이고, 다른 한 개는 바나나이다.

Verifier는 Prover가 가지고 있는 과일 2개가 서로 다른 과일인지 알고 싶다.

이 경우 Prover는 Verifier에게 자신이 가진 과일 2개가 다른 종류의 과일인 것을 어떻게 증명할 수 있을까?

문제: Prover가 가진 두 개의 과일이 다른 종류인가?

Prover는 사과를 1번이라하고, 바나나를 2번이라한다.

그리고 1번 사과의 이름을 하트라고 하고, 2번 바나나의 이름을 별이라고 한다.

Verifier는 1번과 2번 중 하나를 랜덤으로 선택하여 Prover에게 메시지를 보낸다.

1번을 선택했다고 가정

Prover는 1번 사과의 이름인 하트를 Verifier에게 보낸다.

Verifier는 다시 랜덤으로 색을 선택하여 Prover에게 메시지를 보낸다.

2번을 선택했다고 가정

Prover는 2번 바나나의 이름인 별을 Verifier에게 보낸다.

Verifier는 1번과 2번에 대한 Prover의 답이 하트와 별로 서로 같지 않은 것을 확인하고, Prover가 과일이 다른 종류임을 알 수 있다.

여기서 Verifier는 Prover가 가진 과일의 종류가 무엇인지 중요하지 않다.

1번과 2번에 대한 Prover의 답이 다르다는 것이 중요하다.

1번과 2번의 답이 다르다는 것만으로, Prover의 1번 과일과 2번 과일이 서로 다른 과일임을 알 수 있기 때문이다.

특징

여기서 주목해야할 특징은 Verifier가 보내는 메시지는 랜덤하게 선택된다는 것이다.

만약 과일이 2개가 아니라 100개 였다면, Verifier는 Prover가 가진 100개의 과일이 서로 다른 것을 검증하기 위해 정말 많은 메시지를 교환해야한다.

또한, Verifier는 Prover와 메시지를 10번 교환하여 10개의 답이 다르다는 것을 확인할 때보다 메시지를 1000번 교환하여 1000개의 답이 다르다는 것을 확인할 때, Prover가 가진 100개의 과일이 서로 다른 과일임을 더욱 확신할 수 있다.

이는 대화형 증명 시스템 결과의 안전성이 확률에 의존하며, 확률은 대화를 많이 반복할 수록 커진다는 것을 의미한다.

실제로 1000번의 메시지 교환을 통해 Prover가 이야기한 답이 서로 다르다면, 과일 100개가 서로 다른 종류의 과일일 수 있는 확률이 100%에 가깝다고 생각할 수 있을 것이다.

하지만, 이는 100% 다르다 라고 말하기는 어려울 것이다.

즉, 이 시스템은 완전성의 조건을 100%만족시킬 수 없다.

하지만, 대화를 반복하여 확률을 100%에 가깝게 만족시킬 수 있다.

대화영 영지식 증명

High-Level

대화형 영지식 증명 시스템은 대화형 증명 시스템의 속성인 완전성과 건전성을 만족하고, 추가로 영지식성을 만족하는 시스템을 말한다.

영지식성: 증거가 올바르다면, Verifier는 증거가 옳다는 것 이외의 어떤 정보도 얻을 수 없음

즉, 대화형 영지식 증명 시스템은 다음 속성을 모두 만족해야한다.

• Prover의 증거가 옳다면, Verifier는 이를 옳다고 판단해야함(완전성)

• Prover의 증거가 옳지 않다면, Verifier는 이를 옳지 않다고 판단해야함(건전성)

• Verifier는 Prover의 증거가 옳은지, 옳지 않은지의 정보만 얻을 수 있고, 그 이외에는 어떤 정보도 얻을 수 없음(영지식성)

대화형 영지식 증명 시스템은 대화형 증명 시스템의 속성을 포함한다.

따라서, 대화형 영지식 증명에서도 결과의 확률을 높이기 위해서는 대화(Interactive)를 반복해야한다.

비대화형 영지식 증명

High-Level

비대화형 영지식 증명 시스템은 증거를 검증할 때 대화(Interactive)가 없는 시스템을 의미한다.

대화형 영지식 증명 시스템의 결과의 확률을 높이기위해 메시지 교환을 여러번 해야한다.

이처럼 메시지 교환을 증가시키면, 시스템 결과의 안전성을 증가하지만, Prover와 Verifier의 메시지 교환이 많아져서 효율성이 떨어지게 된다.

대화형 영지식 증명 시스템에서 Prover는 Verifier에게 증거를 여러 번 전송한다.

하지만, 비대화형 영지식 증명 시스템에서 Prover는 Verifier에게 증거를 단 한 번만 보내면 된다.

Prover가 Verifier에게 증거를 보낸 후에 Verifier가 증거를 검증할 때 추가적인 메시지 교환이 전혀 일어나지 않는다.

따라서, Prover는 Verifier에게 증거를 한 번 보낸 후에, 통신이 끊어져도 Verifier가 증거가 옳은지 옳지 않은지 검증하는데 아무런 문제가 없다.

예제

가장 대표적인 비대화형 영지식 증명 시스템인 zk-SNARKs를 살펴보자.

zk-SNARKs에서 Prover는 Verifier에게 증거를 한 번만 제출하면 된다.

zk-SNARKs에는 믿어야 하는 제 3자(Trusted Party)가 있다.

Trusted Party는 Prover가 증거를 만들고, Verifier가 증거를 검사할 때 필요한 정보를 제공한다.

Prover는 Trusted Party가 준 정보로 증거를 만들고 Verifier에게 증거를 전송하면, Verifier는 계산을 통해 증거가 옳은지, 옳지 않은지 검증한다.

여기서 Prover는 Verifier에게 증거를 전송한 뒤 추가적인 메시지를 보낼 필요가 전혀 없다.

모든 비대화형 영지식 시스템이 zk-SNARKs 와 똑같이 동작하지는 않는다.

Trusted party가 없는 경우도 있고, 증거를 만들기 위해 Prover와 Verifier가 메시지를 교환해야하기도 한다.

여기서 핵심은 Prover가 Verifier의 검증 결과의 안전성을 높이기 위해 대화형 영지식 증명 시스템처럼 메시지를 반복하여 교환할 필요가 없으며, 결과의 안전성이 확률에 의존하지 않는다는 것이다.