[블록체인 / 영지식 증명] zk-SNARKs와 zk-STARKs 설명

https://academy.binance.com/en/articles/zk-snarks-and-zk-starks-explained

zk-SNARKs and zk-STARKs Explained | Binance Academy

 어쩌다보니 나는 블록체인의 영지식 증명부터 블록체인을 접하게 되었다. 그 개념 자체는 내용 자체를 모르더라도, 암호학적 방식으로 원하는 조건이 성립되는지 확인하는 것이다. 예를들면, 주류를 구매할때 구매자가 19세가 넘는지를 생일확인없이 암호학적 방법으로 증명하는 방식이다. 대략 내용을 훑어보니 쉽게 설명된거 같아 이 글을 들고왔다.

 

TL; DR

• zk-SNARK는 zero-knowledge succinct non-iteractive argument of knowledge
• zk-STARK는 zero-knowledge succinct transparent argument of knowledge

	영지식 증명	사용사례	초기설정(공통 파라미터)	증명크기	효율성
zk-SNARK	O	Zcash	O	작음	상대적으로 낮음(비트코인보단 높음)
zk-STARK	O	-	X	큼	높음
비고	둘다 영지식 증명	-	초기설정 없는게 더 안전

• 영지식 증명?
  • 실제 정보는 보여주지 않은체, 정보를 알고 있다고 증명하는 기술
  • 예) 생일이 만 19세가 넘었는지 안지났는지, 학점 평균이 기준치를 충족하는지 안하는지

---

• 개인정보보호는 암호화폐 커뮤니티에서 항상 중요한 기능으로 여겨짐
• 대부분의 암호 자산 소유자는 본인의 거래이력 및 보유 내역을 완전히 공개하고 싶어하진 않음
• 여러 기술이 있지만  zk-SNARK와 zk-STARK 두가지가 주목할만한 예임

 

• zk-SNARK는 zero-knowledge succinct non-iteractive argument of knowledge를 뜻함
  • Zcash(JP Morgan 지불 시스템)에 사용
  • 서버에 클라이언트를 인증하는 방법으로 사용
• zk-STARK는 zero-knowledge succinct transparent argument of knowledge를 뜻함
  • zk-SNARK의 여러 단점을 보완한 방식

 

알리바바 동굴의 비유

• 1990년 논문 "How to Explain Zero-Knowledge Protocols to Your Children", Jean-Jacques Quisquator 등이 발표됨
• 여기선 알리바바 동굴 비유로 영지식 증명(ZK Proofs)을 설명함
• 여러 버전이 있지만, 기본 정보는 동일

• 원형의 동굴 + 중간의 마법의 문 있는 상황 상상
• 마법의 문을 열기위해선 비밀 단어를 얘기해야함
• 여기서 Alice(노란색)가 Bob(파란색)에게 본인이 비밀 단어를 알고잇다는 것을 입증하려함
  • Bob은 밖에서 기다림
  • Alice는 동굴로 들어가 1 또는 2번 길로 들어감. 여기선 1번 으로 들어갔다고 가정

 

• 시간이 경과한후(Alice가 문 앞에 도착한 후)  Bob은 Alice가 나타났으면 하는 경로를 외침

• Alice가 비밀 단어를 알고있다면, Bob이 말한 경로로 나올 것임
• 충분한 검증을 위해 위 과정은 몇번 반복될 수도 있음

 

• 알리바바 동굴의 비유는 zk-SNARK 및 zk-STARK의 일부인 영지식 증명을 설명해줌
• 영지식 증명은 정보는 밝히지 않은체, 특정 지식의 소유 여부를 밝힐 수 있음

---

zk-SNARKs

• ZCash는 zk-SNARKs가 널리 쓰 첫 사례임
• Monero와 같은 방식은 링 서명 및 기타 기술 사용 <-> zk-SNARK는 데이터 공유방식을 근본적으로 바꿈
• ZCash의 개인정보는 암호화 된 상태에서 영지식 증명을 통해 검증 가능함
• 각 거래의 모든 데이터를 알 필요가 없어짐
• ZCash의 개인정보보호 기능은 기본적으로 활성화 된게 아닌 옵션이긴 함(ZKP 기능을 따로 활성화 해야한다)

 

