Zero-Knowledge proof :: chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs

Published in

Decipher Media ｜디사이퍼 미디어

28 min readJul 26, 2018

Jungwoo Pyo(Jungwoo Pyo)
Jongbok Lee(Jongbok Lee)
Seoul Nat’l Univ. Blockchain Academy Decipher(Medium)

서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’에서 블록체인 기술에 관한 글을 연재합니다. 이번 주제는 “Zero-Knowledge Proof”이며, chapter 1. Introduction to Zero-Knowledge Proof & zk-SNARKs, chapter 2. Deep Dive into zk-SNARKs 로 나누어 설명합니다.

본 글의 작성을 위해 https://blockgeeks.com/guides/what-is-zksnarks/ 의 전체적인 흐름을 참고했으며, 설명의 용이성 및 완결성을 위해 원 글의 설명을 기반으로 타 참고자료 및 직접 제작한 자료를 추가하였습니다.

최근 블록체인 업계는 엄청난 자본의 유입으로 산업이 빠른 속도로 발전하고 있다. 산업의 발전 속도에 따라 기술의 발전 또한 빨라졌지만, 여전히 블록체인은 확장성이나 보안성 등 여러 부분에서 보완해야 할 점이 많은 기술이다. 그 중 한 가지 문제가 프라이버시 문제이다. 퍼블릭 블록체인에서 개인 간의 트랜잭션이 발생하면, 트랜잭션의 상세 내역이 모두에게 공개되기 때문에 이로 인한 피해를 입을 수 있다. 또 다른 문제는, 계속해서 증가하는 블록체인의 용량이다. 이러한 두 가지 문제를 해결할 수 있는 방식으로 zk-SNARKs라는 개념이 대두되었다. zk-SNARKs가 도입되면 거래의 익명성을 보장하고, 블록체인 데이터를 짧은 해시값으로 압축시켜 저장 용량을 줄여줄 수 있다. 먼저 zk-SNARKs의 근간이 되는 zero-knowledge proof가 무엇인지에 대해 알아보도록 하자.

zero-knowledge proof(이하 ZKP)는 prover가 자신이 알고 있는 지식을 공개하지 않으면서, 그 지식을 알고 있다는 사실을 verifier에게 증명하는 proof system으로, 1980년대 MIT의 Shafi Goldwasser, Silvio Micali and Charles Rackoff가 처음 제시했다. 여기서 prover는 knowledge을 알고 있음을 증명하는 주체이고, verifier는 prover가 해당 knowledge을 알고 있다는 사실을 확인 및 검증해주는 주체이다. ZKP의 이론적인 기반은 interactive proof system이다. Interactive proof system이란, prover와 verifier 상호 간 메시지를 교환하는 computation을 모델링한 abstract machine(이론적인 컴퓨팅 모델)을 뜻한다.

Interactive proof system에서 prover는 전능하고 무한정의 계산 자원을 가지고 있지만 신뢰할 수 없는 존재인 반면, verifier는 한정된 계산 자원을 가지고 있지만 신뢰할 수 있는 존재임을 전제한다. 그렇기 때문에 지금까지 interactive proof system과 관련된 대부분의 공격 시나리오는 prover가 악역을 맡고, 이들이 verifier를 속이려고 하는 상황을 가정하였다. 하지만 ZKP를 제시한 위 3명의 연구자들은 interactive proof system에서 추가적으로 verifier가 악의적인 목적을 품는 시나리오에 대하여 생각해 보았다. 예를 들어, prover가 자신의 주민등록번호를 알고 있고, 자신이 알고 있다는 사실을 증명하기 위해 관련 정보를 verifier에게 보낸 상황을 가정하자. 이 때, verifier는 전달받은 prover의 정보를 타인에게 판매하여 부당한 이익을 챙길 수 있다. 이와 같은 경우는 기존의 interactive proof system에서 다루고 있지 않던 문제였다. 따라서 이를 예방하기 위해 그들은 기존의 interactive proof system에 다음과 같은 2가지 질문을 던졌다.

누구나 verifier가 knowledge를 누설하지 않았다는 걸 확인할 수 있는가
verifier가 검증 과정 동안 알고 있어야 하는 knowledge의 비중은 어느 정도인가

위 의문점들을 해결하기 위해서 prover가 제공한 proof를 통해 악의적인 verifier가 검증을 수행할 수는 있지만, prover의 knowledge 자체에 대해서는 유추할 수 없는 proof system이 필요했다. 깊은 고민 끝에 그들이 내놓은 해결책이 바로 ZKP 이다.

