Ethereum 2.0 — Randomness

본 글은 DevCon4에서 Justin Drake가 발표한 “Ethereum 2.0 — Randomness” 세션 자료를 기반으로 작성되었습니다.

Ethereum 2.0

현재 이더리움의 메인체인 PoW 합의알고리즘을 사용하고 있습니다. Serenity에서 사용 될 PoS 체인인 Casper로 전환을 점진적으로 추진하였습니다. Vitalik Buterin이 제시한 Casper FFG 에 의하면 PoS 와 PoW 를 하이브리드한 합의방식으로서, 최종적으로는 완전한 PoS전환 될 것입니다.

Sharding은 플라즈마와 같이 확장성을 해결하기 위해 제안된 모델입니다. 플라즈마가 Sidechain(Off-chain)이라면, Sharding은 On-Chain 솔루션 입니다. 설명하자면, 이더리움 전체 네트워크를 분할한뒤 트랜젝션들을 영역별로 처리하고 병렬적으로 저장함으로써 확장성을 부여합니다.

Ethreum 2.0을 통해 Casper와 Sharding을 합친 비전이 제시되었습니다. 메인체인으로 Layer1을 두고 그 상위에 Layer2인 다수의 Shard체인로서 확장성 해결을 꾀하고 있습니다.

Credits Hsiao-Wei Wang and the Ethereum Team

Randomness

블록체인에서 난수(Random Number)가 왜 어려운 문제인지 이야기해보겠습니다.

아이러니 하지만, 컴퓨터가 난수를 생성하려면 난수가 필요합니다. 현재 컴퓨터에서 난수를 생성하는 방법은 시간을 종자(Seed)로 삼아서 난수를 생성합니다.

이더리움의 경우, 오라클을 통해 외부(오프체인)에서 난수를 블록체인(온체인)으로 가져오는 방법과 블록해쉬를 값을 사용하는 방법들을 사용해왔습니다. 이런 방법들에 문제점이 있습니다. 첫번째는 블록체인에 데이터를 기입하는 주체에 의한 신뢰의 문제가 있으며, 두번째는 미래의 블록해쉬를 마이너가 먼저 볼 수 가능성이 있어, 유저들 보다 이점을 가지게 됩니다.

위와 같은 방법의 난수를 Dapp에서 사용하게되면 형평성에 큰 문제가 생길 수 있습니다. 예를들어, 홀수/짝수를 맞추면 건돈에 두배를 주는 Gambling Dapp이 있다고 하겠습니다. 만약 마이너가 홀수에 판돈을 걸고 짝수로 돈을 잃게 되는 블록을 생성해버리면 어떻게 될까요? 마이너가 홀수에 걸었던 이더가 충분히 커서 마이너는 해당 블록을 네트워크에 전파를 안해버릴 수 있습니다. 이런식으로 마이너는 Gambling Dapp에서 다른 유저들보다 조금이나마 높은 승률을 올릴 수 있게 될 것입니다.

Ethereum 2.0 에서 난수 사용

Ethereum 2.0에서도 난수 가 중요한 문제입니다. Shard체인을 이어주는 중심에 Beacon Chain이 존재하며 여기에서 난수가 사용됩니다. Beacon Chain은 PoS 체인으로서 이더리움이 완전히 PoW에서 벗어났을때 메인체인이 될 것입니다. 이 체인의 역할은 블록검증자(Validator)를 각각의 Shard에 무작위로 배정함으로써, 담합한 검증자 집단으로부터 발생할 가능성이 있는 악의적인 행동을 방지함에 있습니다.

검증자들을 Shard에 무작위로 배정할때 난수가 사용됩니다. 이 난수의 공정성을 잃지 않고 생성한다는 것은 매우 어렵습니다.

RANDAO

다수의 참여자가 제출한 난수를 기반으로 검증가능한 난수를 생성하는 RANDAO가 제시되었습니다.

RANDAO 난수 생성에는 두 단계로 진행됩니다. Phase1 단계에서는 난수 생성 참가자들은 임의의 난수 sSHA3(s)를 RANDAO 컨트랙트에 m ETH와 함께 제출합니다. 시간경과 이후( 6 블록 이후), Phase2에서는 난수 생성 참가자들은 실제 난수 s를 제출하는 reveal과정을 수행해야 하며 그렇지 않으면 m ETH를 몰수 당합니다. 두 과정을 모두 마치면 난수 생성 참가자는 m ETH와 수수료(참가자 보너스)를 받습니다.

최종적인 난수는 참가자들이 제출한 난수들을 XOR 연산한 값을 사용하게 되며, 이는 최소한 한명의 정직한 참가자가 있으면 난수의 보안성이 지켜질 것입니다.

Generate random Number via RANDAO

위의 과정을 보면 난수 생성 참여자의 동기부여와 공정성이 매우 잘 고려된 로직이라고 볼 수 있겠습니다. 하지만, Last Revealer문제가 발생하게 됩니다. 위 슬라이드에 마지막 Slot의 참가자 처럼 이전 난수를 모두 미리 계산해보고 자신이 제출한 난수를 공개할지 여부를 판단할 수 있게됩니다. 블록해쉬로 난수 생성할때 마이너가 이점을 가지는 형평성 문제처럼, RANDAO에서도 Last Revealer와 유저간 불공평한 상황이 발생할 수 있습니다.

VDF (Verifiable Delay Function)

VDF function IO

