블록체인하는 만두아빠

영지식 증명(Zero-Knowledge Proof)

영지식 증명의 개념

영지식 증명은 한 사람이 다른 사람에게 어떤 문장(Statement)이 참(True)임을 증명할 때, 그 문장 자체의 참/거짓 여부를 제외하고는 어떠한 정보도 노출하지 않는 증명 방법을 말합니다. 이 때, 문장을 증명하고자 하는 사람을 증명자(Prover)라고 하고, 증명자의 문장을 검증하는 사람을 검증자(Verifier)라고 합니다. 상대방을 속일 목적을 가진 경우 해당자는 부정직하다(Dishonest)고 합니다.

영지식 증명의 개념은 Shafi Goldwasser와 Silvio Micali의 1985년 논문 "The Knowledge Complexity of Interactive Proof System"에서 처음으로 제안되었습니다. 영지식(Zero knowledge)는 Shafi Goldwasser의 한 궁금증에서 출발합니다. 암호학에서 공격자(Adversary)가 암호문 전체를 해독하지는 못했지만, 부분 부분을 해독했거나, 어떠한 내용인지는 알 수 없지만 해당 암호문의 원본 평문이 영어로 작성되었다는 사실을 알 수 있었다거나하는 등의 일부 속성을 알아냈다면 이는 암호문의 해독으로 봐야하는 것인가라는 문제입니다. Shafi Goldwasser는 암호문을 통해서 공격자가 어떠한 형태의 정보도 얻을 수 없는 Case를 영지식으로 보아야한다고 했습니다. 종합하면, 영지식 증명은 다음의 3가지 성질을 충족하는 경우가 됩니다.

영지식 증명의 3가지 성질

1. 완전성 (Completeness) : 문장이 참일 경우, 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.

2. 건전성 (Soundness) : 문장이 거짓인 경우, 어떠한 부정직한 증명자라도 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.

3. 영지식성 (Zero-knowledgeness) : 문장이 참이면, 검증자는 문장의 참/거짓 외의 어떠한 정보도 알 수 없어야 한다.

ZKP for Kids

어려운 영지식 증명을 어떻게 하면 쉽게 설명할 수 있을까에 대한 고민의 결과로 나온 논문이 있습니다. "How to explain zero-knowledge protocols to your children"이라는 제목의 논문인데, 우리가 영지식 증명에 대해 알아볼 때 가장 많이 접하는 '알리바바의 동굴 예시'가 바로 이 논문에서 나온 것입니다.

증명자인 Peggy는 검증자인 Victor에게 알리바바 동굴 가운데의 문을 통과할 수 있는 방법을 알고 있다는 점을 증명하고 싶어합니다. 하지만 알리바바 동굴 문을 통과하는 방법에 대해서는 어떠한 정보도 알려주고 싶지는 않습니다. 이런 경우 다음과 같은 방법으로 진행하면 안전하게 Victor에게 Peggy의 지식을 증명할 수 있습니다. 영지식 증명에서 이 증명 과정을 Challenge라고 합니다.

1. 먼저 Peggy가 A, B의 두 갈림길 가운데 한 곳으로 들어갑니다. 이 때 Victor는 Peggy가 어느 방향으로 간지 알 수 없어야 합니다.

2. Peggy가 무사히 들어가고 나면, Victor는 동굴의 입구에서 Peggy에게 A/B 중 한 곳으로 나오라고 외칩니다.

3. Peggy는 Victor가 외친 방향의 통로로 나옵니다.

Peggy가 문을 통과할 수 있는 방법을 알고 있다면 문제없이 나올 수 있겠지만, 방법을 모른다면 나올 수 없을 것입니다.

만약 Peggy가 부정직한 증명자라서 Victor를 속일 목적을 가지고 있다고 하더라도 50%의 확률로 위의 Challenge를 통과할 수 있을 것입니다. 그렇다면 어떻게 하면 Peggy는 Victor에게 '확신'을 줄 수 있을까요?

간단하게, 여러번 이 과정을 반복하면 됩니다. Challenge를 단 1회 시행했을 경우 방법을 모르더라도 맞출 확률이 50%가 되지만, 계속 반복할수록 이 확률은 급격히 낮아지게 됩니다. 20번만 반복하더라도 확률은 100만분의 1로 줄어들며, 40회 반복하면 1조분의 1로 줄어듭니다. 방법을 모르는 상태에서 40번 연속으로 이 Challenge를 성공할 확률은 사실상 없다고 볼 수 있습니다. 영지식 증명에서는 이렇게 '수학적으로 증명가능'하여야 한다는 것이 중요합니다.

이 Challenge를 관찰하는 다른 제 3자의 경우에는 이 Challenge의 내용을 신뢰하기가 어렵습니다. 제 3자의 시각에서 보면, 증명자와 검증자가 사전에 미리 나올 통로의 순서를 준비했는지 아닐지 알 수 없기 때문입니다. 영지식 증명은 이와 같이 해당 증명 과정에 참여한 증명자와 검증자만이 이 사실을 확인할 수 있다는 특징이 있습니다.