ZKP의 property

Zero-knowledge proof는 항상 다음과 같은 조건을 모두 만족하여야 한다.

Completeness: 어떤 조건이 참이라면, honest verifier는 honest prover에 의해 이 사실을 납득할 수 있다.
Soundness: 어떤 조건이 거짓이라면, dishonest prover는 거짓말을 통해 verifier에게 조건이 참임을 절대 납득시킬 수 없다.
Zero-knowledge: 어떤 조건이 참일 때, verifier는 이 조건이 참이라는 사실 이외의 정보를 아무것도 알 수 없다.

Completeness와 Soundness는 일반적인 interactive proof system이 가지는 properties 이다. ZKP는 이를 만족하면서 추가적으로 세 번째 조건인 Zero-knowledge property까지 만족해야 하고, 결국 세 번째 조건이 ZKP의 주요한 property이다.

ZKP 가 적용된 사례를 다음 세 가지 예제를 통해 알아보자.

Examples of ZKP

Case 1: Alibaba’s Cave

아마 인터넷에 ZKP를 검색하면 나오는 대표적인 문제 중 하나가 Alibaba’s cave일 것이다. 그림과 같이 고리 형태의 동굴 가운데에 문이 있고, 그 문에는 도어락이 설치되어 있다. verifier는 prover에게 동굴에 설치된 도어락의 비밀번호가 무엇인지 직접 물어보지 않고 prover가 비밀번호를 알고 있다는 명제가 참인지를 확인하고 싶다. 이 조건문이 참인지를 확인하기 위해, 다음과 같은 과정을 따른다.

prover가 먼저 동굴에 들어간 다음, 도어락 근처로 이동한 후 verifier를 동굴 안으로 부른다.
verifier는 A와 B의 갈림길에 서서, prover에게 특정 길(A 또는 B)로 나오라고 지시한다.
prover는 verifier가 지시한 길로 나온다.
1.~3. 과정을 반복한다.

그림 1. Alibaba’s Cave [출처] What is zkSNARKs: Spooky Moon Math

1.~3. 과정만을 보았을 때는, prover가 정말 도어락의 비밀번호를 알고 있어서 verifier가 지시한 길로 나왔는지 확신할 수 없다. 우연에 의해 처음부터 prover가 A를 선택했고, 문을 열지 못했으나 verifier가 A로 나오라고 지시하는 경우가 충분히 있을 수 있기 때문이다. 따라서 우연의 가능성을 낮추기 위해, 위 과정을 일정 횟수 이상 반복한다. 여러 case를 수행하였을 때에도 매번 prover가 verifier의 지시대로 행동한다면, prover가 도어락의 비밀번호를 알고 있다는 사실을 verifier에게 납득시킬 수 있다.

이 예제에 ZKP의 property을 매핑시켜 보면 다음과 같다고 말할 수 있다.

Completeness: 어떤 조건이 참이라면, honest verifier는 honest prover에 의해 이 사실을 납득할 수 있다. => 여러 번의 경우에도 prover가 verifier의 지시를 지속적으로 따른다면, verifier는 prover가 도어락의 키를 안다고 납득할 수 있다.
Soundness: prover가 정직하지 못하다면, prover는 거짓말을 통해 verifier에게 조건의 타당함을 납득시킬 수 없다. => prover가 사실은 도어락의 키를 모르지만 안다고 거짓말을 하였을 경우, verifier에게 언젠가 한 번은 지시대로 수행하지 못하는 경우가 생길 것이기 때문에 자신이 도어락의 키를 안다는 것을 증명할 수 없다.
Zero-Knowledge: 어떤 조건이 참일 때, verifier는 이 조건이 정확히 무엇인지 알지 못하여야 한다. => 여러 번의 수행을 통해서 verifier는 prover가 도어락의 키를 알고 있다는 사실을 납득하였지만, 도어락의 키가 무엇인지에 대해서는 알지 못한다.

Case 2: Finding Waldo

그림 2. 이 그림에서 Waldo를 찾아라! [출처] What is zkSNARKs: Spooky Moon Math

이것은 “Spot the guy”라는 게임과 비슷하다. 위와 같이 여러 종류의 색상이 혼합된 다소 산만한 그림에서 Waldo라는 아래 그림과 같은 특정 인물을 찾아내는 것이다.

