이 글을 이해하기 위해 컴퓨터 공학 지식이 일부 필요할 수 있습니다.
Zero Knowledge Proof (영지식 증명)
Zero Knowledge Proof 는 무엇인가를 증명할 때, 그 무엇인가를 밝히지 않고 증명하는 방식입니다.
KeyPair 기반의 블록체인에서는 Address 소유권을 증명하기 위해서, 소유자는 Private Key 를 보관하고, Address (Public Key) 를 공개합니다. 매 증명 시점에는 Private Key 와 연관된 데이터 (Knowledge) 가 공개됩니다.
블록체인은 모든 Tx 정보가 공개되는 특성이 있습니다.
- 공개된 Address 를 추적하면, 소유자가 어떠한 행동을 취했는지 알 수 있습니다.
- 공개된 Tx 정보를 활용하여 Private Key 를 알아내기 위한 공격을 시도할 수 있습니다.
- 특정 조건이 갖춰진다면, Private Key 를 찾아낼 수 있는 방법이 존재합니다.
Zero Knowledge Proof 는 'Knowledge' 를 제공하지 않음으로써, 익명성을 강화합니다.
Verifiable Computation Algorithm
- KeyGen : λ (보안 파라미터) 와 함수 f 를 통해 EKf(증명키) 와 VKf(검증키) pair 를 생성합니다. 모두 공개키 입니다.
- Compute : EKf 와 함수 f 입력 값인 u 를 통해 y와 π를 생성합니다.
- Verify : VKf 와 u 및 y 를 통해 π가 맞는지 검증합니다.
Zero Knowledge Proof Algorithm
- KeyGen : λ (보안 파라미터) 와 함수 f 를 통해 EKf(증명키) 와 VKf(검증키) pair 를 생성합니다. 모두 공개키 입니다.
- Prove : EKf 와 공개 x 및 비밀 w 를 통해 y와 π를 생성합니다.
- Verify : VKf 와 공개 x 및 y 를 통해 π가 맞는지 검증합니다.
The Strange Cave of Alibaba
How to Explain Zero-Knowledge Protocols to Your Children 에 제시된 예제입니다.
시장에서 물건을 팔던 알리바바의 물건을 도둑이 훔쳐서 갈림길이 2개 (A 와 B) 인 동굴로 도망갔습니다.
알리바바는 동굴의 막다른 길까지 쫓아 들어갔지만, 도둑을 찾을 수 없었습니다.
이 일이 반복되자, 알리바바는 동굴이 이상하다고 생각하고 막다른 길에 숨어 있다가 놀라운 비밀을 알게 됩니다.
도둑이 "Open Sesame" (열려라 참깨) 라고 하자, 동굴의 벽이 열렸고, 잠시 후 다시 닫혔습니다.갈림길이 2개 (A 와 B) 인 동굴이 있으며, 두 갈림길 입구는 내부적으로 하나의 동굴로 연결되어 있지만, 비밀번호를 알아야만 통과할 수 있습니다.
증명자는 자신이 비밀번호를 알고 있음을 증명하려 하고, 검증자는 증명자가 비밀번호를 알고 있는지 확인하려 합니다.
- 증명자가 먼저 동굴에 들어갑니다.
- 검증자는 갈림길에서, 증명자에게 지정한 방향으로 나오라고 지시합니다.
- 증명자가 지정한 방향으로 나옵니다.
우연하게 지정한 출구로 나올 수 있을지도 모르므로, 이를 충분히 반복합니다. 계속해서 검증자가 원하는 결과를 낼 수 있다면, 증명자는 비밀번호를 가지고 있다고 볼 수 있습니다.
- 입구가 2개인 상황에서 정답을 맞출 확률은 1/2 입니다.
- N 회 시행을 반복해서 모두 정답을 맞출 확률은 (1/2)^N 입니다.
zk-SNARKs
Zero-Knowledge Succinct Non-Interactive Argument of Knowledge
자세한 설명은 zk-SNARKs 페이지를 참조해주세요.
Reference
- Parno, B.; Howell, J.; Gentry, C.; Raykova, M. (2013), "Pinocchio: Nearly Practical Verifiable Computation"
- Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990), "How to Explain Zero-Knowledge Protocols to Your Children"
- Sean Bowe, Ariel Gabizon, Matthew D. Green, "A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK"
- Consensys, Introduction to zk-SNARKs
- zk-SNARKs