영지식 스타크

영지식 스타크(zk-STARKs)는 영지식 스나크(zk-SNARKs)의 단점을 보안한 새로운 수학적인 영지식 증명 기술로 과도한 연산을 줄이기 위해 암호 알고리즘을 가볍게 적용한 방식이다.

개요

영지식 스타크는 영지식 스나크의 단점을 보완하기 위해 대체 버전으로 만들어졌으며 더 신속하고 저렴하게 기술을 구현해낼 수 있다. 영지식 스타크는 충돌 저항성 해시함수를 통해 더 희박한 대칭 암호화에 의존하기 떄문에 초기 신뢰 설정을 필요로 하지 않는다. 또한 요구하는 컴퓨팅 능력 수준이 비싸고, 이론적으로 양자 컴퓨터에 의해 공격받기 쉬운 영지식 스나크의 정수론적 가정을 제거한다.

영지식 스타크의 더 빠르고 저렴한 기술 구현을 가능하게 한 주된 이유 중 하나는 증명자와 검증자 간의 통신 횟수의 양이 계산의 증가에 비해 일정하기 때문이다. 대조적으로 영지식 스나크는 더 많은 계산이 필요할수록 당사자들이 더 많은 메시지를 주고받아야 한다. 따라서 영지식 스나크의 전체 데이터 크기는 영지식 스타크 내의 데이터보다 훨씬 크게 된다.

특징

영지식 스타크는 세 가지 측면에서 영지식 스나크보다 강점을 가진다.

• 초기 신뢰 설정 불필요

영지식 스나크의 가장 큰 문제점은 신뢰기관(trusted party)의 존재이다. 프로토콜 내에서 신뢰기관의 역할은 매우 크며, 증명을 생성하는 데 있어서도 큰 비중을 차지하고 있다. 신뢰기관은 노출되면 안 되는 정보를 통해 거짓 증명(fake proof)를 생성할 수 있으며, 외부의 다른 집단과 공모할 가능성 또한 있다.

영지식 스타크의 T는 투명한(Transparent)으로, 초기 신뢰 설정(Trusted Setup) 단계에서 만들어지는 휘발성 정보들이 비트코인 채굴과 비슷한 방법으로 랜덤하게 생성되도록 설계했다. 이를 통해 신뢰 기관의 존재는 불필요해졌다.

또한 영지식 스타크는 충돌저항성 해시함수를 기반으로 하여 사실상 비대칭 암호화 방식이기 때문에 초기 신뢰 설정이 필요하지 않기에 이러한 문제를 해결한다.

* 충돌저항성 해시함수 : 해시함수에 서로 다른 두 개의 입력값을 넣을 때 동일한 출력값이 나오는 상황이다. 이는 해시함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 비둘기집 원리(Pigeonhole principle)를 기반으로 하며 해시충돌을 없애는 것은 매우 어렵다. 해시충돌은 알고리즘, 자료구조의 효율성을 해치는데, 특히 암호화된 해시함수는 그 안정성을 해치기 때문에 더욱 해시충돌 발생을 예방해야 한다. 이렇게 해시충돌에 저항을 갖는 함수를 충돌저항성 해시함수라 한다.

* 대칭 및 비대칭 암호화 : A가 B에게 데이터를 전송할 때 A는 해당 데이터에 암호를 설정하여 해독키를 만든다. 그 후 B가 A로부터 데이터를 받으면 A는 그 해독키를 B에게 알려줘 암호를 풀게 하는데, 이것이 대칭 암호화이다. 대칭 암호화의 가장 큰 문제점은 데이터에 담긴 암호를 안전하게 송수신시키기 위해 추가적인 보안계층이 필요하다는 것이다. 반면에 A와 B가 각자 공개키와 개인키를 갖고 있으며 서로의 공개키는 알지만 개인키는 비밀인 상황에서, A가 B에게 데이터를 송신했을 때 B의 공개키를 사용하여 암호를 설정하고, B는 자신의 공개키를 사용하여 암호를 푸는데 이것이 비대칭 암호화이다. 이 비대칭 암호화의 가장 큰 단점은 공개키 암호화 시 여러 연산 때문에 높은 컴퓨팅 능력이 필요하며 현재까지는 대규모 데이터를 전송하는 기술이 개발되지 않았다.

• 확장성

영지식 스타크는 영지식 스나크에 비해 더 높은 확장성을 제공한다. 영지식 증명은 당사자 간의 거래를 위한 통신, 영지식 증명의 검증 등의 복잡성에 따라 더 높은 연산처리능력이 요구된다. 영지식 스나크의 경우, 복잡성이 증가할수록 점점 더 높은 연산처리능력이 필요한 반면에 영지식 스타크는 복잡성이 증가하더라도 연산처리능력의 변동이 거의 없다. 암호화 방식에 차이가 있기 때문이다. 결론적으로, 영지식 증명의 복잡성 증가에도 연산능력에 큰 영향이 없는 영지식 스타크가 영지식 스나크보다 빠르며 따라서 확장성 측면에도 더 우월하다.

영지식 스나크에서는 증명 데이터와 검증 과정이 획기적으로 간결해졌지만 증명자가 증명을 생성하는 시간이 매우 느리다는 문제점이 있다. 영지식 스타크 논문에 따르면 해당 증명 생성 작업은 오른쪽 그래프와 같이 빨라진다고 한다. y축이 증명 생성 시간이며 x측은 문제의 복잡성이다. 그래프에서 알 수 있는 것은 영지식 스타크(초록색 그래프)의 증명 생성 시간이 영지식 스나크(파란색 그래프)에 비해 빠르다는 것이다.

• 양자컴퓨터 저항성

영지식 스나크는 ECDSA와 같은 키페어 알고리즘에 기반하지 않기 때문에 이론적으로 양자 컴퓨터 공격에 매우 취약하다고 알려져 있다. 소인수분해를 빠르게 처리할 수 있는 양자 알고리즘인 쇼어 알고리즘(Shor’s Algorithm)의 방식을 통해 공개키로부터 비밀키를 추출해 낼 수 있기 때문이다. 또한 타원곡선암호 기법으로 암호화를 하기 때문에 연산능력이 뛰어난 양자컴퓨터로 그 암호를 빠르게 해독하여 무기력할 가능성이 있다.

반면에 영지식 스타크는 타원곡선암호화 방식이 아닌 해시함수를 통한 비대칭 암호화 방식을 사용하기 때문에 연산능력에 자유로울 수 있어 양자컴퓨터에 저항성을 가진다.

활용

스타크웨어(STARKWARE)는 영지식 스타크를 활용하여 사용자의 자산을 보관하지 않는 거래소(Non-custodial Exchange) 솔루션을 개발하고 있으며 현재 제로엑스 프로토콜(0x protocol)과 긴밀하게 협력하고 있다. 또한 예측마켓 프로토콜로 잘 알려져 있는 노시스(Gnosis)에서도 디퓨젼(dFusion)이라는 탈중앙화 거래소(DEX)를 개발 중에 있는데, 이 역시 영지식 스타크를 활용하여 탈중앙화 거래소의 낮은 거래 속도를 개선하고자 시작된 프로젝트이다.