그림 3. Waldo [출처] What is zkSNARKs: Spooky Moon Math

위 문제를 푸는 데에는 크게 2가지 솔루션이 존재한다.

First solution

Waldo’s problem에서 prover가 Waldo를 찾았다는 것을 verifier에게 증명하는 첫번째 방법은 다음과 같다. 먼저, prover와 verifier가 같은 사진을 복사하여 한 장씩 나눠가진다. prover는 사진 속에서 Waldo가 있는 부분을 찾아서 자른 다음 나머지 부분을 버린다. 나머지 부분을 버렸기 때문에 prover가 자른 Waldo 조각이 사진에서 어디에 위치해 있는지는 verifier에게 밝혀지지 않는다. 그리고 나서 prover는 Waldo가 포함된 조각을 verifier에게 보여준다. prover와 verifier는 같은 사진을 나누어 가졌기 때문에, verifier는 prover가 증거로써 제시한 Waldo 조각이 같은 사진로부터 나왔음을 납득할 수 있고, prover는 Waldo가 어디에 위치해 있는지 밝히지 않으면서(zero-knowledge) Waldo가 위치한 곳을 찾았음을 verifier에게 증명할 수 있게 된다.

하지만 본 solution은 “soundness”의 기준을 충족시키지 못한다. 왜냐하면 prover가 verifier를 속이는 다양한 방법이 존재하기 때문이다. 실제로 사진에 포함되어 있지 않더라도, Waldo의 모습을 알고 있으면, prover와 verifier가 따로 떨어져 있을 때 Waldo의 모습을 기존의 사진과 같은 재질과 크기의 용지에 프린트한 후 내가 Waldo가 위치한 곳을 아는 것처럼 눈속임할 수 있게 된다. 이러한 문제는 어떻게 해결할 수 있을까?

해결할 수 있는 방법 중 하나는 prover에게 사진을 주기 전에, verifier가 사진 뒷면에 구별할 수 있는 패턴을 그려 넣는 것이다. 그리고 verifier가 prover를 고립된 방에서 문제를 해결하게 둠으로써 prover가 cheating할 수 있는 기회를 원천 차단한다. 후에 prover가 Waldo가 포함된 조각을 verifier에게 제출하고, 위 과정을 여러 번 반복한다. 나중에 prover가 제출한 Waldo의 조각들의 배경들은 조금씩 다를 테지만, 뒷면에 나와 있는 특정 패턴이 일정하다면 verifier는 비로소 Waldo가 어디에 위치해 있는 지 모르더라도 prover가 이를 알고 있다는 것을 납득할 수 있게 된다.

Second solution

Second solution은 매우 간단하다. 주어진 photo의 2배 이상 크기의 cardboard를 준비한 뒤, 직사각형의 구멍을 뚫어 놓는다. 그 구멍을 통해 prover는 사진에 있는 Waldo의 모습을 verifier에게 직접 보여준다. verifier는 cardboard의 뒷면을 볼 수 없기 때문에 실제로 자신이 보고 있는 Waldo가 사진에 어디쯤 위치해 있는지 알 수는 없지만(Zero-Knowledge), prover가 알고 있다는 것을 납득할 수 있게 된다.

Case 3: Mini Sudoku

# 이 case는 Ethereum Foundation의 Christian Reitwiessner가 devcon3에서 발표한 자료를 참고하였다.

다들 Sudoku 게임을 최소한 한 번씩 해봤거나, 적어도 게임에 대해 들어본 경험이 있을 것이다. Sudoku란 주어진 9*9 정사각형 판에 있는 각각의 가로, 세로줄에 1부터 9까지의 숫자를 한 번씩만 사용하여 판을 모두 채우는 게임이다. 이 9*9 정사각형 판은 다시 9개의 작은 3*3 정사각형 판으로 쪼개져 있는데, 해당 정사각형 판에도 1에서 9까지의 숫자가 한 번씩만 들어가야 한다.

ZKP를 실제 Sudoku 문제에 대입해 설명할 수도 있지만, 이를 통해 설명하기에는 너무 경우의 수가 많아지기 때문에 9*9 판을 4*4로 축소한 버전인 Mini Sudoku 게임을 통해 설명하도록 하겠다.

Mini Sudoku 문제가 주어졌을 때, prover와 verifier가 해결하고자 하는 일은 다음과 같다.

