[Xangle Digest]

※해당 컨텐츠는 외부에서 기발간 된 컨텐츠입니다. 컨텐츠에 대한 추가적인 주의사항은 본문 하단에서 확인해주세요.

written by 이재성 오승훈 은지우 장인영 / reviewed by 돌비콩

 

목차

1. 영지식 증명이란?
2. 영지식 증명의 활용
3. 블록체인에서의 영지식 증명
4. 결론

 

 

TL; DR

블록체인은 중앙화된 기존의 방식에서 벗어나 정보를 여러 대의 컴퓨터에 복제해 저장하는 분산형 데이터 저장 기술이다. 블록체인을 활용하면 모든 사용자가 데이터를 공유할 수 있기 때문에 투명성이 보장되어 위변조가 어렵다. 그러나 이러한 투명한 데이터 구조는 프라이버시 문제를 야기하기도 한다.

이런 상황에서 적절한 해결책으로 주목받고 있는 것이 바로 ‘영지식 증명(Zero Knowledge Proof)’이다. 본고에서는 영지식 증명의 기본적인 개념을 알아보고 이해하기 쉬운 예시와 수학적 공식을 통해 어떤 방식으로 작동하는지 서술할 예정이다. 이어 사례 분석을 통해 블록체인에서는 영지식 증명 기술을 어떻게 활용하고 있는지 현황을 살펴볼 것이다.

 

 

1. 영지식 증명이란?

한 눈에 보는 영지식 증명 작동 방식 (출처: Medium @GOPAX)

 

1.1 프라이버시 보호의 키(Key)로 떠오른 영지식 증명

블록체인 기술이란 기존 중앙 관리 시스템에서 벗어나, P2P(Peer to Peer) 네트워크를 통해 데이터를 다수의 컴퓨터에 분산 저장 및 보관하는 기술이다. 모든 참여자들이 동일한 데이터를 각자 가지고 있어 데이터의 투명성을 지원함과 동시에 데이터의 위·변조가 어렵다.

이러한 탈중앙성은 블록체인 기술이 각광받게 된 이유지만, 데이터가 투명하게 보이는 구조는 개인정보 유출 등 프라이버시 문제에 취약하다. 여러 연구자, 개발자들이 믹싱, 동형암호, 링 서명(Ring Signature)과 함께 영지식 증명 기술을 활용해 프라이버시 문제 극복을 위해 노력해 왔고, 그중 특히 영지식 증명 기술은 가장 적절한 해결책이 될 것으로 기대되는 기술이다.

특히, 웹3.0가 주목받으면서 사용자의 금융거래, 데이터 공유 및 신원 확인 등 여러 분야에 걸친 프라이버시 보호의 중요성이 높아지고 있다. 이는 영지식 증명 기술이 더욱 각광받는 계기가 되었다.

 

1.2 영지식 증명의 개념

영지식 증명이란 자신이 알고 있는 지식이나 정보 등을 상대방에게 공개하지 않고도 자신이 그 내용을 알고 있다는 것을 증명할 수 있는 방법이다. 영지식 증명을 활용하면, 자신이 증명하고자 하는 명제의 참 거짓 여부를 제외한 어떠한 정보도 노출하지 않고도 지식을 입증할 수 있다.

영지식 증명을 설명하는 가장 대표적인 예시인 ‘알리바바 동굴’을 살펴보자.

알리바바 동굴(Ali Baba’s Cave),
(출처: How to explain zero-knowledge protocols to your children)

알리바바 동굴에는 A와 B 방향의 두 갈래길이 있고, 가운데에 특정 주문을 통해 열 수 있는 비밀문이 존재한다. 이 주문을 알아낸 사람에게 상을 주는 대회가 열렸다. 그런데 이 대회에는 특별한 규칙이 하나 있다. 참가자는 심사위원에게 주문을 직접 말하지 않고 자신이 주문을 알고 있다는 사실을 증명해야 하는 것이다. 어떻게 해야 할까? 아래 순서에 따르면, 참가자는 자신이 주문을 안다는 사실을 쉽게 증명할 수 있다.

1. 심사위원은 동굴 밖에서 기다리고, 참가자는 A와 B 중 하나를 택하여 동굴로 들어간다.
2. 심사위원은 참가자에게 A와 B 중 하나의 길로 나올 것을 요구한다.
3. 심사위원이 요구한 길로 참가자가 나온다.
4. 반복

