블록체인에서의 난수 생성
블록체인에서 난수 생성이 어려운 이유와 중요한 이유를 설명하고, 블록체인에서의 난수 생성 방법에 대해서 알아봅니다.
Author: gganbukim
Reviewer: Yohan Lim
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
[목차]
- Introduction
- 블록체인에서의 난수 생성 방식 소개 및 평가
- Outro
1. Introduction
블록체인에서는 파이썬의 RANDOM 모듈과 같은 것을 제공할까?
파이썬 랜덤 함수는 따로 입력 값을 입력하지 않아도 매번 다른 값을 출력합니다. 이런 함수를 이더리움에서 제공할까요? 만약 이를 블록체인에서 제공하지 않는다면, 밸리데이터의 선출은 어떻게 진행될까요? 이번 글에서는 블록체인의 난수 생성 방식에 대해서 다루어보겠습니다.
먼저 난수란 정해진 범위 내에서 무작위로 추출된 수를 의미합니다. 그리고 이러한 난수는 비편향, 예측 및 조작 불가능, 입증 가능이라는 특징을 만족하여야 합니다. 일상에서 흔히 찾아볼 수 있는 예로는 로또 추첨기가 있습니다. 로또 추첨기는 바람을 이용해 1~45 범위 내에서 숫자를 뽑습니다. 바람을 이용하기 때문에 예측 및 조작이 어렵습니다. 그러나 컴퓨터에는 로또 추첨기의 바람과 같은 자연 현상이 없습니다. 그리고 컴퓨터는 같은 입력값에서 같은 결과값을 출력합니다. 예를 들어, 같은 입력값을 입력하면 어떤 컴퓨터에서든 같은 결과값을 출력하는 SHA-256 함수를 떠올려보시면 좋을 것 같습니다. 이를 ‘결정론적’으로 동작한다고 말합니다. 이러한 환경에서 난수를 생성할 때 핵심은 입력 값입니다. 입력 이후에는 결정론적으로 동작해 무작위성이 없기 때문입니다. 따라서 입력값을 누구도 예측할 수 없도록 하는 것이 중요합니다.
블록체인에서의 난수 생성
블록체인에는 마우스, 키보드 입력값, 인터럽트, disk i/o 등의 데이터가 없기 때문에 난수의 입력 값을 확보하기 어렵습니다. 블록체인은 여러 대의 컴퓨터로 구성된 하나의 컴퓨터로, 결정론적으로 동작합니다. 그리고 노드가 블록을 받아 실행했을 때 모든 노드는 같은 결과값을 출력해야 합니다. 이러한 특성으로 단일 컴퓨터에 존재하는 데이터를 사용할 수 없습니다. 예를 들어 마우스 입력 값을 난수 생성 시의 입력 값으로 사용하는 함수를 이용하여 사용자들에게 랜덤한 개수의 토큰을 분배한다고 가정해봅시다. 이 때, 각 노드의 마우스 입력값이 같을 확률은 0에 가깝습니다. 따라서 트랜잭션의 결과값이 노드 별로 달라질 수밖에 없습니다. 이러한 이유로 블록체인에는 로컬 데이터를 활용한 랜덤 함수를 지원하지 않습니다.
블록체인에서의 난수는 왜 중요할까요? 이더리움의 예시를 들어보겠습니다. 이더리움은 밸리데이터(validator)를 선출할 때 난수를 사용합니다. 이 때, 선출되는 밸리데이터가 편향성 없이 랜덤하게 선출되어야 전체를 대표한다고 할 수 있습니다. 만약 랜덤이 아닐 경우 스테이킹 총량의 ⅓ 없이도 공격이 가능하게 될 수도 있습니다. 그리고 이는 밸리데이터의 보상과도 직결되는 문제입니다. 따라서 밸리데이터의 선출 과정을 모든 노드가 받아들일 수 있어야 하고 누구도 조작할 수 없어야 합니다. 만약 외부에서 난수를 생성하고 이를 가져올 수는 없을까요? 이러한 경우에는 외부에서 생성한 난수에 대해 노드 간의 합의가 필요하고 수 많은 밸리데이터가 해당 난수에 합의하기도 어렵습니다. 특정 주체가 난수를 생성하고 그것을 모든 노드가 따를 수도 있지만 이는 탈중앙화를 훼손합니다. 특정 주체가 난수를 조작해 악의적인 밸리데이터를 지속적으로 선출되게 할 수 있고 동작을 멈추면 블록 생성이 불가능해질 수 있습니다. 이처럼 블록체인에서의 난수 생성은 어렵지만 중요한 문제입니다.
2. 블록체인 난수 생성 방식 소개 및 평가
(1) 블록 상태값
블록체인의 난수 생성 방법에 대해 첫번째로 살펴 볼 방법은 블록의 상태값을 이용하는 방법입니다. 블록의 상태 값이란, 블록 해시, 상태 루트, 트랜잭션 해시 등 블록의 상태를 나타내는 값을 의미합니다. 그리고 이러한 블록의 상태 값 조합을 난수 생성의 입력 값으로 사용하여 난수를 생성하게 되는 것입니다.
이는 입력값에 대해 합의가 필요하지 않으므로 빠른 의사결정이 가능하다는 장점이 존재합니다. 그러나 블록 생성자는 블록의 상태 값을 미리 알 수 있고 트랜잭션 순서 등의 입력 값을 임의로 변경함으로써 상태값을 변경하여 의도적인 영향을 끼칠 수 있습니다. 예를 들어, 블록 생성자가 블록체인을 사용한 로또 번호 추첨에 참여하는 경우를 생각해봅시다. 로또 번호의 추첨은 블록 해시의 맨 뒤 10자리와 추첨 번호의 매칭률을 기반으로 이루어진다고 가정해보겠습니다. 블록 생성자는 자신의 추첨 번호와 일치율이 낮을 경우 블록 상태 값에 의도적인 영향을 끼침으로써 매칭률을 올릴 수 있습니다. 이러한 경우 블록 생성자의 개입이 존재하지 않았을 경우 상금을 받을 수 있었던 참여자가 상금을 받을 수 없게 될 것입니다. 따라서 블록의 상태 값을 이용한 난수 생성 방법은 블록 생성자의 개입으로 공정한 난수 생성이 어려워진다는 한계가 존재합니다. 이는 앞서 설명한 이더리움 2.0의 검증자 선정에서도 동일한 문제가 발생할 수 있습니다.
(2) Commit and Reveal 방식
앞서 살펴본 것처럼 블록체인의 상태값을 이용하여 난수를 생성할 경우, 블록 생성자가 블록에 포함될 트랜잭션의 구성을 바꾸어 가면서 본인이 원하는 블록 해시를 만들어 낼 가능성이 존재합니다. 따라서 이러한 임의의 사용자에 대한 의도를 최대한 제거하여 난수를 생성하는 방법이 필요합니다.
Commit and Reveal 방식이란 말 그대로 참가자들이 각자의 난수를 해시한 값을 Commit하고 이를 Reveal하여 최종 난수를 생성하는 방식으로 진행되는 방식을 의미합니다.
Commit and Reveal 방식은 다음과 같은 과정으로 이루어집니다. 먼저 첫 번째 참가자가 랜덤한 숫자에 대해 해시 값을 얻습니다. 그리고 이를 두 번째 참가자의 랜덤 숫자와 결합하여 해시 값을 얻습니다. 이를 최종 참가자까지 반복하여 최종 난수를 얻는 것입니다. 여기서 해시 값이란 해시 함수를 통해 얻은 결과 값을 의미합니다. 해시 함수는 같은 입력값에 대해 같은 결과값을 얻을 수 있는 결정적인 함수이며, 결과 값을 통해 입력 값을 예측할 수 없는 일방향 함수(one-way function)이라는 특징을 가지고 있습니다.
이더리움2.0에서 공정한 위원회 선출을 위해서는 공정한 난수 생성이 필요합니다. 예를 들어 아래 사진과 같이 난수에 편향이 생기게 된다면 지분에 따른 공정한 선출이 이루어지지 않을 가능성이 존재하기 때문입니다.
Commit and Reveal 방식은 RANDAO에 의해 구현되어 사용되고 있는데, RANDAO에서 구현한 Commit and Reveal 방법에 대해서 살펴보도록 하겠습니다. RANDAO에서는 Commit and Reveal에 대한 절차를 3 phase로 나누어서 진행하고 있습니다.
먼저 Phase 1에서는 난수생성 요청자가 컨트랙트에 난수 생성을 요청합니다. 난수 생성을 요청하는 과정에서 해당 난수 요청자는 일종의 Bounty를 걸고 난수 생성 참가자들의 참가를 독려하게 됩니다. 그리고 해당 요청자 뿐만 아니라 다른 사람(Follower)들도 함께 바운티를 걸고 해당 난수를 얻을 수 있습니다. 이러한 난수 요청 단계 이후에는 난수를 생성하고자 하는 참가자들이 컨트랙트에 일정량의 이더리움을 예치합니다. 이후 난수를 생성하기 위한 일정 참가자가 충족되면 난수 생성 프로세스가 시작됩니다. 그리고 각 참가자는 각자의 난수 s에 대하여 Sha3() 해시 알고리즘을 통해 Sha3(s)를 생성하여 결과 값을 컨트랙트에 제출합니다. 이 과정에서 해당 sha3(s) 값은 기록되어 다시 사용될 수 없으며, 만약 같은 sha3(s)가 체출될 시에는 컨트랙트는 첫 번째 sha3(s)의 값만 유효한 값으로 받아들이게 됩니다.
Phase 2에서는 각 참가자들이 sha3(s)에 사용한 s를 컨트랙트에 공개 및 제출하는 단계입니다. 그러나 그림에서 볼 수 있듯이 두 번째 참가자처럼 s를 제출하지 않을 수도 있습니다. s를 제출하지 않은 참가자는 예치했던 이더리움과 바운티를 받을 수 없게 됩니다. 그럼에도 s를 제출하지 않을 경우, 특히 마지막 참가자가 s를 제출하지 않는다면 문제가 발생할 수 있는데 이는 뒤에서 자세히 살펴보도록 하겠습니다. 그리고 컨트랙트는 공개된 s에 대하여 Phase1에서 제출했던 sha3(s)와 공개된 s를 이용한 sha3(s)가 일치하는지 여부를 판단합니다.
Phase3에서는 컨트랙트가 참가자들이 공개한 s들을 통해 XOR 함수로 연산을 시행하고 최종 난수를 생성하여 난수 생성을 요청한 컨트랙트에 해당 값을 전송합니다.
해당 그림에서는 마지막 참가자가 랜덤 숫자를 제출하지 않은 상황을 나타내었습니다. 이 때, 만일 마지막 참가자가 높은 연산력을 확보한 경우 마지막 참가자는 이전 난수들을 미리 계산해보고 자신이 제출한 난수를 공개할지 여부를 판단할 수 있게 됩니다. 그리고 이를 통해 의도적인 영향을 끼칠 수 있습니다. 연산력이 높은 참가자의 경우 이러한 방식으로 난수를 미리 계산하여 의도적인 영향을 끼칠 수 있게 되는 것입니다. 이를 Last Revealer 문제라고 합니다.
Last Revealer 문제를 방지하기 위한 방법이 바로 Verifiable Delay Function(이하 VDF)입니다.
VDF에 대한 자세한 설명은 디사이퍼의 미디엄 Brief Overview of VDF를 참고해주시면 좋을 것 같습니다. VDF는 난수를 계산하는 데에는 상당한 시간이 필요하지만 검증하는 데에는 적은 시간이 필요한 함수입니다. VDF에는 병렬화가 불가능한 계산을 최대한 포함하고, VDF의 결과값을 다시 입력 값으로 사용하는 계층화(folding)를 통해 결과 도출 시간을 지연시킵니다. 앞서 높은 계산력을 가진 마지막 참가자의 경우 Last Revealer 문제가 발생할 수 있다고 하였는데 VDF는 이 부분에 대해 계산 시간을 증가시켜 이를 방지하는 것이죠. Commit and Reveal 방식에서는 이러한 Last Revealer 문제 뿐만 아니라 앞서 sha3(s) 값을 모두 저장하는 과정에서 컨트랙트 용량 문제가 발생한다는 단점이 존재합니다.
(3) Signidice
Signidice 방식은 Commit and Reveal 방식에서 sha3(s) 값을 모두 저장하기 때문에 발생할 수 있는 컨트랙트 용량 문제를 보완하고자 하는 방식입니다. Signidice 방식은 현재 많이 사용되고 있는 ECDSA(Elliptic Curve Digital Signature Algorithm)방식이 아닌 DSA(Digital Signature Algorithm)을 사용하는데, 이는 ECDSA를 이용할 경우 다수의 참가자가 아닌 두 참가자만이 존재하는 Signidice 방식에서 입력 매개변수를 조작하여 서명에 영향을 줄 수 있는 가능성이 존재하기 때문입니다. 그러나 Signide 방식에서는 다수의 참가자가 아닌 두 참가자만이 존재하므로 앞서 Commit and Reveal 방식에서 참가자가 많아 sha3(s) 저장에 많은 공간이 필요한 문제를 보완할 수 있습니다. Signidice 방식에 대한 대략적인 개념도는 다음과 같습니다.
먼저 난수 생성 요청자가 난수의 입력 값(seed)을 난수 생성 참가자에게 전달합니다. 참가자는 입력 값(seed)을 해싱하고 (h← H(seed)) 이를 프라이빗 키로 서명합니다. (S←sigma.Sign_d(h)) 그리고 이 서명값을 다시 해싱하여 최종 난수인 L을 생성하게 되는 것입니다. 참가자는 이를 통해 획득한 S와 L 값을 난수 생성 요청자에게 보내게 되고 난수 생성 요청자는 S를 통해 L 값을 확인하고 수용 여부를 결정합니다. 이러한 Signidice 방식은 Commit and Reveal 방식에 비해 참가자 수가 적으므로 Commit and Reveal 방식에서의 용량 문제를 일부 보완할 수 있으나 Signidice 방식 또한 난수의 중복을 막기 위해 난수 요청자의 입력 값(seed)를 모두 저장하게 되므로 컨트랙트 용량 문제가 여전히 발생할 수 있고 요청되었던 입력 값(seed)가 많아질수록 확인 작업 시간이 오래걸린다는 단점이 존재합니다.
(4) Boneh–Lynn–Shacham Digital Signature
Boneh–Lynn–Shacham Digital Signature(이하 BLS) 방식은 Elliptic Curve Cryptography(이하 ECC) 방식과 Paring-Based Cyptography(이하 PBC) 방식을 이용한 전자 서명 알고리즘을 의미합니다. BLS 방식에 대한 설명을 위해 ECC와 PBC에 대해 간단하게 알아보도록 하겠습니다.
ECC 방식은 기존의 RSA 방식보다 높은 안정성과 효율성을 가지는 전자 서명 알고리즘으로 ECC를 이용해 구성한 전자서명 알고리즘이 바로 비트코인과 이더리움1.0을 비롯해 공인 인증서 등에 사용되는 ECDSA 방식입니다. ECC 방식에서는 개인키에 Generator 역할을 하는 G 값을 곱해 공개키를 얻을 수 있습니다. 아래는 비트코인 등에서 자주 사용되는 타원 곡선인 secp256k1을 나타내고 있습니다.
타원 곡선에서의 연산은 다음과 같은 방식으로 수행됩니다.
위의 그림에서 타원 곡선 위의 임의의 점 P에서 직선을 그으면 P, Q, R 세 점이 한 곡선에 존재하게 되며 P, Q, R은 항등원이라고 표현할 수 있고 P + Q + R = 0로 표현할 수 있습니다. 또한, 타원곡선은 가로축에 대해 대칭이므로 R에서 수직선을 그으면 R과 -R 이 항등원이라고 표현할 수 있으며 R — R = 0이 됩니다. 이 때 같은 점인 P+P와 같은 연산의 경우에는 해당 점에서 타원 곡선의 접선을 그어 2P + Q =0 으로 표현할 수 있습니다. 이러한 더하기 연산을 여러 번 수행한 것이 곱하기 연산이 됩니다. 그리고 이를 이용하여 개인키와 g의 곱으로 개인키를 구할 수 있게 됩니다.(sk* G = pk) ECC 방식에서 계산 과정을 반복 수행하면 마지막 점에서 첫 번째 점을 찾는 것이 어려우므로 공개키를 통해 개인키를 찾는 것을 불가능하게 만드는 방식이라고 할 수 있습니다.
PBC란 Bob과 Alice가 존재할 때, Pairing 함수와 Gap Group을 통해 Bob이 Alice의 서명을 Alice의 개인키로 검증할 수 있는 방식을 의미합니다. 이더리움 2.0에서는 이러한 PBC 방법을 사용할 수 있는 Paring-friendly ellipstic curve인 BLS curve를 타원곡선으로 사용합니다.
BLS 방식은 앞에서 설명한 ECC와 PBC를 이용한 전자 서명 알고리즘이며 이더리움 2.0에서도 사용되고 있습니다. 이 방식은 각자의 개인키로 메시지에 서명한 공개키들을 합쳐서 일괄적으로 서명을 검증할 수 있는 것이 가장 큰 특징이자 장점이며 이를 Signature aggregation이라고 합니다.
이는 Signidice 등의 방식에서 생길 수 있는 단일 서명자에 의한 문제를 방지할 수 있습니다. 각 참가자는 누구도 전체 프라이빗 키를 가지지 않고 부분적으로만 소유하기 때문에 전체 서명을 계산할 수 없습다. 이는 ECC만을 이용한 ECDSA 방식에 비해 서명 및 검증 시간이 느리지만 만일 모든 서명자가 같은 메시지에 서명할 경우에는 더 빠르게 작동할 수 있습니다. 이러한 특징은 이더리움 2.0에서 용이하게 사용됩니다. 이더리움 2.0에서 구성된 위원회(Committee)의 검증자(Validator)는 ‘같은 데이터에 대해’ 디지털 서명을 진행합니다. 여기서 서명 대상이 되는 데이터는 슬롯 번호, Committee index, 비콘체인 및 체크포인트 등의 AttestationData입니다. 이렇듯 이더리움 2.0에서는 같은 데이터에 대해 서명이 이루어지므로 BLS 방식을 통해 속도 개선을 이룰 수 있으며, 더 나아가 모든 서명을 보관하지 않고 합쳐진 서명만 보관할 수 있으므로 노드의 공간 절약도 가능해지게 되는 것이죠. 또한, BLS 방식은 검증자가 검증자임을 검증하는 과정인 Proof-of-Possession에서도 사용됩니다.
다음으로 RANDAO에서 구현한 BLS에 대해서 살펴보겠습니다.
먼저 대리인(Deputy)가 서명이 필요한 메시지 M을 전파하면 참가자들은 이 메시지 M을 각각의 프라이빗 키 s-i로 서명하여 sig-i를 생성하고 다른 참가자들에게 전파합니다. 그리고 각 참가자들은 퍼블릭 키를 통해 전파받은 sig-i를 검증하고 대리인은 이를 이용하여 최종 서명 SIG를 생성하고 전파하게 됩니다.
대리인이 최종 서명 SIG를 생성하는 과정에서 사용되는 것이 ECC와 PBC입니다. 참가자들의 서명과 공개키를 더하는 과정에서 ECC를 이용하며 더해진 서명과 공개키를 이용하여 더해진 공개키를 통해 이루어진 서명이 더해진 서명과 같은지 검증하는 과정에서 PBC를 사용합니다.
앞에서 사용한 BLS 방식을 이용하여 난수를 생성할 수도 있습니다. 이를 위해서 먼저 그룹을 h로 나누어 첫번째 그룹에서 SIG-1을 생성하고 두번째 그룹을 선택합니다. 이후 두번째 그룹은 SIG-1에 서명하고 SIG-2를 생성한 뒤, 세번째 그룹을 선택합니다. 그리고 이러한 과정을 반복하여 최종 서명이자 난수인 SIG-h를 생성합니다. 해당 과정은 모든 그룹이 생성 과정에 두 번 참여할 수 없고 결과를 예측할 수 없습니다. 그러나 이는 마지막 그룹이 SIG-h를 생성하기 때문에 마지막 그룹인 h그룹에서 악의적인 참여자가 k보다 적을 때만 SIG-h가 안전하다는 단점이 있습니다.
3. Outro
앞서 설명한 방법들을 요약하면 다음과 같습니다.
지금까지 블록체인에서 난수 생성이 어려운 이유와 중요한 이유, 그리고 블록체인에서 난수를 생성하는 방식과 각 방식의 장단점을 알아보았습니다. 블록체인에서는 여러 대의 컴퓨터가 결정론적으로 작동하기 때문에 로컬 데이터를 입력 값으로 사용하기 어렵고, 특정 주체가 난수를 생성할 경우 탈중앙성을 훼손한다는 문제가 존재합니다. 난수의 생성은 이더리움을 비롯해 합의에 참여하는 밸리데이터를 선출할 때 사용될 수 있습니다. 그리고 해당 난수는 비편향, 예측 및 조작 불가능, 재생성 불가능, 입증 가능이라는 특징을 만족하여야 합니다. 이에 대한 만족 여부는 네트워크의 보안에 아주 큰 영향을 끼칠 수 있고, 이를 만족하기 위해서는 난수 생성과 관련한 방법에 대한 심도 깊은 고민이 필수적입니다. 이번 글을 통해서 블록체인에서 난수 생성의 중요성이 널리 인식되고 관련된 논의가 활발히 이루어지기를 기대하며 글을 마칩니다.
References
Pairing-based Cryptography와 BLS signature의 이해
RANDAO — white paper
ethereum.org — BLOCKS
devcon4 — Ethereum 2.0 Randomness
