입문자를 위한 영지식 증명 — 1편
해당 글은 서울대학교 블록체인 학회 디사이퍼(Decipher)에서 ‘입문자를 위한 영지식 증명’을 주제로 Weekly Session에서 발표한 내용입니다. 입문자를 위한 영지식 증명 1편에서는 영지식 증명이 탄생하게 된 과정을 알아보고, 어떠한 특징을 가지고 있는지 알아보고자 합니다.
Author: gganbukim, Min Young Kang
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
Reviewed By (박찬우, 하성환, 임요한)
1.입문자를 위한 영지식 증명 — 1편
신발을 잃어버린 월리를 찾아라
영지식 증명이란 무엇일까요? 쉬운 예시로 시작해보겠습니다. 아래의 사진은 추억의 게임 ‘월리를 찾아라’에서 발췌한 사진입니다. 사진 속에서 신발을 잃어버린 월리를 찾아봅시다.
신발을 잃어버린 월리를 찾다 지친 여러분은 제가 답을 알고 있는지 궁금합니다. 그리고 저는 답을 알고 있습니다. 하지만 이를 바로 알려드린다면 재미가 없겠죠? 따라서 제가 답을 알고 있다는 사실만을 증명하고자 합니다. 이를 위해서 위의 사진보다 훨씬 큰 가림막에 구멍을 뚫어 답을 보여드리겠습니다.
월리의 위치를 들키고 싶지 않은 prover
가림막은 상당히 크기 때문에 사진은 여러 방향으로 있을 수 있습니다. 따라서 여러분은 월리의 위치를 정확하게 파악할 수 없을 것입니다. 그러나 동시에 제가 답을 알고 있다는 사실은 알 수 있습니다. 이는 영지식 증명에 대한 쉬운 예시 중 하나입니다. 즉, 영지식 증명이란 증명을 함에 있어서 참/거짓(위의 예시에서는 신발을 잃어버린 월리의 위치를 알고 있는가에 해당)을 제외하고는 어떠한 것도 노출되지 않을 수 있는 증명을 의미합니다.
이번 글에서는 영지식 증명의 탄생 과정과 함께 영지식 증명이 해결하고자 하는 바에 대해서 살펴보고자 합니다.
1930년대 Alan Turing은 Turing Machine과 결정론적 알고리즘으로 계산 가능한 기계와 계산 가능한 함수를 정의하였습니다.
‘모든 문제를 풀 수 있는 알고리즘이 과연 존재할까?’
다시 말해 알고리즘을 이용하여 어려운 문제를 포함해 모든 문제를 풀 수 있는가에 대한 질문입니다. 이를 위해 튜링은 순수하게 기계적으로만 함수의 답을 알 수 있을 때 해당 함수를 계산 가능한 함수로 정의하였습니다. 그리고 계산 가능한 함수가 정의됨에 따라 계산 가능하지 않은 함수도 정의되었습니다. 그리고 여기서 알고리즘이란 결정론적 알고리즘을 의미합니다. 결정론적 알고리즘과 비결정론적 알고리즘에 대한 설명을 위해 잠시 아래의 예시를 살펴보겠습니다.
결정론적 알고리즘과 비결정론적 알고리즘
먼저 유한 상태 기계(Finite State Machine, FSM)에서는 시작 상태(Initial State, q0)와 받아들여지는 상태(accept, q2)를 정하고 주어진 경로(transaction)에 따라 받아들여지는 상태(accept)에 도달하면 입출력(x, 시작 상태와 최종 상태)이 해당 언어(Language)에 속한다고 표현할 수 있습니다. 쉽게 말해 아래 그림에서 q0에서 시작하여 q2에 있는 보물을 찾는 상황을 생각해봅시다.
위의 사진은 유한 상태 머신(Finite State Machine) 중에서도 결정론적 유한 상태 머신(Deterministic Finite State Machine)에 해당합니다. 해당 그림에서 시작 상태에 해당하는 q0에서 시작해보겠습니다. q0에서 출발하여 a-a-b의 경로를 따라 이동하면 q0 — q1 — q1 — q2로 이동하여 보물을 찾을 수 있게 되고, b-a의 경우 q0-q3-q4로 보물을 찾지 못하게 됨을 알 수 있습니다. 이렇듯 한번에 하나의 길로만 갈 수 있는 알고리즘을 결정론적 알고리즘이라고 합니다. 이번에는 비결정론적 알고리즘에 대해서 살펴보겠습니다.
위의 사진은 비결정론적 유한 상태머신(Nondeterministic Finite State Machine)에 해당합니다. 이 그림에서도 q0에서 시작하여 a-a의 경로를 따라 이동하면 여러 가지의 길을 갈 수 있음을 알 수 있습니다.
- q0-q1-q1(not accept)
2. q0 — q1 — q2(accept)
3. q0 — q3- q2(accept)
4. q0 — q3 — q4(not accept)
이렇게 총 4가지 경우의 길이 나올 수 있고, 이처럼 한번에 여러 개의 길을 갈 수 있는 알고리즘을 비결정론적 알고리즘이라고 합니다. 그리고 다양한 경우의 수에서 하나라도 받아들여지는 상태(accept)에 도달할 수 있는 경로가 있다면 해당 입출력은 받아들여지는 상태에 도달할 수 있다고 판단합니다.
이번에는 길이 무수히 많다고 가정해보겠습니다. 그렇다면 한번에 하나의 길만을 갈 수 있는 결정론적 알고리즘을 이용하여 보물을 찾으려면 많은 시간이 소요됩니다. 따라서 해당 보물을 빠르게 찾기 위해서는 한 번에 여러 개의 길을 갈 수 있는 비결정론적 알고리즘을 이용하여 문제룰 풀어야 할 것입니다. 그러나 결정론적 알고리즘으로도 문제를 빠르게 풀 수 있는 방법이 있습니다. 바로 누군가가 답을 알려주는 것입니다. 만약 누군가가 답을 알려준다면 주어진 답대로 길을 따라가 보물이 있는지 확인만하면 되기 때문에 한 번에 하나의 길을 가는 결정론적 알고리즘으로도 문제를 풀 수 있게 되는 것입니다. 이를 증명(Proof)의 도움을 받아 빠르게(Efficiently)하게 검증(Verify)할 수 있다고 표현합니다.
이것이 바로 증명 시스템의 핵심이 되는 개념입니다. ‘답을 아는 사람이 있다면’ 결정론적 알고리즘으로 빠르게 풀 수 없었던 문제를 빠르게 풀 수 있게 되기 때문이죠. 이 때, 답을 아는 존재를 증명자(이하 Prover)라고 이름 붙이고 이를 확인하는 존재를 검증자(이하 Verifier)라고 이름 붙이게 되는 것입니다. 이번에는 증명 시스템을 구축하기 위해 필요한 증명 시스템의 조건을 짚고 넘어가겠습니다. 바로 Completeness와 Soundness입니다.
증명 시스템의 조건 : Completeness & Soundness
- Completeness : x가 L에 속하면 proof가 존재해서 verifier가 proof의 도움을 받아 x가 accept되는 것이 존재해야한다. 즉, Prover가 정직하다면 결국 정직한 Verifier를 설득할 수 있어야 한다는 것입니다.
- Soundness : x가 L에 속하지 않아서 모든 proof에 대해 verifier가 x를 accept하지 않아야 한다. 즉, Prover는 진술이 참인 경우에만 Verifier를 설득할 수 있다는 것입니다.
*Efficiency : VL의 실행 시간(running time)은 x에 대해서 다항 시간(poly)이어야 한다. 추가적으로 efficiency라는 특징을 만족해야 실용적으로 이를 사용할 수 있기 때문에 이 또한 중요한 성질이라고 할 수 있습니다.
증명 시스템은 어디에 쓰일 수 있는가?
이러한 증명 시스템은 어디에서 사용될 수 있을까요? 기본적으로는 코드의 수행 사실을 증명하는 것에 사용될 수 있습니다. 이를 적용한다면 DID에서 신원 정보를 증명하는데 사용될 수 있고, 블록체인에서 데이터의 정당성을 증명하기 위해서도 사용될 수 있습니다. 그리고 금융 거래에서 신용 등급을 증명하거나 인공지능에서 정당한 학습을 증명하기 위해서도 사용될 수 있을 것입니다.
NP 증명 시스템
이번에는 증명 시스탬의 시작이라고도 할 수 있는 NP 증명 시스템에 대해서 살펴보도록 하겠습니다.
NP 증명 시스템에서는 Prover가 Verifier에게 입출력(x)과 중간 과정(witness)를 주고 Verifier가 이를 검증합니다. 여기서 중간 과정이란 함수에서 입력을 넣으면 중간 과정을 거쳐 출력이 나오게 되는데 이러한 중간 과정을 의미합니다. 즉, 아래의 그림에서 처럼 Prover가 입출력(x)과 중간과정(w)을 Verifier에게 전달하고 Verifier가 이를 검증하는 시스템인 것입니다. 해당 과정에서 Verifier는 결정론적 튜링 머신을 가정하고 Prover는 비결정론적 튜링 머신을 가정합니다. 앞에서 살펴보았듯이 많은 길이 존재할 때 보물을 찾아야 한다면 Verifier의 결정론적 알고리즘으로는 이를 찾는데 오랜 시간이 걸리기 때문에 비결정론적 알고리즘으로 보물을 찾은 Prover가 입출력과 중간과정을 Verifier에게 전달하고 실제로 보물이 있는지 이를 검증하는 시스템이라고 할 수 있습니다. 그러나 NP 증명 시스템의 한계는 Prover에게 너무 많은 역할이 부여되었다는 것입니다. 그렇기 때문에 악의적인 Prover는 잘못된 증거(proof)를 제공하여 Verifier의 비효율적인 계산을 발생시킬 수 있습니다.
악의적인 증명자(Fake Prover)를 막기 위해 무작위성과 대화를 도입한 IPS
이를 해결하기 위해 등장한 것이 바로 IPS(Interactive Proof System)입니다. NP 검증 시스템에서는 Prover가 먼저 Verifier에게 입출력과 중간과정을 보내면 Verifier는 해당 입력이 중간과정을 통해 출력으로 도달할 수 있는지에 대한 여부를 예 또는 아니오로 검증하였습니다. 이에 반해 IPS에서는 Verifier가 먼저 랜덤 포인트를 지정해주고 Prover에게 질문을 던집니다. 아래의 예시를 확인해보겠습니다.
Prover는 가장 아래에 속하는 k가 1인지의 여부를 알고 있다는 사실을 증명하고 싶습니다. IPS에서는 Verifier가 랜덤하게 포인트를 지정하여 Prover에게 물어봅니다. 예를 들어 x1 = 0일 경우 k=1 인 경우는 몇 개인가? Prover가 이를 알고 있다면 3개라고 대답할 수 있을 것이고 이러한 방식을 통해 증명 시스템을 구축하게 됩니다.
그러나 만약 Prover가 k=1인 경우를 찍어서 맞춘다면 어떻게 할까요? 이러한 문제는 IPS에서의 Completeness와 Soundness의 정의에서도 찾아볼 수 있습니다.
- Completeness :
L에 속하는 모든 x에 대해서 P,V가 대화를 통해 받아들여지는 상태(accept) 있는 프로토콜 P가 존재한다.
2. Soundness :
L에 속하지 않는 모든 x에 대해서 P,V가 대화를 통해 받아들여지는 상태(accept)가 있는 프로토콜 P가 존재하지 않는다. (이 때, 반드시 1/2이 아니어도 되며, 0이 아닌 값)
Soundness의 정의에서 알 수 있듯이 Prover가 찍어서 답을 맞출 경우를 고려하여 Soundness가 0이 아닌 값으로 정의됨을 알 수 있습니다. 이는 무작위성(randomness)의 도입으로 인해 발생한 문제입니다.
따라서 무작위성의 도입으로 인해 발생하는 문제인 찍어서 맞추는 경우를 제거하기 위해 도입된 것이 바로 대화(interaction)입니다. 쉽게 말해 x1 = 0 인 경우를 물어봐서 Prover가 이를 맞췄다면 이번에는 x2 = 0인 경우를 물어보고 이를 반복하는 것입니다. 만약 Prover가 찍어서 답을 맞출 확률이 1/2라면 이러한 대화 과정(interaction)을 반복할 경우 찍어서 맞출 확률이 계속해서 줄어들기 때문에Prover가 알고 있는지를 확률적으로 검증할 수 있게 되는 것입니다. 즉, 의도적으로 soundness 에러를 부여했지만 그럼에도 반복해서 확률적으로 soundness를 확보할 수 있게 된 것이죠.
정리해보면 NP 증명 시스템에서는 Prover에게 너무 많은 역할이 부여되었고 보다 효율적인 시스템을 위해 NP 증명 시스템에 무작위성과 대화를 도입한 IPS가 탄생하였습니다. (NP + Interactive + Randomness = IPS) 그리고 무작위성의 도입으로 인해 Prover가 답을 찍어서 맞출 수 있는 확률이 발생하였지만 이는 대화를 반복함으로써 이를 확률적으로 제거할 수 있었습니다.
그러나 NP증명 시스템에서도 한계가 존재하는데 바로 대화(Interactive)의 비효율입니다.
대화를 이용한 증명 시스템에서는 Prover와 Verifier가 하나씩 물어보고 답하기 때문에 대화 과정에서 비효율이 존재하게 됩니다. 따라서 이를 해결하기 위해 PCP가 등장하게 됩니다.
대화의 비효율을 극복하기 위해 등장한 PCP
기존의 IPS 방식에서는 Prover와 Verifier가 하나씩 물어보고 답하는 방식이었다면, PCP에서는 Prover가 Oracle access to proof라는 큰 증명을 내보내고 Verifier는 해당 증명과 상호작용(interaction)하여 검증을 진행합니다. 이 때, Verifier는 해당 증명에서 원하는 값을 선택하여 검증을 진행합니다. Verifier가 원하는 값을 선택하는 과정은 시험과도 비슷합니다. 시험 문제가 해당 내용의 전부를 대변하는 것은 아니지만 시험을 통해서 문제를 선별하고 해당 내용을 알고 있는지 판별하는 것처럼 Verifier 또한 큰 증명 속에서 몇 가지를 확인함으로써 증명을 수행하게 됩니다. 따라서 IPS 방식에서 발생하였던 대화의 비효율을 보완하는 것이죠. 그럼에도 불구하고 PCP 방식 또한 여전히 증명(oracle access to proof)과 상호작용해야하는 문제가 발생합니다.
또한, 지금까지 살펴 본 NP, IPS, PCP에서 발생하는 공통적인 문제가 있습니다. 이는 Verifier가 Prover의 정보를 얻어서 Prover인 척할 수 있다는 것입니다. 증명 시스템이 사용되는 예시 중 하나인 신원 증명을 예시로 들면 Prover가 신원 정보를 통해 신원을 증명할 때 Verifier가 이를 이용하여 Prover인 행세를 할 수도 있으므로 이 또한 해결해야하는 문제입니다.
이를 해결하기 위해서는 어떻게 해야할까요? 바로 영지식 증명이 등장하게 된 배경입니다.
Adversarial Verifier를 방지하기 위한 영지식 증명의 등장
<<The Knowledge Complexity of IPS(1985)>>에서는 어떤 이론을 어떤 사람에게 증명하기 위해 필요한 추가 정보(additional knowledge)를 어떻게 0으로 만들 수 있을 것인가?그리고 이러한 추가 정보가 없는 것을 영지식 증명이라고 정의하였습니다.
”Additional knowledge level should be zero”
어떻게 하면 이러한 추가 정보(additional knowledge)를 0으로 만들 수 있을까요?
위의 그림에서 Prover는 입출력(x)과 중간 과정(w)을 통해 증명(**π)**을 생성합니다. Verifier가 Prover가 사용한 중간 과정 없이 증명을 만들어낼 수 있을까요? 만약 가능하다면, Prover는 중간 과정을 제공하지 않고 증명만을 제공하여 Verifier가 이를 검증할 수 있을 것입니다. 이를 위해서는 어떠한 알고리즘과 같은 결과가 나올 수 있는 또다른 알고리즘이 필요하게 됩니다. 즉, (1) 알고리즘을 숨기고 싶은데 (2) 해당 알고리즘과 같은 결과가 나오는 알고리즘이 있을까? 라는 과제에 직면하게 됩니다. 그리고 이러한 역할을 하는 것이 바로 시뮬레이터(simulator)입니다. 시뮬레이터는 실제 알고리즘을 노출시키지 않을 수 있으면서도 동일한 값을 반환하는 일방향 함수 알고리즘입니다. 쉽게 말해 계산을 하면 같은 값이 나오지만 같은 알고리즘은 아니라는 의미입니다. 이는 순수하게 기계적인 관점에서 추가 지식을 얻지 못하는 특별한 종류의 Prover라고도 할 수 있습니다. Prover가 가진 중간 과정(w) 없이 증명을 생성할 수 있기 때문이죠. 여기에서 중요한 점은 실제 함수가 노출되지 않도록 암호화가 얼마나 안전한지가 중요한 포인트가 될 것입니다.
시뮬레이터에 속하는 Bit commitment를 예시로 들어보겠습니다. 시뮬레이터의 중요한 특징은 Hiding과 Binding입니다. Hiding은 말그대로 Prover가 증명을 숨길 수 있도록 하는 특징을 의미합니다. 즉, 커밋(commit) 값을 통해 입력 값을 알 수 없어야 한다는 특징입니다. 그림에서 0과 1이 답일 경우 시뮬레이션 알고리즘을 통해 computation 0과 computation 1을 제공하며 각각은 0에서 나온 값인지 1에서 나온 값인지 구별할 수 없습니다. 그리고 Binding이란 커밋(commit) 값에 해당하는 다른 입력 값을 구할 수 없어야 한다는 특징입니다. 이러한 특징을 만족하는 시뮬레이터를 통해 알고리즘을 제공하지 않으면서도 같은 값이 나오는 알고리즘을 사용하여 Prover의 중간 과정을 Verifier가 알 수 없는 상태에서도 증명이 가능하게되는 것입니다.
위의 내용들을 정리하면 NP 증명 시스템은 Prover에게 너무 많은 역할이 부여되었고 Prover가 잘못된 정보를 보내는 것을 막아야 했습니다. 따라서 IPS가 등장한 것이죠. IPS는 Prover의 역할을 줄이고자 무작위성(randomness)과 대화(interaction)를 도입했습니다. Verifier가 Prover에게 랜덤 포인트에서 질문을 하여 Prover가 알고 있는지를 검증하는 시스템입니다. 여기서 발생할 수 있는 첫 번째 문제인 (1)Prover가 답을 찍어서 맞출 수 있다는 문제는 여러번 질문하여 대화를 통해 해결하고자 하였고 (2) 대화 시스템에서 비효율적으로 걸리는 시간에 대해서는 PCP를 통해 해결하고자 하였습니다. 그러나 PCP에서는 여전히 Verifier가 증명과 상호작용해야하는 문제가 존재하였으며 NP, IPS, PCP 모두 Verifier(skeptical verifier)가 Prover의 증명을 이용하여 Prover인척 할 수 있다는 문제가 존재하였습니다. 따라서 이를 해결하기 위해 영지식 증명이 등장하게 된 것입니다. 그렇다면 영지식 증명을 어떻게 구현할 수 있을까요? 1992년도, 1994년도에 Killian과 Micali는 PCP를 이용하여 영지식 증명 시스템을 구현하고자 하였습니다.
PCP를 기반으로 한 ZK-SNARK, PCP-based ZK-SNARK
앞서 살펴보았던 PCP 방식에서는 Prover가 oracle access to proof라는 큰 증명을 내보내고 Verifier가 해당 증명과 상호 작용하여 검증을 진행하였습니다. 그러나 해당 시스템에서는 증명 크기가 크기 때문에 효율적인 시스템을 달성하기에는 부족함이 있었습니다. 따라서 이를 해결하기 위해 PCP를 기반으로한 ZK-SNARK에서 Prover는 증명을 머클 해시 트리(merkle hash tree)로 구현하고 Verifier에게 머클 루트(merkle root)만을 주는 방식을 이용하여 증명의 크기를 줄일 수 있게 됩니다.
즉, 위의 그림에서 Prover는 Verifier에게 증명하고 싶은 부분과 이에 해당하는 머클 경로(merkle path)를 같이줍니다. 이를 통해 기존에 poly(|C|)만큼 걸렸던 시간이 klogc만큼(k는 Verifier가 안정성을 위해 선택하는 개수) 걸리므로 보다 효율적인 시스템이 될 수 있습니다.
해당 시스템을 통해 증명의 크기를 줄여 보다 효율적인 시스템을 구축하였지만 여전히 증명과 상호작용해야하는 과정이 존재하므로 비효율적인 부분이 남아있습니다. 따라서 상호작용을 제거하기 위해서 fiat-shamir transform를 사용합니다.
위의 그림에서 fiat-shamir transform을 사용할 경우, r 대신 H(x, msg1)을 사용하여 Prover가 스스로 랜덤 값을 만들어 사용할 수 있습니다. Prover가 스스로 랜덤 값을 만들지만 이러한 방식을 사용할 수 있는 이유는 Prover가 해시 값을 컨트롤할 수 없기 때문입니다. 그러나 이러한 방식은 Prover의 계산 시간이 너무 오래 걸려 이론적으로만 가능하며 실용적이지 않은 시스템이었습니다.
이러한 문제로 인해 현재는 IOP를 이용하여 영지식 증명을 구현하고 있으며 회로(circuit)를 다항식으로 바꾸는 polynomial interactive oracle proofs, 해당 다항식이 맞는지 체크하는 polynomial commitment scheme을 이용하여 ZK-SNARK를 구현하고 있습니다. 해당 구현에 대한 자세한 내용은 입문자를 위한 영지식 증명 - 2편을 참고해주세요.
지금까지 영지식 증명이 나오기까지의 과정을 설명하였습니다. 정리하면 다음과 같습니다.
- NP 증명 시스템
특징 : 결정론적 알고리즘과 비결정론적 알고리즘에서 풀 수 있는 문제를 정의함으로써 증명 시스템 구축. 비결정론적 튜링머신으로 가정되는 Prover는 결정론적 튜링머신으로 가정되는 Verifier에게 답을 알려주고 Verifier는 이를 검증함.
한계 : Prover에게 너무 많은 역할이 부여되었고 Prover가 거짓 증명을 보낼 수 있는 가능성이 존재.
2. IPS(Interactive Proof System)
특징 : 무작위성(randomness)과 상호작용(interaction)의 도입으로 악의적인 증명자를 방지하고자 함.
한계 : Prover와 Verifier가 하나씩 물어보고 답하는 방식이므로 상호작용의 비효율이 존재.
3. PCP(Probabilistic Checkable Proof)
특징 : Prover가 Oracle access to proof라는 큰 증명을 내보내고 Verifier는 해당 증명과 상호작용하는 방식.
한계 : 여전히 증명과 상호작용을 해야하는 비효율이 존재.
4. NP, IPS, PCP
한계 : Verifier가 Prover의 증명을 훔쳐 Prover 행세를 할 수 있는 가능성이 존재.
따라서 영지식 증명이 등장하게 됩니다. 아래의 내용들은 2편에서 다루는 내용의 미리보기입니다.
- 영지식 증명(Zero-Knowledge Proof)
특징 : 중간 과정에 대한 정보 없이 검증이 가능하다는 특징이 존재. 이를 통해 영지식 증명의 첫 번째 특징인 프라이버시 확보.
2. ZK-AOK(ZK-Argument of Knowledge)
특징 : Verifier가 증거를 올바르다고 판단할 경우, Prover의 중간 과정이 올바르다.
3. NIZK-AOK(Non-interactive ZK-AOK)
특징 : 상호작용의 비효율 제거
4. Succinct(ZK-SNARK)
특징 : Succint란 Verifier의 시간이 Prover보다 적게 걸린다는 특징을 의미하며 이를 위해서는 증명의 크기가 작고 검증 시간이 빨라야 함. 증명 시스템을 실용적으로 사용되기 위해서는 Succinct라는 특성을 만족해야 하고, 위의 특징들(Succint, Non-interactive, Argument of Knowledge)을 만족하는 ZK-SNARK는 확장성이라는 특징을 가짐.
이렇게 증명 시스템은 영지식 증명으로 발전하게 되고 ZK-SNARK에 도달하면서 프라이버시와 확장성이라는 특징을 가지게 되었습니다. 그리고 이러한 특징을 적용할 수 있는 대표적인 분야가 바로 블록체인인 것입니다. 2편에서는 ZK-SNARK의 실제 구현 방법과 문제점 및 ZK-STARK가 등장하게 된 배경, 그리고 영지식 증명을 기반으로 한 기술들이 블록체인에서 어떻게 적용되고 있는지에 대해서 살펴보겠습니다.
Reference
