들어가며
앞서 ‘영지식 증명 이해하기’에서 영지식 증명을 소개했습니다. 영지식 증명에 대한 추가적인 정보가 필요하다고 생각하여, 좀 더 자세하고 쉽게 이해할 수 있는 자료를 만들었습니다. 이번 포스팅은 대화형 증명 시스템, 대화형 영지식 증명 시스템, 비대화형 영지식 증명 시스템을 소개합니다.
[블록체인 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- ZKP Under the Hood - 비대화형 영지식 증명 이해하기
- 대화형 증명 시스템 (Interactive Proof System)
- 대화형 영지식 증명 시스템 (Interactive Zero-Knowledge Proof System)
- 비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof System)
영지식 증명 구현을 위한 타원곡선 이해하기
- 타원곡선의 수학 이야기(1)
- 타원곡선이 왜 생겼나요?
- 왜 타원곡선이라 부르나요?
- 타원곡선의 특징은 무엇인가요? - 타원곡선의 수학 이야기(2)
- 타원곡선이 암호학에서 사용되는 이유는 무엇인가요?
- 타원곡선의 수학적 정의는 무엇인가요?
블록체인에서 가장 많이 사용하는 zk-SNARKs 이해하기
- zk-SNARKs의 수학 이야기(1)
- Homomorphic Hidings
- Blind Evaluation of Polynomials
- The Knowledge of Coefficient Test and Assumption - zk-SNARKs의 수학 이야기(2)
- How to make Blind Evaluation of Polynomials Verifiable
- From Computations to Polynomials
- The Pinocchio Protocol - zk-SNARKs의 수학 이야기(3)
- Pairing of Elliptic Curves
영지식 증명을 활용한 블록체인 확장 솔루션
대화형 증명 시스템(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%에 가깝게 만족시킬 수 있습니다.
대화형 영지식 증명 시스템(Interactive Zero-Knowledge Proof System)
High-Level
대화형 영지식 증명 시스템은 대화형 증명 시스템의 속성인 완전성과 건전성을 만족하고, 추가로 영지식성을 만족하는 시스템을 말합니다.
- 영지식성: 증거가 올바르다면, Verifier는 증거가 옳다는 것 이외의 어떤 정보도 얻을 수 없음
즉, 대화형 영지식 증명 시스템은 다음 속성을 모두 만족해야합니다.
- Prover의 증거가 옳다면, Verifier는 이를 옳다고 판단해야함(완전성)
- Prover의 증거가 옳지 않다면, Verifier는 이를 옳지 않다고 판단해야함(건전성)
- Verifier는 Prover의 증거가 옳은지, 옳지 않은지의 정보만 얻을 수 있고, 그 이외에는 어떤 정보도 얻을 수 없음(영지식성)
대화형 영지식 증명 시스템은 대화형 증명 시스템의 속성을 포함합니다. 따라서, 대화형 영지식 증명에서도 결과의 확률을 높이기 위해서는 대화(Interactive)를 반복해야합니다.
예제
간단한 예시를 통해 이를 알아봅시다.
Prover는 동굴의 문을 열 수 있는 주문(‘열려라 참깨’)을 알고 있습니다. Verifier는 Prover가 주문을 알고 있다는 것을 검증하고 싶으며, Prover는 자신의 주문을 Verifier에게 알려주고 싶지 않습니다.
Prover가 주문를 공개하지 않고, Verifier에게 이를 알고 있다는 것을 어떻게 증명할 수 있는지 알아봅시다.
- Prover: 분홍색 옷을 입은 사람
- Verifier: 초록색 옷을 입은 사람
이 동굴은 A와 B 방향의 두 갈래길이 있고, 가운데는 문으로 막혀있습니다. 동굴의 문은 주문을 통해 열 수 있고, 주문을 알지 못하면 다른 방향으로 나올 수 없습니다.
- Verifier는 동굴 밖에서 기다리고, Prover는 A 또는 B 방향의 길 중에서 가고 싶은 곳으로 먼저 들어갑니다.
- Verifier는 Prover에게 A(또는 B)로 나오라고 합니다.
- Prover는 Verifier가 요구한 A(또는 B)로 나옵니다.
- 이 과정을 반복합니다.
Prover는 동굴의 문을 여는 주문을 알고 있기 때문에, B로 들어갔어도 A로 나올 수 있습니다. 하지만, 만약 Prover가 주문을 모른다면 B로 들어갈 경우 A로 나올 수 없고, 이에 따라 Verifier는 Prover가 주문을 모른다고 의심할 수 있습니다.
비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof system)
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의 검증 결과의 안전성을 높이기 위해 대화형 영지식 증명 시스템처럼 메시지를 반복하여 교환할 필요가 없으며, 결과의 안전성이 확률에 의존하지 않는다는 것입니다.
마치며
본 편에서는 [블록체인 영지식 증명 시리즈] 1편에 이어서 영지식 증명에 대한 좀 더 자세한 내용을 다루었습니다. 전 편과 다르게 대화형 증명과 비대화형 영지식 증명에 대한 내용을 작성하였습니다. 이번 게시글을 통해 비대화형 영지식 증명을 조금 더 쉽게 이해하셨기를 바랍니다.
피드백과 질문은 언제든지 환영합니다 :)
email: tjfh3217@gmail.com
[블록체인 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- ZKP Under the Hood - 비대화형 영지식 증명 이해하기
- 대화형 증명 시스템 (Interactive Proof System)
- 대화형 영지식 증명 시스템 (Interactive Zero-Knowledge Proof System)
- 비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof System)
영지식 증명 구현을 위한 타원곡선 이해하기
- 타원곡선의 수학 이야기(1)
- 타원곡선이 왜 생겼나요?
- 왜 타원곡선이라 부르나요?
- 타원곡선의 특징은 무엇인가요? - 타원곡선의 수학 이야기(2)
- 타원곡선이 암호학에서 사용되는 이유는 무엇인가요?
- 타원곡선의 수학적 정의는 무엇인가요?
블록체인에서 가장 많이 사용하는 zk-SNARKs 이해하기
- zk-SNARKs의 수학 이야기(1)
- Homomorphic Hidings
- Blind Evaluation of Polynomials
- The Knowledge of Coefficient Test and Assumption - zk-SNARKs의 수학 이야기(2)
- How to make Blind Evaluation of Polynomials Verifiable
- From Computations to Polynomials
- The Pinocchio Protocol - zk-SNARKs의 수학 이야기(3)
- Pairing of Elliptic Curves
