제로지식 증명 입문 가이드: 발전 역사, 응용 및 기본 원리

2023.12.07

제로지식 증명 입문 가이드: 발전 역사, 응용 및 기본 원리

ZKP 이론과 응용 측면의 일부 변화를 처음부터 다시 정리해 본다.

2023.12.07 - 09:33:41

Web3 심층 보도에 집중하고 흐름을 통찰

ZKP 이론과 응용 측면의 일부 변화를 처음부터 다시 정리해 본다.

글: HashKey Capital

현재 블록체인 산업에서는 제로 나이지식 증명(Zero-Knowledge Proof, ZKP) 프로젝트의 성장 속도가 매우 빠르며, 특히 확장성(Scale-out)과 개인정보 보호라는 두 가지 측면에서의 활용이 부상하면서 다양한 형태의 제로 나이지식 증명 프로젝트들을 접하게 되고 있다. ZKP는 수학적 특성이 매우 강하기 때문에 암호화 애호가들이 ZK를 깊이 이해하는 것은 매우 어려워졌다. 따라서 우리는 ZKP 이론과 응용 분야의 변화를 처음부터 정리해보고, 독자들과 함께 암호화폐(crypto) 산업에 미치는 영향과 가치를 탐구하고자 한다. 일련의 보고서 형식으로 함께 학습하며, HashKey Capital 리서치 팀의 사고를 정리한 결과물이다. 본 문서는 시리즈의 첫 번째 글로서 ZKP의 발전 역사, 응용 및 기초 원리를 주로 소개한다.

1. 제로 나이지식 증명의 역사

현대 제로 나이지식 증명 체계의 시초는 Goldwasser, Micali, Rackoff가 공동 집필한 논문 『The Knowledge Complexity of Interactive Proof Systems』(이하 GMR85)에서 비롯되었다. 이 논문은 1985년에 발표되어 1989년에 게재되었다. 이 논문은 상호작용 시스템(interactive system) 내에서 K라운드의 상호작용을 거쳐 어떤 진술(statement)이 올바름을 입증하기 위해 얼마나 많은 지식이 교환되어야 하는지를 설명한다. 교환되는 지식의 양을 '제로'로 만들 수 있다면 이를 제로 나이지식 증명이라 한다. 여기서 증명자(prover)는 무한한 자원을 가지고 있고, 검증자(verifier)는 제한된 자원만을 가진다고 가정한다. 그러나 상호작용 시스템의 문제점은 증명이 완전히 수학적으로 증명 가능한 것이 아니라 확률적으로 올바르다는 점이며, 비록 그 오류 확률이 매우 작지만 (1/2^n), 여전히 존재한다.

따라서 상호작용 시스템은 완벽하지 않으며 근사적인 완전성을 갖는다. 이에 반해 비상호작용형 시스템(NP 시스템)은 완전성을 가지며, 제로 나이지식 증명 시스템의 이상적인 선택이 되었다.

초기의 제로 나이지식 증명 시스템은 효율성과 실용성 면에서 부족하여 오랫동안 이론 단계에 머물러 있었으나, 최근 10년 동안 급속히 발전하였고, 암호학이 암호화폐 분야에서 주목받게 되면서 제로 나이지식 증명이 주요한 방향 중 하나로 부상하였다. 특히 일반적이며(non-universal), 비상호작용적이며(non-interactive), 증명 크기가 유한한 제로 나이지식 증명 프로토콜 개발이 가장 중요한 탐색 방향 중 하나였다.

기본적으로 제로 나이지식 증명은 증명 속도, 검증 속도, 증명 크기 사이에서 트레이드오프를 해야 하며, 이상적인 프로토콜은 증명이 빠르고, 검증이 빠르며, 증명 크기도 작아야 한다.

제로 나이지식 증명에서 가장 중요한 돌파구는 2010년 Groth의 논문 『Short Pairing-based Non-interactive Zero-Knowledge Arguments』이며, 이는 ZKP 분야에서 가장 중요한 zk-SNARK의 이론적 선구자이다.

