합의에서의 검증 가능한 무작위 함수

합의 프로토콜에는 지도자 선출, 위원회 선택, 샤드 할당을 위한 무작위성이 필요합니다. 무작위성은 세 가지 특성을 만족해야 합니다. 예측 불가능성은 공개되기 전에 누구도 결과를 예측할 수 없어야 한다는 뜻이고, 조작 불가능성은 어떤 참여자도 자신에게 유리하도록 결과를 조작할 수 없어야 한다는 뜻이며, 공개 검증 가능성은 생성자를 신뢰하지 않아도 누구나 결과가 올바른지 검증할 수 있어야 한다는 뜻입니다. 단순한 방식은 실패합니다. 단일 노드의 난수는 조작할 수 있고, 약정-공개 방식은 마지막 공개자가 결과를 편향시킬 수 있습니다. 검증 가능한 무작위 함수(VRF)는 이 세 가지 요구 사항을 모두 해결합니다.

1999년 Micali, Rabin, Vadhan이 소개한 검증 가능한 무작위 함수(VRF)는 정확성 증명을 제공하는 의사 난수 함수입니다. VRF에는 세 가지 알고리즘이 있습니다. KeyGen은 키 쌍(SK, PK)을 생성하고, 증명(SK, alpha)은 (beta, pi)를 생성하며 여기서 beta는 출력이고 pi는 증명입니다. 검증(PK, alpha, beta, pi)은 유효 또는 무효를 반환합니다. SK를 모르는 사람에게 출력 beta는 무작위 출력과 구별할 수 없고(VRF 의사 난수성), 증명 pi는 위조할 수 없습니다(VRF 고유성). 증명 크기는 O(1)이며 입력과 무관하게 일정합니다.

가장 널리 배포된 VRF 구성은 타원 곡선 이산 로그 문제의 어려움에 기반한 ECVRF(IETF 표준 문서 9381)입니다. 증명자는 개인 키 x와 입력 alpha를 받아 H = 곡선으로 변환하는 해시(PK, alpha)를 계산하여 alpha를 곡선의 한 점으로 매핑한 다음 gamma = x * H를 계산합니다. VRF 출력은 beta = 케착(gamma)입니다. 증명 pi는 슈노르와 유사한 영지식 논증을 사용합니다. 증명자는 무작위 k를 약정하고, c = 해시(H, gamma, k*G, k*H)라는 도전값을 계산하며, s = k - c*x라는 응답을 계산한 뒤 pi = (gamma, c, s)를 출력합니다. 검증은 슈노르 방정식을 확인하고 beta를 다시 계산합니다.

Algorand(Silvio Micali 외, 2017)는 블록체인 합의에서 VRF 활용을 개척했습니다. 각 라운드마다 모든 검증자는 VRF(SK, round || seed)를 비공개로 계산하여 무작위 출력을 얻습니다. 출력은 임계값과 비교됩니다. VRF_output < stake_fraction * threshold이면 검증자가 위원회 구성원 또는 블록 제안자로 선택됩니다. 검증자는 자신의 블록/투표를 VRF 증명과 함께 전파하기 전까지 자신이 선택되었다는 사실을 아는 유일한 주체입니다. 이 암호학적 자기 선택 방식은 공개 리더 선출의 필요성을 없애므로, Algorand는 앞으로 리더가 될 것으로 알려진 대상에 대한 표적 서비스 거부 공격에 강합니다.

Cardano의 Ouroboros Praos(현재 배포된 버전)는 슬롯 리더 선출에 VRF를 사용합니다. 각 에포크마다 블록체인에서 새로운 무작위 시드가 도출됩니다. 각 스테이크 풀 운영자(SPO)는 에포크의 각 슬롯에 대해 VRF(SK, slot || epoch_seed)를 계산합니다. 출력이 지분에 비례하는 임계값보다 작으면 해당 운영자는 슬롯 리더가 되어 블록을 생성할 수 있습니다. VRF 증명은 블록 헤더에 포함되므로 누구나 해당 SPO가 정당하게 선출되었는지 검증할 수 있습니다. 이를 통해 Cardano는 에포크 중간에 리더 일정을 알아내는 적응형 공격자에 대해서도 입증 가능한 보안을 제공합니다.

Ethereum은 무작위성 비콘에 VRF 대신 RANDAO(BLS 서명의 누적)를 사용합니다. RANDAO는 BLS 외에 추가 암호학적 기본 요소가 필요하지 않아 더 단순하지만, 마지막 공개자 편향에 취약합니다. 블록 제안자는 자신의 RANDAO 기여가 불리한 결과를 만들 것이라고 예측할 수 있으면 블록 보상을 포기하는 대가로 자신의 블록을 공개하지 않을 수 있습니다. VRF 기반 선출은 선출된 주체가 자신을 공개하기 전까지 그 정체를 숨기므로 이러한 공격 경로를 완전히 제거합니다. 그 대가로 VRF는 암호학적 복잡성(해시-대-곡선, 증명 생성)을 추가하는 반면, RANDAO는 기존 BLS 인프라를 재사용합니다.

