블록체인에서 VDF를 이용해 난수생성하기 — 3
Random Number Game: Commit-Reveal-Recover Using VDFs
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
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs
3. Random Number Game: Commit-Reveal-Recover Using VDFs (v)
Introduction
이번 글에서는 우리는 드디어 블록체인에서 안전하게 난수를 생성할 수 있는 한가지 방법인 Commit-Reveal-Recover에 대해 알아보게 된다. 만약, 이전의 글을 읽어보지 않았다면, 이전 시리즈를 읽어보기를 추천한다. 첫번째 글에서는 Verifiable Delay Function (VDF) 의 기초적인 개념에 대해 소개했고, 두번째 글에서는 실용적으로 사용가능한 두가지 VDF 함수가 어떻게 동작하는지 설명한다. 우리는 이렇게 소개된 VDF에 대한 이해를 기반으로 오늘 글을 다루고자 한다.
Recap: Commit-Reveal
우리는 이 시리즈의 첫번째 글에서 Ethereum Randao에도 사용되는 Commit-Reveal 스킴에 대해 이야기를 했었다. 이 메커니즘의 핵심은 참여자들이 비밀값을 생성하고 이 값을 hash 함수와 같은 일방향 함수를 사용해 처리한 값을 어떤 기한까지 제출한다. 이후, 참여자들은 원래 비밀값을 공개하여 고정된 비밀값을 조합해 간단히 수를 생성할 수 있다.
이 과정에서 간단하지만 치명적인 보안 문제가 존재한다. 마지막 참여자는 이익을 얻을 가능성이 있다. 만약 이를 통해 구성될 난수 혹은 심지어 이를 알 수 없다 할지라도 난수를 조합하는 행위가 자신에 이익에 도움이 되지 않는다면, 해당 참여자들은 단순히 비밀값을 공개하지 않을 수 있다.
이러한 행위를 방지하고자, 일부 Commit-Reveal 구현에서는 참여자에게 보증금(deposti)을 강제한다. 만약 참여자가 정해진 기한까지 비밀값을 공개하지 않을 경우 보증금을 삭감한다. 이러한 방지책에도 불구하고, 참여자는 여전히 비밀값을 공개하지 않을 수 있다. 이는 자살 공격이라고도 불리며 난수 생성을 막아버린다. 이러한 한계는 Commit-Reveal 의 확장버전인 Commit-Reveal-Recover 스킴에 대한 논의를 낳았다.
Commit-Reveal-Recover 를 이해하기 위해 지금부터 Bicorn-RX 라는 블록체인에서 사용가능하며 VDF를 이용한 최신 Commit-Reveal-Recover 의 구현 논문에 대해 살펴본다.
Commit-Reveal-Recover Example: Bicorn-RX
Bicorn-RX 는 Bicorn [1] 논문에서 제안하는 3가지 메커니즘 중 가장 실용적이라고 소개된 메커니즘이다. 여기서 실용적이라는 의미는 스마트 컨트랙트에서의 gas 비용이 아닌 communication 비용과 계산의 복잡성이 관여된 결과이다. 알고리즘의 구체적인 내용과 보안에 대한 수학적 증명은 논문 원문을 살펴보기를 권한다.
위 그림은 Bicorn-RX가 어떻게 동작하는지 간단하게 보여주고 있다:
Setup
군(group)과 군의 생성자(generator)를 생성한다. 그리고 나서 의도하는 지연값인 T를 설정해 h = g^(2^T) 를 연산한다. 이 h 값은 최종적으로 생성될 난수값을 복구하는데 핵심적인 역할을 수행한다. 참고로, Bicorn 논문에서는 low-order assumption 을 만족하기 위해 원소 1을 제거한 QR+ (Signed Quadratic Residue)를 군으로 사용하였다.
Commit
참여자들은 비밀값 a 를 생성하고, c = g^a 를 연산해 기한인 T1까지 제출한다.
Reveal
기한 T2까지, 참여자들은 원래 생성했던 비밀값인 a 를 공개한다. 낙관적(optimistic)으로 해결된 경우, 집단적으로 생성된 난수 값인 Ω 가 간단한 지수 연산을 통해 생성된다. 이때 공격자의 역연산을 방지하기 위해 b* 라는 값이 관여된다.
Recovery (Pessimistic case)
만약 어떤 한명의 참여자라도 기한 T2까지 비밀값을 공개하지 않을 경우, ‘생성되어야 했던’ 난수 값인 Ω 는 VDF를 연산을 수행함으로서 복구될 수 있다. 복구된 값과 함께 해당 VDF를 실제로 수행하였다는 증거값을 함께 제출해야한다. 요약하자면, Bicorn-RX는 참여자들이 낙관적인 경우 난수값을 생성하기 까지 두 번 값을 제출하기를 필요로 한다. 하지만 만약 그 누구도 비밀 값을 제출하지 않더라도, 공개되지 않은 비밀값을 통해 생성될 난수는 단 한 명의 정직한 참여자를 통해 복구될 수 있다. 또한, VDF를 사용하기 때문에, 연산에 시간은 소모될지라도 엄청난 컴퓨팅 파워를 필요로 하지도 않는다.
Open Problems
지금까지 3개의 시리즈를 통해, 우리는 Commit-Reveal-Recover 가 왜 블록체인에서 난수를 생성하는데 핵심적인 기술 중 하나인지, 여기서 VDF가 어떤 역할을 하는지, 그리고 실제로 블록체인에서 사용가능한 알고리즘은 어떻게 구성되는지까지 살펴보았다. 마지막으로, 우리는 몇가지 열린 문제를 소개하며 글을 마치고자 한다:
- 최적화 Optimization: 현재 VDF를 이용한 Commit-Reveal-Recover 스킴들은 한 번 혹은 두 번의 기한과 함께 동작한다. 이러한 설정은 난수의 즉각적인 생성을 지연시키므로 실제 블록체인 서비스에 실용적으로 사용되기 위해 이러한 시간 지연을 최소화시키는 것이 중요한 문제가 된다.
- 보상과 처벌 Reward and Punishment: 앞서 언급하였듯이 Commit-Reveal 에서는 참여자들이 보증금을 넣어두고 비밀값을 제 때 공개하지 않을 시에 보증금을 삭감하는 식으로 처벌을 하여 정직한 행동을 유도하였다. 그렇다면 Commit-Reveal-Recover에서는 이에 대해 어떻게 적용되어야 할까? Commit-Reveal 보다 고려할 점이 월등히 많은 문제이다. 예를 들어, VDF를 수행하여 난수값을 복구한 참여자에게는 얼마를 어떤 보상을 해줄 것인지도 고민이 필요하다.
- 시간 지연 조정 Time Delay Adjustment: 참여자들에게 VDF의 시간 지연은 모두 같지 않다. 그리고 CPU의 퍼포먼스가 시간에 따라 증가하며, 시간지연 T값에 대한 조정도 필요할 것이다. 이러한 조정은 CPU 혹은 VDF를 위해 제작된 ASIC 칩의 퍼포먼스 측정을 얼마나 정확하게 하는지에 기반해야할 것이다. 이러한 맥락에서, ASIC칩을 저렴하게 배포함으로서 공정한 VDF 연산을 보장하게 하려는 노력도 존재한다.
Acknowledgement
이 글은 토카막 네트워크의 연구개발 노력의 일환으로 작성되었습니다. 토카막 네트워크는 최선을 다해 블록체인 기술에 기여하기 위해 노력하고 있습니다.
Reference
[1] K. Choi, et al. “Bicorn: An optimistically efficient distributed randomness beacon.” Cryptology ePrint Archive (2023).