제로 나이지식 증명의 응용에서 가장 중요한 진전은 2015년 Z-cash가 사용한 제로 나이지식 증명 시스템으로, 거래 내용 및 금액의 개인정보를 보호할 수 있게 되었고, 이후 zk-SNARK와 스마트 계약의 결합을 통해 더욱 광범위한 응용 분야로 진입하게 되었다.

그 동안의 중요한 학술적 성과로는 다음과 같은 것들이 있다:

2013년 Pinocchio(PGHR13): 『Pinocchio: Nearly Practical Verifiable Computation』 - 증명 및 검증 시간을 실용적인 수준으로 줄였으며, Zcash의 기반 프로토콜로 사용되었다.
2016년 Groth16: 『On the Size of Pairing-based Non-interactive Arguments』 - 증명 크기를 축소하고 검증 효율성을 향상시켰으며, 현재 가장 널리 사용되는 ZK 기본 알고리즘이다.
2017년 Bulletproofs(BBBPWM17): 『Bulletproofs: Short Proofs for Confidential Transactions and More』 - 신뢰 설정(trusted setup) 없이도 작동하는 짧은 비상호작용 제로 나이지식 증명 알고리즘을 제안했으며, 6개월 후 Monero에 적용되어 빠른 이론-실용 적용 사례를 보여주었다.
2018년 zk-STARKs(BBHR18): 『Scalable, transparent, and post-quantum secure computational integrity』 - 신뢰 설정이 필요 없는 ZK-STARK 알고리즘을 제안했으며, 현재 ZK 기술 발전의 또 다른 주목할 만한 방향이 되었고, 이를 기반으로 StarkWare라는 가장 중요한 ZK 프로젝트가 탄생했다.

그 외 PLONK, Halo2 등도 매우 중요한 진전이며, zk-SNARK의 일부 측면에서 개선을 이루었다.

2. 제로 나이지식 증명의 응용 개요

제로 나이지식 증명의 가장 널리 퍼진 두 가지 응용은 개인정보 보호와 확장성이다. 초기에는 Zcash와 Monero 등의 유명한 프로젝트들이 개인정보 보호 거래를 도입하면서 개인정보 보호 거래가 중요한 카테고리로 떠올랐으나, 개인정보 보호의 필요성이 업계가 기대했던 만큼 두드러지지 않아 대표적인 프로젝트들이 서서히 2~3선 그룹으로 물러났다(역사에서 사라진 것은 아니다). 한편, 응용 차원에서 확장성의 중요성은 극대화되었으며, 2020년 이더리움 2.0(이제는 컨센서스 레이어라 불림)이 롤업 중심 전략으로 전환함에 따라 ZK 기술이 다시 업계의 주목을 받으며 핵심 요소가 되었다.

개인정보 보호 거래: 이미 구현된 여러 프로젝트들이 있으며, SNARK를 사용하는 Zcash, Tornado, bulletproof를 사용하는 Monero, 그리고 Dash 등이 있다. Dash는 엄밀히 말하면 ZKP를 사용하지 않고 단순한 믹싱 시스템(mixing system)을 사용하여 주소만 숨길 수 있고 금액은 숨기지 못하므로 여기서는 생략한다.

Zcash가 사용하는 zk-SNARK 거래 절차는 다음과 같다:

출처: Demystifying the Role of zk-SNARKs in Zcash

System setup 단계에서 KeyGen 함수를 이용해 증명 키(암호화된 다항식)와 검증 키를 생성
CPA 단계에서 ECIES 암호화 방법(Elliptic Curve Integrated Encryption Scheme)을 사용해 공개키와 개인키 생성
Minting Coins 단계에서 새로운 코인의 수량, 공개 주소, 코인 커밋먼트(commitment) 생성
Pouring 단계에서 zk-SNARK 증명 생성, 증명은 pour 거래 장부에 추가됨
Verification 단계에서 검증자가 Mint 및 Pour 거래량이 올바른지 확인
Receiving 단계에서 수신자가 코인을 수령. 수령한 코인을 사용하려면 다시 Pouring을 호출하여 zk-SNARK 검증을 생성하고, 위 4~6단계를 반복하여 거래 완료