단어에서 의미하듯 검증가능한 지연함수, 즉 입력후 일정시간 이후 출력되는 값이 나오는 함수입니다. 예를들어 10 입력하여 임의의 난수 결과(output)가 나오는데 3시간이 걸린다는 것을 의미합니다. 그리고 해당 난수가 입력값인 10에 기반한 결과임을 증명하는 proof도 같이 도출됩니다.

VDFreserch.org에 VDF 관련해 많은 자료들이 올라오고 있습니다. 이들중 DevCon4에서 소개된 Wesolowski의 VDF 함수를 살펴보도록 하겠습니다.

N은 RSA 계수로서, RANDAO처럼 여러 참여자들로 부터 받은 임의의 수로 산출된 난수입니다. x는 난수 생성을 위해 입력되어지는 종자(seed) 난수입니다. T 는 시간 파라미터로 지연시간만큼을 할당합니다. 여기서 검증가능함을 보여주는 것은 Proof수인 p 입니다.

입력값 x는 32bytes의 난수로서 2^256 자리수만큼 매우 큰 수입니다. 이 숫자를 2**T번 자기자신을 곱하니 엄청나게 큰 연산임을 짐작할 수 있습니다. output값이 과연 input값으로 부터 계산되어진것인지 진위를 알려면 직접 해당 과정을 동일하게 반복해보아야 할것입니다. 앞서 예를 들었지만 3시간동안 계산되어진 난수 y를 검증해보려고 동일과정을 3시간동안 연산하는 것은 자원낭비 일것입니다. 대신 Fiat-Shamir 방법을 통해서 빠르게 검증 할 수 있습니다.

예를들어 T = 10, B = 3 라고 할때, output연산을 위해서는 x를 200번 거듭제곱해야 합니다. 반면 Verification 공식에 대입 해보면 x를 2번 제곱하고 p 3번 제곱하여, 총 5번의 거듭제곱으로 줄어들게 됩니다.

RANDAO + VDF

RANDAO의 Last Revealer문제를 해결하기 위해 VDF를 거쳐 난수를 생성합니다. 매우 큰 연산을 빠르게 수행하는 VDF를 통해 최종적으로 사용될 난수를 발생시킴으로서 예측 불가능성을 높입니다. 아래 그림에서처럼 VDF 연산은 오프체인에서 수행하게 되며 결과값인 난수 output과 검증을 위한p 값이 최종적으로 Beacon Chain에서 사용될 것입니다.

VDF연산이 결과가 다시 RANDAOmixing에 초기값으로 사용되어 지며, 이 난수 생성 사이클은 병렬적으로 수행됨으로 지속적으로 Beacon Chain을 위한 난수가 발생할것입니다.

VDF Hardware

VDF 연산은 매우 큰 연산이기 때문에 일반적인 범용 CPU로 연산하기에는 큰 부담이 생깁니다. 따라서 Bitcoin 채굴에 사용되는 것처럼 전용 ASIC을 통한 연산을 계획하고 있습니다. 아래 표는 프로젝트에서 요구(계획)되는 ASIC chip의 성능과 기기(rig)의 Spec입니다.

Latency(연산속도)와 Power(전력소모)는 이율배반 관계로서 연산속도를 높이기 위해서는 더 많은 전력을 필요로 하게 됩니다. 두 지점의 최적점을 맞출수 있도록 전문가의 설계가 필요할 것입니다. Open-Source Hardware프로젝트로서 VDF Hardware 설계에 100만달러 이상의 상금을 걸었습니다. 그리고 이 하드웨어들은 무료로 전세계에 에어드랍? 할 것으로 계획하고 있습니다.

다음의 표는 PoW에서의 난수 발생을 위한 비용과 VDF에서의 발생 비용을 비교한 차트입니다. 아직 Beacon Chain또한 실체가 명확하게 드러나 있지 않지만, VDF-rig는 독립적인 노드로서 다른 블록체인 플랫폼에서도 충분히 사용할 수 있을것이라 생각됩니다.

Project Goal

Ethereum 2.0의 난수 발생 시스템은 예측 불가능하고, 종속적이지 않으며, 세계3차 대전 이후에도 작동할 수 있도록 개발되는 것을 목표로 하고 있습니다.

VDF(+Hardware)를 통해 예측불가능하고 검증가능한 연산결과(=난수)를 보여줄 것입니다. 그리고 전세계에 10%의 정직한 난수발생 노드(VDF node)가 유지된다면, 난수의 보안성(Security)이 보장될 것으로 예상하고 있습니다.

Conclusion

자동차 네비게이션 부터, 스마트폰의 헬스케어, 사용자 위치기반 타겟 광고까지 모두 GPS시스템에 의존한 다양한 서비스들이 있습니다. 이 GPS시스템은 지구 궤도를 돌고 있는 위성들의 매우 정확한 시계에 기반을 하고 있습니다. GPS 위성은 원자시계를 탑재하고 있는데, 원자시계들은 몇천만년 ~ 억만년 정도에 1초가 틀릴 정도로 매우 정확합니다.

GPS satellites around Earth orbit

위성들의 원자시계를 기반으로 작동하는 GPS 시스템처럼, 전세계에 분포되어 있는 VDF-hardware에서 가장 공정성(Fairness)있는 난수신호를 내보낼 것입니다. 그리고 검증가능한 속성으로 인해 블록체인에 필요한 “신뢰”를 확보할 것입니다. 앞으로 블록체인과 Dapp뿐만 아니라 더 다양한곳에서 응용될 것으로 기대합니다.

References

Jin