VDF를 이용한 난수생성 — 1
An Introduction to Verifiable Delay Functions
Author
Suhyeon Lee (Security researcher, Tokamak Network)
Reviewed by Jake Jang and Jamie Judd
Random Number on Blockchain Using VDF Series
1. An Introduction to Verifiable Delay Functions (v)
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs
3. Random Number Game: Commit-Reveal-Recover Using VDFs
Introduction
암호화폐의 기반이 되는 기술인 블록체인은 탈중앙화된 환경에서 신뢰와 공정성을 보장하기 위한 알고리즘을 기반으로 발전하였습니다. 블록체인 프로세스의 타이밍과 검증 가능성의 중요성과 함께 VDF(Verifiable Delay Functions)는 중요한 암호 기술로 부상했습니다. VDF에서는 특정 연산이 일정 시간 이상 걸리도록 강제하며 효율적으로 검증 가능하도록 보장하는 특성이 있습니다.
그렇다면 VDF가 중요한 이유는 무엇일까요? 연산자가 가진 자원(예를 들어, 컴퓨팅 파워)에 관계없이 특정 프로세스가 일정 시간 지속되도록 보장합니다. 이를 이용하면 에너지 소비가 많다는 이유로 많은 비판을 받는 작업증명(PoW) 시스템을 보다 효율적인 지연증명(PoD)으로 대체하여 블록체인 마이닝의 환경적 영향을 줄일 수 있다는 연구도 있습니다. 순차 계산을 사용하는 VDF를 이용하면 블록 제안자가 되기 위해 경쟁할 때, 거대한 병렬 계산 능력이 필요하지 않습니다. 또한 마이닝 풀을 만들 필요도 없습니다.
다시 말하자면, VDF는 결과가 나올 때까지 시간을 지연시킵니다. 즉, 아무도 ‘미리’ 알 수 없는 값을 만들고 싶을 때 VDF를 사용할 수 있습니다. 이와 관련하여, 블록체인에서 VDF의 또 다른 핵심 응용 프로그램은 안전한 난수(random number) 생성으로, 복권과 같은 간단한 앱에서부터 합의 메커니즘에 이르는 활동에 필수적입니다.
A Glimpse into Random Number Generation using VDFs
검증 가능한 지연(delay)과 난수 생성이 어떻게 연관되었을까요? 물론 지연 자체가 난수를 직접 생성하지 않습니다. 따라서 검증 가능한 지연은 난수를 안전하게 생성할 수 있습니다. 이 글에서 아직 VDF가 어떻게 작동하는지 다루지 않았지만 일단 참여자들에게 지연된 연산결과를 강제하는 VDF가 존재한다 가정해보겠습니다.
분산시스템에서 난수를 생성하는 한 가지 방법은 Commit-Reveal 게임입니다. 이 게임을 간단히 설명하면 다음과 같습니다: 참여자들은 먼저 난수(혹은 비밀 값)을 생성하고 해시함수와 같은 안전한 단방향 함수로 처리해 제출합니다 (Commit). 모두 값 제출을 끝났다면, 참여자들은 원래 비밀로 하고 있던 값을 공개합니다(Reveal). 참여자들은 간단히 해시함수로 공개된 값이 원래 비밀로 하던 값과 같은지 확인을 할 수 있어 거짓말을 할 수 없습니다. 마지막으로, 참여자들은 값의 검증이 끝났다면 모든 공개된 비밀 값을 같이 해시하여 난수를 생성할 수 있습니다.
그러나, 어떤 참여자가 비밀값을 공개하지 않으면 어떻게 될까요? 최종적으로 구하려고 했던 난수가 생성되지 않습니다. 하지만 참여자의 비밀값을 확인할 수 있는 VDF 함수가 있다면 어떻게 달라질까요? 그러면 우리는 참여자들이 비밀값을 공개할지 기다리다가 끝내 공개하지 않을 경우 VDF를 이용해 비밀값을 밝혀낼 수 있습니다. 그리고 이 방법에 VDF가 활용되기 때문에 공개할때까지 기다리는 시간 동안 VDF 를 연산할 수 없도록 지연되도록 VDF를 사전에 설정해 목표하던 안전한 난수 생성을 할 수 있습니다.
이러한 맥랙에서, 이 아티클 시리즈에서는 블록체인에서의 안전한 난수생성을 위한 VDF를 사용하는 개념에 대해 알아보겠습니다. 이 시리즈는 최종적으로 Commit-Reveal-Recover 스킴에 VDF를 이용해 안전한 난수를 어떻게 생성할 수 있는지 설명하는 것을 목표로 합니다. VDF에 관련된 기술적, 수학적 맥락에 익숙하지 않은 사람들이 있기 때문에, 이번 글에서는 VDF의 선구자격인 time-lock puzzle의 개념을 다시 살펴보며 VDF의 개념에 대해 살펴보겠습니다.
Hint to VDFs: Time-Lock Puzzles using Hash Chains
Time-lock puzzle 이란 “Time-Lock Puzzles and Timed-Release Crypto” by Rivest, Shamir, and Wagner 에서 소개된 개념으로 엄격하게 연산시간에 지연을 가지는 퍼즐을 말합니다 [1].
hash(x) → hash(hash(x)) → hash(hash(hash(x))) → …
예를 들어, 위처럼 당신이 중첩된 해시 연산을 수행해야한다고 해보겠습니다. 이것이 수십 수백번이면 별로 문제가 되지 않겠지만 백만 번의 해시연산이면 어떨까요? 이것은 해시연산이기에 병렬적 연산으로 해결하기 힘들고 순차적으로 연산해야 합니다. 이러한 수학적 퍼즐은 엄청난 시간 소모를 강제합니다. 하지만, 빠르게 검증하기는 힘듭니다. 실용적인 퍼즐을 구성하기 위해서는, VDF는 시간을 지연하는(time-lock) 메커니즘 뿐만 아니라 효율적인 검증 메커니즘을 요구합니다. 그러므로, VDF는 필수적으로 다음과 같은 메커니즘이 필요합니다:
- 지연(Delay): 병렬적으로 연산될 수 없는 순차연산 함수
- 검증가능성(Verifiability): VDF 연산이 옳게 되었는지 검증하는 효율적임 함수
Bridging to VDFs: Enforcing Time and Ensuring Swift Verification
VDF는 이러한 아이디어(특정 시간이 소요되는 계산 집약적인 작업과 연산결과를 효율적으로 검증할 수 있는 증명을 제공함) 위에서 구성할 수 있습니다. 이를 설명을 위해서 RSA 암호에 기반한 아주 단순한 VDF를 사용하는 검증자(Verifier)와 증명자(Prover)의 상호작용을 예로 들어보겠습니다.
SetUp (Verifier):
- 두 개의 큰 소수인 p 와 q 를 선택 후, n = p × q, 를 연산하고 n을 Prover에게 공개
- 검증자에게 다음의 연산을 질의: y = g^(2^t) mod n.
Computation (Prover’s Challenge):
- y 를 연산하는 것은 p와 q를 알지 못하고는 효율적으로 수행하기 매우 어려움
- 따라서, 다음과 같은 순차연산을 수행할 수 밖에 없음
g² = g×g → g⁴ = g² × g² → g⁸ = g⁴ × g⁴ → … t interation … → y
- 이러한 연산의 과정은 RSW 가정을 따름
Ref. The RSW Assumption
A critical contemplation is the RSW (Rivest, Shamir, Wagner) assumption, propounding that evaluating y = g^(2^t) mod n mandates t sequential squaring operations and cannot be expedited significantly, serving as a keystone in both mechanisms.
Verification (Verifier’s Check):
- p, q를 알고 있다면 ϕ(n), Euler’s totient function ϕ(n) (이 경우 (p-1)×(q-1)) 를 이용해 순차연산을 피해 매우 효율적으로 검증자의 연산결과를 검증할 수 있음
- 오일러의 정리(Euler’s theorem)에 따라 g^(2^t) ≡ g^(2^t mod ϕ(n)) mod n
Ref. Euler’s theorem. a^ϕ(n) ≡ 1 mod n
where ϕ(n) is Euler’s totient function, this theorem lays fundamental in number theory and cryptographic applications, permitting efficient modular exponentiation calculations.
What Lies Ahead: Towards Practical VDF Mechanisms
안타깝게도, 위에서 설명한 간단한 VDF는 실용적이지 않습니다. 왜냐하면, 효율적 검증을 위해서는 오일러 정리를 이용하기 위한 비밀값인 소수들이 필요하기 때문입니다. 좀 더 수학적으로 설명하자면, (Z/nZ)로 표현되는 integer multiplicative group 에서는 그룹의 위수(order)가 Euler’s totient function 의 결과값이 됩니다. 검증자는 그룹의 위수를 알아야면 VDF 결과값을 효율적으로 검증할 수 있다는 뜻입니다. 그렇다면, 우리는 VDF가 실용적이기 위한 핵심 요구사항을 하나 생각해볼 수 있겠죠.
- VDF 연산 결과를 어떠한 비밀값에 대한 지식 없이 효율적으로 검증할 수 있는 메커니즘이 존재한다
이 조건이 만족된다면 누구나 검증자의 역할을 수행할 수 있습니다. 더욱이, 참여자 누구도 비밀값을 모르는 상태에서 VDF 를 이용한 이벤트를 수행할 수 있게 되었습니다.
이 시리즈의 다음 편에서는 VDF의 고급 메커니즘, 특히 Wesolowski와 Pietrzak이 설명한 메커니즘을 통해 VDF의 암호학적 영역에 대해 자세히 알아보고, 그 다음 편에서 블록체인에서 난수 생성을 위한 Commit-Reveal-Recover 체계를 소개할 예정입니다.
Acknowledgement
이 글은 토카막 네트워크의 연구개발 노력의 일환으로 작성되었습니다. 토카막 네트워크는 최선을 다해 블록체인 기술에 기여하기 위해 노력하고 있습니다.
Reference
1. R. L. Rivest, A. Shamir, and D. A. Wagner, “Time-lock puzzles and timed-release Crypto,” 1996. [Online]. Available: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf.