비밀문을 여는 주문을 모르더라도 심사위원이 요구한 방향으로 참가자가 나올 확률(50%)도 물론 있다. 하지만 이 과정을 계속해서 반복한다면, 주문을 모르는 참가자가 매번 심사위원이 요구한 방향으로 나올 확률은 기하급수적으로 낮아진다. 반복할수록 심사위원은 참가자가 주문을 알고 있다는 사실을 더 강하게 신뢰할 수 있게 된다.

결국, 참가자는 주문을 공개하지 않고도 자신이 비밀문을 여는 주문을 안다는 사실을 증명할 수 있게 된다. 심사위원은 이 사실만을 알게 될 뿐 비밀문을 여는 주문에 대해서는 어떠한 단서도 얻지 못한다. ‘영지식’을 갖게 된다는 의미이다.

알리바바 동굴의 예시에서는 참가자와 심사위원이 대화를 반복하는 과정이 발생한다. 이처럼 증명자와 검증자가 상호 통신하면서 영지식 증명을 만들어 나가는 시스템을 대화형 영지식 증명이라고 부른다. 이 유형에 대해서는 후술할 영지식 증명의 유형에서 더 살펴보도록 하겠다.

 

1.3 영지식 증명의 조건

영지식 증명을 위해 필요한 조건은 세 가지가 있으며, 이를 모두 충족할 때 비로소 영지식 증명이라고 부를 수 있게 된다. 앞서 살펴 본 알리바바 동굴 예시를 바탕으로, 세 가지 조건에 대해 알아보겠다.

1)완전성(Completeness)

• “어떤 명제가 참이라면, 검증자는 증명자에 의해 이 사실을 납득할 수 있어야 한다.”
• 참가자가 심사위원의 요구를 계속 따르게 된다면, 심사위원은 참가자가 주문을 알고 있다고 납득할 수 있어야 한다.

2)건전성(Soundness)

• “어떤 명제가 거짓이라면, 어떠한 증명자라도 거짓말을 통해 검증자에게 조건이 참임을 납득시킬 수 없다.”
• 참가자가 비밀번호를 모르지만 안다고 거짓말했을 경우, 참가자는 자신이 비밀번호를 안다는 것을 증명할 수 없다.

3)영지식성(Zero-Knowledge)

• “검증자는 명제의 참, 거짓 여부 이외에 어떠한 정보도 얻을 수 없다.”
• 여러 번의 반복을 통해 심사위원은 참가자가 비밀번호를 알고 있다는 사실을 납득했지만 비밀번호가 무엇인지는 알지 못한다.

 

1.4 영지식 증명은 어떻게 문제를 해결하는가?

사용자는 원본 데이터를 암호화하여 생성된 암호문과, 암호문이 올바르게 생성되었다는 사실에 대한 영지식 증명을 블록체인에 같이 저장한다. 영지식 증명으로 공개 검증을 가능하게 하는 동시에 암호문을 통해 프라이버시까지 보호한다. 당사자들은 개인 정보를 보호하고, 민감한 데이터를 손상시키지 않으면서 상호작용하고 정보를 교환할 수 있다. 영지식 증명의 유형과 구체적인 구현 방식에 대해 살펴보겠다.

 

 

2. 영지식 증명의 유형

영지식 증명의 유형은 크게 두 가지로 나눌 수 있다. 앞서 살펴본 알리바바 동굴의 예시와 같이 증명자와 검증자가 상호작용하는 ‘대화형 영지식 증명’과 반대의 개념으로 상호작용 없이 증명자의 증거를 검증자가 받아서 혼자 검증해 증명하는 형태의 ‘비대화형 영지식 증명’이 있다. 이 두 가지 증명의 차이점은 증명자와 검증자의 상호작용 여부일 뿐, 영지식 증명의 세 가지 조건은 모두 충족할 수 있도록 구성된다.

 

2.1. 대화형 영지식 증명 (Interactive Zero-Knowledge Proof)

대화형 영지식 증명은 증명자와 검증자 사이에 상호 작용을 진행하며 검증하는 모델이다. 많은 시간과 상당한 양의 계산이 요구되는 대신, 증명을 손상시키기 어려워 안전하고 다양한 유형의 정보에 대한 지식을 증명하기가 용이하다. 대화형 영지식 증명에서 검증자는 임의의 랜덤 값을 생성해 증명자에게 상황에 맞는 올바른 답을 대화를 통해 원하는 만큼 요구할 수 있기 때문이다.

 

2.1.1. 대화형 영지식 증명의 예시

대화형 영지식 증명의 주요 특징이 상호작용이라는 점을 이용한다면, 알리바바의 동굴 외에도 쉽고 다양한 예시를 만들 수 있다. 다음은 그림에서 증명자가 Waldo의 위치를 공유하지 않고도 Waldo가 어디에 있는지 알고 있다는 사실을 증명하는 예시이다.

