Micali , Rabin, Vadhan의 99년 논문에서 처음 소개된 VRF(Verifiable Random Function)은  입력에 대해 검증 가능한 의사난수(pseudorandom) 값을 출력하는 함수이다.

VRF의 특성

VRF는 Keygen, Evaluate, Verify 3개의 함수로 구성된다.

• Keygen(r) -> (VK, SK): 키 생성 함수는 랜덤한 입력 r에 대해 검증키 VK와 비밀 SK 쌍을 생성한다.
• Evaluate(SK, X) -> (Y, ⍴): 실행 함수는 비밀키 SK와 메시지 X를 입력으로 받아 유사 난수 S와 증명 ⍴를 리턴한다.
• Verify(VK, X, Y, ⍴) -> 0/1: 검증 함수는 입력으로 검증키 VK와 메시지 X, 출력 Y, 증명 ⍴를 입력으로 받아 Y가 실제로 SK와 X에 의해 생성된 출력이 맞으면 1을 리턴한다.

정리하면, VRF는 키쌍 VK, SK를 고정했을 때 입력 X에 대해 유일하고 검증 가능한 유사난수 Y를 출력하는 함수이다.

VRF 함수가 유용하려면 다음 조건을 만족시켜야 한다.

1. 출력 Y는 유일해야 한다. (VK, SK) 키쌍과 입력 X에 대해 또 다른 출력을 찾는 게 불가능해야 한다.
2. 출력 Y는 유사난수여야 한다.  증명 ⍴가 없는 제 3자 입장에서 Y는 예측이 불가능한 랜덤한 값이어야 한다.
3. 1, 2 속성은 키쌍(SK, VK)가 신뢰할 수 없는 제3자에 의해 생성되었을 경우에 유효해야 한다.

별도의 검증키를 이용해 출력을 검증할 수 있다는 점에서 VRF는 디지털 서명 방식과도 유사하다. 하지만 디지털 서명의 경우 하나의 입력에 대해 여러 개의 유효한 서명이 존재하고, 출력값이 유사난수 조건을 만족시킬 만큼 충분히 랜덤하지 않다는 점에서 VRF 함수와는 차이가 있다.

VRF 함수와 블록체인

텐더민트 합의 알고리즘은 리더를 선출할 때 라운드 로빈(round robin) 방식을 사용한다.  이 방식은 고정된 순서대로 리더가 정해지기 때문에 공격자 입장에서는 쉽게 다음 리더 노드에 대한 DoS (Denial of Service) 공격이 가능하다는 약점이 있다.

VRF를 사용하면 이러한 문제를 완화시킬 수 있다. 일례로, 다음과 같이 현재의 리더가 자신의 비밀키와 이전 블록의 해시(메시지)를 VRF 함수에 입력하여 나온 출력을 다음 리더를 정할 때 사용하는 방식을 생각해보자.

Evaluate(SK_of_current_leader, prev_block_hash) = (Y, ⍴)

next_leader = Y % num_of_validators

여기서 Y는 현재의 리더만 계산할 수 있는 랜덤한 값이라 다른 노드들이 예측할 수 없다. 또한 다른 노드들은 Y 값이 리더가 마음대로 정한 값이 아니라 정해진 규칙에 의해 계산된 값임을 Verify 함수를 이용하여 검증할 수 있다.

하지만 이 방식은 문제를 완벽하게 해결하지 못한다. 모든 노드들이 거의 동시에 다음 리더가 누구인지 알게 되기 때문에 다음 리더가 블록을 제안하기 전에 DoS 공격을 할 수 있는 잠깐의 틈이 생긴다.  DoS 가능성을 완전히 차단하려면 다음 리더만 스스로 다음 리더라는 사실을 알 수 있고 다른 노드들은 다음 리더가 제안한 블록을 보고 나서야 다음 리더가 누구인지 알 수 있는 방식이어야 한다.  이러한 일을 가능케 하는 VRF를 이용한 암호학적 추첨(cryptographic sortition)에 대해서는 다음 글에서 자세히 설명하겠다.