  A verifiable random function (VRF in short) is a powerful pseudo-random
function that provides a non-interactively public verifiable proof for the
correctness of its output. Recently, VRFs have found essential applications in
blockchain design, such as random beacons and proof-of-stake consensus
protocols. To our knowledge, the first generation of blockchain systems used
inherently inefficient proof-of-work consensuses, and the research community
tried to achieve the same properties by proposing proof-of-stake schemes where
resource-intensive proof-of-work is emulated by cryptographic constructions.
Unfortunately, those most discussed proof-of-stake consensuses (e.g., Algorand
and Ouroborous family) are not future-proof because the building blocks are
secure only under the classical hard assumptions; in particular, their designs
ignore the advent of quantum computing and its implications. In this paper, we
propose a generic compiler to obtain the post-quantum VRF from the simple VRF
solution using symmetric-key primitives (e.g., non-interactive zero-knowledge
system) with an intrinsic property of quantum-secure. Our novel solution is
realized via two efficient zero-knowledge systems ZKBoo and ZKB++,
respectively, to validate the compiler correctness. Our proof-of-concept
implementation indicates that even today, the overheads introduced by our
solution are acceptable in real-world deployments. We also demonstrate
potential applications of a quantum-secure VRF, such as quantum-secure
decentralized random beacon and lottery-based proof of stake consensus
blockchain protocol.