prover: Mini-Sudoku의 해답을 공개하지 않고, 해당 문제가 풀릴 수 있다는 것을 증명하려 함
verifier: prover가 Mini-Sudoku의 해답을 알고 있다는 것을 납득하려 함

이를 증명하는 과정은 다음과 같은 세 단계로 이루어진다.

Shuffling solution
shuffled solution과 mapping table을 가리는 과정
verifier가 선택한 sub solution을 공개하는 과정
shuffling solution

prover는 random one-to-one mapping을 통해, 가지고 있는 solution을 변형하는 과정을 거친다.

위 그림에서, 좌측에 위치한 판이 prover가 실제 가지고 있는 solution이다. prover는 이 solution을 verifier에게 바로 공개할 수는 없으니, 기존의 숫자를 다른 숫자로 겹치지 않게 shuffling시킨다. 우측의 판은 mapping table에 의해 한번 shuffle된 shuffled solution이다.

2. shuffled solution과 mapping table을 가리는 과정

prover는 shuffled solution과 mapping table을 verifier에게 공개하지 않고, 각각의 값을 숨긴 뒤에 공개를 하게 된다.

그림 5. masking shuffled solution & mapping table

3. verifier가 선택한 sub solution을 공개하는 과정

Sudoku에는 여러 sub solution들이 존재한다. 만일 prover가 solution을 알고 있다면, verifier가 다음과 같은 정보의 공개를 요구했을 때 이를 모두 만족해야 비로소 sudoku 문제의 해법을 안다고 할 수 있다.

특정 row를 공개했을 때, 해당 row에 포함된 숫자가 모두 달라야 함
특정 column을 공개했을 때, 해당 column에 포함된 숫자가 모두 달라야 함
특정 sub-square를 공개했을 때, 해당 sub-square에 포함된 숫자가 모두 달라야 함
임의의 cell들을 공개했을 때, 공개된 cell들이 기존 sudoku의 constraint를 해치지 않아야 함

위 조건들 중에서 verifier가 한 가지를 선택하여 정보공개를 요구할 수 있다. 예를 들어서, verifier가 “column 2를 공개하라”는 요청을 했다고 가정하자. prover는 요구 조건에 맞추어 masking한 column 2을 공개하게 된다.

공개된 solution은 sudoku의 constraint(특정 column에는 1부터 4까지의 숫자가 한번씩만 들어간다)를 해치지 않기 때문에, 위 사실은 verifier로 하여금 prover가 정말 solution을 알고 있다고 납득할 수 있게 되는 근거가 된다. 하지만 위 사실만을 가지고 prover가 solution을 알고 있다고 하기에는 무리가 있다. 왜냐하면 sub-solution을 만족하더라도 공개되지 않은 판에 적힌 숫자들은 sudoku의 solution이 아닐 수 있기 때문이다. 따라서 1.부터 3.까지의 과정을 여러 번 반복함으로써 판단의 정확성을 높이게 된다.

위 과정을 반복할 때마다, 1.의 shuffling solution 수행 전에 매번 mapping table을 새로 구성해야 한다. 만일 mapping table을 새로 만들지 않고 같은 mapping table을 계속 사용할 경우, prover가 sub-problem을 공개할 때의 단서를 모아서 실제로 prover가 어떤 solution을 가지고 있는 지 유추할 가능성이 생기게 된다. 이는 zero-knowledge의 특성에 반하기 때문에 prover의 solution을 verifier가 알 수 없도록 새로운 mapping table을 통해 shuffling을 해 준다.

결론적으로, 1. ~ 3.의 반복을 통해 prover는 자신의 solution을 공개하지 않으면서, solution을 알고 있다는 것을 증명할 수 있게 된다.

지금까지 위 세 가지 예제를 살펴보았는데, 이 예제들에서 공통적으로 발견되는 부분이 있다. 바로 prover와 verifier가 항상 on-line 상태여야 한다는 점이다. 이러한 constraint는 전체적으로 보았을 때 매우 비효율적인 구조로, 어느 정도의 개선이 필요했다. 1986년, Fiat과 Shamir가 결국 non-interactive ZKP를 제시하였고 이는 prover와 verifier의 on-line 여부에 관계없이 증명을 할 수 있도록 고안되었다. 다음에 소개할 Schnorr Identification Protocol도 non-interactive ZKP의 방식 중 하나이다.

From interactive to non-interactive: Schnorr Identification Protocol

