By Tariz, Co-Founder & ZK researcher at Rádius
들어가며
본 편은 블록체인 영지식 증명 시리즈의 첫 번째 주제로 영지식 증명이 무엇인지에 대해 알아봅니다. 이 글은 블록체인이나 수학에 대한 이해가 없어도 영지식 증명에 대해 이해할 수 있도록 쉽게 설명하고자 했습니다.
본 글의 작성을 위해 김균태님의 영지식 증명 설명 영상의 전체적인 흐름과 내용을 참고 했으며, 설명의 완결성을 위해 구체적 설명을 추가했습니다.
[디사이퍼 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- 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
영지식 증명을 활용한 블록체인 확장 솔루션
영지식 증명이 무엇인가?
영지식 증명은 암호학에서 누군가가 상대방에게 어떤 상태가 참이라는 것을 증명할 때, 그 문장의 참 거짓 여부를 제외한 어떤 것도 노출되지 않도록 하는 절차입니다. 영지식 증명을 활용한 프로토콜의 가장 큰 특징은 정보를 공개하지 않고 정보의 ‘유효성'을 증명할 수 있는 방법이라는 것입니다.
영지식 증명에는 어떤 상태의 유효성(참 혹은 거짓)을 증명하고자 하는 Prover와 이를 검증하고자 하는 Verifier가 참여합니다.
- Prover
Prover는 자신이 가지고 있는 정보가 무엇인지 공개하지 않고, Verifier에게 ‘정보를 알고 있다'는 것을 증명하고 싶은 참여자 - Verifier
Prover가 해당 정보를 가지고 있음을 검증하고 싶은 참여자 - Secret
Prover가 가지고 있음을 증명하고 싶은 정보이며, 모두에게 숨기고자 하는 정보 - Challenge
Verifier가 Prover가 Secret을 가지고 있는지 확인하기 위해 문제를 내는 과정 - Statement is true
Verifier가 Prover가 Secret을 가지고 있음을 검증한 상태
영지식 증명에서 Prover는 Secret을 그 누구에게도 공개하지 않고, 오직 Verifier에게 자신이 secret을 알고 있다는 것을 증명하고 싶습니다.
The Ali Baba Cave
간단한 예시를 통해 Prover가 secret을 공개하지 않고 Verifier에게 이를 알고 있다는 것을 어떻게 증명할 수 있는지 알아봅시다.
- Prover: 분홍색 옷을 입은 사람
- Verifier: 초록색 옷을 입은 사람
- Secret: 동굴의 문을 열 수 있는 주문
- Challenge: Verifier가 Prover에게 나올 방향을 요구하는 과정
이 동굴은 A와 B 방향의 두 갈래길이 있고, 가운데는 문으로 막혀있습니다. 동굴의 문은 주문을 통해 열 수 있고, 주문을 알지 못하면 다른 방향으로 나올 수 없습니다. Prover는 동굴의 문을 열 수 있는 주문을 알고 있고, 이를 Verifier에게 알리지 않은채 자신이 주문을 알고 있다는 것을 증명하고 싶습니다.
Prover는 자신의 주문(secret)을 Verifier에게 알리지 않고, 주문을 알고 있다는 것을 Verifier에게 어떻게 증명할 수 있을까요?
- 먼저 Verifier는 동굴 밖에서 기다리고, Prover는 A 또는 B 방향의 길 중에서 가고 싶은 곳으로 먼저 들어갑니다.
- Verifier는 Prover에게 A(또는 B)로 나오라고 합니다.
- Prover는 Verifier가 요구한 A(또는 B)로 나옵니다.
- 이 과정을 반복합니다.
Prover는 동굴의 문을 여는 주문을 알고 있기 때문에, B로 들어갔어도 A로 나올 수 있습니다. 하지만, 만약 Prover가 주문을 모른다면 B로 들어갈 경우 A로 나올 수 없고, 이에 따라 Verifier는 Prover가 주문을 모른다고 의심할 수 있습니다.
그런데 Prover는 주문을 몰라도 Verifier에게 주문을 알고 있다고 속일 수 있습니다. Prover가 B로 들어갔는데 정말 운이 좋게 Verifier가 B로 나오라고 할 경우, Prover는 주문을 몰라도 B로 나올 수 있고, 이에 따라 Verifier를 속일 수 있습니다. 우리는 이러한 불상사를 막기 위해 위 과정을 반복합니다. 잠깐 수학으로 들어가 볼까요?
Prover는 주문 없이 Verifier가 요구하는 방향으로 나올 수 있는 확률은 1/2 입니다. 이 확률은 Verifier가 Prover가 들어간 방향으로 나오라고 요구할 확률과 일치합니다. 이 과정을 20번 정도 계속 반복합니다. Prover가 주문을 모른채 20번 모두 성공할 확률은 얼마일까요? (1/2)²⁰ 입니다.
이 성공 확률은 시행 횟수에 따라 줄어들게 됩니다. 하지만 우선 성공하면 Verifier는 Prover가 주문을 알 고 있다고 ‘확률적’으로 확신할 수 있게 됩니다.
이 과정을 수학적 정의를 통해 살펴봅시다.
Zero Knowledge Proof formal definition
zkp의 수학적 정의는 다음과 같습니다.
- P(x): Prover
- V(x, z): Verifier
- ←-→: interactive proof system; Prover와 Verifier의 Challenge 과정
- Veiw: interactive proof 과정을 관찰하여 기록한 것
- z: Verifier의 challenge value
위 정의를 간략히 살펴보면, Verifier의 challenge value인 0, 1에 대한 Prover와 Verifier의 Challenge 증명 과정을 다른 컴퓨터에서 똑같이 시뮬레이션 할 수 있어야 한다는 것입니다(여기서 간단히 컴퓨터라고 했지만 실제로는 turing machine입니다).
앞서 설명한 알리바바 동굴에 대입하면 다음과 같습니다.
- Prover가 A 혹은 B로 들어갑니다.
- Verifier은 Prover를 A로 나오게 할 지, B로 나오게 할 지를 challenge value인 z값으로 결정합니다(예: z가 0이면 A, 1이면 B).
- Prover는 Verifier의 z값에 따라 A혹은 B로 나옵니다.
- 이 과정을 반복하고(z의 값은 계속 바뀝니다), 이를 기록합니다.
- 그리고 이 과정을 turing machin에서 똑같이 실행하면, Prover 는 사전에 시행한 시뮬레이션과 똑같은 방향으로 나와야 합니다.
Prover가 Challenge 과정에서 Verifier에게 secret을 알고 있음을 확신시킬 수 있는 ‘올바른 답’을 계속 제공했다면, Verifier는 확률적으로 Prover가 secret을 가지고 있다고 확신할 수 있습니다.
여기서 주의해야 할 점은 Verifier는 z값을 통해 Prover가 주문을 알 고 있는지 확률적으로 확신할 수 있지만, 주문이 무엇인지에 대한 그 어떤 정보도 알아내는 건 불가능 해야 한다는 것입니다. 또한 S에서 위와 과정을 시뮬레이션 할 때도, Prover의 주문에 대한 정보는 알 수 없어야 합니다.
또한, 여기서 주의해야 하는 것은 Verifier를 제외한 다른 사람들은 Prover가 secret을 알고 있는지에 대해 확신하는 것도 불가능하도록 만들어야 한다는 것입니다.
Prior agreement
위의 조건을 가능하게 하는 것이 영지식 증명의 Prior agreement 가능성입니다.
Ali Baba Cave에서 Verifier는 Prover가 주문을 알고 있는지 확인하기 위해 A 혹은 B로 나오라고 요구 하는 것을 20번 반복할 것입니다. 그런데 만약 사전에 Verifier가 Prover에게 20번의 순서를 공유했다고 가정합니다. 이렇게 되면 Prover는 주문을 몰라도 Verifier가 어디로 나오라고 할 지 알기 때문에 20번의 challenge를 모두 성공하는 것을 의미합니다. 실제로 영지식 증명에서는 이러한 사전 공모가 가능합니다.
이는 영지식 증명의 한계로 보이기도 하지만, 사실 이는 Prior agreement를 가능하게 하는 조건입니다.
Prior agreement 가능성을 통해 Prover와 Verifier를 제외한 제 3자는 영지식 증명 과정에서 서로 사전에 정보를 공유했는지, 혹은 공유하지 않았는지 확신할 수 없습니다. 이에 따라, 제 3자는 Peggy와 Victor가 서로 짜로 Peggy가 주문을 알고 있다고 거짓으로 증명할 수 있다는 의심을 하게 됩니다.
이는 ‘Verifier에게 secret을 알고 있다고 증명하는 것에 성공한 Prover가 진짜 secret을 알고 있을까’라는 의심으로 이어지게 됩니다.
즉, 이는 Prover가 secret을 알고 있다는 정보 조차 제 3자에게 노출되지 않는 것을 의미합니다. 한편, Verifier는 본인이 Prover와 사전에 공모를 했는지 안했는지 알고 있습니다. 이에 따라 Prover는 Verifier에게만 secret을 알고 있다고 증명할 수 있습니다.
그런데 이를 성공적으로 시행해야 하기 위해서는 한 가지 사전 조건이 필요합니다. ‘Verifier는 challenge value인 z값을 공개하면 안됩니다.’ 만약 Verifier가 z 값을 도출하는 과정과 이에 대한 값을 제 3자에게 공개한다면, 제 3자는 Prover와 Verifier가 사전에 공모했다고 의심할 수 없게 됩니다. 이는 Prover의 challenge 성공에 따라 secret을 알고 있다는 것을 Verifier외에도 제 3자가 확신할 수 있다는 것이고, 영지식을 잃는다는 것을 의미합니다.
영지식 증명과 디지털 서명의 차이
이제 영지식 증명과 디지털 서명의 차이를 알아보자.
- zkp에서는 public address를 identity라고 생각할 수 있습니다. 즉, zkp는 prover의 secret뿐만 아니라 identity도 함께 감출 수 있습니다. 하지만 digital signature은 identity를 감추지 못합니다.
- Digital signature 결정론적이기 때문에, digital은 증명과정을 관찰하고 있는 모든 사람(verifier과 제 3자들)을 납득시킬 수 있습니다. zkp는 prior agreement 가능성이 있기 때문에, 제 3자는 Prover가 secret을 가지고 있다고 100% 확신하기 어렵습니다.
- Zkp에서 verifier는 0또는 1의 질문(challenge)를 하게 되는데, 제 3자가 이를 기록하여 허위로 prover에게 행사하려고 하더라도, 그는 verifier로부터 어떤 challenge(0 or 1)이 나올지 확신할 수 없기 때문에 prover을 납득시킬 수 없습니다. 하지만 digital은 (현실적인 확률은 극도로 낮지만) 굉장히 많은 message/signature pairs를 모으면 prover에게 자신이 verifier이라고 속일 수 있습니다.
# 예를 들어 어떤 공개된 주소를 가진 prover가 보통 verifier과 메시지를 주고 받을 때 “Hello World”를 많이 쓴다고 가정해봅시다. 이를 제 3자가 알고 있다면 prover에게 “Hello World”를 메시지로 보내 자신이 verifier라고 속일 수 있습니다. - Proxy relaying attack은 중간자가 있다고 가정하는 공격입니다. prover에게 verifier인 척하고, verifier에게 prove인 척하는 중간자가 있다고 가정하면, 다음과 같은 공격이 가능합니다.. 먼저 verifier가 prover에게 challenge를 하면, 중간자는 똑같은 내용으로 prover에게 challenge를 합니다. 그 후 중간자는 prover의 응답을 받고 이를 verifier에게 보내게 됩니다. 이렇게 하면 중간자가 secret을 가지고 있다고 verifier을 속일 수 있습니다. 이러한 공격은 digital signature과 zkp에서 둘 다 가능합니다.
하지만 zkp 계열 중 tamper-resistance(non-malleability from simulation extractability)을 이용하면 중간자가 Proxy relaying attack을 통해 정보를 캐내려고 하는 것을 캐치할 수 있습니다. 하지만 digital signature에서는 공격을 캐치할 수 있는 방법이 없습니다.
ZKP Under the Hood
Using discrete logarithm
이제 zkp가 실제로 어떻게 구현되는지 알아봅시다.
- y: 주어진 값, p: large prime(소수), g: generator
- Prover는 g^x (mod p) = y 가 되는 x 값(secret)을 알고 있으며, y값은 x값을 통해 구할 수 있습니다.
- Prover는 사전에 y값을 Verifier에게 공유(setup)합니다.
- Prover는 모든 Verifier에게 x값을 알고 있다고 증명하고 싶지만, x값은 노출하고 싶지 않습니다.
Prover는 다음과 같은 과정을 통해 Verifier에게 secret의 정보를 알리지 않고, secret을 가지고 있음(statement is true)을 증명할 수 있습니다.
- Prover는 y = g^x(mod p)를 계산하여 Verifier에게 y값을 준다.
- Prover는 C = g^r (mod p)를 계산하여 C를 Verifier에게 주고, r 값은 공개하지 않는다. (r: random number)
- Verifier는 Prover에게 r을 요청하거나, (x+r) (mod (p-1))을 요청한다: challenge 0 or 1
- Verifier가 (x+r) (mod (p-1))을 요청한 경우, 1번과 2번을 통해 Verifier는 y값과 C값을 알고 있기 때문에 Verifier는 아래 식을 통해 Prover가 보낸 값이 true(the statement is true)인지 확인하면 됩니다.
- Verifier가 r을 요청한 경우, Verifier는 C를 알고 있기 때문에 r 값을 통해 C를 계산하여 값을 비교하면 됩니다.
Verifier가 Prover에게 (x+r) (mod (p-1))을 건네 받는 것은 x값을 숨기는 역할을 해주며, Prover가 가진 x 값을 유추하기 굉장히 어렵게 만듭니다. 이는 아래 설명된 Witness의 w의 값과 대응되는 내용인데, x값(w값)알고 있으면 y값을 구하기 굉장히 쉽지만, y값을 가지고 x값을 유추하기 굉장히 어렵습니다. 한편, 이 두 가지 challenge를 여러번 시도하면 Prover는 Verifier에게 x값을 가지고 있다고 확률적으로 증명할 수 있습니다.
마치며
본 편에서는 [블록체인 영지식 증명 시리즈]를 시작하며 첫 번째 주제로 영지식 증명이 무엇인지, 어떻게 구현될 수 있는지에 대한 내용을 다루었습니다. 이 내용은 차후에 진행되는 zk-SNARKs의 구현에 대한 설명을 이해하는데 기초적인 자료로 활용됩니다.
영지식 증명에 대한 궁금증이 해결되었기를 바라며, 피드백과 질문은 언제든지 환영합니다.
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
