영지식 증명

ZKP; Zero-Knowledge Proof

prover가 자신이 알고 있는 지식을 공개하지 않으면서, 그 지식을 알고 있다는 사실을 verifier에게 증명하는 proof system

• 1980년대 MIT의 Shafi Goldwasser, Silvio Micali and Charles Rackoff가 처음 제시

조건

• 완전성(completeness)
  • 어떤 조건이 참이라면 신뢰할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다.
• 건전성(soundness)
  • 어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에게 조건이 참임을 절대 납득시킬 수 없다.
• 영지식성(zero-knowledge)
  • 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다.

활용

활용 예	설명
Z-cash	블록체인상의 거래내역 추적을 막는 익명성 부과
Zk roll up	Layer2의 상태를 Layer1에서 검증할 수 있도록 증명
Zokrates	Off-chain에서 생성한 증명을 검증 가능한 스마트 컨트랙트 생성
zkvm	컨트랙트 실행 환경 VM의 상태 증명
Oracle	오프체인의 개인 데이터를 온체인에서 검증 가능하도록 구현
Interoperability	Chain간 블록 및 상태 전이에 관한 증명 및 검증
Selective Disclosure	DID의 Claim을 Verifier에게 선택적으로 증명

분류

분류		기술
Interactive		Graph Isomorphism zk-stick(2018)
Non-Interactive	TTP 사용	zk-SNARKs(2013) Libra(2019)
	TTP 미사용	Ligero(2017) zk-STARKs(2018) Bulletproof(2018) Supersonic(2019)

Non-interactive ZKP

Prover와 Verifier가 온라인 상태가 아니더라도 영지식 증명 가능

TTP 사용

• zk-SNARKs : Non-interactive ZKP의 proof size를 줄인 실용 모델
  • 지캐시에서 도입

TTP 미사용

• zk-STARKs
• BulletProofs

비교

구분	zk-SNARKs		zk-STARKs		BulletProofs
증명자 연산 복잡도	O(N * log(N))	2.3s	O(N * poly-log(N))	~1.6s	O(N * log(N))	~30s
검증자 연산 복잡도	~O(1)	10ms	O(poly-log(N))	~16ms	O(N)	~1100ms
증명 크기	~O(1)	~200Byte	O(poly-log(N))	45~200KB	O(log(N))	~1.3KB
TTP	필요		필요 없음		필요 없음
양자 내성	없음		있음		없음