• 영지식 증명은 내용의 진실성을 정보를 밝히지 않고 다른 사람들에게 입증 가능
• 여기에 참여자들을 증명자(prover)와 검증자(verifier)라고 함
• 주 목적은 최소한의 정보를 밝히는 것임

 

• SNARK 중 "succint(간결한)" -> 사이즈가 작고 빠르게 검증 가능함을 뜻함
• "Non-interactive(비대화형)" -> 증명자와 검증자 사이 상호작용이 거의 없음을 뜻함
  • 구버전 영지식 증명은 서로 많은 상호작용이 필요했음
  • 비대화형에서는 하나의 증명만 교환하면됨

 

• 현재 zk-SNARK 방식은 증명자와 검증자사이 초기의 신뢰할수 있는 설정에 의지함
  • 개인 트랜잭션을 구성하기 위해 공개 매개변수 필요
  • 이 매개변수는 게임의 룰과 같음 -> 거래내역이 유효함을 증명하기 위해 필요한 요소 중 하나 임
  • 매개변수가 소수 그룹에 의해 생성되기 때문에 중앙화 문제 발생 가능성

 

• 초기 신뢰할수 있는 설정이 중요함. 이 과정에서 필요한 신뢰의 양을 줄이는 대안 연구중임
  • 초기 설정에서 위조 지출 방지가 중요함. 누군가 가짜 증명을 만들어낼 수도 있음
  • Zcash에서 초기 설정 단계를 Parameter Generation Ceremony.

 

• "Arguments of Knowledge(지식의 주장)" 부분
  • 부정직한 증명자가 실제 지식 없이 시스템을 성공적으로 속일 가능성이 매우 낮음
  • 이 속성을 "건전성(soundness)"라고 하며, 증명자의 컴퓨팅 능력이 제한적이라 가정함
  • -> 이론적으로 충분한 컴퓨팅 파워를 가진 증명자는 가짜 증명 생성 가능(양자 컴퓨터)

 

• 영지식 증명은 빠르게 검증 가능하며 보통 비트코인보다 더 적은 데이터를 차지함
  • 개인정보보호와 확장성 해결책으로 가는 길을 열어줌

---

zk-STARKs

• Eli-Ben Sasson, Technion-Israel Institute of Technology 교수가 만듬 
• zk-SNARK 보다
  • 효율적이고
  • 잠재적으로 더 빠르고
  • 저렴
  • 초기 신뢰 설정 필요 없음("T"는 transparent를 뜻함)

Eli-Ben Sasson

• 기술적으로, zk-STARK는 충돌 방지 해시 기능을 통해 더 간결한 암호화에 의존 -> 초기 신뢰할 수 있는 설정 불필요
• 양자 컴퓨터의 공격을 받기쉬운 zk-SNARK의 이론적인 가정 제거

 

• 암호학적 가정에선 더 간편한 구조임
• 증명의 크기가 더 큰 단점 존재
  • 사용 상황에 따라 한계가 될수도 있지만 테스트와 검증 필요

---

정리후기

 Hyperledger Aries / Indy를 하다가 영지식 증명이라는 개념을 처음 접하게 되었다. 내 기억으론 Hyperledger Fabric에서도 private data에 대한 영지식 증명을 일부 지원하는 것으로 알고있다. 이 글을 정리하고 얻은 가장 큰 수확은 영지식 증명을 쉽게 설명하는 원문이 무엇인지 알게 되었다는 점이다. 

 원문에서도 영지식 증명에 대해서 깊이 이야기 하지 않은것은 한페이지에 담아내기에는 너무 어려운 내용이었기 때문은 아니었을까 싶다. 아마 글만보면 "이게 돼?"라고 의심을 가지는 사람이 많을 것 같다. 백문이 불여일견이라고, Hypereldger Aries 증명서 발급 및 proof 부분을 해보면 내용은 밝히지 않고 증명을 해볼 수 있다. 좀더 구체적으로 말한다면 주류 구매를 위해서 본인의 주소와 같은 부분은 밝히지 않고 생일에 대한 부분만 암호화 해서 넘긴해 ZKP를 이용해 T/F를 만들어 내는 부분이 있다. 

 아무튼 둘다 영지식 증명이고 후자가 좀더 컴퓨팅 파워는 크지만 안전한 방식으로 이해하면 되겠다.

 

끝.