Non-interactive 의 핵심은 결국 prover와 verifier의 메시지 교환이 최소화 되어야 한다는 것을 의미한다. 즉, prover가 특정 메시지를 verifier에게 보내고 난 다음 차후의 작업을 처리할 때 verifier로부터 추가로 전달받는 메시지가 필요하다면 이는 non-interactive한 방식이 아니다. prover가 증명에 필요한 메시지를 보내고 난 후 연결이 끊어진다고 하더라도 결국에는 그 메시지가 verifying되어야 하는 것이 non-interactive proof의 핵심이다.

암호학에서, Schnorr Protocol은 prover가 자신의 private key를 공개하지 않고 이를 가지고 있다는 것을 증명할 수 있는 방법이다. 키 교환과 관련된 프로토콜이기 때문에 지금까지 소개한 예제 중에 실제 블록체인에 적용될 수 있는 non-interactive ZKP와 가장 가까운 예제이다.

먼저, prover만 알고 있는 변수와, prover 및 verifier가 같이 공유하는 변수들은 다음과 같다. 각 변수의 값을 선택 혹은 도출하는 방식은 아래의 그림을 참고하길 바란다.

그림 7. Schnorr Identification Protocol에 사용되는 변수

prover는 s의 값을 verifier에게 공개하지 않고, 자신이 s를 알고 있다는 것을 납득시키려 한다.

먼저, prover는 random value인 r (0<r<q) 을 하나 선택하여 그에 따른 X 값을 계산한다. 그리고 나서 prover는 보내고자 하는 메시지 M과 X 값을 concatenate 시킨 후 이를 hash function에 통과시켜 새로운 서명 e를 만든다. e를 만든 이후에, prover는 이로부터 또 다른 서명 y 값을 도출해낼 수 있다. prover는 M과 도출해낸 서명 e, y 를 verifier에게 보낸다. 참고로, 이 방식은 non-interactive하기 때문에 prover는 해당 메시지를 보내고 난 후 off-line 상태가 되어도 증명에는 지장이 없다.

verifier가 prover로부터 받은 정보를 통해 수행하여야 할 것은, M,e,y를 통해 reproduce한 X’와 prover가 가지고 있는 X가 일치하는지를 확인하는 것이다. 그런데 정확히 말해서 X는 prover만 알고 있는 정보이기 때문에 reproduce한 X’와 X가 같은지를 직접적으로 비교할 수는 없다. 이에 verifer는 다음과 같은 과정을 통해 X’ 를 도출해낸다.

위와 같은 과정에 따라 X=X’ 임을 확인할 수 있다. 하지만 여기서 증명을 끝낸다면, verifier가 X’ 값을 도출하였어도 실제로 X와 같은지를 확인할 방법이 없다. 왜냐하면 verifier는 X값을 prover로부터 전달받지 못했기 때문이다. 그래서 verifier는 도출한 X’를 이용하여 e’ 값을 계산한다.

만일 실제로 X=X’ 라면, e = e’가 되어 verifier는 X=X’임을 납득할 수 있고, 결국 verifier는 private key s 값이 무엇인지는 모르지만, prover가 s를 알고 있다는 사실을 수학적으로 납득할 수 있게 된다.

위 예제가 ZKP의 property를 만족하는지 확인해 보겠다.

Completeness: 어떤 조건이 참이라면, honest verifier는 honest prover에 의해 이 사실을 납득할 수 있다. => X = X’ 가 참이라는 사실을 honest prover에 의해 납득할 수 있다.
Soundness: prover가 정직하지 못하다면, prover는 거짓말을 통해 verifier에게 조건의 타당함을 납득시킬 수 없다. => prover가 private key를 몰랐을 경우, prover는 X = X’ 임을 납득시킬 수 없었을 것이다..
Zero-Knowledge: 어떤 조건이 참일 때, verifier는 이 조건이 정확히 무엇인지 알지 못하여야 한다. => verifier는 결국 prover의 private key를 알지 못한다.

Add one more property — Succinctness: zk-SNARKs

zk-SNARKs는 zero-knowledge Succinct Non-interactive Argument of Knowledges의 줄임말로, 기존의 non-interactive ZKP에서 succinctness(간결함)가 추가된 개념이다.

