티스토리 뷰
영지식 증명이란?
영지식증명(Zero-knowledge Proofs: ZKPs)은 간단히 말하자면, 비밀정보를 직접 보여주지 않아도 내가 그 비밀정보를 가지고 있다는 것을 증명할 수 있는 강력한 암호기술 입니다. ZKP를 처음 접하신다면, 어떻게 가능한지 의문이 드실겁니다. 계속해서 읽으시면 이해할 수 있게 직관적인 설명을 해보겠습니다.
영지식증명은 1985년 샤피 골드바저, 실비오 미칼리, 찰스 래코프에 의해서 발명되었습니다. 그 이후로 ZKP는 암호학에서 많은 관심을 받으며 활발히 연구되어 왔습니다. 최근에는 실제 애플리케이션, 특히 블록체인 기술에 상당한 영향을 미치며 사용되고 있습니다. 한 예를 보자면 블록체인 프로젝트 중 Zcash는 금융거래 익명성을 위해 영지식 증명을 사용하였습니다. CODA[미나프로토콜의 모체버전]에서도 영지식 증명을 이용하여 많은 트랜잭션이 쌓인다고 할지라도, 블록체인의 풀 노트가 몇 kb size 로 남도록 유지하는 기술을 연구하고 있습니다.[ 현재 미나프로토콜은 위 방식으로 22KB사이즈의 블록체인 풀노드를 유지하고 있음]
영지식 증명의 목적은 다른 사람에게 내가 가진것이 무엇인지 밝히지 않고 내가 가지고 있다는것을 설득하는 것입니다. 예를 들어, 해결책을 제시하지 않고 퍼즐의 해결책을 알고 있다고 누군가를 설득하고 싶을 수 있습니다.
예시를 들어 생각해 보겠습니다.
3-Coloring이라는 퍼즐이 있습니다. 이 퍼즐에는 아래 그림과 같이 각 점과 선의 그래프가 제공됩니다. 퍼즐은 세 가지 색으로 각 점과 인접한 두 점이 같은 색을 칠하면 풀립니다. 즉 인접한 점과 겹치지 않게 3가지 색을 칠하는 3-Coloring퍼즐입니다.
3-Coloring 퍼즐을 위한 영지식 증명
3-coloring 퍼즐을 위한 영지식 증명 프로토콜을 설계해 보겠습니다.
사용자와 다른사람 사이의 영지식 증명에서 누군가를 검증자(Verifier)라고 부르려면 다음 두가지 속성을 충족해야 할 것입니다.
1. 탈락을 하는 경우 (ex, 3가지 색을 모르는 경우) 검증자가 사용자를 잡을 수 있을겁니다. 이 속성을 건전성(soundness)라고 부르겠습니다.
2. 검증자는 3색에 대해 아무것도 배우지 않아야 합니다. 이 속성을 영지식성 (Zero-knowledgeness) 라고 부르겠습니다.
이제 영지식증명 프로토콜을 구성해 보겠습니다. 여기서, 사용자의 증명 및 검증 절차는 다음과 같습니다.
증명(Proving): 닫힌 공간에서 바닥에 그려진 그래프를 상상해보세요. 사용자가 알고 있는 3가지 색상에 따라, 해당 색상을 점에 배치합니다. 그 후 점의 색이 안보이게 천으로 덮을 것입니다.
검증(Verifying): 검증자가 와서 사용자가 선택한 가장자리를 가리킵니다. 사용자는 가장자리 양쪽에 있는 두 점의 색을 공개합니다. 검증자는 표시된 점의 색이 서로 다른지 확인합니다. 만약 그렇지 않다면, 사용자는 탈락할 것입니다.
지금까지 프로토콜을 정의했으므로 이제 영지식성 (Zero-knowledgeness)와 건정성(soundness)을 충족하는지 확인해보겠습니다.
영지식성 (Zero-knowledgeness)
검증자가 본 모든 내용은 무작위로 두 개의 다른 색 점을 선택하여 확인 할 수 있으므로 3-coloring퍼즐에 대한 정보는 검증자에게 표시되지 않습니다. 따라서 이 프로토콜은 완벽한 영지식성을 제공합니다.
건전성 (Soundness)
3가지 색을 잘 몰라서 실패했을 경우 가장자리로 연결된 일부 두 점이 검증 단계에서 같은 색의 공이 나올것입니다. 즉 검증 단계에서 검증자가 무작위로 가장자리를 선택하므로, 사용자의 실패가 잡힐 확률은 최소 1/|E|입니다. 여기서 E는 그래프의 가장자리 갯수를 의미합니다.
실패를 들키지 않을 확률도 존재합니다. ((E-1)/E) 우리는 이 가능성을 건전성에러(Soundness error)라고 부릅니다. 우리는 이 에러를 최소화 하기 위해 하나의 아이디어를 제시할 수 있습니다.
위 프로토콜을 여러번 반복하는 것입니다. 그러면 실패했음을 놓칠 확률이 크게 줄어들 것이고, 건전성오류는 크게 감소합니다.
건전성 (SoundNess)을 최대한 확보하기
더 많이 프로토콜을 반복할수록 요청의 건전성에 대한 검증자의 신뢰가 높아집니다. 그래프에 대한 3가지 색상을 모른다고 가정하고 확률을 계산해보면, 사용자가 실패를 들키지 않을 확률은 다음과 같습니다.
N을 총 반복횟수라고 하겠습니다.
Pr(실패를 들키지 않은 횟수 i<=N) <=1^-E
Pr(N회차에 들키지 않을 확률)<=(1-^E)N
반복할수록 매우 줄어든다는 이야기 입니다.
제로지식 돌아보기
유감스럽게도, 이 프로토콜에는 이슈가 있습니다. 검증과정이 충분히 반복되면, 검증자가 3-coloring의 3색을 모두 알게 될 수 있습니다. 이는 영지식성이 깨지는 이슈입니다. 이 문제는 한번 프로토콜이 시행될 때 마다 검증자에게 시야에서 벗어나라고 요청하고, 무작위로 색상을 순열한 다음 다시 모든 점의 색을 숨깁니다. 이렇게 하면 검증자가 한번 시행했을 때 학습한 내용은 다음 시행에서 관련이 없습니다. 검증자가 본 내용은 각 시행에서 무작위로 두 개의 다른 색 점을 선택하여 시뮬레이션 할 수 있기 때문입니다.
References
https://minaprotocol.com/ko/blog/zero-knowledge-proofs-an-intuitive-explanation
Zero-knowledge Proofs: An Intuitive Explanation
Zero-knowledge proofs (ZKPs) are a powerful cryptographic primitive that enables you to prove that you have a secret, without revealing it to anyone. If you are hearing about ZKPs for the first time, you are likely to say "Hah! That sounds impossible." Rea
minaprotocol.com
'Study > 블록체인' 카테고리의 다른 글
| zk-SNARK (Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge) (0) | 2022.10.25 |
|---|---|
| zk-SNARK - 영지식 증명(Zero-knowledge Proofs) (0) | 2022.10.24 |
| Ethereum - GAS (가스) (0) | 2022.05.29 |
| EVM (Ethereum Virtual Machine) - 개요 (0) | 2022.05.29 |
| EVM( Ethereum Virtual Machine ) - OPCODE 현황 (0) | 2022.05.29 |