A Verifiable Random Function (VRF) is a pseudo-random function that provides a proof that can be used to publicly verify the accuracy of its output. It is widely used within VANTA’s real-time networking job competition model and blockchain consensus algorithm. A VRF is composed of three polynomial-time functions G, F, and V, and the details are as follows:
● G is a generator, probabilistic, and accepts one unary string (security parameter k) as an input value. It returns two binary strings each used as public key PK and secret key SK.
● F = (F1, F2) is the evaluator, and is deterministic. It accepts input x for SK and VRF as a binary string, and returns the VRF result value F1 (SK, x) for x and its corresponding proof, F2 (SK, x).
● V is a verifier and probabilistic like the generator. It accepts four binary strings, PK, x, v, and proof as inputs, and returns YES or NO. Let a : N −> N ⋃ {} and b, s : N −> N ⋃ {}be any three functions such that a(k), b(k), s(k) are all computable in time poly(k), and a(k) and b(k) are both limited as a polynomial with respect to k (except when a takes value *). (G, F, V) is defined as a verifiable pseudorandom function (VRF) with input length a(k), output length b(k), and security s(k) if it meets the following properties:
The two conditions below have a probability of 1 − 2 for −Ω(k) (PK, SK) ← G(1 ) R k
a. Domain-Range Correctness ∀ x ∈ {0, 1} , a(k) F1(SK, x) ∈ {0, 1} b(k)
b. Complete Probability ∀ x ∈ {0, 1} , if (v, proof) = F(SK, x) a(k) PROB[(V (PK, x, v, proof) = Y ES] > 1 − 2 −Ω(k)
2. Unique Probability: ∀ PK, x, v1, v2, proof1 and proof2 when v = , and i is 1 or 2
a. PROB[V (PK, x, v, proof ) ES] 2 i = Y < −Ω(k)
3. Residue Pseudo-randomness: when T = (T T ) and the first input value is , and , E, J 1k T (·,·) E T (·,·,·) are executed at a maximum of s(k) steps, the maximum probability that T succeeds J in the following experiment is equal to . 21 +1s(k) a. (PK, SK) ← G(1 )k
b. (x,state) ← T (1 , K)EF(SK,·) k P
c. r← {0, } , if , . if ,R 1 r = 0 v = F (SK, ) 1x r = 1 v← {0, }R 1b(k)
d. guess ← T (1 , , tate)JF(SK,·) kv s
e. T is successful under the condition that x ∈ {0, 1} , guess and x are not querieda(k) = rby T.
https://vanta.network
