VDF를 이용한 난수생성 — 2
Wesolowski and Pietrzak’s VDFs
Author
Suhyeon Lee (Security researcher, Tokamak Network)
Random Number on Blockchain Using VDF Series
1. An Introduction to Verifiable Delay Functions
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs (v)
3. Random Number Game: Commit-Reveal-Recover Using VDFs
Introduction
이전 아티클에서는 VDF 함수의 개념에 대해서 소개했습니다. 다시 간단하게 정리하자면, VDF는 특정 연산을 수행하는데 정해진 시간을 소모하도록 보장하며 이 결과를 빠르게 검증할 수 있는 함수입니다. 이러한 특성이 VDF는 블록체인에서 안전한 난수생성을 위해 사용될 수 있다는 점을 강조드렸습니다.
그러나, 우리가 소개했던 simple VDF의 한계는 명확했습니다: simple VDF는 검증자가 Proof-of-Exponentiation (PoE)를 위한 비밀값에 접근할 수 있어야만 검증을 수행할 수 있다는 점이고 이는 투명하고 탈중앙화된 환경에서 실용적이지 않습니다.
이 부분에서 Wesolowski 와 Pietrzak 이 각각 제안했던 VDF가 필요합니다. 두 연구자가 제안한 VDF 둘 모두 비밀값에 대한 지식 없이도 누구나 VDF연산 결과를 검증할 수 있습니다. 그래서 이 아티클에서 우리는 그들의 VDF가 어떻게 Proof-of-Exponentiation을 다루는지 초점을 맞추어 살펴보겠습니다.
VDF에 대한 기초적인 내용에 대한 이해가 필요한 분은, 여기서 이 시리즈의 첫번째 아티클을 읽고 오시면 이번 내용을 이해하는데 도움이 될 것입니다. 그리고 소개드릴 내용의 수학적인 함의와 한계에 대해서 정확하고 자세히 이해하고 싶은 분들은 Wesolowski와 Peitrazak의 논문 원문 [1, 2] 그리고 두 함수에 대한 수학적 분석을 담은 Dan Boneh의 논문[3] 을 참고하시면 좋을 것 같습니다.
설명드리기에 앞서, 핵심 두 VDF 모델을 관통하는 통찰은 검증자에 대한 챌린지(challenge)입니다. 이를 통해 비밀값 없이도 견고한 검증 프로세스를 수행할 수 있습니다. 또한, 두 VDF의 interactive 모델을 설명하지만, 두 함수 모두 Fiat-Shamir heuristic이라는 기법을 통해 non-interactive하게 구성이 가능합니다. 하지만, 이 아티클에서는 이에 대해서는 다루지 않습니다. 이러한 맥락에서, 이제부터 Wesolowski와 Pietrzak의 VDF에 대해 설명해보겠습니다!
Wesolowski’s Approach: A Prime Number Challenge
아래 그림은 Wesolowski VDF가 어떻게 동작하는지 보여주고 있습니다. 핵심 단게는 소수(prime number) l 을 이용한 챌린지입니다. 검증자(prover)는 증명자(verifier)에게 VDF수행값에 의존하는 소수를 골라서 챌린지를 합니다. 검증자는 이 소수를 적절한 증명(proof)을 구성하기 위한 나눗셈에 사용합니다. 그리고 나서, 검증자는 그렇게 구성된 증명을 효율적으로 검증할 수 있습니다.
The Wesolowski’s VDF in Detail:
Value Check:
- 시작에 앞서, 검증자는 입력값(g, h)이 사전에 약속된 군(group) G에 속하는지 확인합니다.
- 그렇지 않다면, 검증을 멈추고 프로토콜을 중단합니다.
Random Prime Challenge:
- 검증자는 임의의 난수(l)를 선택하여 증명자에게 보냅니다.
Prover’s Response:
- 증명자는 전달받은 소수를 이용해 2^T =ql+r를 만족하는 q와 r을 계산합니다.
- 증명자는 증명값인 π = g^q 를 계산해 검증자에게보냅니다.
Final Verification:
- 검증자는 r = 2^T mod l 을 만족하는 r을 계산합니다.
- 만약 π 가 그룹 G 의 원소이며 h=π^l × g^r 가 성립한다면, 검증자는 VDF 검증이 성공적으로 수행되었다고 판단합니다.
요약하자면, Wesolowski VDF는 소수를 이용한 챌린지를 통해 VDF 수행결과를 검증할 수 있습니다. 이 스킴은 뒤에서 소개할 Pietrzak VDF보다 상대적으로 짧고 간결합니다. 그러나, 이러한 구성이 Wesolowski VDF가 Pietrzak VDF보다 효율적일 것이라 보장하지는 않습니다. 첫째로, 블록체인 상에서 구현시 소수를 찾는 hash-to-prime 함수가 기본적으로 제공되지 않아 이에 대한 구현이 고려되어야 합니다. 두번째로, 두 VDF의 구현에 다룬 연구에서는 Wesolowski VDF가 상대적으로 속도 측면에서 유리하지 않다는 결과를 보여줍니다.
Pietrzak’s Approach: Halving Protocol
아래 그림은 Pietrzak VDF의 일부가 어떻게 동작하는지 보여줍니다. 그리고 이는 halving protocol (번역을 시도하자면, 반으로 나누는 프로토콜) 이라고 불립니다. 이 프로토콜에서 검증자와 증명자는 지수연산의 규모를 절반씩 줄여나가는 작업을 반복합니다. 특히, VDF 연산에서의 시간 관련 인자 T가 1이 될 때까지 이 작업을 반복합니다. 결과적으로 T가 1인 상황에서, 검증자는 Proof-of-Exponentiation 검증작업을 단순 제곱 연산으로 확인할 수 있게 됩니다.
The Pietrzak’s VDF in Detail:
Pietrzak 은 VDF 검증 문제를 여러 층으로 구성하는 접근을 하였습니다. 이 프로토콜은 (G, g, h, T) 튜플을 입력으로 하여 동작합니다:
# Halving procotol for T > 1
Prover’s Computation:
- 증명자는 v = g(2^(T/2)) 를 연산하여 검증자에게 보낸다
Verifier’s Initial Check:
- 검증자는 랜덤값 r을 챌린지 값으로 생성하여 보낸다
Next Input Calculation and Repeat:
- 검증자, 증명자 양쪽은 다음을 계산한다: g1 = g^r v and ℎ1 = v^r h
- 결과적으로 검증자와 증명자는 얻은 튜플인 (G, g1 ,h1 ,T/2) 를 이용해 다음 halving protocol을 반복해 수행할 수 있게 된다. VDF가 올바르게 수행하였다면 다음이 성립하는 관계를 가진다: ℎ1= g1(2^(T/2)) within group G.
# Halving procotol for T =1
마침내, T 가 1에 도달하면, 검증자는 ℎ ≟ g² 을 확인하여 등호가 성립하면 VDF가 올바르게 수행되었다 판단하여 프로토콜을 종료한다.
정리하자면, Pietrzak의 메커니즘은 Proof-of-Exponentiation을 반으로 나누는 작업을 반복하여 검증하는 접근을 사용한다. 그렇기에 이 과정은 log₂T만큼 반복되어야 하며 증명의 길이 역시 log₂T 가 된다. 한 개의 증명을 단 한 번 보내는 Wesolowski의 접근과 비교하자면 상당히 길다. 그러나, 후술할 구현에 대한 실험결과와 hash-to-prime 함수와 같은 상당한 연산을 요구하는 메커니즘이 필요없다는 사실을 고려하면 블록체인에서 실용적으로 고려될 수 있다.
Performance Comparison
앞서 언급한 메커니즘에 대한 정보는 어떤 VDF가 더 효율적이고 실용적인지 직접적으로 보여주지는 않습니다. 물론, 장단점이 있습니다. 여기서 한가지, 우리가 고려해야 할 한 가지 중요한 측면이 있다면 성능이라고 생각합니다. Attias et al., “Implementation Study of Two Verifiable Delay Functions,” Tokenomics 2020의 연구 결과를 정리하면, 아래 표와 같이 두 VDF를 비교할 수 있습니다:
테이블에서 t 는 시간 매개 변수, λ 는 보안 수준에 대한 변수, 그리고 s 는 CPU 연산 코어의 개수를 의미합니다. VDF를 수행하는데 병렬연산은 불가능하지만 연산결과에 대한 증명을 생성하는 일부 연산에 대해서는 병렬연산이 적용가능하기 때문입니다. λ = 2048인 경우 RSA 2048 수준을 의미해 현재 기준 충분한 보안수준을 제공하는 경우를 뜻합니다. 그래서 저는 VDF를 단순히 수식적인 측면이 아니라 특정 보안수준에서 비교해보았습니다. 요약하자면 Pietrazak VDF는 증거 생성 및 검증작업에 더 유리합니다. 하지만, Pietrazak VDF는 훨씬 더 긴 증명의 길이를 가져 분산 네트워크에 부담이 될 수 있다는 점을 고려해야합니다.
Concluding Remarks on Assumptions and Open Problems
마무리하기 전에, VDF 메커니즘은 다양한 수학과 암호화 가정에 의존한다는 점을 강조하고 싶습니다. 특히, 두가지 중요 가정이 있습니다. 첫 번째는 RSW (Rivest, Shamir, Wagner) assumption 입니다. 이에 대해서는 이전 아티클에서 설명되어 있습니다. 두번째는, 이를 Fiat-Shamir heuristic을 통해 non-interactive하게 구현할 시 우리는 Random oracle model에 의존하게 됩니다.
추가적으로, 군 Group G 를 구성하는 방법에 대해 논의를 별로 하지 않았지만 사실 이 부분이 아주 어려운 부분입니다. 검증자가 군의 비밀값을 모른다고 해도 검증할 수 있다고 하였지만 누군가는 비밀값을 통해 군을 구성해줘야 하지 않을까요? 그래서 연구자들은 위수(order)를 모르는 그룹을 구성하는 방법을 연구하고 있습니다. 이 문제는 굉장히 수학적으로 복잡하지만 관심이 있다면 아래에 제시된 참고문헌을 통해 알아보시기를 추천드립니다.
Acknowledgement
이 글은 토카막 네트워크의 연구개발 노력의 일환으로 작성되었습니다. 토카막 네트워크는 최선을 다해 블록체인 기술에 기여하기 위해 노력하고 있습니다.
Reference
[1] B. Wesolowski. “Efficient verifiable delay functions.” Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer International Publishing, 2019.
[2] K. Pietrzak. “Simple verifiable delay functions.” 10th innovations in theoretical computer science conference (itcs 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[3] D. Boneh, B. Bünz, and B. Fisch. “A survey of two verifiable delay functions.” Cryptology ePrint Archive (2018).
[4] Attias et al., “Implementation Study of Two Verifiable Delay Functions,” Tokenomics 2020