출처: Where’s Waldo series

① 사진에서 Waldo를 잘라내고 잘라낸 Waldo를 검증자에게 보여준다. 검증자는 잘라낸 Waldo가 사진과 일치함을 확인하며 증명자가 정답을 알고 있음을 판단할 수 있다.

 

② 그림과 같은 사이즈의 종이에 Waldo의 위치와 모습을 그리고 그 부분만을 잘라낸다. 검증자는 원본 그림에 종이를 맞대어보고 증명자가 정답을 알고 있음을 판단할 수 있다.

 

이 예시에서 검증자에게 공개된 유일한 정보는 ‘증명자는 Waldo를 찾았다.’이며 위치 등 다른 정보는 공개되지 않는다.

또 다른 예시도 있다. 색상을 구분할 수 없는 사람에게 증명자가 색상을 구분할 수 있는 사람임을 증명하는 예시이다.

검증자는 왼손에 파란색 공, 오른손에 빨간색 공을 들어 손을 안 보이게 해 놓고 두 손 사이에서 공을 교환하거나 교환하지 않을 수 있다. 그 후에 양손에 있는 공을 보여줬을 때, 색깔을 볼 수 있는 사람이라면 당연히 교환여부를 맞출 것으로 확신할 수 있다.

출처: Medium @GOPAX

검증자는 증명자가 색깔을 볼 수 있는 사람임을 확신할 때까지 같은 게임을 여러 번 반복할 것이다. 결과를 계속해서 맞힌다면, 검증자는 증명자가 색상을 구분할 수 있는 사람임을 합리적으로 확신할 수 있다.

다음 대화형 영지식 증명에서는 조금 더 수식화된 내용으로 살펴보도록 하자.

출처: Medium @GOPAX

앞서 살펴본 것처럼 대화형 영지식 증명은 증명자와 검증자 간에 메시지를 주고받는 과정이 반드시 필요하다. 따라서 대화형 영지식 증명을 위해, 먼저 검증자에게 증명자가 0이 아닌 정수의 집합 중에서 소수인 p, g를 선택하고 y=g^x를 만족하는 x의 값을 알고 있다는 것을 증명하겠다고 명제를 전달한다. x의 값을 직접적으로 언급하지 않고도 아래의 과정들을 통해 증명자가 검증자에게 자신이 x값을 알고 있음을 증명할 수 있다면, 영지식 증명이 성립된다.

 

증명 과정

① 증명자가 y=g^x 를 통해 자신이 x값을 알고 있다는 명제(Statement)를 증명한다

② 증명자는 랜덤한 r 값을 선택해서 C=g^r mod p 계산해 C 값을 검증자에게 전달

③ 검증자는 증명자에게 다음 중 하나를 요청해 증명자가 x의 값을 아는지 확인

• ⑴ x+r mod p-1 값을 요청해서 받아 검증자가 C*y mod p = g^(x+r mod p-1)인지 확인
• ⑵ r 값을 요청해 C = g^r mod p 인지 확인

④ 검증에 문제가 없으면 증명자가 x 값을 알고 있다고 검증자가 검증 완료

 

2.2. 비대화형 영지식 증명 (Non-Interactive Zero-Knowledge Proof)

비대화형 영지식 증명은 수학적 알고리즘을 사용하여 증명자와 검증자의 지속적인 상호 작용 없이 검증자가 확인할 수 있는 증거를 생성하는 증명 방식을 말한다. 대화형 영지식 증명에 비해 비용 효율적으로, 더 적은 계산으로 빠르게 검증이 가능한 것이 특징이다. 당사자간의 신뢰 구축이 어려운 분산형 시스템에 적합한 모델로, 블록체인 네트워크에서 활용하기에 더욱 알맞다.

다만 상호작용이 있는 대화형 영지식 증명보다 유연성이 떨어지며, 특정 유형의 정보를 다룬 지식 증명에 특화되어 있으며, 기술적인 구현이 어렵고 많은 연구가 필요하다는 한계도 존재한다.

 

2.2.1. 비대화형 영지식의 예시

비대화형 영지식 증명을 통해 아무도 풀지 못하던 스도쿠 퍼즐을 증명자가 풀어냈다는 사실을 증명해 보자.

스도쿠의 기본 룰은 ‘각 셀에는 행, 열 및 3×3 격자에 고유한 숫자(1~9)가 포함되어야 한다’라고 할 수 있다. 이 룰 하에서 다음과 같은 과정으로 영지식 증명을 활용할 수 있다.