2023. 6. 15. 10:58ㆍBlockchain/Roll up
※ 원글 작성 : 23년 6월 12일
Roll up Series
[Blockchain/Roll up] - Rollup의 개념과 특성
[Blockchain/Roll up] - ZK rollup - 1. 목적/library
[Blockchain/Roll up] - ZK rollup - 2. ZKP
[Blockchain/Roll up] - ZK rollup - 3. zkEVM 프로젝트
[Blockchain/Roll up] - ZK rollup - 4. zk-SNARK의 Circuit & QAP
zk-SNARK 등 ZK rollup을 위한 기술을 사용함에 있어 그래도 기술의 근본인 ZKP는 언급하고 가야 맞을거 같아서 Zero Knowledge Proof의 개념과 의의를 확인하고 간단히 수학적으로 어떻게 증명을 하는지 확인하기 위해 포스팅을 진행하려 한다.
Zero Knowledge Proof
ZKP(영지식 증명)은 어떤 정보에 대한 실제 값을 상대방에게 보이지 않고서 해당 값을 알고 있다는 것을 상대방에게 증명할 때 사용한다. 이 때 증명하고자 하는 사람을 prover, 증명자와 정보를 주고 받는 사람을 verifier라고 한다.
ZKP는 다음 3가지 성질을 만족시켜야 한다.
- 완전성(completeness): 어떤 문장이 참이면, 정직한 prover는 정직한 verifier에게 이 사실을 납득 시킬 수 있어야 한다.
- 건실성(soundness): 어떤 문장이 거짓이면, 어떠한 부정직한 prover라도 정직한 verifier에게 이 문장이 사실이라고 납득 시킬 수 없어야 한다.
- 영지식성(zero-knowledgeness): 어떤 문장이 참이면, verifier는 문장의 참/거짓 이외에는 아무것도 알 수 없어야 한다.
이러한 성질을 만족하는 장 자크 키스케다(Jean-Jacques Quisquater)의 아주 간단하고 유명한 예제를 언급 해본다.
Example
위 그림은 입구와 출구가 같은 동굴을 나타내며 입구에서부터 양갈래길이 존재한다. Prover는 갈림길 중간에 가로막고 있는 문을 열 수 있는 열쇠를 소유하고 있다고 가정하고, 이 열쇠를 직접 verifier에게 보여주지 않고 자신이 열쇠를 가지고 있음을 증명하고 싶다. (입구에서는 이 문이 보이지 않는다.) 먼저 prover가 A, B 통로중 아무것이나 골라서 문쪽으로 위치해 있고 verifier는 prover가 어떤 통로로 갔는지 알지 못하는 상태이다.
verifier는 통로의 초입에 위치해 있고 prover에게 A, B 중 지정한 통로로 나와보라고 소리친다.
prover가 verifier가 요청한 통로로 나오면 실제로 prover의 열쇠를 확인하지 않고도 prover가 열쇠를 소유하고 있음을 verifier는 판단할 수 있게 된다.
그림에서 처럼 prover가 B로 들어갔다고 가정하자. Verifier가 B로 나오라고 요청했을 시 prover는 굳이 문을 열지 않고 B로 나와서 verifier를 만날 수 있고 verifier가 A로 나오라고 요청했을 시 prover는 열쇠로 문을 열고 A로 나와서 만날 수 있다. 만약 prover가 열쇠를 가지고 있지 않다면 prover는 처음 들어갔던 통로로만 나올 수 있기 때문에 50%의 확률로 verifer의 요구를 만족할 수 없으며, 이 테스트를 여러번 반복하면 prover는 verifier의 요구를 전부 만족시킬 확률은 매우 낮아진다. 20번만 반복해도 열쇠를 가지고 있지 않는 prover가 verifer의 요청을 모두 만족시킬 확률은 100만분의 1 이하가 된다.
Interactive/Non-interactiver ZKP
위의 예시는 ZKP의 성질을 만족하는 예시가 된다. 하지만 증명의 정확성을 높이기 위하여 prover와 verifier 간에 지속적으로 메시지 교환이 이루어져야 한다. 이러한 ZKP를 interactive ZKP라 한다. 이를 네트워크 시스템에 접목시켜보면 증명의 정확성을 높이기 위해 request/response를 많이 수행해야 한다는 뜻이 되며, 네트워크의 효율성이 많이 떨어지게 될 것이다. 또한 증명을 계속 전달하다가 예기치 못한 통신 장애 등으로 proof를 전달하지 못한다면 prover는 verifier의 검증을 통과하지 못할 것이다.
이를 보완하기 위해 non-interactive ZKP도 존재한다. Non-interactive ZKP는 prover가 verifier에게 proof를 전달하는 메시지 전달이 딱 한번 이루어지고 추가적인 communication이 없다. 그리하여 네트워크 BW를 아낄 수 있고 검증의 안정성도 높일 수 있다. Non-interactive ZKP를 구현하기 위해서는 신뢰할 수 있는 trusted 3rd party가 필요하다. prover와 verifier에게 ZKP를 위한 정보를 동일하게 제공해주고, 해당 정보로 prover는 proof를 생성하고 verifer는 정보를 활용하여 proof를 검증하게 된다.
How?
그렇다면 Non-interactive ZKP가 이루어지는 과정을 수학적으로 확인해본다. (Schnorr protocol with Fiat-Shamir)
전체적인 프로세스는 위 그림과 같으며, 설명을 위한 notation을 먼저 정의 한다.
| Value | Desc |
|---|---|
| $i$ | Prover (Representative & Participant node) |
| $k$ | Verifier (Authenticate server) |
| $X_i$ | Prover's private key |
| $Y_i$ | Prover's public key($Y_i=g_i^{X_i}modP$) |
| $P, Q$ | Random prime number |
| $G_i$ | Generator ($g^QmodP=1$) |
| $E_i$ | Random number |
| $R_i$ | Proof variable |
| $H()$ | Cryptographic hash function |
| $D_i$ | Hash value |
| $U_i$ | Integer number(from $D_i$) |
| $W_i$ | Prover variable |
| $U_k$ | Integer number(from $D_i$ |
| $R_k$ | Proof variable |
위 프로세스는 다음과 같다.
- Prime number 중에서 랜덤으로 $P, Q$를 선택
- $g_i^QmodP=1$를 만족하는 $g_i$를 계산
- 랜덤 넘버 $E_i$를 설정
- $E_i$와 $P$를 사용하여 $R_i$ 계산 ($R_i=g_i^{E_i}modP$)
- $Y_i$ 및 $R_i$를 사용하여 $D_i$ 계산 ($D_i=H(Y_i,R_i)$)
- $D_i$의 integer값 $U_i$ 도출
- prover variable(=witness) $W_i$계산 ($W_i=E_i-U_iX_i$)
Prover가 verifier에게 $g_i$, $R_i$와 $W_i$ 전달
- 알고 있는 prover의 pubkey $Y_i$와 전달받은 $R_i$를 사용하여 $D_k$ 계산 ($D_k=H(Y_i,R_i)$)
- $D_k$의 integer 값 $U_k$ 도출
- $W_i, Y_i, U_k$를 사용하여 $R_k$ 계산 ($R_k=g_i^{W_i}Y_i^{U_k}modP$)
- Verifier는 전달받은 $R_i$와 계산한 $R_k$가 일치하면 ZKP 정상 확인
증명 과정은 아래와 같다.
$R_k=g_i^{W_i}Y_i^{U_k}modP$
$=g_i^{E_i-U_iX_i}\times g_i^{X_iU_k}modP$
$=g_i^{E_i}modP$
$=R_i$
이로써 $X_i$를 전달하지 않고도 $X_i$를 알고 있다는 것을 증명 가능하다.
Conclusion
ZKP는 privacy를 보장한다는 측면에서 모든것이 오픈되어 있는 블록체인 분야에서 활용 범위가 매우 큰 알고리즘이다. Zcash 처럼 sender/receiver를 숨기는 곳에서도 사용할 수 있고, DID의 verifiable presentation을 제출 시에도 privacy를 위해 ZKP를 활용하면 숨길 수 있다. 무엇보다도 ZKP는 앞으로 블록체인 확장성의 주요 모델이 될 ZK rollup의 기본 개념으로써 큰 의의를 갖는다.
ZK rollup도 ZKP의 정보 숨김 기능을 사용한다. '어떠한 정보를 숨기는가' 라면, 사이드 체인의 전체 tx 정보를 숨기는(메인넷에 모든 정보를 제출하지 않는)것이다. 사이드체인의 상태 변화된 모든 데이터를 메인 체인이 전달하지 않고도 해당 상태 변화가 올바른 것임을 검증하고, 이를 위해 메인 체인이 사이드 체인의 상태 정보를 알 필요가 없어진다.
메인넷은 ZK proof만 보고 올바르게 상태변화가 이루어진 것임을 확인해야 하는데, 크게 두가지를 검증한다.
- Proof가 유효한지 확인
- Proof는 암호학적으로 안전한 서명 및 랜덤값으로 구성되어 있기 때문에 이 값들이 올바르게 포함되었는지, proof 자체가 유효한지 확인이 필요하다.
- Merkle tree root hash 계산
- Proof 내에는 이전 state와 새로운 state의 차이를 나타내는 데이터를 포함하여 메인 체인은 이전 상태의 merkle root hash를 가져올 수 있고(메인 체인에 저장되어 있음), proof에서 얻은 데이터를 추가하여 새로은 merkle root hash를 생성 가능하다.
- 이 때 proof에는 계산한 새로운 merkle root hash가 존재하기 때문에 메인 체인에서 계산한 값과 proof에서 전달한 값이 일치하는 지 확인해야 한다.
ZKP 자체가 개념적으로나 수학적으로나 어려운 알고리즘이고, 이를 응용하여 만든 기술은 그보다 더 어렵기 때문에 이해와 활용에 많은 시간을 요한다. 필자도 아직 ZKP, ZK rollup에 대해서는 어려움을 많이 느끼고 있지만 앞으로 블록체인을 연구함에 있어 ZK는 필수적이라 생각되어, 공부를 많이 하여 자연스러운 활용이 가능하도록 만들어 볼것이며, 중간중간 알게 되는 관련 지식도 블로그에 게시해 보려 노력할 것이다.
참고
https://ko.wikipedia.org/wiki/%EC%98%81%EC%A7%80%EC%8B%9D_%EC%A6%9D%EB%AA%85
'Blockchain > Roll up' 카테고리의 다른 글
| ZK rollup - 4. zk-SNARK의 Circuit & QAP (0) | 2023.09.21 |
|---|---|
| ZK rollup - 3. zkEVM 프로젝트 (0) | 2023.09.21 |
| ZK rollup - 1. 목적/library (0) | 2023.06.15 |
| Rollup의 개념과 특성 (0) | 2023.06.14 |