[ZK롤업]영지식 증명 파먹기(2탄) — 현대 암호학 역사와 전개 원리
안녕하세요, 카린(Karin) UI Engeener& Crypto-Dev입니다.
‘냉장고 파먹기 시리즈’는 블록체인 냉장고 안에 쌓아놓았던 Crypto 인사이트 식품을 골라먹기하는 = 크립토 냉장고를 깊게 파먹는 시리즈입니다.
외식 소비를 줄이기 위해 집에있는 냉장고 식품을 먼저 파먹는 제 모습을 그리다가 만들어낸 아이디어 입니다.
드디어 독자분에게 Zero Knowledge Proofs줄임말로 ZKP(지케이피)한국어로는 영지식 증명이란 현대 암호학을 간단히 소개시켜 드리게되었습니다.
1) 영지식 증명(Zero Knowledge Proofs)?
영 지식 프로토콜과 같은 말입니다. = 제로 지식 증명 / 제로 지식 프로토콜 (우리나라 숫자 발음)
블록체인 기술이 금융에 들어오면서 ‘공개 검증 가능’ 즉 독점을 없애자는 주장으로 거래 명시에 대한 요구가 존재했다. 늘 명시할 수 있는 개인정보와 프라이버시의 적정 균형을 맞추는 것은 어딜 가든 논쟁거리가 이러한 개인정보보호와 공개 명시 사이에서 균형을 맞춰가는 과정에서 나온 ‘너무 공개적’이란 탈중앙화 거래의 단점을 보완하고자 나온 게 여러 익명 거래 방법인데 그중 하나를 수학인 ‘확률’과 ‘이산수학’을 사용해서 구사한 게 영 지식 증명이다.
영 지식 증명_ “선택적 공개” 옵션
필자가 느낀 영 지식 증명은 소유만 증명하고, 구체적 데이터는 가리는 것이다. (마치 풀소유 스님이 숨기는 미국 부동산이랄까?) 선물받은 것만 보여주고, 개인정보를 위해 자세히 뭔지는 안보여주는 것이다. 개인정보보호법을 위한 개인식별정보를 비식별 처리하는 것과 유사하다. 공개키는 대중적으로 알릴 수 있는데 내 개인키는 알릴 수 없다! (공인인증서 비밀번호)
영지식 증명에서 제공자 목표는 주어진 진술이 참임을 다른 검증인에게 증명하는 것인데, 아이러니 하게도 제공자는 진술이 참이라는 사실 외 추가 정보를 전달하는 것을 피한다. 본질은 단순 정보만 공개하고, 특정 정보 지식은 넌지시라도 얘기하는건 사생활 공개로 치부한다. 다시말해 정보 그 자체나 추가 정보를 공개하지 않고, 소유만 증명하는 것이다. (아래에 자세히 나온다)일단 사용부터 보자.
2) 영지식증명이 암호 화폐 거래에서 어떻게 쓰이나?
암호 화폐 거래에서 거래자가 공개하는 것 외 받는 사람이 알 수 없도록 분산 형 암호화 기술로 설계됐다. 그래서 모든 거래(트랜잭션)의 프라이버시를 보호하고, 지급거래 자체는 공개 블록체인(Public chain)에 게시되지만, 거래 대상과 금액은 암호화 되어 있어 보안이 유지된다. 즉, 거래자와 블록체인값을 모두 드러내지 않는 ‘프라이버시보호 기능’과 당사자들이 서로 ‘신원을 확인하지 않고 거래’할 수 있게 해주는 기능을 갖게 된다. 이 특징을 통해 거래 익명화가 가능한 다크코인이 완성되었다.
3) 영지식 증명 탄생 (기원)
1985년 Goldwasser, Micali, Rockoff가 영지식 상호 증명 방식에 대한 개념을 최초로 제안했다.
‘대화형 지식 증명의 복잡성’이란 논문에서 해결책으로 영 지식 증명(제로 지식 증명)이란 현대 암호학으로 등장했다. 1986년, 드디어 ‘대화형의 복잡성 문제’를 해결할 ‘비대화형’이 등장했다. 80년대부터 이미 대화형은 비효율적이다란걸 알고 비대화형을 추구했단 말로 해석된다.
4) 영 지식 증명의 초기 쓰임 역사
순서: 제로 코인 > 제로 캐시 > 피로 코인
2016년: 영 지식증명은 제로 코인(Zcoin)과 제로 캐시(Zero cash) 프로토콜에 적용되어 2016년에 만들어진 Zcoin(2020년 Firo로 변경)과 Zcash 암호화폐 탄생에 정점을 찍었다.
1) Zcoin: 익명성을 확보하기 위해 피어 또는 집중형 믹싱 제공자를 비신뢰하는 내장 혼합 모델 존재. 사용자는 기준 통화로 거래하며 제로 코인을 사용할 수 있다. But 거래금액을 모호하게 할 수 있단 단점이 있다.
2) Zcash: 반면 제로 캐시는 모호한 단점이 없다. 그런데도 둘은 유사한 모델인 비대화형 영지식증명을 사용한다. Zcash는 네트워크상 정보 거래 시에 큰 제한을 두기 때문에 Zero coin에 비해 프라이버시 시간차 공격 가능성이 낮아진다. (보안) 그러나 이러한 사생활을 갖는 레이어는 악의적인 코인을 추적할 수 없기에 Zcash는 공급하는 과정에서 잠재적으로 초인플레이션을 일으킬 수 있단 단점이 있다.
참고로 영지식 스나크(zk-SNARKs)가 이때 등장한다. 스나크(SNARK)는 “간결한”(succinct)이란 뜻을 가진다. 증명 크기가 작아 신속히 확인할 수 있음을 내포한다. ‘zero-knowledge Succinct Non-interactive Argument of Knowledge’의 약자이며, 기존의 영지식 증명을 좀 더 간결하고(succinct) 비상호적인 환경(non-interactive)=비대화형에서 적용 가능하도록 변형한 기술이다.
2012년 지캐시(Zcash)에 의해 개발되었다. 지캐시는 영지식 스나크를 기반으로 작동하고 있는 애플리케이션 중 가장 큰 규모다. 영지식 스나크를 최초로 적용한 암호화폐는 지캐시가 있으며, 이외에 이더리움의 비잔틴 하드포크에도 관련 내용이 적용되었다.
영지식 스나크를 활용한 블록체인 트랜잭션의 경우 수신자, 송신자, 전송금액 등의 정보를 노출하지 않고도 해당 트랜잭션의 유효성을 송수신노드 외의 다른 노드들에게 알릴 수 있다.(이건 ZK라면 다 같은 의미다.)
비상호작용 구조에서는 증명자와 검증자가 하나의 증거만 주고받아도 된다. 영지식 스나크는 증명자와 검증자 사이의 신뢰할 수 있는 초기 설정에 의존한다. 즉 영지식 증명 및 개인거래를 구축하기 위하여 일련의 고객 매개 변수가 필요한 것이다. 이 매개 변수는 게임의 규칙과 거의 상응하며 프로토콜에 인코딩되어 트랜잭션이 유효하다는 것을 증명하기 위해 필요한 요소이다. 그러나 매개 변수가 매우 작은 그룹에 의하여 공식화 되는 경우가 있기 때문에 잠재적으로 중앙 집중화 문제가 존재한다.
그리고,,,2018년 ,,,여기서 방탄이 왜 나와? (피땀 눈물 흘림…_ 피로 코인)
2018년에는 방탄(Bulletproofs)-불렛 증명이 도입되었다. 방탄은 신뢰할 수 있는 설정이 필요없는 비인터랙티브(비대화형) 영지식 증명보다 개선된 것이다. (놀라운 사실은 실제 방탄소년단 이름 모티브이자 앨범 제목이라고.)
이후 Mimblewimble Protocol(Green 및 Beam -밈블윔블 암호학 기반 코인)과 Monero (모네로) 화폐에 구현되었다.
빔(BEAM) 또한 완전 비공개로 누구에게 알리지 않고 진행할 수 있는 가상화폐로 실제 존재함.
2019년 Firo는 신뢰할 수 있는 설정이 없는 제로코인 프로토콜을 개선한 Sigma 프로토콜을 구현했다. 같은 해 Firo는 거래 출처와 금액을 숨기는 Sigma 프로토콜을 개선한 Lelantus 프로토콜을 도입했다.
현재 피로 코인의 시발점이 되었고, 피로 코인이 영지식 증명기반이라고 하는데 정확하게는 방탄 증명을 통한 기반으로 렐란투스 프로토콜(Lelantus)을 사용한다. (익명, 거래주소 숨김, 금액만 공개 명시해주고 있다.)
영지식 증명(Zero Knowledge Proofs)은
영지식 증명은 다음 세 가지 속성을 충족해야 한다.
- 완전성: 진술이 참이면, 정직한 검증자( 즉 프로토콜을 제대로 따르는 사람)은 정직한 검증자에 의해 이 사실을 확신하게 될 것이다.
- 건전성: 만약 그 진술이 거짓이라면, 어떤 부정행위 방지자도 그것이 진실이라는 것을 정직한 검증자에게 납득시킬 수 없다. 다만 약간의 가능성이 있다.
- 제로 지식: 스테이트먼트가 참일 경우 그 스테이트먼트가 참이라는 사실 이외에는 어떤 검증자도 학습할 수 없습니다.즉, (비밀이 아닌) 진술을 아는 것만으로도 프로버가 비밀을 알고 있다는 것을 보여주는 시나리오를 상상하기에 충분합니다.이것은 모든 검증자가 증명해야 할 진술(프로버에 대한 접근 없음)만 주어져 정직한 검증자와 문제의 검증자 사이의 상호작용처럼 보이는 스크립트를 생성할 수 있는 시뮬레이터를 가지고 있다는 것을 보여줌으로써 공식화된다.
1) 영지식 상호 증명 = ZKIP(Zero-Knowledge Interactive Proof)?
증명자와 검증자가 항상 온라인(on-line) 상태여야 한다는 전제가 필수다.
비밀 내용은 밝히지 않으면서 비밀을 알고있단 사실을 증명하는 방법이다. 증명자와 검증자 간 일반 난수와 비밀 정보로부터 연산한 결과를 주고받으며 확률적으로 납득시키며, 횟수가 늘어날수록 확신도는 높아지게 된다. 영지식 대화형 증명이라고 한다.
보편적으로 우리가 패스워드를 사용할 때 화면상 비밀 패스워드를 그대로 표시하므로 보안 위험성이 따른다. 하지만 영지식 상호 증명 방식을 사용하면 일반 난수와 비밀 정보로부터 연산한 결과를 증명자(유저)와 검증자간 주고받으며 확률적으로 납득시켜 증명하는 방식이다. 결과를 주고받는 횟수가 늘어날수록 확신도도 비례해서 높아진다. (약속을 여러번 지키면 믿어줌)
장점은 데이터 정보를 공개하지 않고도 정보의 ‘유효성을 증명’가능해서 빠르다는 점이다. 또한 정보를 공개하지 않기 때문에 익명 거래 가능하단 점이다.(어둠의 거래 가능 ex:다크코인) 빠르기 때문에 효과적으로 확장 솔루션 구축한다는 점, 효율적으로 정보 저장이 가능한 점, 여러 DApp구성 요소를 개선하는 방안을 제공한다는 점이 있다.
2) 영지식 비상호 증명= ZKNIP(Zero Knowledge Non-Interactive Proof)
영지식 상호 증명 방식에서 무조건 온라인(on-line) 상태가 필수적이란 전제조건은 ‘위치'에 종속된단 이유로 시스템을 전체적으로 비효율적이게 만들었다. 따라서 1986년 fiat, Shamir는 결국 영지식 비상호 증명 방식인 ZKNIP(Zero Knowledge Non-Interactive Proof)를 제시했다. 이 방식은 증명자와 검증자의 온라인 여부와 관계없이 증명할 수 있도록 고안됐다. 결국 증명자와 검증자의 ‘메시지 교환이 최소화 되어야 한다는 것’을 의미하며 증명자가 증명에 필요한 메시지를 보내고 난 후 연결이 끊어진다고 하더라도 그 메시지가 보증돼야 하는 것이 비상호 증명 방식의 핵심이다. 교환 최소화 및 보증이란 장점이 있는 비상호 증명 방식의 경우 연산 횟수가 기하급수적으로 증가하기 때문에 증명에 대한 검증을 완료하는데 상당한 시간이 걸릴 수 있다는 단점 역시 존재하게 된다. 이를 해결하기 위해 비상호 증명 방식에서 발생하는 증명자의 증거 데이터의 사이즈를 줄여 빠른 검증을 수행할 수 있도록 하여 비상호 증명 방식의 실용성을 극대화 한 것이 현재지캐시(Zcash)기반이 되는 핵심 기술인 영지식 스나크(zk-SNARKs)다.
영지식 증명의 사용은
- ZK-EVM : PSE, Polygon Hermez, Scroll
- not Zot : ZkSync, Starkware
- 기타 옵티미즘, 아비트럼
영지식 증명의 구동 원리는
- 알리바바 동굴의 비유 (가장 유명한 방법이다_ 확률 이용)
증명자는 검증자에게 자신이 알고 있는 비밀번호를 알려주지 않고도 자신이 비밀번호를 알고 있음을 증명할 수 있다. 하지만 이 과정을 한 번만 보았을 때는 증명자가 비밀번호를 정말로 알고 있어서 검증자가 지시한 길로 나왔는지 확신하기 어렵다. 증명자가 우연히 올바른 길로 나왔을 수도 있기 때문이다. 하지만 위 과정을 일정 횟수 이상 반복하여도 항상 증명자가 검증자의 지시대로 행동했다면 증명자는 검증자에게 자신이 비밀번호를 알고 있다는 사실을 납득시킬 수 있다. 예를 들어 위와 같이 20번만 반복해도, 증명자가 비밀번호를 모르면서도 검증자의 지시를 모두 따를 수 있는 확률은 100만분의 1 이하가 된다.만약 이 과정을 40회 반복하게 되면, 우연히 비밀번호를 맞출 확률은 1조분의 1 이하가 된다.
2. 스도쿠 게임
영지식증명은 스도쿠(sudoku) 에도 적용가능하다. 스도쿠 게임(sudoku game)은 정사각형 모양에 1~9까지 숫자를 넣되, 총 9*9=81개의 칸에 대해, 반드시 하나의 가로줄에 1~9의 숫자를 각각 한 번씩 사용해야 하고, 하나의 세로줄에 대해서도 1~9까지 숫자를 각각 한 번씩 사용해야 하며, 3*3 크기의 작은 정사각형 보드 안에도 1~9까지의 숫자가 오직 한 번만 사용되도록 만드는 게임이다. 이 게임의 정답을 맞춘 사람인 증명자는 자신이 발견한 정답을 검증자에게 공개하지 않으면서도 자신이 정답을 찾았다는 사실을 증명해야 하는데, 이때 영지식증명 방법을 사용할 수 있다.
- 증명자는 9*9 = 81개의 정사각형 보드를 다른 종이로 덮어서 검증자가 볼 수 없도록 한다.
- 증명자는 자신이 찾아낸 정답을 바탕으로, 1~9까지의 전체 숫자에 대해, 1 →2, 2 →5, 3 →9, 4 →7, … 이런 식으로 랜덤하게 숫자를 1:1로 바꿔치기를 한다. 이러한 셔플링(shuffling) 과정을 거치더라도 스도쿠 게임의 정답은 여전히 유효하게 적용된다. 즉, 가로줄, 세로줄, 3*3 하위 정사각형 보드에 1~9까지의 숫자가 각각 한 번씩만 사용된다.
- 검증자는 증명자에게 특정 가로줄 또는 세로줄 혹은 3*3 하위 정사각형 보드를 공개하라고 요청한다.
- 증명자는 검증자가 요청한 특정 부분의 정답을 공개한다. 증명자가 공개한 부분에 1~9의 숫자가 각각 한 번씩만 사용되었다면, 증명자가 스도쿠 문제의 정답을 알고 있다는 증명이 된다.
하지만, 위 과정을 오직 한 번만 수행할 경우, 증명자가 우연히 해당 줄의 정답을 맞춘 것일 수도 있기 때문에, 검증자는 전적으로 증명자를 신뢰할 수 없다. 따라서 위 과정은 여러 회 반복해서 수행되어야 한다. 두번째 과정에서 증명자는 다시 자신이 알고 있는 정답의 숫자를 랜덤하게 1:1로 바꿔치기한다. 만약 이러한 셔플링 과정을 수행하지 않는다면, 검증자가 증명자가 알아낸 정답을 추측할 수 있기 때문에 증명자는 매번 이러한 셔플링을 수행해야 한다. 결국 위 과정을 상당히 여러 회 반복하였음에도 불구하고, 증명자가 매번 정답을 맞춘다면, 검증자는 증명자가 정답을 알고 있을 확률이 매우 높다고 결론을 내릴 수 있다. 이처럼 영지식증명 방법을 이용해 증명자는 자신이 찾아낸 스도쿠 게임의 정답을 공개하지 않고도 검증자에게 자신이 정답을 알고 있다는 사실을 증명할 수 있게 된다.
이 실험에서 증명자는 오직 검증자에게만 자신이 정답을 안다는 사실을 증명할 수 있다. 하지만 제3자들은 증명자가 정말로 정답을 알고 있는지 확신할 수가 없다. 왜냐하면 제3의 관찰자는 증명자와 검증자가 사전에 미리 짜고 그 순서대로 특정 줄의 값만 1~9가 되도록 조작했을 수도 있기 때문이다. 하지만 검증자는 자신이 정말로 랜덤하게 특정 가로줄이나 세로줄을 지정했다는 사실을 알고 있기 때문에, 증명자가 정답을 알고 있다고 확신할 수 있게 된다. 이처럼 영지식증명을 이용하면, 오직 해당 증명 과정에 참여한 증명자와 검증자만 사실을 확신할 수 있으며, 제3자의 관찰자는 증명자가 정말로 해당 내용을 알고 있는지 확신할 수 없다.
영지식 증명의 트랜잭션 방법은
- 자금을 메인체인(예: 이더리움)인 온체인에서 취하고, 필요한 계산과 데이터 저장은 모두 off-chain에서 수행한다.
- 무허가 프로토콜을 지원하는 기본 기술로 암호화 검증 방식을 사용한다. 암호화 네트워크에서 개인정보만 가리는 개념이라 생각하며 된다.
블록 생성자는 트랜잭션과 상태 루트값뿐만아니라 상태 루트값을 변경한 영지식 증거(변경 루트 값)를 동시에 루트체인에 업로드함.
영지식 증거가 이미 첨부되었기때문에 별도의 연산 검증 기간이 필요없다. 따라서 빠르게 롤업 블록을 확정할 수 있다는게 장점이다. (일 처리 빠름)
영지식 증명 방식은 ‘3가지 조건’을 만족해야 한다.
① 어떤 조건이 참이면 신뢰 할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다는 완전성(completeness).
② 어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에 조건이 참임을 절대 납득시킬 수 없다는 건전성(soundness).
③ 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다는 영지식성(zero-knowledge).
여러 반복을 통해 검증자는 증명자가 비밀번호를 알고 있다는 사실을 알게됐지만 비밀번호가 무엇인지는 알지 못한다는 사실은 영지식성에 부합한다.
상태 증명을 위해
- 제공자가 비밀정보를 보유해야 하는 경우> 검증자는 비밀정보를 필히 보유해야함. 아니라면 그 상태를 타인에게 증명 불가.
- 증명되는 진술은 증명자가 그러한 지식을 가지고 있다는 주장을 포함해야 하지만, 주장 자체에 구체적 지식을 전달하지는 않는다.
그렇지 않으면, 그 문장은 프로토콜 종료까지 그 문장에 대한 추가 정보를 검증자에게 제공하기 때문에 제로 지식으로 증명되지 않는다. 제공자가 비밀 정보를 소유하고 있다는 진술만으로 구성될 때는 사실 특별한 경우임.
결론
한마디로 영지식 증명은 암호화로 비식별 처리하는 원리가 중요하다. 다크캐쉬의 존재를 생각해보면 된다. 여러 글을 읽어도 글이 복잡해지는 이유는 수학적 원리로 해싱하는 원리를 한글말로 적절히 비유하며 풀자니 말이 간결하게 못나온다. 아무튼 영지식 증명은 쉽진않다. 하지만 많은 자료를 통해 나도 배웠고 내재화하여 보기좋게 정리한것이니 도움이 되었으면 좋겠다.
논문 참고: Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems” (PDF), SIAM Journal on Computing, 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095–7111
이상 카린 개발자였습니다.
