[ZK-STARK series] #01 The Birth of STARK
서울대학교 블록체인 학회 디사이퍼(Decipher) ZK-STARK 팀에서 영지식 증명 및 그 활용에 대한 글을 시리즈로 연재합니다. 본 시리즈에서는 논문에 나온 의미를 그대로 전달하려다 보니 글 중간중간 영어가 많이 섞여 나올 수 있습니다.
본 게시글은 ZK-STARK 에 대해 분석한 시리즈 중 1편입니다. 이번 편에선 STARK만의 내러티브와 다른 ZK 기술들과의 차별점에 중점을 두어 분석합니다.
목차
- Starkware 의 등장 배경
- PCP-Theorem
- 다양한 ZK 솔루션들
- ZK-STARK 의 차별점
Starkware 의 등장 배경
Starkware 는 현재의 ZK-STARK 메인넷을 만들고 있는 회사로 Eli Ben-Sasson 이 2018년에 창업한 회사입니다. Starkware CEO 는 초기 ZK 기술인 ZCash 설립자 중 한명이었는데, 현재는 스타크넷을 따로 만들고 있습니다. ZK-STARK 를 통해 무엇을 차별화시키고 싶었던 걸까요? 이번 단락에서는 Starkware 의 등장 배경을 살펴보면서 풀고자 했던 문제와 접근 방식이 다른 회사와 어떻게 달랐는지를 알아보고자 합니다.
ZK (Zero-Knowledge) 에 관한 논의는 블록체인이 탄생하기 훨씬 전부터 암호학계에서 활발히 논의되고 있던 주제입니다. 아래의 직관적인 예시를 통해 어떠한 문제가 있었고, 어떻게 논의되어 왔는지 살펴보도록 하겠습니다.
경찰만 접근할 수 있는 비밀로 유지되어야 하는 DNA 장부가 있습니다. 현재 대통령 후보가 범죄에 연루되었는데 장부에 등록되어 있는 DNA 와 범죄자의 DNA 가 일치하는지 검사해야 합니다. 하지만, 경찰은 대통령 후보자의 DNA 가 장부에 등록되어 있지 않다고 대답합니다.
위와 같은 상황을 마주하게 된다면 크게 2가지 문제가 떠오를 것입니다.
Q1. 경찰이 대답한 답을 어떻게 믿을까요?
가장 간단한 방법은 DNA 장부를 대중들이 원할 때 다 보여주는 것입니다. 대중들이 DNA 장부를 하나씩 살펴봄으로써 경찰들의 답을 검증할 수 있기 때문입니다. 이 방식을 Naive Replay 라고 합니다.
다음으로, 현실에서 가장 많이 쓰는 방법은 우리가 믿을만한 사람(Auditor) 에게 권한을 위임하고 그 사람들이 검증하게 하는 것입니다. 이 방식을 Delegation of Accountability 라고 합니다. 예컨대, 대중들이 검사에게 수사의뢰를 함으로써 검사가 DNA 장부를 대신 넘겨받아 검증해주는 방식이 있습니다.
하지만, 위 두가지 방식 모두 두 번째 문제에서 자유롭지 못합니다.
Q2. 대통령 후보자의 Privacy를 어떻게 유지하며, 이 방식은 충분히 Scalable 한가?
Naive Replay 의 경우, 모든 사람이 DNA 장부에 접근할 수 있으므로 privacy 는 전혀 지켜지지 못할 뿐더러, 모든 사람이 수긍하려면 모두가 데이터셋을 보고 검증할 때까지 기다려야하기 때문에매우 비효율 적입니다.
Delegation of Accountability 의 경우에, 평판이 좋은 몇명의 Auditor에게 권한을 위임함으로써 데이터셋을 보는 사람의 수가 많이 줄어들게 됩니다. 따라서 Naive Replay 의 경우보단 전체적으로 훨씬 효율적이지만, 아직도 Auditor 가 전체 데이터셋을 봐야한다는 점에서 privacy 와 scalability 가 완전하게 이뤄질 수 없습니다.
이제 위 문제를 프로그램의 관점으로 치환해서 생각해봅시다.
DNA 장부를 dataset(D),
DNA 장부를 검증하는 과정을 computation (C : callable) 이라고 생각할 수 있습니다.
이 때, 컴퓨터가 계산과정을 거쳐서 반환하는 값이 P 라고 할 때,
P = C(D) 라고 확신할 수 있겠냐는 것입니다.이렇게 컴퓨터가 아무도 보지 않아도 옳은 값을 낸다고 확신할 수 있는 것을 ‘Computational Integrity (CI)’ 라고 합니다.
결론적으로, Starkware 는 Computational Integrity 를 confidential한 Dataset 에서도 확장가능하고, 투명하고, 양자컴퓨터에서도 안전한 방식으로 만들고 싶었습니다. 실제로 Starkware의 첫 논문의 제목도 ‘Scalable, transparent, and post-quantum secure computational integrity’ 이었습니다.
하지만 이러한 논의를 Starkware 가 처음으로 시작한 것은 아니었습니다. 모든 ZK 시스템은 증명을 생성하는 데 사용하는 알고리즘과 생성된 증명을 검증하는 알고리즘으로 이루어져 있는데 아래와 같은 성질을 만족시키고자 하였습니다.
- Completeness (완전성) : prover 가 옳게 생성한 증명을 verifier 가 맞다고 받아들일 확률이 1에 가까워야 한다.
- Soundness (무결성) : prover 가 틀리게 생성한 증명을 verifier 가 실수로 맞다고 받아들일 확률이 0에 가까워야 한다.
암호학계에서는 1990년대 초반에 나온 PCP (Probabilistically Checkable Proofs) Theorem 덕분에 위 목표에 대해 프로그램이 최종적으로 어떠한 것을이뤄야 하는지 증명되었습니다. 따라서 이 PCP 정리는 비단 Starkware 뿐만 아니라, 모든 ZK 기술에 단초가 된 이론이라고 볼 수 있고, 이를 먼저 이해한다면 등장 배경과 발전 과정에 대해 훨씬 깊은 이해를 할 수 있습니다.
PCP Theorem
PCP Class는 ZK 시스템에서 verifier 가 증명을 검증하는 알고리즘이 어떠한 성질을 만족해야 하는지 보여줍니다. verifier 가 생성된 증명을 검증하기 위해서는 전체 데이터셋 중에 몇개를 랜덤으로 볼 것이냐 하는 randomize complexity 와 이 정보를 선택하는 데 걸리는 query complexity 2가지를 속성으로 가지고 있습니다.
따라서 PC 클래스는 PCP(randomize_complexity, query_complexity) 로 정의할 수 있습니다. 이 때, PCP 정리는 아래와 같습니다.
여기서 NP 는 해당 문제의 답이 주어졌을 때, 그 답을 알고리즘을 통해 다항식의 시간 복잡도 안에서 검증할 수 있는 문제 집단입니다. 이를 ZK 기술에 대입해서 생각해보면 prover 에 의해 생성된 증명이 데이터에 대한 답이 되고, verifier 가 사용하는 알고리즘이 NP 군이면 다항식 시간 내에 검증할 수 있다는 것입니다. 다항식 시간 복잡도가 중요한 이유는 현실 세계에서 Scalable 하게 돌아갈 수 있는 마지노선이기 때문입니다.
따라서 ZK 시스템이 실현 가능하려면 verifier가 증명을 검증하는 데 사용하는 알고리즘이 NP군이 되어야 합니다. 즉, 전체 데이터셋 n개 중 log n 개의 랜덤한 데이터만 추출해서 봐야하고, 각각의 쿼리를 날리는 데에 상수 시간 복잡도가 걸려야 합니다.
PCP(log n, 1) 이 NP 군에 속한다는 한쪽 방향만 증명하면 verifier 의 알고리즘이 최소한 만족해야 하는 것이 무엇인지 알 수 있기 때문에 이번 글에서는 아래 보조정리를 통해 한쪽 방향만 증명하도록 하겠습니다.
여기서 NTIME(T(n)) 은 특정 컴퓨터에 해당 문제의 결과가 주어졌을 때, 그 결과를 T(n) 복잡도에 검증할 수 있는 문제 집단입니다. 위에 등장했던 NP의 개념과 연관지어 생각해보면 NTIME(다항식) 이 NP인 셈입니다.
ZK 이론을 처음 접할 때 자주 드는 ‘Alibaba Cave’ 예시를 생각해보면 위 보조정리를 직관적으로 이해할 수 있습니다.
동굴 안의 prover 는 동굴 밖에서 기다리고 있는 verifer 에게 동굴 키를 공개하지 않고, 자신이 동굴 키를 안다는 것을 어떻게 증명할 수 있을까요?
Answer : prover 가 동굴 키를 안다면 어디로 들어가든 매번 verifier 가 요청한 출구로 나올 수 있습니다. (들어간 곳으로 돌아나오거나, 동굴 키를 통해 열고 나오거나) 따라서 이에 대한 검증을 수행하면 됩니다.
다시 PCP 보조정리로 돌아오면, 전체 데이터셋 n 개 중 우리는 랜덤으로 r(n) 개를 선택합니다. prover가 r(n) 개에 대해 생성한답을 verifier가 확인하려면 2^(r(n)) 가지 경우를 모두 살펴봐야 합니다. 따라서 살펴보는 매 과정마다 쿼리를 날리는 복잡도인 q(n) 을 곱해주면 verifier 가 이 문제를 검증하는데 O(2^(r(n)) * q(n)) 시간이 걸린다는 것이 나옵니다. 따라서 앞서 설명한 NTIME() 의 의미를 생각해보면 보조정리가 이미 증명된 것입니다.
이제 이 보조정리를 활용하면, PCP(log n, 1) 은 NTIME(n) 에 속한다는 것이 나옵니다. 또한 n은 다항식이므로 NTIME(n)은 NP이고, PCP(log n, 1)이 NP군에 속한다는 PCP 정리의 한쪽 방향이 증명되었습니다.
이 PCP 정리가 시사하는 점을 다시 한 번 살펴볼 필요가 있습니다. 처음에 살펴봤던 Naive Replay 와 Delegation of Accountability 방식 모두 verifier 의 수만 다를 뿐, 각각의 verifier 가 모든 데이터셋을 살펴보아야 합니다. 따라서 randomize complexity 가 O(n) 인 셈이고, 보조정리에 의해 이 방식으로 검증하는 것은 지수 시간 복잡도가 필요합니다. 이는 현실 세계에서 완벽히 검증하기 불가능하다는 의미이고, 위 두 방식 모두 애초부터 privacy를 보호하지 못할 뿐더러 Scalable 하지도 않았다는 것입니다.
하지만, PCP 정리를 만족하는 verifier 알고리즘은 확장가능할 뿐만 아니라 전체 데이터셋을 다 보지 않으니 privacy 도 지켜집니다. 이 성질을 “Verifier Scalability” 라고 하고, ZK 기술에서는 “Succint” 라는 용어로 자주 대표되는 것을 볼 수 있습니다.
Succint 한 ZK-PCP 는 매우 많은 장점이 있습니다.
- Transparency : 과정이 명확하여 제 3의 trusted 집단에 의존하지 않는다.
- Universality : 효율적인 Computation 과정(O(poly(n)) 이라면 모두 적용될 수 있다.
- Confidentiality : privacy 가 보장된다.
- Post-quantum Security
- Argument of Knowledge : prover 가 자신이 맞다는 것을 확신시키는 과정이다.
- Scalable Verification
암호학계에서는 이러한 장점들을 누리기 위해 1990년대부터 활발한 논의가 이어져왔지만, 코드로 실현시키기 매우 어려웠습니다.
이러한 논의가 2010년대부터 다시 데이터가 모두에게 공개된 블록체인의 특성과 잘 결부되어 ZK-STARK 를 포함한 여러 솔루션들이 등장하고 있습니다. ZK proof 를 통해 데이터의 privacy를 해결하고, 다음 블록을 생성하려면 이전 거래들을 검증해야 하기 때문에 확장성이 떨어지는 문제를 ZK-Rollup 을 통해 해결하고자 합니다.
다양한 ZK 솔루션들 (ZK-SNARK, Bulletproof)
STARK 의 특징을 보기 전에, 다른 ZK 솔루션들의 특징들도 간단히 살펴봄으로써 STARK 가 집중하고 싶었던 문제를 다시 한 번 환기시키고자 합니다.
처음에 말했듯이 Starkware 의 창업자는 원래 ZCash 창업자 중 한명이었습니다. ZCash 는 STARK 와 더불어 가장 유명한 ZK 기술인 ZK-SNARK 를 구현하는 곳이었습니다. ZK-SNARK 는 “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge” 의 줄임말인데, 앞에서 살펴봤듯이 “Succint” 는 Verifier Scalability 를 의미합니다. “Argument of Knowledge” 도 prover 가 자신이 옳다고 verifier 를 확신시키는 검증과정을 거친다는 것을 의미합니다. 이 2가지는 ZK-PCP 에도 모두 공통되는 특징이고, ZK-STARK 와도 같습니다. 하지만, 여기서 집중해야 할 부분은 “Non-Interactive” 입니다.
“Non-Interactive” 즉, 비대화형 검증 방식을 거친다는 것입니다. prover 가 자신의 증명을 암호화해서 verifier 에게 전달하면 verifier 는 이것이 맞는지 검증하는 방식입니다. 서로 여러 번의 상호 작용을 거치지 않고, 딱 한 번에 끝나기 때문에 비대화형 검증인 것입니다.
한 번에 끝나기 때문에 prover 가 증명을 생성하는 과정이 굉장히 효율적이지만, 증명 생성 과정의 암호화 방식이 미리 세팅되어 있어야 한다는 한계가 있습니다. ZCash 는 여기서 원래 trusted-party 라는 제 3자를 이용했습니다. trusted-party 는 prover 가 증거를 생성하기 전에 prover와 verifier 각각에게 “Make a proof”, “Check a proof” 를 할 수 있는 재료를 제공해줍니다. 이 재료를 이용하여 높은 효율성으로 검증과정이 이루어질 수 있습니다. 하지만 우리는 trusted-party 가 옳은 재료만 제공해준다고 맹목적으로 믿어야 하기 때문에 블록체인 탈중앙화 가치를 감소시키고, ZK-PCP 의 장점 중 하나인 transparency 가 퇴색된다고 볼 수 있습니다.
이러한 한계를 해결하기 위해 trusted-party 를 사용하지 않는 Bulletproof 라는 새로운 솔루션도 제시되었지만, 반대급부로 검증 생성시간이 너무 증가해버려, 사용하기가 어려웠습니다. ZCash 에서도 trusted-party 를 사용하지 않는 Halo2 를 업데이트 하였는데, 여기서는 좀 더 효율적인 타원 곡선을 사용하는 방식으로 접근하였습니다. ZK-SNARK 는 타원 곡선의 수학적 성질을 이용해서 검증이 이루어지는데 여기서 사용되는 타원 곡선의 종류를 Pasta Curve 로 바꾼 것입니다.
ZK-SNARK 에서 타원곡선을 어떻게 사용하는 지 자세히 궁금하신 분들은 이 미디엄 시리즈를 참고하여 주시길 바랍니다.
ZK-STARK 의 차별점
그렇다면, ZK-STARK 는 위 솔루션들이랑 무엇이 다를까요?
ZK-STARK 도 줄임말을 풀어보면 다른 솔루션들과 어떤 것을 차별화 시키고 싶었는지 알 수 있습니다. “Zero-Knowledge Scalable Transparent ARgument of Knowledge” 입니다. SNARK 와 비교해보면 Succint 와 Scalable 은 같은 의미이고, Non-Interactive 와 Transparent 만 차이가 납니다.
굳이 Interactive 라는 단순한 반의어를 쓰지 않고, Transparent 를 사용하면서 ZK-SNARK 가 Non-Interactive 방식을 채택하면서 trusted-party 를 통해 잃게 된 transparency 의 특성을 강조한 것입니다. 즉, 대화형 ZK Proof 를 통해 효율성과 투명성 두 마리 토끼를 모두 잡고자 한 것입니다.
하지만, 기존의 Interactive(대화형) ZK proof 는 효율성 측면에서 한계가 있었습니다. 비대화형 증명은 딱 한번의 검증만 거치면 되었지만, 대화형은 말 그대로 매 라운드 PCP 과정을 반복하는 것입니다. 한 라운드의 과정을 살펴보면 prover 가 각 오라클마다 머클트리를 생성하고, prover의 메세지는 머클트리의 루트가 됩니다. verifier 는 랜덤으로 선택된 노드에 쿼리를 날리고 prover 는 이 쿼리에 답을 다시 리턴해서 머클트리에 추가됩니다. 위에서 잠깐 예로 들었던 알리바바 동굴 문제와 거의 같은 상황인 것입니다.
대화형 증명의 경우, 비대화형 증명과 다르게 prover 의 역할이 한 번만 증명을 생성하고 끝이 아니라 계속 verifier 와 상호작용하면서 머클 트리를 업데이트 해나가야 합니다. 즉, verifier 만 scalable 하다고 되는 것이 아니라 prover 의 속도도 특정 복잡도 안에서 이뤄져야 합니다.
이 특정 복잡도가 얼마인지는 STARK 의 창립자가 여러 논문을 통해 이론적으로 위와 같아야 한다고 증명하였습니다. 위에 식에서 T(n)은 전체 과정을 돌리는 데 필요한 컴퓨팅 시간입니다. 이 컴퓨팅 시간을 Tc라 했을 때, scalable 한 verifier 는 PCP 정리를 통해 log(Tc) 여야 함이 증명됐습니다. prover 가 걸리는 시간을 Tp, verifier 가 걸리는 시간을 Tv 라고 했을 때, Tp = O(Tc*Tv) 인 것입니다. 직관적으로 생각해보면, prover 는 매번 verifier가 검증할 때마다 이전 상태를 트리에 계속 업데이트를 해야하기 때문에 두 과정의 시간을 곱했다고 생각할 수 있겠습니다. 이 성질을 “quasi-linear” 라고 부릅니다.
이러한 조건을 만족하는 fully scalable 한 interactive system 을 이론적으로 STIK (Scalable Transparent IOP of Knowledge) 라고 했는데, 위에서 PCP 처럼 STIK 도 구현하기가 매우 어려웠습니다. 이 STIK 구현체가 바로 현재의 ZK-STARK 인 것입니다.
실제로 구현하기 위해 STARK는 위와 같은 과정을 거쳤는데 너무 이론이 복잡해 간단히 표현하자면, 컴퓨팅 과정에서의 단계를 매우 줄이는 산술화(Arithmetization) 에 집중하였습니다. 이 Arithmetization 과정이 무엇인지는 간단한 문제로 부록에서 설명하고 있습니다.
이렇게 이번 시리즈에서 ZK 기술의 등장배경부터 다른 솔루션들과 비교해 STARK의 차별점 및 주목한 부분들을 살펴보았습니다. 다음 시리즈에서는 STARK 에서 위 예시를 구체적으로 어떻게 이루려 했는지 STARK 만의 언어인 Cairo 의 특징들을 살펴볼 예정입니다.
Reference
