영지식 증명을 통해 알아보는 MINA
1. 영지식 증명은 무엇인가
1) 개괄 : 영지식 증명이란?
영지식 증명(zero knowledge succinct non-interactive argument knowledge)이란 자신이 해당 정보를 보여주지 않아도 그 정보의 보유 유무(또는 참/거짓)를 증명하는 암호화기법을 의미한다. 이러한 특성으로 인해 영지식 증명은 secure와 private의 이점을 갖고 unknown party와 trust를 형성하여 거래할 수 있게 만들어준다. 영지식 증명에 대한 흔한 비유로는 알리바바의 동굴 비유가 있다. 고리 모양을 가진 동굴이 있고 그 동굴 가운데에 비밀번호를 입력해야 풀 수 있는 잠긴 문이 있다고 가정해보자. 이제 검증자가 동굴로 들어가서 잠긴 문 앞에 도달한 뒤 동굴 밖의 사람이 왼쪽/오른쪽으로 나올지 말한다. 만약, 증명자가 비밀번호를 알고 있다면 그는 몇번의 시험을 반복하든, 원하는 방향으로 나올 수 있을 것이다. 그러나 비밀번호를 알지 못한다면 우연히 나오는 방향이 맞더라도 반복할 경우 오류가 발생할 것이다. 영지식 증명은 바로 이와 같은 기법을 활용한 암호화 기법이라고 할 수 있다.
영지식 증명은 다음의 3가지 특징을 만족해야 한다. 완전성completeness, 건전성soundness, 영지식성zero-knowledge가 그것이다. 완전성이란 검증자는 진술이 사실일 경우 정직하게 검증을 수행한다는 것을 의미한다. 건전성이란 진술이 거짓일 경우 약간의 확률을 제외하고 계속 반복할 경우 그것이 사실이라는 것을 확신할 수 없는 것을 의미한다. 영지식성은 진술의 참거짓을 제외하면 그 어떤 정보도 알지 못한다는 것을 의미한다.
▶영지식 증명의 종류 : 대화형 vs 비대화형, zk-snarks vs zk-starks
대화형 vs 비대화형 : 대화형이란 prover가 정보의 사실임을 증명하기 위해 일련의 행동을 수행해야 하는 영지식 증명 방식을 의미한다. 즉, 사실 검증을 위해 질문을 하는 것과 같다. 그러나 대화형은 transferability가 limited된다는 단점이 존재한다. 검증을 위해 매번 동일한 검증방법을 수행해야 하기 때문이다. 반대로 비대화형은 스스로 검증을 해 보일 수 있다. 바로 이 비대화형이 snark라 할 수 있다. 비대화형은 prover와 verifier가 기속적인 메세지를 주고 받지 않아도 된다는 점에서 효율성이 높다고 할 수 있다.
zk-snark vs zk-stark : zk-snark는 비대화형 영지식 증명 중 하나로 널리 사용되고 있다. zk-snark는 초기 신뢰할 수 있는 설정을 만들어 검증에 의존한다. 이는 검증을 수행하는 데 있어 공용 매개변수를 활용하여 검증을 완료한다는 의미이다. 그러나 이러한 방식은 소규모의 그룹에 의해 공용 매개변수가 좌지우지될 수 있다는 잠재적인 중앙 집중화의 문제점이 발생한다. zk-stark는 암호화를 더 간결하게 만들었기 때문에 검증에 필요한 초기 신뢰할 수 있는 설정을 만들 필요가 없다. 이로인해 zk-snark보다 탈중앙성은 높지만 증명에 필요한 데이터 크기가 크다는 문제점이 존재한다.
2) 영지식 증명은 왜 필요한가 — 블록체인의 painpoint
▶ 데이터 개인 정보 보호(데이터 프라이버시)
블록체인의 투명성은 모두가 거래내역을 확인할 수 있다는 점에서 보안성과 신뢰도를 높일 수 있고 탈중앙화 매커니즘에 기여한다는 장점이 있었다. 그러나 블록체인의 탈중앙화 네트워크라는 이점은 누리면서도 때로는 정보를 감출 필요가 있다. 기업의 비지니스 전략 정보 또는 사생활은 보호할 필요성이 있기 떄문이다. 투명성과 정보의 공개의 모순적인 대립을 해결하는 데 있어 영지식 증명은 핵심적인 방법을 제공한다. 영지식 증명은 가지고 있는 정보를 공개하지 않고도 해당 정보의 참/거짓 혹은 정보의 소유 여부 등을 증명할 수 있다. 이를 활용한다면 자신의 정보를 밝히지 않고도 해당 사항을 검증할 수 있다. 예를 들어 편의점에서 술을 구매하려는 경우를 생각해보자. 성인 인증은 해야 되지만 편의점 직원에게 자신의 주민등록증을 보여주는 것은 원치 않는 경우가 있다. 이럴 경우 영지식 증명을 활용한다면 자신의 주민등록증의 정보들을 보여주지 않아도 자신이 성인인지 확실히 증명할 수 있다. 실제의 사례에서는 중국의 세서미 크레딧을 들 수 있다. 세서미 크레딧은 자신의 사용기록을 중국 정부가 확인할 수 있는데 이처럼 자신의 거래기록을 누군가 볼 수 있다는 것은 검열, 타겟마케팅 등에 정보 주체가 쉽게 노출될 수 있음을 시사한다.
▶ 데이터 누적
현재 많은 블록체인 네트워크가 마주하는 문제는 바로 검증을 위해 필요한 데이터가 점점 늘어난다는 것이다. 비트코인의 경우 2012년 처음 등장하였을 때 굉장히 작은 수준의 데이터였으나 이제는 200기가 바이트가 넘는 양으로 성장하였다. 블록체인의 용량을 더 효율적으로 쓰려는 여러 시도가 존재하였지만 결국 용량이 성장하는 속도를 늦추는 것일 뿐 시간이 갈수록 블록체인의 용량이 점점 늘어난다는 문제는 근본적으로 해결되지 않았다. 이러한 문제는 블록체인을 검증하려는 노드들이 부담해야 하는 용량과 계산 비용이 점점 높아진다는 것을 의미하며 결과적으로 검증 노드의 숫자가 줄어드는 문제로 이어지게 되었다. 그러나 영지식 증명을 사용한다면 아무리 용량이 큰 블록체인이라도 그 모든 데이터를 보유하고 검증할 필요 없이 데이터의 참/거짓을 증명할 수 있다. 이러한 특성은 블록체인을 검증하는 데 필요한 리소스를 획기적으로 감소시키며 이를 통해 블록체인 네트워크의 확장성에 기여할 수 있다.
2. 영지식 증명이 문제를 해결하는 방법
- 영지식 증명의 두 주체
영지식 증명의 주체로는 증명자(prover)와 검증자(verifier)가 있다. 증명자는 특정 정보가 참임을 증명하려는 주체로 무제한의 계산 자원을 가지고 있으며 전능한, 그러나 신뢰할 수 없는 존재이다. 반면 검증자는 해당 정보의 증명 과정에 참여하는 주체로 제한적인 계산 자원을 가지고 있으나 신뢰할 수 있는 존재를 의미한다. 두 참여자의 악의적 목적을 갖고 상대방을 속이려고 하는 행위를 ‘부정직하다(dishonest)’라고 표현하는데 블록체인을 공부하며 흔히 마주하는 ‘51%의 공격’ 등의 문제는 증명자가 부정직할 때를 다룬 현상이다. 영지식 증명은 이와 반대로 검증자가 부정직할 경우를 가정하고 예방할 수 있는 방안을 모색한다.
▶ 2가지 질문 제시
“누구나 검증자가 정보를 누설하지 않는다는 것을 확인할 수 있는가”
“검증자가 검증 과정 동안 알고 있어야 하는 정보는 어느 정도인가”.
영지식 증명은 검증자와 관련된 위 두 질문에서 착안된다. 질문에 대한 답은 영지식 증명의 정의에서도 볼 수 있듯이 “검증자가 해당 정보를 알지 못해도 정보의 유효성을 확인할 수 있다.”는 것이다.
▶ 간단한 로직
위 답이 구현되는 로직은 크게 두 가지 파트로 분리할 수 있는데, 증명하고자 하는 문제의 특정 형태로의 변환과 변환된 문제를 사용한 실제 증명 진행이 그것이다. 문제의 변환은 연산회로(Arithmetic Circuit), R1CS, QAP의 세가지 과정을 거쳐 실현할 수 있고 실제 증명은 주로 타원 곡선 암호화 방식 (Elliptic Curve Pairing)을 사용하여 구현한다.
2) 증명하고자 하는 문제를 특정 형태로 변환
▶연산회로
영지식 증명은 우선 연산회로(Arithmetic Circuit)로 문제의 형태를 변형함으로써 시작된다. 연산회로는 주어진 수식을 사칙연산 단위로 작성하는 방법으로, 덧셈, 곱셈과 같은 산술 연산들이 있는 게이트(gate)와 각 게이트를 연결하는 와이어(wire)로 구성되어 있다. 이 때, 와이어는 게이트를 연결할 뿐만 아니라 게이트에 의해 연산된 결과를 전달해주는 역할도 한다. 문제를 이루고 있는 요소들이 각각 게이트와 와이어로 구분되며 문제가 회로의 형태로 표현될 수 있다.
▶ R1CS
문제가 회로 형태로 정리되면 이를 다시 R1CS (Rank1 Constraint System) 형태로 변형한다. R1CS는 주어진 회로를 좀 더 간단하게 만든 형태인데, 연산 회로가 여러 게이트로 이루어진 단일 회로인 반면에, R1CS는 게이트 하나만 포함되어 있는 회로가 여러 단계에 걸쳐 표현된다. 이는 연산회로에서는 쉽게 판단할 수 없었던 각 게이트 입출력 값의 유효성을 검증할 수 있게 한다. 그러나 하나의 수식을 위한 유효성을 검증하기 위해 여러 게이트의 제약사항에 대한 유효성을 일일이 검증해야 한다는 단점 역시 가지고 있다.
▶ QAP:
이러한 R1CS의 단점을 극복하기 위해 QAP (Quadratic Arithmetic Program) 형태로의 문제의 변환이 다시 한 번 요구된다. QAP는 R1CS의 각 게이트, 즉 각 단계별 회로의 제약사항(constraint)가 임의의 게이트 변수로 표현된 것이다. 예를 들어, 어떤 문제의 QAP 형태를 f(x)라고 정의할 때, x 값이 1일 경우 첫 번째 단계의 유효성 검증을 제공하고, 2일 때는 두 번째 단계의 유효성 검증을 진행하는 등의 방식이다. 이 때, 각 게이트를 의미하는 모든 게이트 변수 x는 f(x)의 해이어야 하고, 따라서 f(x)는 하나의 다항식 형태를 이룬다. 보통 R1CS 형태에서 문제는 많은 게이트를 가지고 있기 때문에 f(x)는 다양한 해를 가진 복잡한 다항식을 이루게 되며, 두 개의 서로 다른 QAP 형태에서 특정 x는 같지 않은 답을 도출한다. 유효성을 증명할 때, 전체 게이트를 알 필요 없이 해당 x값을 다항식 f(x)에 대입해봄으로써 확인할 수 있다는 QAP의 특징은 영지식 증명이 간결성(succinctness)이라는 강점을 가질 수 있는 이유이다.
▶ 타원 곡선 암호화 방식
연산회로, R1CS, QAP의 세 가지 방법을 거쳐 증명하고자 하는 문제가 최종적으로 변환되면 마지막으로 정보를 숨기고 실제 증명을 진행하는 과정이 필요하다. 이 파트는 타원 곡선 암호화 방식 (Elliptic Curve Pairing)을 통해 구현할 수 있다. 정보를 숨기기 위해서는 가장 어렵고 복잡한 방식의 연산을 수식이 구성되어야 하는데, 이에 ‘타원 곡선’이 가장 적합하다는 평가를 받고 있다. 우선 타원 곡선은 유한한 원소 범위를 가지고 있으나 특정 기준으로 원소가 분류되지는 않기 때문에 구간 단위로 정의된다. 또한 타원 곡선은 복잡한 덧셈 규칙, 즉 어려운 연산과정을 가지고 있다. 예를 들어 수학의 ‘제곱’ 개념을 잠시 살펴보자. b가 a의 x제곱이라고 가정하고 a와 b가 주어진 상황에서, 본래의 x 값이 클수록 a와 b를 통해서만 x의 값을 유추하기는 더 어려워진다. 타원곡선 암호화 방식은 제곱보다 더 어려운 연산을 x번 반복한 뒤, 검증자가 a를 제시하면 증명자가 자신만 가지고 있는 비밀키(여기서는 검증자에게 알려지기를 원하지 않는 정보) x를 통해 b가 도출됨을 보인다. 따라서 검증자는 a와 b의 값을 확인하여 증명자가 x를 알고 있다는 것을 증명할 수 있다
3. 영지식 증명의 사용 사례
- z-cash
zcash는 독자적인 블록체인이 아닌 비트코인 네트워크에서 사용할 수 있게 만들어진 암호화폐이다. zcash가 다른 암호화폐뜰과 차별성을 보이는 이유는 바로 영지식 증명을 적용하여 만들어진 암호화폐이기 떄문이다. 기존의 비트코인 네트워크에서는 암호화폐의 거래내역이 전부 다 공개 되었다. 비록 익명성 때문에 누가 누구에게 보냈는지 알 수 없다 하지만, 결국 공권력 등을 통해 조사를 하면 거래내역을 통해 거래자들을 식별 할 수 있었던 이유가 바로 거래 내역이 모두 다 드러나기 떄문이었다. 그러나 zcash는 거래액을 공개적으로 보여주는 대신 영지식증명의 서로에 대해 모르더라도 신뢰 할 수 있는 특성을 사용하여 부정행위가 없음을 신뢰 할 수 있게 해준다. 그렇기에 zcash의 경우는 비공개 계좌를 사용 할 수 있게 되며 비공개 계좌를 통해 이루어진 거래의 경우는 외부에 의해서 누가 거래를 했는지 알 수 없게 만들어준다.
이러한 zcash의 사례는 비록 프라이버시의 강화라는 점에서는 효과적이지만 사회라는 울타리 내에서 문제가 될 수도 있다. 실제로 zcash와 같이 개인 정보를 식별 할 수 없게 만드는 코인을 우리는 다크코인이라 부른다. 이러한 다크코인의 대표적인 예로는 2020년 대한민국 n번방 사태에서 이용된 모네로가 있다. 비록 zcash와 모네로에 사용되는 기술은 다르지만 사용자들의 프라이버시를 강화 시킨다는 점에서는 공통점이 있다. 그리고, 모네로가 악용 되는 사례를 보여준 만큼 zcash등 다른 다크코인들 또한 사회에서 악용 될 가능성을 지니고 있음을 보여주고 있다. 따라서, 영지식 증명의 기술적인 문제보다는 프라이버시의 강화와 악용될 가능성, 그 두 요인의 합의점을 기술적으로도, 그리고 제도적으로도 확보해야하는 현실이 어떻게 보면 zcash에서 영지식증명의 기술을 활용하는데 있어서의 현실적인 한계라고 볼 수 있다.
2) 온더(국내 사례)
국내 블록체인 기업 온더에서 ‘일반 연산 검증용 영지식 증명 서킷 기반 가상머신을 구현하기 위한 시스템’ (출처: 코인캣 미디어)에 대한 특허를 냈다. 온더에서는 이 기술을 현재 자신들이 개발한 ‘토카막 네트워크’에 적용 하려 하고 있다. 토카막 네트워크는 이더리움 블록체인의 속도와 보안성을 강화하고 네트워크의 확장과 다른 기능을 추가하기 위해 개발 되었다. 아직 정확히 영지식 증명에 기반한 특허를 어떻게 토카막 네트워크에 적용할지에 대해서는 안 나왔지만 아마도 영지식 증명의 특성상 보안성과 프라이버시 강화에 사용 될것이라고 생각된다.
3) 한계와 전망
고려대학교 정보보호대학원에서 2019년에 발간한 ‘영지식 증명을 활용한 프라이버시 보장 신용평가방법’에 의하면 영지식증명은 중앙기관에 의존하지 않는 그 탈중앙성과 이를 뒷받침 할 수 있을 정도로 프라이버시를 강화 시켜주기 때문에 신용평가 방법에 있어서 효율적이다. 그러나, “현재의 영지식 증명은 대량의 데이터와 많은 연산량이 필요할 경우 그 효율이 낮을 수 있으므로 서비스의 특성을 분석하여 채택 여부를 결정해야한다.”라고 결론지어 현재 영지식 증명에는 명확한 한계 또한 있음을 보여주었다.
4. MINA와 영지식 증명
1)mina 의 블록 전송 과정에서
▶Mina는 전체 블록체인을 몇 개의 트윗 크기(22kb)정도의 작은 용량으로 압축한 다음 해당 데이터를 보내는 방식을 사용하며 재귀적 영지식 증명을 활용하여 이 데이터를 일정한 크기로 유지한다. 이를 위해 MINA는 영지식 증명의 재귀적 구성이라는 방법을 사용한다.
▶미나에서 SNARK의 재귀적 구성 : 인증서들을 재귀적인(recursive) 구성으로 함께 엮을 수 있고 블록체인이 20kB(SNARK + 꼬리 끝 Merkle path)의 일정한 크기를 유지할 수 있도록 할 수 있다. 새로운 블록이 생성될 때마다 새로운 SNARK/인증서가 생성된다. 기존 인증서로 구성된 단일 SNARK를 만들면 블록체인의 전체 거래 이력을 증명하는 의미에서 단일 ‘메가’ SNARK를 만들 수 있어 단일 인증서의 크기를 유지하면서 제네시스 블록에서 현재 상태로 점프할 수 있다. 일반적으로 영지식 증명을 적용한다고 하더라도 snark가 쌓이면서 용량이 커지는 문제는 해결할 수 없다. 그러나 MINA는 블록이 새로 나올 때마다 그 블록을 앞선 블록체인과 하나로 묶어 하나의 snark를 만듦으로써 snark가 매번 쌓이지 않고 일정 크기로 유지할 수 있는 것이다. 이를 영지식 증명의 재귀적 구성이라고 한다.
▶MINA에서 SNARK란? SNARK는 합의를 위한 모든 규칙 검증에 필수적 요소로써 트랜잭션이 서명되었는지, 유효한지, 합의규칙에 따랐는지 (total hash power + chain strength for PoW, and the Variable Random Function/other rules for PoS)를 검증한다. snark는 블록 생산자가 스나커(snarker, 스나크 생산자)로부터 사들여 블록에 적용할 수 있다.
2) 피클에서 (피클이란? MINA의 스마트 컨트랙트)
Pickles에서 MINA는 zk-SNARK를 통해 재귀적 구성을 발전시킬 수 있다. 이는 영지식 증명을 통해 753비트를 255비트의 필드로 압축하여 MINA를 더욱 효율적으로 만들어주기 때문이다. 이렇게 압축함으로써 다음과 같은 3가지 효과를 얻을 수 있다.
- VRF 검증 속도의 16배 증가
- 해시 속도 8배 증가
- 렛저가 필요한 용량을 3배 절감
이처럼 MINA는 zk-SNARK를 활용하여 전체 연산을 증명하지 않고 정확하게 계산이 수행되었음을 증명한다. 즉, zk-snark가 모든 거래를 보여줄 필요 없이 블록 거래 이력의 정확성을 보장하는 위조불가능한 인증서의 역할을 수행하는 셈이다. 이를 통해 MINA는 검증에 필요한 비용을 감소시킴으로써 블록체인의 확장성을 높이고자 한다.
References
https://blockgeeks.com/guides/what-is-zksnarks/
글쓴이 : 윤기훈(Kihun Yun), 이수현(Suhyeon Lee), 심양헌(Yangheon Sim), 한지환(Jihwan Han)