Zcash의 제로 나이지식 증명 사용에도 한계가 있는데, UTXO 기반으로 인해 일부 거래 정보만 쉴드(shield) 처리될 뿐 진정한 의미의 은폐는 아니라는 점이다. 또한 비트코인 설계 기반의 별도 네트워크이기 때문에 확장성(타 애플리케이션과의 연동)이 어렵다. 실제로 쉴딩(shielding, 즉 개인정보 보호 거래)을 사용하는 비율은 10% 미만이며, 개인정보 보호 거래가 크게 확산되지 못했다는 것을 보여준다.(from 2202)

Tornado는 더 범용적인 큰 믹싱 풀(mixing pool)을 사용하며, 오랜 기간 검증된 이더리움 네트워크 기반이다. Torndao는 본질적으로 zk-SNARK를 사용하는 믹싱 풀이며, 신뢰 설정은 Groth16 논문을 기반으로 한다. Tornado Cash의 주요 특징은 다음과 같다:

저장된 코인만 인출 가능
같은 코인은 두 번 인출 불가
증명 과정과 폐지 알림(nullifier)이 바인딩되며, 동일한 증명이더라도 다른 nullifier의 해시값은 인출을 허용하지 않음
보안 수준은 126비트이며, 조합(composition)으로 인한 보안 저하 없음

Vitalik은 확장성과 비교할 때 개인정보 보호는 상대적으로 쉽게 달성 가능하다고 언급한 바 있다. 만약 몇 가지 확장성 프로토콜이 성립한다면, 개인정보 보호는 거의 문제가 되지 않을 것이다.

확장성: ZK 기반 확장성은 1층 네트워크에서 이루어질 수 있으며(Mina처럼), 또는 2층 네트워크에서 이루어질 수 있다(zk-rollup). ZK rollup 개념은 아마도 Vitalik이 2018년에 올린 포스트 『On-chain scaling to potentially ~500 tx/sec through mass tx validation』에서 처음 제안되었다.

ZK-rollup에는 두 가지 역할이 있다: Sequencer와 Aggregator. Sequencer는 거래를 묶는 역할을 하고, Aggregator는 다수의 거래를 통합하여 롤업을 생성하고 SNARK 증명(또는 다른 알고리즘 기반의 제로 나이지식 증명)을 생성한다. 이 증명은 Layer1의 이전 상태와 비교되어 이더리움의 Merkle 트리를 갱신하고 새로운 상태 트리를 계산한다.

출처: Polygon

ZK rollup의 장단점:

장점: 수수료가 낮고, OP처럼 경제적 공격에 취약하지 않으며, 거래 지연이 없고, 개인정보 보호 가능, 최종성이 빠르게 달성됨
단점: ZK 증명 생성에 큰 계산량 필요, 보안 문제(SNARK는 신뢰 설정 필요), 양자 공격에 취약(SNARK는 취약하지만 STARK는 안전), 거래 순서가 변경될 수 있음

출처: 이더리움 리서치

데이터 가용성(data availability)과 증명 방법에 따라 Starkware는 L2에 대한 고전적인 분류도를 제공한다(Volition의 데이터 가용성 계층은 체인 내 또는 체인 외에서 선택 가능):

출처: Starkware

현재 시장에서 가장 경쟁력 있는 ZK rollup 프로젝트로는 Starkware의 StarkNet, Matterlabs의 zkSync, Aztec의 Aztec connect, Polygon의 Hermez와 Miden, Loopring, Scroll 등이 있다.

