블록체인 현재 문제
- 프라이버시 문제
- 블록체인 용량
zk-SNARKs의 도입으로
- 익명성을 보장한다.
- 블록체인 데이터를 짧은 해시값으로 압축시켜 저장 용량을 줄일 수 있다.
zk-SNARKs의 근간이 되는 기술은 **영지식(zero-knowledge proof)**이다.
영지식:
- prover가 자신이 알고 있는 지식을 공개하지 않는다. 하지만 그 지식을 알고 있다는 사실을 verifier에게 증명할 수 있다. 이러한 시스템을 proof system이라고 부른다.
- prover는 지식을 알고 있음을 증명하는 주체를 말한다.
- verifier는 prover가 해당 지식을 알고 있다는 사실을 확인 및 검증해주는 주체를 말한다.
ZKP의 이론적인 기반은 Interactive Proof System이다. Interactive Proof System는 Prover와 Verifier 상호 간에 메시지를 교환하는 Computation을 모델링한 Abstract Machine을 뜻한다.
ZKP는 Prover가 제공한 Proof를 통해 악의적인 Verifier가 검증을 수행할 수는 있지만, Prover의 knowledge 자체에 대해서는 유추할 수 없는 Proof System이 필요했다.
ZKP는 다음과 같은 조건을 모두 만족해야 한다.
- Completeness: 어떤 조건이 참이라면, Honest Verifier는 Honest Prover에 의해 이 사실을 납득할 수 있다.
- Soundness: 어떤 조건이 거짓이라면, Dishonest Prover는 거짓말을 통해 Verifier에게 조건이 참임을 절대 납득시킬 수 없다.
- Zero-knowledge: 어떤 조건이 참일 때, Verifier는 이 조건이 참이라는 사실 이외의 정보를 아무것도 알 수 없다. 이 조건이 ZKP의 주요한 property다.
Case 1: Alibaba's Cave
Prover가 비밀번호를 알고 있다는 명제가 참인지를 확인하고 싶다. 이 명제가 참인지를 확인하기 위해, 다음과 같은 과정을 따른다.
- Prover가 먼저 동굴에 들어간 다음에, 도어락 근처로 이동한 후 Verifier를 동굴 안으로 부른다.
- Verifier는 A와 B의 갈림길에 서서, Prover에게 특정 길(A 또는 B)로 나오라고 지시한다.
- Prover는 Verifier가 지시한 길로 나온다.
- 1.-3. 과정을 반복한다.
이 과정을 반복하다보면, Prover가 도어락의 비밀번호를 알고 있다는 사실을 Verifier에게 납득시킬 수 있다.
이 때 Completeness, Soundness, Zero-Knowledge를 모두 만족한다. 이에 대해서는 한번 생각해보자.
Case 2: Finding Waldo
Case 3: Mini Sudoku
위의 세 가지 경우에서 공통적으로 발견되는 부분이 있는데, 그것은 바로 Prover와 Verifier가 항상 Online 상태여야 한다는 점이다. 이는 결국 Non-Interactive ZKP를 제시하였고, 이는 Prover와 Verifier의 Online 여부에 관계없이 증명을 할 수 있도록 고안되었다.
Non-Interactive의 핵심은 Prover와 Verifier의 메시지 교환이 최소화되어야한다는 것이다.
암호학에서 Schnorr Protocol은 Prover가 자신의 PK를 공개하지 않고 이를 가지고 있다는 것을 증명할 수 있는 방법이다. 이 프로토콜은 실제 블록체인에 적용될 수 있는 Non-Interactive ZKP와 가장 가깝다고 볼 수 있다.
먼저 Prover만 알고 있는 변수들과, Prover 및 Verifier가 같이 공유하는 변수들이 있다.
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는 X`를 도출해내고, e`를 도출해낸다.
zk-SNARKs는 Zero-Knowldge Succinct Non-Interactive Argument of Knowldeges의 줄임말로, 기존의 Non-Interactive ZKP에서 Succinctness(간결함)가 추가된 개념이다.
위의 Protocol에서는 a^r mod p에 포함된 값의 크기에 따라 다소 시간이 많이 걸린다. (Note: Verifier는 한정된 계산 자원을 가지고 있음을 전제한다.)
zk-SNARKs는 다음과 같은 과정으로 이루어진다.
- Keygen: Key generator G를 이용해 key pair(pk, vk)를 생성한다.
- Prove: Prover가 Proof를 생성한다.
- Verify: Verifier가 Proof를 Verifying한다.
- Keygen: Key Generator G를 이용해 Key pair(pk, vk)를 생성하는 과정