기존의 non-interactive ZKP는 prover가 항상 on-line 상태일 필요가 없다는 장점이 있지만, 증명을 완료하는데 상당한 시간이 걸릴 수 있다는 단점이 있다. 간단한 예로, 위에서 언급한 Schnorr Identification Protocol에서도, verifier가 X’를 계산하기 위해서는 a^r mod p 라는 연산을 수행해야 한다. 언뜻 보기에는 쉬워 보이지만, 사실 이 연산은 a, r, p의 값이 커짐에 따라 상당한 시간이 소요되는 연산이다. 특히 암호학에서 사용되는 숫자의 크기는 매우 크기 때문에, 간단해 보이는 연산도 엄청난 횟수의 instruction을 수행하고 난 후에야 결과를 도출할 수 있다.

zk-SNARKs 에서 중요한 property는 바로 succinctness 이다. 글의 도입부에서 언급했듯이 interactive proof system은 verifier가 한정된 계산 자원을 가지고 있음을 전제로 한다. prover가 특정 knowledge를 알고 있다는 증거로 제출한 proof가 엄청난 size의 데이터라면, 이의 증명은 굉장히 비효율적일 것이다. 따라서 zk-SNARKs에서는 non-interactive ZKP의 proof size를 줄이고 빠른 시간 내에 verify를 수행할 수 있도록 하여 non-interactive ZKP의 실용성을 극대화하였다.

그렇다면 zk-SNARKs 의 동작 방식에 대한 설명을 통해 succinctness가 어떻게 적용되는지 확인해보도록 하자. 설명의 간결함을 위해 key generator G의 자세한 생성 과정, 알고리즘 P와 V의 세부 구현 등 자세한 동작 방식은 이후의 글에서 다룰 예정이며, 수학적으로 디테일한 부분은 Eli Ben-Sasson의 paper를 참고하기 바란다.

zk-SNARKs는 크게 세 과정으로 이루어진다.

Keygen: key generator G를 이용해 key pair (pk, vk)를 생성하는 과정
Prove: prover가 proof 를 생성하는 과정
Verify: verifier가 proof를 verifying하는 과정

1. Keygen: key generator G를 이용해 key pair (pk, vk)를 생성하는 과정

prover가 알고 있다고 주장하는 값인 witness(w) 가 있을 때, 이를 parameter로 받는 특정 program C가 있다고 하자. program C는 다음과 같다고 가정한다. (아래의 예는 가장 직관적이고 간결한 예시이며, 실제로 C의 세부적인 구현은 당연히 훨씬 더 복잡할 수 있다)

function C(x, w) {return ( hash(w) == x) ;}

위처럼 내가 w를 알고 있음을 증명할 수 있는 program C와 random sampling seed인 lambda를 generator에 parameter로 집어넣음으로써 key pair를 생성할 수 있다. 여기서 lambda는 prover 및 외부에 노출되어서는 안된다. 왜냐하면 prover가 이 값을 알고 있을 경우 fake proof를 생성할 수 있기 때문이다. 그렇기 때문에 key generating은 verifier가 수행하게 된다.

G(C, lambda) = (pk, vk)
pk = proving key
vk = verifying key

C의 program size bound를 l, input(x) size의 bound를 n, execution time bound를 T라고 할 때, key generating의 시간 복잡도는

O (l + n + T) · log(l + n + T)

에 해당한다. 즉, program이 길고, input size가 크고, 실행 시간이 길수록, key generating에 소요되는 시간이 길다.

2. Prove: prover가 proof(prf)를 생성하는 과정

증명 알고리즘을 P, 증명하고자 하는 witness인 w, w의 hash를 x 라고 할 때, prf를 구하는 방법은 다음과 같다.

prf = P(pk, w, x)

prover는 prf를 계산한 후, prf만을 verifier에게 전달한다. prf을 계산하는 데 걸리는 시간은 입력값 x와 w의 크기에 비례하여 길어진다. prf가 계산된 이후에는 당연히prf로부터 w 값을 유추할 수 없으며, prf의 길이는 매우 짧다. 이는 기존의 ZKP가 갖지 못했던 간결함(succinctness)의 특성을 갖게 해주는 요소이다. 실제로 Eli의 논문에서 구현된 zk-SNARKs 구현체의 proof는 230바이트, 288바이트 정도로 매우 짧았다.

3. Verify: verifier가 prf를 verifying하는 과정

verifier는 prf를 prover로부터 전달 받은 후, verifying algorithm V를 수행하여 prf의 진위 여부를 판단한다. verifying에 걸리는 시간은 매우 짧은데, 이 역시 zk-SNARKs가 간결함의 특성을 가지는 요소 중 하나이다. 자세한 실험 결과는 역시 Eli의 논문에서 확인 가능하다.