기술 로드맵은 기본적으로 SNARK(및 그 개선 버전)와 STARK의 선택, 그리고 EVM 지원 여부(호환성 혹은 동등성)에 달려 있다.

Aztec는 일반화된 SNARK 프로토콜인 Plonk 프로토콜을 개발했으며, 운영 중인 Aztec3는 EVM을 지원할 수 있지만 개인정보 보호를 EVM 호환성보다 우선시한다.
StarkNet은 신뢰 설정이 필요 없는 zkp인 zk-STARK를 사용하지만 현재 EVM을 지원하지 않으며, 자체 컴파일러와 개발 언어를 보유하고 있다.
zkSync 역시 plonk를 사용하며 EVM을 지원한다. zkSync 2.0은 EVM과 호환되며 자체 zkEVM을 보유하고 있다.
Scroll은 EVM과 호환되는 ZK rollup이며, 팀은 이더리움 재단의 zkEVM 프로젝트에 중요한 기여를 하고 있다.

간단히 EVM 호환성 문제를 논하자면:

ZK 시스템과 EVM의 호환성은 항상 골칫거리였다. 일반적으로 프로젝트들은 둘 사이에서 선택해야 했다. ZK에 중점을 둔 프로젝트는 자체 시스템 내에 가상머신을 만들고, 자체 ZK 언어와 컴파일러를 개발하지만, 이는 개발자의 학습 곡선을 높이며, 대부분 비공개 소스이기 때문에 블랙박스처럼 느껴진다. 현재 업계는 일반적으로 두 가지 선택지를 가지고 있다: Solidity의 오퍼코드(opcode)와 완전히 호환되거나, 새로운 가상머신을 설계하면서 ZK에 친화적이면서도 Solidity와 호환되도록 하는 것이다. 업계는 처음에는 이렇게 빠른 통합이 가능할 것이라고 생각하지 못했지만, 최근 1~2년간의 기술 급속한 반복을 통해 EVM 호환성이 새로운 수준에 도달했으며, 개발자는 어느 정도까지는 원활한 마이그레이션(이더리움 메인넷에서 ZK rollup으로)을 할 수 있게 되었고, 이는 고무적인 진전이다. 이는 ZK 개발 생태계와 경쟁 구도에 영향을 미칠 것이다. 이후 보고서에서 이 문제를 자세히 다룰 예정이다.

3. ZK-SNARK 구현의 기본 원리

Goldwasser, Micali, Rackoff는 제로 나이지식 증명이 가져야 할 세 가지 성질을 제시했다:

완전성(Completeness): 적절한 증거(witness)를 가진 모든 진술(statement)은 검증자가 검증할 수 있어야 한다.
건전성(Soundness): 부적절한 증거만을 가진 진술은 검증자가 검증해서는 안 된다.
제로 나이지식성(Zero-knowledgeness): 검증 과정은 제로 나이지식이어야 한다.

따라서 ZKP를 이해하기 위해 우리는 zk-SNARK에서 시작한다. 현재 많은 블록체인 응용이 SNARK에서 시작되기 때문이다. 먼저 zk-SNARK를 살펴보자.

zk-SNARK란 zero-knowledge Succinct Non-interactive ARguments of Knowledge의 약자이다.

Zero Knowledge: 증명 과정이 제로 나이지식이며, 불필요한 정보를 노출하지 않는다.
Succinct: 검증 데이터 크기가 작다.
Non-interactive: 상호작용이 필요 없다.
ARguments: 계산의 신뢰성이 보장되며, 제한된 계산 능력을 가진 증명자는 증명을 위조할 수 없고, 무한한 계산 능력을 가진 증명자만이 위조할 수 있다.
of Knowledge: 증명자는 유효한 정보를 모른 채 파라미터와 증명을 구성할 수 없다.
증명자 입장에서, 증거(Witness, 예: 해시 함수의 입력값이나 특정 Merkle-tree 노드의 경로)를 모른 채 파라미터와 증명을 구성하는 것은 불가능하다.