블록체인은 신뢰성, 안전성 등과 같은 장점을 가지고 있습니다. 하지만 보안성이나
퍼블릭 블록체인의 문제점 : 프라이버시 퍼블릭 블록체인에서 개인간의 거래가 발생하면 거래에 관한 상세 내역이 모두에게 공개되기 때문이다.
해결방안으로 나온 것이: zk-SNARKs
zk-SNARKs 를 도입하여 거래의 익명성을 보장하고 블록체인 데이터를 짧은 해시값으로 압축시켜서 저장용량을 줄일 수 잇다.
zk-SNARKs의 근간이 되는 것이 zero-knowledge proof 이다.
zero-knowledge proof = 영지식 증명 증명인, 검증인 등장 증명인 = 어떠한 것이 참임을 증명하고자 하는 사람 검증인 = 증명과정에 참여하여 증명인과 정보를 주고 받는 사람
증명하고자 하는 것이 참, 거짓 여부를 제외하고는 어떤 것도 노출하지 않는 것이다. zkp = zero knowledge proof의 기반은 interactive proof system이다. interactive proof system을 간략하게 설명하자면, 증명인과 검증인이 상호간에 메시지를 교환하면서 컴퓨팅하는 것을 모델링 한것이다. 그리고 이론적인 컴퓨팅 모델이다.
interactive proof system 에서는 증명인이 계산에 쓰이는 무한한 자원을 가지고 있다. 하지만 증명인은 신뢰할 수 없는 존재이다. 반면에 검증인은 한정된 자원을 가지고 있지만 신뢰할 수 있는 존재이다. 이러한 interactive proof system에서 일어날 수 있는 공격시나리오 중 검증인이 악의적인 행동을 하는 경우를 생각해 볼 수 잇따. 예를 들어서, 증명인이 자신의 주민등록번호를 알고 있고, 이 사실을 검증인에게 증명하기 위해서 관련정보를 검증인에게 보냈을 때 검증인은 증명인으로 받은 정보를 타인에게 판매하여 이득을 챙길 수 있다. 이렇게 증명인이 악의를 품는 경우를 예방하기 위해서 등장한 것이 zkp이다.
zkp에서는 앞서서 말했듯 증명하고자 하는 것의 참,거짓 여부를 제외하고는 어떤 것도 노출하지 않기 때문에 이와 같은 공격도 막을 수 있다.
영지식 증명의 경우에는 다음과 같은 세가지 조건을 모두 충족시켜야한다. 첫번째, 완전성(Completeness) = 어떤 조건이 참이라면, 정직한 증명인은 정직한 검증인에게 이 사실을 납득시킬 수 있어야한다. 두번재, 건실성(Soundness) = 어떤 문장이 거짓이면, 부정직한 증명인이라도 정직한 검증인에게 이 문장이 사실이라고 납득시킬 수 없어야한다. 세번째 영지식성(zero-knowledges) = 어떤 문장이 참이면, 검증자는 문장의 참, 거짓 이외에는 아무것도 알 수 없어야한다.
이 중에서 세번째가 영지식 증명의 핵심이되는 조건이다.
영지식증명이 적용된 사례
대표적인 사례 1) 알리바바의 동굴 그림가 같이 동굴은 고리형태이고 그 가운데에 잠겨진 문이 있다. 증명인 페기는 동굴안에 있는 문의 열쇠를 가지고 있다. 증명인 페기는 자신이 열쇠를 가지고 있다는 사실을 다른 사람에게는 알리지 않고 검증인 빅터에게 알리고자 한다.
이때 영지식 증명 방법이 사용될 수 있다.
증명인인 페기가 먼저 동굴의 A나 B방향 중 아무 방향으로들어간다. 이어서 검증인인 빅터가 A나 B 중 아무 것이나 출구를 골라서 페기에게 알려준다. 페기는 빅터가 말한 출구로 나온다.
만약 페기가 정말로 열쇠를 가지고 있다면, 빅터가 어떤 통로를 골라도 맞는 출구로 페기가 나올 것이다. 하지만 페기가 열쇠가 없다면은 처음에 고른 통로로만 나올 수 있다. 우연의 일치로 빅터가 말한 방향으로 나올 수 있겠지만 이 실험을 여러번 반복한다면 맞출 수 있는 확률은 매우 낮아진다. 페기가 빅터가 고를 통로로 들어갈 확률은 50센트이기 때문에 20번만 반복해도 100만분의 1 확률이 된다.
그리고 이 실험을 아무리 반복한다고 할지라도 제 3자의 입장에서는 페기와벡터가 사전에 어떤 통로로 나올지 약속을 했다고 생각할 수 있기 때문에 페기는 벡터외의 다른 사람들에겐 어떠한 증명도 되지 않는다. 즉, 벡터에게만 유효한 증명이 된다. 영지식 증명의 조건과 같이 생각해본다면 첫째, 완전성(Completeness) = 어떤 문장이 참이라면 정직한 증명자는 정직한 검증인에게 이 사실을 납득할 수 있어야한다. 증명자인 페기는 벡터가 말하는 동굴의 방향으로 항상 나올 것이기 때문에 벡터에게 자신이 열쇠를 가지고 있다는 사실을 납득시킬 수 있다.
둘째, 건실성(Soundness) = 어떤 문장이 거짓이라면 부정직한 증명자라도 정직한 검증인에게 이 문장이 사실임을 납득시킬 수 없어야한다. 이 실험을 계속해서 반복하다보면 벡터가 말하는 방향으로 항상 페기가 나올 확률은 현저히 떨어진다. 따라서 페기가 벡터에게 자신이 열쇠를 가지고 있다고 속이려고 할지라도 속일 수 없다.
셋째, 영지식성(Zero-Knowledge) = 어떤 문장이 참이면, 검증자는 문장의 참 거짓 이외에는 아무것도 알 수 없어야한다. 벡터는 이 실험을 여러번 해본 결과로 페기가 열쇠를 가지고 있다는 사실은 알 수 있지만 그 외에 열쇠가 어떻게 생겼는지와 같은 정보는 알 수 없다.
이러한 영지식 증명은 다크코인에서 활용되고 있다. 다크 코인이란 코인 거래에 대한 장부기록이 익명으로 진행되기 때문에 코인이 어떻게 이동했는지 알 수 없는 코인이다.
영지식 증명을 위해서는 증명자와 검증자가 항상 on-line 상태여야한다. 이러한 제약은 매우 비효율적인 구조였기 때문에 이에대한 개선책으로 non interactive zkp 가 나왔다. 증명자와 검증자 사이의 상호작용 업싱도 영지식 증명이 가능한 것을 의미한다.
이는 증명자와 검증자가 on-line 상태인지 아닌지 관계없이 증명을 할 수있다.
From interactive to non-interactive : schnorr identification proto
Non interactive의 핵심은 결국 증명자와 검증자의 메시지 교환이 최소화되어야한다. 즉, 증명자가 특정메시지를 검증자에게 보낸후 다음작업을 할 때 검증자가 증명자로부터 추가적인 메시지가 필요하다면 이는 non-interactive한 방식이 아니다. 증명자가 증명하려는 메시지를 검증자에게 보낸 후 둘 간의 연결이 끊겨서 더 이상의 추가적인 정보를 보내지 못하더랃 결국은 보낸 메시지가 검증되어야하는 것이 non-interactive proof의 핵심이다.
먼저,
영지식 증명의 수학적 구현 영지식 증명의 수학적 구현에 있어서 핵심은 일방향 함수이다. 일방향 함수란, 함수의 결과값으로 부터 함수에 주어진 입력값을 계산하기 어려운 함수를 의미한다. 즉, 역함수 계산이 어려운 것을 의미한다. 이버에는 일방향특성을 가지는 이산 로그 문제(Discrete Logarithm Problem, DLP)를 다룬다.
( 이를 위해서 대수 구조의 전반을 학습해보자. 암호학에서는 정수의 집합가 그들사이에 정의되는 연산이 요구된다. 일련의 연산들의 집합을 대수 구조라고 한다. 이러한 연산들의 집합인 대수구조 중 대표적인 것인 군, 환, 체에 대하여 살펴보자
군(group) <G, +> 가장 기초적인 대수 구조이다. 하나의 이항연산만을 갖는다. (이항 연산이란 두개의 항을 필요로하는 연산을 말한다. ex, 덧셈, 곱셈)
군은 다음과 같은 네개의 공리를 만족한다. 공리 = 수학과 같은 이론체계에서 가장 기초적인 근거가 되는 명제. 증명할 필요가 없는 진리에 해당한다.
결합법칙이란 한 식에서 연산이 두번 이상 연속될 때, 계산의 순서가 달라져도 결과가 같다는 법칙이다.
환(ring) <R, +> 두 개의 이항연산을 갖는 대수 구조이다. 환은 다음과 같은 공리를 만족한다. 이항연산 ‘+’에 대하여
참고로 공리 1과 2 만 만족한다면 이를 반군(semigroup) 이;라고 하며, 1, 2,3을 만족한다면 모노이드(monoid) 1 부터 4까지를 모두 만족할 때 군이 된다. 군의 네가지 공리와 더불어 교환법칙이 성립한다면 이를 아벨군 또는 가환군이라고 한다. (교환 법칙: 이항 연산의 결과과 두 원소의 순서에 관계없다는 뜻이다.)
따라서 <R, +>는 아벨군이다.
이항연산 ‘º’ 에 대하여
)이산 로그 문제란 간단히 말해서, a의 x제곱은 b라는 식이 존재할 때 지수에 해당하는 x를 구하는 것이 어렵다는 것이다. x라는 값이 존재할 때 a는 x제곱을 구하는 것은 쉽지만 a와 b라는 값만 존재할 때에는 x라는 값을 구하는 것이 어렵다는 것이다. 이러한 이산 로그 문제는 디피헬만 키교환의 보안성에서 중요한 역할을 하고 있다.