알리바바의 동굴 예시는 어려운 수식과 용어, 암호학적 지식 없이도 쉽게 영지식 증명에 대한 이해를 돕는다는 측면에서 훌륭하지만 영지식 증명에 대한 공부를 알리바바의 동굴 예시로만 그쳐서는 안될 것입니다.

개념을 이해하기에는 위의 알리바바 동굴 예시의 도움으로 어렵지 않을 수 있지만, 실제 구현하는 과정에 있어서는 매우 복잡하고 까다로운 것이 영지식 증명입니다. 실제 수식으로 사용되는 ZKP의 경우 검증이 쉽도록 하기 위해 p np문제에 해당하는 모듈러 연산을 사용하는 경우가 많은데, 이 연산식이 난해할수록 보안성이 증가하기 때문에 일반적으로 아주 큰 소수(Prime number)를 사용합니다. 많은 컴퓨팅 파워를 사용하기 때문에 그동안 실제 프로토콜로 사용되는 경우가 많지 않았는데 영지식 증명을 실용적으로 할 수 있도록 고안된 zk-SNARK 프로토콜이 알려지면서 최근 개인정보보호 이슈가 대두된 블록체인 쪽에서 많이 사용되고 있습니다.

zero-knowledge Scalable Transparent ARguments of Knowledge

1. 기본 개념
   충돌 저항성 해시함수를 통해 더 희박한 대칭 암호화에 의존하기 때문에 초기 신뢰 설정을 필요로 하지 않는다.
   기존 영지식 스나크의 과도한 연산을 줄이기 위해 암호 알고리즘을 가볍게 적용한 방식. 더 신속하고 저렴하게 기술 구현이 가능
2. 특징
   • 충돌 저항성 해시 함수
     • 해시 값이 같은 입력 값 두 개를 찾을 수 없다는 특성
   • 초기 신뢰 설정 불필요
     • 영지식 스나크의 가장 큰 문제점이었던 신뢰기관의 존재를 해결하기 위해 초기 신뢰 설정 단계에서 만들어지는 휘발성 정보들이 비트코인 채굴과 비슷한 방법으로 랜덤하게 생성되도록 설계했다. 이를 통해 신뢰 기관의 존재가 불필요해졌다. 또 충돌저항성 해시함수를 기반으로 하여 사실상 비대칭 암호화 방식이기 떄문에 초기 신뢰설정이 필요하지 않기에 이러한 문제를 해결한다.
   • 확장성
     • 영지식 스나크와의 암호화 방식 차이로 복잡성이 증가하더라도 연산처리능력의 변동이 거의 없어 확장성 측면에도 우월하다.
   • 양자 컴퓨터 저항성
     • 해시함수를 통한 비대칭 암호화 방식을 사용하기 때문에 연산능력에 자유로울 수 있어 양자 컴퓨터에 저항성을 가진다.
3. 장점
   • 신뢰기관이 없어 중앙화 위험이 적다
   • 비교적 낮은 연산능력을 요구하고 이는 높은 확장성으로 이어진다
   • 빠른 증거생성시간 및 적당한 검증시간
4. 단점
   • 영지식 스나크에 비해 비교적 큰 증명의 크기
   • 수수료가 영지식 스나크에 비해 비싼 편이나 아주 큰 차이는 아니다

 1. 기본 개념

 증명자가 자신이 알고 있는 지식과 정보를 공개하지 않으면서, 그 지식을 알고 있다는 사실을 검증자에게 증명하는 시스템

 2. 영지식 증명의 3가지 조건

• 완전성(completeness) : 어떤 조건이 참이라면 신뢰할 수 있는 검증자verifier는 신뢰할 수 있는 증명자prover에 의해 이 사실을 납득할 수 있어야 한다.
• 건전성(soundness) : 어떤 조건이 거짓이면 신뢰할 수 없는 증명자는 거짓말을 통해 검증자에게 조건이 참임을 절대 납득시킬 수 없다.
• 영지식성(zero-knowledge) : 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다.

 3. 알리바바 동굴의 비유

 영지식 증명의 3가지 조건을 만족시키는 사례 but, 이 실험에서 증명자는 오직 검증자에게만 자신이 비밀번호를 알고 있다는 사실을 증명할 수 있다. 제 3자는 미리 짰는지 여부를 신뢰할 수 없기 때문

검증자verifier가 증명자prover가 도어락의 비밀번호를 알고 있는지 물어보지않고도 증명할 수 있는 방법으로 해당 과정을 계속 반복하면 할수록 증명력이 더 높아진다

 4. 활용

 거래 내역 자체는 누구에게나 공개된 블록체인에 게시되지만, 거래 상대자의 신원과 거래 금액은 암호화되어 보안이 유지된다. 즉, 영지식증명 기술은 거래 금액을 드러내지 않는 프라이버시 보호 기능과 당사자들이 서로의 신원을 확인하지 않고도 암호화폐를 교환할 수 있게 해주는 기능인 거래의 익명화가 가능하게 해주었다.

 개인정보보호를 중요시하는 프라이버시 코인에 주로 활용되며 암호화폐 거래에서 거래 제공자가 공개하는 것 이외의 정보는 제공 받는 사람이 알 수 없도록 분산화 기술로 설계되어 프라이버시 보호 기능이 뛰어나다.