boolean: V(vk, x, prf)

위 값이 TRUE이면 prover는 w 값을 정말로 알고 있다고 할 수 있고, FALSE이면 prover는 w 값을 속였다고 판단하게 된다.

위 3단계의 과정을 통해서 verifier는 prover의 knowledge를 직접 확인하지 않고 이를 빠른 시간에 verifying할 수 있게 된다.

Applications of zk-SNARKs

현재 다양한 field에서 zk-SNARKs를 이용한 application이 고안되고 있다. 아래에서 소개하는 예제는 대부분 이론적인 것으로, 실제로 구현되어 사용되는 application은 매우 적다는 것을 참고하기 바란다.

Confidential Tx: Ethereum에서 transaction의 상세 내용을 숨기는 방식

zk-SNARKs를 이용하면 Ethereum에서 ETH를 송금하는 트랜잭션을 발생시킬 때, sender가 receiver에게 트랜잭션을 보낸 사실은 공개하고, sender와 receiver의 balance와 transfer amount에 대한 상세 내용을 숨기는 전송 방식이 가능하다.

For Blockchain Scalability

zk-SNARKs를 이용하여 blockchain의 scalability를 해결할 수 있다는 아이디어가 많이 제시되고 있다. blockchain에 참여하는 client는 실제로 블록의 내용을 모르더라도 full node의 proof를 보고 해당 블록의 내용이 변조되지 않았음을 빠르게 verifying할 수 있다. 결국, 이는 client의 block sync 속도를 급격하게 높여주게 되어 새로운 client들이 빠르게 네트워크에 참여할 수 있게 된다.

또한, blockchain의 append-only 한 속성으로 blockchain의 용량은 시간이 지날수록 계속 커진다. 특히 Ethereum에서는 trie 형태의 여러 global data structure(state trie, transaction trie, receipt trie 등)가 쌓여가고 있다. 이 trie 구조에는 각종 smart contract의 code와 storage 등 여러 데이터들이 자리를 차지하고 있는데, zk-SNARKs를 통해 실제 데이터를 pruning하고 데이터에 대한 proof만 남기는 방식으로 압축시킴으로써 contract가 차지하는 공간을 획기적으로 줄일 수 있다. smart contract의 code와 storage를 체인 위에 공개하지 않으면서 state change를 증명하는 방법이 가능하기 때문이다.

Zcash

zk-SNARKs는 Zcash Team에 의해 개발되었으며, zk-SNARKs 기반으로 작동하고 있는 application 중 가장 큰 규모이다. Zcash는 영지식 증명을 기반으로 완전히 익명화된 트랜잭션의 전송을 가능하게 한다. 기본적인 동작방식은 Bitcoin과 상당히 유사하나, 가장 두드러지는 차이점은 address의 종류가 2가지라는 것이다.

Shielded address와 Transparent address를 이용하여, 사용자들은 이 두 address를 사용하여 ZCash의 화폐인 ZEC를 공개적으로 전송할지, 사적으로 전송할지 선택할 수 있다. Shielded address에서 Transparent address로 송금을 하게 되면 전달받은 ZEC가 공개가 되며, 반대의 경우는 숨겨진다. ZCash는 두 주소 체계의 공존을 통해 자금 흐름의 추적을 거의 불가능하게 만들었고, 이는 ZCash가 익명 코인이라고 불리는 대표적인 이유 중 하나이다.

위에서 소개한 application 이외에도 zk-SNARKs는 블록체인이 당면하고 있는 여러 문제들을 해결할 수 있는 개념으로 다양한 분야에서 이용될 수 있을 것이다.

Conclusion

지금까지 zk-SNARKs에 관한 개괄적인 내용을 살펴보았다. zk-SNARKs는 암호학을 바탕으로 한 개념이기 때문에 이론 자체가 매우 어려워도 이를 잘 이해할 수 있다면, 응용할 수 있는 분야는 무궁무진할 것이라고 생각한다. 다음 글에서는 zk-SNARKs의 자세한 과정을 수학적 이론에 기반해서 조금 더 심도깊게 설명해보도록 하겠다.

References

Special thanks to Se Jin OH, Jihyeok Choy, Jeongho Jeon for reviewing.

다음글: chapter 2. Deep Dive into zk-SNARKs