Chainlink VRF는 스마트 계약에 검증 가능한 무작위성을 서비스로 제공합니다. 사용자는 LINK 토큰을 지불하여 소비자 계약에 무작위성을 요청합니다. Chainlink 오라클 노드는 VRF 키 쌍을 보유합니다. 노드는 블록 해시와 사용자가 제공한 논스에서 도출한 시드를 사용하여 ECVRF(SK, seed)를 계산한 다음 (beta, pi)를 체인상에 제출합니다. VRF 조정자 계약은 증명을 검증한 후 무작위 출력을 소비자에게 전달합니다. 이를 통해 스마트 계약은 체인에 네이티브 VRF 비콘을 구현하지 않고도 조작에 강한 무작위성을 사용할 수 있으며, NFT 발행, 복권, 게임 등에 유용합니다.

Signal Protocol은 Curve25519 위에 구축된 VRF 구성인 VXEdDSA(검증 가능한 X25519 EdDSA)를 사용합니다. 발신자가 일회용 사전 키 서명을 생성할 때 VRF는 메시지와 발신자 키로부터 결정적이지만 예측할 수 없는 논스를 생성하는 데 사용됩니다. 이를 통해 EdDSA의 보안을 무너뜨릴 수 있는 논스 재사용을 방지하면서 서명을 검증 가능하게 유지합니다. VRF 증명을 사용하면 수신자가 논스가 올바르게 도출되었는지 검증할 수 있으므로, 키 복구 공격을 가능하게 할 수 있는 악의적인 논스를 발신자가 선택하지 못하도록 막습니다. VXEdDSA는 합의를 넘어선 일반적인 암호학적 도구로서 VRF의 활용 가능성을 보여 줍니다.

검증 가능한 지연 함수(VDF)는 때때로 VRF와 혼동됩니다. VDF는 최소 T단계의 순차 계산을 요구하는 시간 잠금 속성을 가지며, 정확성을 입증하는 짧은 증명과 함께 출력을 생성합니다. VDF는 RANDAO의 마지막 공개자 편향을 완화하는 데 사용됩니다. Ethereum에서 계획 중인 VDF 계층을 사용하면 조작을 시도하려는 주체가 미리 VDF를 실행해야 하며, 이 작업에는 공격 가능 시간보다 긴 시간이 걸립니다. VRF는 즉각적인 비공개 계산을 제공하고, VDF는 공개적이고 느린 계산을 제공합니다. 두 기술은 상호 보완적입니다. VDF는 마지막 공개자 편향을 방지하고 VRF는 리더 예측을 방지합니다.

VRF 선출은 적응형 공격자에 대해 중요한 보안 향상을 제공합니다. PBFT와 Tendermint에서는 리더의 신원이 미리 알려져 있어(라운드 로빈 일정) 공격자가 다음 리더가 제안하기 전에 분산 서비스 거부 공격을 가할 수 있습니다. VRF 기반 선출(Algorand, Cardano)은 블록이 전파될 때까지 리더의 신원을 비밀로 유지합니다. 그 시점에는 이미 블록이 제안되었으므로 분산 서비스 거부 공격이 너무 늦게 도착합니다. 이를 적응형 보안 또는 예측 불가능한 리더 선출이라고 합니다. 이를 가능하게 하는 암호학적 속성은 비밀 키가 없는 누구에게나 VRF 출력이 의사난수로 보인다는 점입니다.

VRF를 올바르게 구현하려면 몇 가지 사항에 주의해야 합니다. 해시-대-곡선은 상수 시간으로 실행되며 균등한 알고리즘을 사용해야 합니다(IETF RFC 9380은 타이밍 누출을 방지하기 위한 표준화된 방법을 정의합니다). 증명의 VRF 논스 k는 RFC 6979를 사용하여 (SK, alpha)에서 결정적으로 도출해야 합니다. k를 재사용하거나 약한 무작위 k를 사용하면 비밀 키가 유출됩니다(ECDSA 논스 재사용과 동일한 취약점입니다). ECVRF-P256-SHA256-TAI의 증명 크기는 80바이트이고, ECVRF-ED25519-SHA512-ELL2도 80바이트이므로 둘 다 체인상 포함에 적합합니다. VRF의 유일성 속성은 동일한 (SK, alpha) 쌍에 대해 유효한 증명이 두 개 존재할 수 없도록 보장합니다.

VRF는 정확성을 입증하는 암호학적 증명과 함께 의사난수 출력을 생성하여 예측 불가능성, 편향 불가능성, 공개 검증 가능성을 충족합니다. ECVRF(RFC 9381)는 타원곡선 기반의 표준 구성입니다. Algorand는 적응형 공격자에 대한 저항성을 확보하기 위해 VRF 암호학적 자기 선택을 사용합니다. Cardano Ouroboros Praos는 슬롯별 리더 선출에 VRF를 사용합니다. Chainlink VRF는 스마트 계약에 검증 가능한 무작위성을 제공합니다. VRF는 마지막 공개자 편향을 해결하는 VDF와 상호 보완적이며, 누적된 BLS 서명을 사용하지만 마지막 공개자의 알려진 취약점이 있는 RANDAO와 대조됩니다.