지케이스나크 정복을 위한 '초중급' 암호학 부록
RSA와 비대칭적 암호화
암호 알고리즘에서는 암호화와 복호화 과정에 암호키가 필요하다. 암호키가 없으면 암호문을 평문으로 다시 복호화할 수 없다. 암호 알고리즘은 사용되는 암호키에 따라 다시 대칭과 비대칭 암호 알고리즘으로 분류된다.
대칭 암호 알고리즘은 암호화할 때 사용하는 암호키와 복호화에 사용되는 암호키가 동일하다. 하지만 비대칭 암호알고리즘에서는 암호화에 들어가는 열쇠와 복호화에 들어가는 열쇠가 서로 다르다. 1970년에 만들어진 암호 알고리즘인 RSA 암호에서는 공개키와 개인키가 만들어지며 이를 통해 암호의 생성과 해독을 비대칭적으로 수행한다.
모든 사람에게 공개되고 받는 사람을 기준으로 메시지를 암호화하는데 필요한 키를 공개키라고 한다. 또 암호화된 메시지를 받은 당사자가 암호문을 해독하기 위한 열쇠를 개인키라고 한다. 사용자는 공개키와 개인키 두개의 키를 보유하게 되는데 개인키는 사용자가 항상 비밀로 유지해야 하며 분실에 유의해야 한다.
앨리스가 밥에게 밥만 볼 수 있는 암호문을 보내려면 먼저 밥의 공개키가 필요하다. 앨리스는 보내고자 하는 메시지를 밥의 공개키를 사용해 암호화한다. 암호문을 받은 밥은 밥의 개인키를 써서 암호문을 평문으로 복호화한다. 비대칭 암호화의 특징을 역으로 사용해 앨리스가 개인키로 암호문을 만들면 누구나 앨리스의 공개키로 암호문을 복호화해 볼 수도 있는데 이는 전자서명에서 사용되는 방식이다.
RSA의 개인키와 공개키는 소인수 분해의 난해함을 기반으로 커다란 2개의 소수를 곱하며 생성된다. RSA는 인터넷 암호화의 SSL, TLS, 공인인증서등 현재 가장 대중적으로 쓰이고 있는 암호화 방식이다. 하지만 RSA 암호는 소인수 분해 알고리즘인 이차체 등의 해법으로 풀리곤 해 문제가 됐다.
RSA는 숫자가 커질수록 모바일 기기 등에서 연산이 많아져 느려지는 단점이 있으며 수가 클수록 소수의 증가폭이 감소해 공격자에 의한 복호화가 오히려 쉬운 단점이 존재한다. 한편 양자컴퓨터가 등장하면 복호화가 너무 쉽게 풀리는 등의 우려가 있어 암호학계에는 새로운 트랩도어 함수가 필요해졌다.
암호학계에 등장한 차세대 강자, 타원 곡선 암호화 기법
암호가 쉽게 풀리지 않도록 여러 연구가 진행되던 중 타원곡선암호학(ECC)은 1985년 처음 등장했다. 하지만 업계에서 표준으로 채택된 건 2000년대 초반으로 그리 오래되지 않았다. 타원곡선의 종류는 많지만 암호학에 쓰이는 표준형은 y^2=x^3+ax+b의 형태를 지닌다. 이를 바이어슈트라스 표준형이라고도 한다. 곡선이 만들어내는 실제의 모양은 타원과는 사실 관련이 없다. 수학의 역사에서 타원의 둘레를 구하는 적분의 과정에서 도출된 식이기 때문에 타원곡선이라고 부른다.
특히 암호학에서는 부딪히는 값의 추측을 더욱 어렵게 하기 위해 정의역과 치역을 소수 체계로 한정한다. 여기서는 덧셈과 곱셈에 대해 나머지값을 결과값으로 쓰는데 이를 유한체라고 말한다. 유한체는 속한 원소가 한정돼 있고 덧셈과 곱셈 등의 연산에 닫혀있는 집합이다.
이렇게 바뀐 타원곡선함수는 나머지가 같은 수 여럿 존재하는 까닭으로 형태가 곡선이라기보다 점들이 뭉쳐있는 구름의 모양새를 지닌다. 한편 암호학에서는 타원곡선의 난이도를 높이기 위해 곡선에 부딪히는 횟수도 소수 단위로 한정한다. 또 일정한 한계치 값을 넘치면 새로운 값에서 함수를 시작시키는 등 제약을 도입하게 되는데 이렇게 추가적으로 암호화한 값은 해독하기가 매우 어렵다.
타원곡선에서 생성되며 소중히 보관해야 하는 개인키는 소수 기준값보다 작은 값으로 주로 난수생성기를 통해 생성된다. 타원곡선의 공개키는 제너레이션 포인트인 시작점 G가 개인키에 해당하는 숫자만큼 타원곡선 상의 덧셈 연산을 실행해 곡선에 안착한 좌표에 해당한다. 공개키는 생성된 후 공개되지만 공개키와 시작점 G를 토대로 개인키를 유추하기란 상당히 어렵다.
이를 문제를 타원곡선이산로그문제(ECDLP)라고 하는데 수학적으로 매우 난해한 문제로 알려져 있다. ECDLP의 특성상 타원곡선을 뚫고 지갑을 해킹할 가능성은 낮지만 안심할수는 없다. 2013년 안드로이드 스마트폰에 저장된 비트코인 지갑이 털린 사건이 있었는데 모바일 기기의 난수생성기의 품질이 떨어져 타원곡선의 개인키가 예측하기 쉬워서 발생했다.
수학자들은 타원곡선에서 발생한 교차횟수를 발견하기 위한 효과적인 솔루션을 발견해내지 못했다. 직접 대입하는 방식 말고는 아직까지 해답이 없다. 실제로 트랩도어 함수가 생성한 암호의 난이도는 매우 높다. 예를 들어 228비트의 RSA 암호를 해독하는데 드는 컴퓨팅 자원을 사용하면 티스푼 정도의 물을 끓일수 있지만 타원곡선에 기반한 228비트의 암호를 풀기 위해서는 지구 전체의 물을 모두 끓일 정도의 컴퓨팅 자원이 들어간다.
ECC는 적은 비트수로도 높은 암호 성능을 낼 수 있어 비트코인의 서명과 애플 기기들이 ECC를 주로 사용한다. 실제로 2006년 등장한 타원곡선인 y^2=x^3+486662x^2+x는 커브25519라고 불리는데 구글의 크롬브라우저, 오픈SSH, 애플 기기 등 여러 곳에 사용되며 y^2=x^3+7라는 수식인 secp256k1 곡선은 비트코인과 이더리움의 서명에 현재 사용되고 있다. 한편 타원곡선 알고리즘은 우수한 암호 성능을 갖고 있지만 특허상의 문제로 보편화되고 있지 않다. 하지만 조만간 특허가 종료되기에 내년부터는 ECC가 보편화 될 거라는 예측도 나오고 있다.
지케이스나크 도입 위해 수식 변환하는 R1CS 연산과 QAP로의 간단한 변환
블록체인에 지케이스나크를 도입할 경우 사용자 입장에서는 커다란 변화는 없지만 지케이스나크 내부의 데이터는 다소 복잡한 처리과정을 거친다. 타원곡선암호화 뿐만 아니라 여러 수학적인 트릭이 사용된다. 지케이스나크는 ‘열려라 참깨처럼’ 증명자가 주민등록 번호 등과 같은 단순한 정보를 알고 있는지 증명하는 수준이 아니다. 한 발 더 나아가 증명자가 단순한 정보를 토대로 만들어진 수식 전체를 알고 있는지 검증하는 방법이다.
때문에 지케이스나크를 사용하는 블록체인 네트워크나 인증 서비스 사용자인 증명자는 증명해야 할 정보를 그저 해시함수값으로 만드는 등 단순한 연산을 수행하는 수준을 넘어 증명 정보를 토대로 여러 개의 항으로 이뤄진 다항식 수식을 생성해야 한다. 복잡해보이지만 이 작업은 지케이스나크 프로그램 내부에서 입력값이 들어오면 자동으로 이뤄지게 돼 사용자 경험은 이전과 다르지 않다.
다만 무턱대고 아무런 수식이나 생성되면 안 된다. 생성된 다항식은 연산의 효율성과 검증을 위해 특별한 종류의 형식에 맞춰야 한다. 이같은 특수한 형식을 이차산술프로그램(QAP)이라고 부른다. 증명자가 공개하고 싶지 않은 내용을 담은 이전의 수식은 계산을 거쳐 QAP로 변환된다.
이에 앞서 주어진 다항식을 컴퓨터 언어에 맞도록 변환하는 플래트닝 과정이 필요하다. 이 과정이 있어야만 증명자가 어떤 다항식의 해를 알고 있음을 기계적으로 증명할 수 있다. 수식으로 만들어지는 과정은 암호화함수를 통하면 된다. 이러한 방식으로 개인정보를 수식으로 표현할 수 있다.
예를 들어 y=0, y=x^3+1이라는 수식을 알리바바의 개인정보를 수학적으로 표현하는 수식으로 가정하면 해 x=-1는 이에 접근하는 핵심정보가 된다. 즉 y값 0은 공개키, x값 -1은 개인키인 셈이다. 알리바바는 x^3+1=0의 답인 x= -1을 알고 있고 원래 수식과 답은 공개하지 않으면서 이를 증명하고 싶다. 이 수식을 자바스크립트 코드로 간단히 작성하면 function func(x){return x**3+1} 라고 쓸 수 있다.
먼저 지케이스나크 프로그램은 다항식의 단일 사칙연산을 기준으로 코드를 수학적으로 쪼개 한줄씩 나눈다. x^3+1라는 수식은 이제 in=x*x, y=in*x, ~out=y+1 이렇게 변환된다. 분할된 각각의 줄은 로직게이트라고 불린다. 중간에 발생한 변수와 더미 변수들은 행이 한개인 벡터로 매핑된다. 변수는 (one, x, ~out, in, y)와 같은 형식으로 모아지는데 이를 토대로 게이트는 행렬로 다시 표현될 수 있다.
각 게이트의 행렬 변환을 위해 a, b, c 벡터가 선언된다. 각 게이트에 등장하는 변수는 순서대로 a, b, c 벡터에 담기게 된다. 이 때 one, x, ~out, in, y등의 성분이 각각의 로직게이트에서 등장하는지 그렇지 않은지에 따라 0과 1로 표현한다. 상수항의 경우 0, 1 이외의 수가 들어갈 수 있다. 예를 들어 첫번째 게이트에서는 a=(0, 1(x), 0, 0, 0), b=(0, 1(x), 0, 0, 0), c=(0, 0, 0, 1(in), 0)이 된다. 코드는 이렇게 0과 1등의 수로 나타낸 행렬 그룹으로 펼쳐져 컴파일되는데 이를 R1CS라고 한다. 한편 이 과정에서 (one, x, ~out, in, y) 괄호 안의 값을 계산해 모두 채워넣은 해를 솔루션벡터 s라고 한다.
쭉 나열된 모든 a, b, c 벡터의 나열을 A, B, C 군으로 명명하고 각 게이트별로 존재하는 행렬을 각 군에 모두 모은다. 한편 게이트에서는 s*a+s*b-s*c 수식에 a, b, c 등의 변수값들을 입력할 때 결과가 항상 0이 되는 특징이 있다. 이를 응용해 검증자가 a, b, c를 대입해 실제로도 0이 되는지 확인하면 솔루션 s를 몰라도 증명자의 솔루션 벡터 s가 유효하다고 인정할 수 있는 셈이다.
하지만 이러한 검증방식은 실제 상황에서는 너무 많은 연산이 들고 전부를 검증해야 하기에 실용성이 떨어진다. 대부분의 경우 다항식 코드를 분할한 로직 게이트가 실제로는 수천개가 훌쩍 넘어가기 때문이다. 이같은 복잡성을 극복하고 검증을 깔끔하게 하도록 R1CS는 주로 QAP 형태로 변환된다.
QAP는 일종의 공식을 유도하는 과정과도 같은데 지케이스나크에서는 증명자가 QAP까지 생성을 완료해야 암호화를 거쳐 영지식증명이 생성된다. QAP에서는 기존의 R1CS의 복잡한 벡터의 점곱이 다항식의 연산으로 대체된다. 수학이 사용하는 여러 형태 중 다항식을 꼽아 쓰는 이유는 서로 다른 다항식은 대부분의 점에서 다르다는 슈워츠-지펠의 보조 정리를 응용했기 때문이다.
이전에 (0, 1(x), 0, 0, 0)으로 표현한 R1CS의 성분 벡터들은 이제 px^3+qx^2+rx+t 등의 형태로 바뀐다. QAP의 변수가 다항식이 됐다. 이렇게 특정한 점을 토대로 다항식으로 만드는 가장 간단한 방식은 라그랑주 보간법이다. 라그랑주 보간법을 사용하면 R1CS로 생성된 좌표를 지나는 다차함수를 만들수 있다. 생성된 다차함수 역시 각 n번째 게이트에서 s*a+s*b-s*c 수식의 점곱이 0이 되어야 하는 사실에는 변함이 없다.
한편 변수 x가 1인 지점에서 함수값이 0이 된다는 사실에 착안하면 다항식의 나머지 정리를 적용할 수 있다. 즉 1번째, 2번째... n번째 게이트에서 함수값이 0이 된다는 사실에서 (x-1)(x-2)...(x-n)를 인수로 갖는 다항식 z를 유도할 수 있다. 이는 곧 검증을 위한 도구처럼 쓰인다. 이를 활용하면 검증은 매우 간단하다. 검증자는 지케이스나크 프로그램을 통해 전달받은 일차적으로 가공된 값을 토대로 s*A+s*B-s*C을 z으로 나누어 떨어지는지만 확인하면 된다. 나머지가 없이 나누어 떨어지면 알리바바가 수식 전체를 알고 있다고 검증할 수 있다.
단순한 R1CS QAP는 뚫리기 쉬워...QAP에 타원곡선 암호화를 사용
하지만 위와 같이 다항식의 행렬을 생성하는 간단한 수준의 QAP는 외부에서 마음만 먹으면 뚫을 수 있어 보안 성능이 높지는 않다. 알리바바가 답을 알고 있다고 증명하지만 다른 사람도 역함수나 임의적인 값 추정을 통해 답을 맞추는 경우가 충분히 발생할 수 있기 때문이다. 이같은 문제가 금융거래에서 발생하면 송금의 차질이나 이중지불의 문제가 생길 수 있어 위험하다.
이를 막기 위해 지케이스나크에서는 생성된 QAP를 타원곡선 위에 올려 높여 문제를 쉽게 풀지 못하도록 하고 있다. 트러스트파티는 QAP의 다항식 A, B, C, H에 어떤 임의의 값을 대입해 QAP를 타원곡선상의 좌표 (x, y)로 만든다. 타원곡선 위의 점 (N, M)는 비밀값 k를 곱한 N*k=M 관계를 항상 만족한다. 한편 사용자로부터 정보를 입력받아 변환되는 다항식 A, B, C에는 실제로 매우 거대한 자료형이 들어가게 된다.
이같이 QAP의 다항식 A, B, C, H에서 도출된 점 P, Q, R, H는 타원 곡선상에 공개된다. 점들은 QAP의 본래 방정식인 P*Q-R=H*Z를 만족한다. 이렇게 QAP를 타원곡선에서 암호화한 뒤 공개해 전송하면 검증자는 공개된 암호화된 값을 토대로 타원곡선의 특수한 연산을 수행해 원본 정보의 값이 참임을 검증할 수 있다.
이더리움에서는 세컨드레이어에서 여러 사용자가 익명 거래의 트랜잭션을 만들 목표로 트랜잭션을 생성하고 릴레이어에게 전송한다. 이때 사용자가 보내는 요청 트랜잭션은 암호화가 안 된 일반적인 트랜잭션이다. 릴레이어는 요청된 여러 사용자의 트랜잭션을 주기적으로 취합한다.
릴레이어는 일종의 오프체인이며 블록의 작동방식과 유사하게 내용을 취합하며 이를 하나의 증명 트랜잭션으로 만들어 전송한다. 증명 트랜잭션은 컨트랙트의 검산 등의 검증을 거쳐 최종적으로 메인 블록에 포함된다. 한편 지캐시에는 릴레이어가 따로 존재하지 않으며 애초에 공개, 비공개의 두가지 주소타입이 있어 비공개 주소로 보내는 트랜잭션은 타원곡선의 암호화를 통해 영지식으로 전달된다.
증명과 검증 과정의 로직은 복잡하지 않다. 영지식증명의 증명자가 수식에 값을 넣고 QAP로 변환하면 V(x)*W(x)-Y(x)=H(x)*T(x)의 형식으로 수식이 만들어지는데 이를 암호화하면 E(V(x)*W(x) -Y(x)) = E(H(x)*T(x))의 식이 만들어진다. 증명자는 E(V(x), W(x), Y(x)), E(T(x))의 암호화된 값을 증명으로 공개한다.
하지만 암호화된 값만으로는 어떠한 정보도 알아낼 수 없어 사실상 안전하다. 주어진 암호문을 토대로 검증자는 E(T(x))가 E(V(x)*W(x)-Y(x))로 나누어 떨어지는지 검증한다. 즉 x값을 모르고 암호화돼 있어도 나누어 떨어지는지 확인할 수 있다. 암호문의 이같은 마법같은 연산이 가능한 이유는 동형암호의 특성에 있다. 특히 이를 위해 타원곡선에서는 페어링이라는 정교한 동형암호화 기법을 사용한다.
타원 곡선상의 동형암호화를 위한 페어링 암호화
동형암호는 암호화되지 않은 평문의 값 a, b와 이를 암호화한 암호문 H(a), H(b) 객체 간 연산 관계를 보존하는 방식으로 4세대 암호기술로 꼽힌다. 즉 어떤 값 a, b를 동형은닉함수를 통해 암호화하면 두 대수 구조 사이의 연산이 암호문에서도 보존되는 특징이 있다. 예를 들어 평문을 토대로 a+b를 더한 값과 평문을 동형은닉한 암호문 둘을 덧셈 연산한 H(a)+H(b) 값은 같다.
동형암호화를 통해 암호화하면 검증자가 원본값을 몰라도 암호문 값을 토대로 연산을 수행해 증명자의 a+b, a*b 등의 연산이 올바른지 검증할 수 있다. 특히 타원곡선의 페어링은 타원곡선 위에서의 동형암호화 기법의 일종인데 증명자가 원본값을 노출하지 않고도 검증자가 수식의 결과값을 알 수 있다. 즉 검증자가 원래의 내용을 몰라도 증명자가 옳고 그른지 검증할 수 있다.
지케이스나크 영지식증명이 구현된 가장 간단한 형태는 타원곡선 페어링의 형태와 비슷하다. 타원곡선의 페어링은 타원곡선이 디지털 서명이나 암호화 기술 분야에 등장한지 30년만에 추가된 새로운 개념이다. 페어링은 겹선형사상(바이리니어맵)이라고도 하는데 타원 곡선 상에서 동형암호화를 하는 방법을 제공한다.
예를 들어 타원 곡선 위의 좌표가 방정식 P=G*p, Q=G*q, R=G*r라는 관계를 만족하고 증명자가 5*P+7*Q=11*R라는 수식을 제출했을 때 검증자는 증명자의 민감정보를 담고 있는 p, q, r 값을 직접 몰라도 5*p+7*q=11*r 수식을 페어링 연산으로 확인해봄으로써 증명자의 원래 정보가 옳은지 검증할 수 있다.
타원곡선의 페어링 개념을 사용하면 단순한 일차식 검증 뿐만 아니라 암호화된 이차식이나 곱셈식의 검증도 비교적 쉽게 수행된다. 특히 페어링은 타원곡선상에서 곱셈의 동형암호화를 가능하게 해준다. 페어링을 통해 수행하는 곱셈은 곱하기는 쉬워도 역으로 원래 값을 추정하기는 매우 어려운 특징이 있다. 반면 검증자는 증명자로부터 공개된 P, Q, R값만 갖고도 실제로 p, q, r을 모르지만 곱셈연산 p*q=r은 쉽게 확인할 수 있다. 또 P, Q, R값을 토대로 암호화 상수로 쓰인 p, q, r 값을 역추적하는 디피 헬만 컴퓨테이셔널 알고리즘도 이론상으로 가능하긴 하지만 실제로는 매우 어렵다.
사실 페어링에 사용되는 연산의 규칙은 사용자가 정의하기 나름이다. 예를 들어 E(x, y) = 2^xy 등의 수식을 곡선 상 페어링 규칙으로 삼을 수도 있다. 하지만 이처럼 쉬운 연산의 경우 역함수가 쉽게 만들어져 암호 체계가 붕괴될 우려가 있다. 또 실수 공간을 연속적으로 담을 경우 하드웨어의 저장공간도 많이 차지할 수 있어 문제다.
이를 막고 타원곡선 암호화 함수의 난이도를 높이기 위해 페어링 연산도 소수 공간으로 한정되며 타원곡선 그래프를 표현하는 데는 나머지 값이 좌표로 활용된다. 연산을 수행하며 나눈 값의 나머지를 반드시 정수로 만들기 위해 페르마의 소정리, 확장된 유클리드 호제법 등 다양한 수학적 기법이 사용된다.
한편 페어링 개념에 추가된 수학적인 기법 중에는 증명자가 수식의 해답을 공개하지 않고도 QAP를 풀 수 있다는 사실을 증명하는 방법이 여럿 있다. 바로 페어링 작업에서 타원 곡선의 좌표 함수를 처리하는 디바이저라는 개념이다. 두 함수의 디바이저가 같다면 각 함수는 배수의 관계에 있다고 표현하는데 이를 이용해 값을 직접 계산하지 않고도 대체값을 연산해 수식을 확인할 수 있는 특징이 있다. 하지만 이같은 연산을 지원하려면 계산적인 수식 문제를 수학적 기법을 적용하기 쉬운 QAP로 변환하는 과정이 필수적으로 선행돼야 한다.
입력값을 타원곡선의 점으로 올리는 트러스티드 셋업
라그랑주 보간법 등으로 만든 QAP 다항식을 증명자가 타원곡선 위에 올리는 과정을 트러스티드 셋업이라고 한다. 이렇게 타원곡선을 도입하면 여러 수학적 기법을 사용할 수 있는데 증명자가 QAP의 해를 알고 있음을 민감 정보의 ‘민’자도 꺼내지 않고도 증명할 수 있다. 검증자의 검증도 어렵지 않다. 타원곡선의 페어링을 확인하면 수식의 검증이 간단히 끝난다.
트러스티드 셋업은 증명자인 릴레이어가 주축이 돼 수행된다. 검증자의 검증 수행을 위해 필요한 정보는 트러스티드 셋업 단계에서 생성돼 공개되며 네트워크의 모든 사람이 동일하게 공유하게 된다. 이렇게 공개하는 이유는 증명과 검증 과정에서 값을 주고받는 상호 작용을 애초에 줄이기 위한 목표가 크다. 지케이스나크는 증명자와 검증자 간 여러차례의 상호작용이 없이 단답형으로 검증이 이뤄지는 특성이 있다.
다만 트러스티드 셋업 과정에는 검증 단계에서 필요한 다항식 H가 몇차식으로 나올지 모름에도 불구하고 최고차항을 미리 포함하고 있어야만 한다. 때문에 지캐시의 경우 이를 t값의 20만차 등비수열을 추가하는 형태로 풀고 있다. 한편 트러스티드 셋업에 들어가는 휘발성 비밀값 t, k는 톡식 웨이스트라고 부르는데 또 다른 마스터키처럼 사용되기 때문에 알려지면 매우 곤란한다. 때문에 공개 파라미터를 생성하는 과정에서 톡식 웨이스트를 반드시 제거해야 한다.
만약 k값이 노출되면 식이 악의적인 공격에 의해 여럿 만들어지는데 이로써 복제코인이 등장할 수도 있다. 지캐시에서 톡식 웨이스트는 여러 참여자에게 분할돼 관리되는데 만약 한 사람이라도 자신이 소유한 키를 폐기하면 나머지 사람들은 동작되기로 가정한 키가 파괴돼 참여자 모두가 사용할 수 없는 상태가 된다. 이같은 메커니즘을 지캐시의 멀티파티컴퓨테이션(MPC)이라고 한다.
비밀값을 확실하게 폐기하기 위해 지캐시에서는 여러 사람이 열쇠의 일부분을 조금씩 만들어서 조합해 사용하고 비밀키를 생성할 때 쓴 하드웨어도 파기해 버리는 등 복잡한 과정을 수행한다. 스타크(zk-STARK)는 이같은 과도한 연산을 줄이기 위해 암호 알고리즘을 가볍게 적용한 방식인데 별도의 트러스티드 셋업 단계도 필요하지 않는 특징이 있다.
트러스티드 셋업과정에서 증명자는 A*B-C=H*Z라는 QAP 수식을 완성시킨다. QAP가 완성되면 타원곡선 페어링를 생성해 증명을 생성한다. 증명자가 여기까지 마쳐야 트러스티드 셋업도 끝난다. 하지만 이 과정에서 타원곡선 상의 좌표쌍을 생성하는 동형암호화 작업과 배수연산을 통해 다항식 H값을 얻는 작업이 증명을 생성하는 데 있어 병목으로 꼽힌다. 이를 해결하기 위해 증명을 만드는 과정에서 H값을 빠르게 얻기 위해 고속 퓨리에 연산 등이 활용되기도 한다. 한편 고속 퓨리에 연산은 O(n log n)로 선형로그의 시간이 걸리는 높은 성능의 알고리즘에 속한다.
페어링을 사용하는 ‘블라인드’ 검증 알고리즘
트러스티드 셋업까지 모든 단계를 준비하고 연산을 거쳐 다항식을 타원곡선 위의 점으로 변환하면 검증은 매우 쉽다. A*B-C=H*Z의 검증은 수학적 기법인 페어링을 통해 e(a,b)/e(c,G)=e(h,G*Z(t))가 성립하는지만 확인하는 식으로 이뤄진다. 따라서 검증자는 점P, Q, R, H값을 토대로 페어링 연산인 e(p,q)/e(r,G)=e(h,G*Z(t))만 확인하면 된다.
이처럼 상대방의 내용을 알지 못해도 그것이 유효함을 검증할 수 있는 이유는 타원곡선 페어링 기법 때문이다. 검증자의 검증은 P*k=Q가 사실이고 k 값을 모를 때 R*k=S의 검증은 페어링을 통해 e(R, Q)가 e(P, S)와 일치하는지 알아보면 된다는 특징에 기초한다. 컨트랙트는 이를 토대로 검증 로직을 갖추고 있다.
검증은 스마트 컨트랙트가 자동적으로 수행한다. 먼저 검증자는 증명자가 제출한 수식을 검증하기 위해 매개변수를 확인한다. 2단계에서는 A, B, C 수식의 선형 결합을 확인한다. 3단계에서는 선형 결합의 계수가 올바른지 확인한다. 마지막 단계에서는 QAP의 디바이저 연산 등을 통해 A*B-C=H*Z 좌항과 우항이 배수 관계에 있는지 판정한다. 증명자인 릴레이어가 생성한 증명은 8개의 타원곡선 좌표를 포함하고 있는데 이를 검증하기 위해 타원곡선의 곱셈 연산이 수행되며 페어링도 5번 확인하게 된다.
모든 과정이 오류없이 확인되면 지캐시는 경우 트랜잭션을 블록에 포함시키게 되며 이더리움은 컨트랙트의 스테이트에 트랜잭션을 적용한다. 즉 검증자는 증명자의 증명이 유효하다고 인증하며 증명자의 잔고확인 등의 요청을 수락하는 등 다음 과정으로 넘어가게 된다. 지캐시에서는 돈의 소유권을 증명해 돈을 실제로 쓸 수 있도록 하는 규약을 영지식증명으로 정했다. 반면 이더리움에서는 영지식 증명의 검증 컨트랙트와 관련해 정의된 기능이 현재 아무것도 존재하지 않으며 스마트 컨트랙트로 어떤 내용을 진행할 것인지 사용자의 정의가 반드시 필요하다.
최근 지캐시는 사플링으로 프로토콜을 업데이트하며 타원곡선의 성능을 끌어올리고 소요되는 연산의 양을 비약적으로 줄였다. 영지식증명에 생성에 걸리는 시간이 40초에서 10초 내외로 줄었고 차지하는 메모리도 3GB에서 40MB로 97%를 감량했다. 사플링 정도면 모바일에서도 충분히 쓸 수 있는 수준이다.
기사작성에 참여하고 검수를 진행한 전범준 아르고 수석연구원은 티맥스에서 룰엔진 및 데이터베이스를 개발했고 에스코어에서 노에스큐엘(NoSQL) 데이터베이스 서비스 및 검색엔진을 개발했다. 지난 2016년 블로코에 합류해 블록체인 백엔드 모듈 개발과 에코시스템 구축을 담당하고 있다. 이밖에 최지혁 해치랩스 개발자, 박정원 온더 연구원의 도움도 함께 받았다.
[강민승 D.STREET(디스트리트) 기자]
[ⓒ 매일경제 & mk.co.kr, 무단전재 및 재배포 금지]
Copyright © 매일경제 & mk.co.kr. 무단 전재, 재배포 및 AI학습 이용 금지