Verifiable random function

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key (or verification key[1]), can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key.[2]

A verifiable random function can be viewed as a public-key analogue of a keyed cryptographic hash[2] and as a cryptographic commitment to an exponentially large number of seemingly random bits.[3] The concept of a verifiable random function is closely related to that of a verifiable unpredictable function (VUF), whose outputs are hard to predict but do not necessarily seem random.[3][4]

The concept of a VRF was introduced by Micali, Rabin, and Vadhan in 1999.[4][5] Since then, verifiable random functions have found widespread use in cryptocurrencies, as well as in proposals for protocol design and cybersecurity.

Constructions[edit]

In 1999, Micali, Rabin, and Vadhan introduced the concept of a VRF and proposed the first such one.[4] The original construction was rather inefficient: it first produces a verifiable unpredictable function, then uses a hard-core bit to transform it into a VRF; moreover, the inputs have to be mapped to primes in a complicated manner: namely, by using a prime sequence generator that generates primes with overwhelming probability using a probabilistic primality test.[3][4] The verifiable unpredictable function thus proposed, which is provably secure if a variant of the RSA problem is hard, is defined as follows: The public key PK is , where m is the product of two random primes, r is a number randomly selected from , coins is a randomly selected set of bits, and Q a function selected randomly from all polynomials of degree over the field . The secret key is . Given an input x and a secret key SK, the VUF uses the prime sequence generator to pick a corresponding prime (the generator requires auxiliary inputs Q and coins), and then computes and outputs , which is easily done by knowledge of .[4]

In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy.[3][6] When the input is from a small domain (the authors then extend it to a larger domain), the function can be defined as follows:

where e(·,·) is a bilinear map. To verify whether was computed correctly or not, one can check if and .[3][6] To extend this to a larger domain, the authors use a tree construction and a universal hash function.[3] This is secure if it is hard to break the "q-Diffie-Helman inversion assumption", which states that no algorithm given can compute , and the "q-decisional bilinear Diffie-Helman inversion assumption", which states that it is impossible for an efficient algorithm given as input to distinguish from random, in the group .[3][6]

In 2015, Hofheinz and Jager constructed a VRF which is provably secure given any member of the "(n − 1)-linear assumption family", which includes the decision linear assumption.[7] This is the first such VRF constructed that does not depend on a "Q-type complexity assumption".[7]

In 2019, Bitansky showed that VRFs exist if non-interactive witness-indistinguishable proofs (that is, weaker versions of non-interactive zero-knowledge proofs for NP problems that only hide the witness that the prover uses[1][8]), non-interactive cryptographic commitments, and single-key constrained pseudorandom functions (that is, pseudorandom functions that only allow the user to evaluate the function with a preset constrained subset of possible inputs[9]) also do.[1]

In 2020, Esgin et al. proposed a post-quantum secure VRF based on lattice-based cryptography.[10]

Uses and applications[edit]

VRFs provide deterministic pre-commitments for low entropy inputs which must be resistant to brute-force pre-image attacks.[11][better source needed] VRFs can be used for defense against offline enumeration attacks (such as dictionary attacks) on data stored in hash-based data structures.[2]

In protocol design[edit]

VRFs have been used to make:

  • Resettable zero-knowledge proofs (i.e. one that remains zero-knowledge even if a malicious verifier is allowed to reset the honest prover and query it again[12]) with three rounds in the bare model[3][7]
  • Non-interactive lottery systems[3][7]
  • Verifiable transaction escrow schemes[3][7]
  • Updatable zero-knowledge databases[7]
  • E-cash[7]

VRFs can also be used to implement random oracles.[13]

In Internet security[edit]

DNSSEC is a system that prevents attackers from tampering with Domain Name System messages, but it also suffers from the vulnerability of zone enumeration. The proposed NSEC5 system, which uses VRFs[how?], provably prevents this type of attack.[14][importance?]

In cryptocurrency[edit]

Cardano and Polkadot implement VRFs for block production.[15][16]

The Internet Computer cryptocurrency uses a VRF to produce a decentralized random beacon whose output is unpredictable to anyone until they become available to everyone.[17] More precisely, its protocol allows clients to agree on a VRF (i.e. a commitment to a deterministic pseudorandom sequence) and to produce one new output thereof every round by using threshold signatures and distributed key generation.[17]

Algorand uses VRFs to perform cryptographic sortition.[18][19] In this platform, every block produces a new random selection seed, and a user secretly checks whether they were selected to participate in the consensus protocol by evaluating a VRF with their secret participation key and the selection seed.[18] (This also produces a proof, which the user can send to anyone to show that they have been selected to participate.[18]) Thusly, accounts are selected to propose blocks for a given round.[18] In this manner, VRFs prevent users from gaining staking advantages by registering multiple accounts.[5] The particular VRF that Algorand uses is based on elliptic-curve cryptography, specifically Curve25519;[10] proposed by Sharon Goldberg, Moni Naor, Dimitris Papadopoulos, Leonid Reyzin, and Jan Včelák, the function is currently undergoing standardization as an IETF Internet Draft.[19][20] Algorand's own implementation of this function has been open-source since October 2018.[19]

VRFs based on elliptic curve cryptography have been implemented in the programming language Solidity.[21][importance?]

In May 2020, Chainlink announced that it launched Chainlink VRF, a service that uses verifiable random functions to generate verifiable randomness on-chain.[22] To use Chainlink VRF, a smart contract supplies a seed (which should be unpredictable to the oracles to whom it is provided), and the seed in turn is used to generate a random number that is sent back to the contract; this is published on-chain along with a proof and verified using the oracle's public key and the application's seed.[22] Each oracle, when generating randomness, uses its own secret key.[22]

In July 2021, Harmony, a cryptocurrency project that bridges between blockchains[how?], and Oraichain, a cryptocurrency project involving artificial intelligence,[how?] announced that they had introduced VRFs[how?].[23][24]

References[edit]

  1. ^ a b c Bitansky, Nir (2020-04-01). "Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs". Journal of Cryptology. 33 (2): 459–493. doi:10.1007/s00145-019-09331-1. ISSN 1432-1378.
  2. ^ a b c Goldberg, Sharon; Vcelak, Jan; Papadopoulos, Dimitrios; Reyzin, Leonid (5 March 2018). Verifiable Random Functions (VRFs) (PDF) (Technical report). Retrieved 15 August 2021.
  3. ^ a b c d e f g h i j Dodis, Yevgeniy; Yampolskiy, Aleksandr (16 November 2004). "A Verifiable Random Function With Short Proofs and Keys" (PDF). 8th International Workshop on Theory and Practice in Public Key Cryptography. International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg (published 2005). pp. 416–431. ISBN 978-3-540-30580-4. Retrieved 26 August 2021.
  4. ^ a b c d e Micali, Silvio; Rabin, Michael O.; Vadhan, Salil P. (1999). "Verifiable random functions" (PDF). Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. 40th Annual Symposium on Foundations of Computer Science. pp. 120–130. doi:10.1109/SFFCS.1999.814584. ISBN 0-7695-0409-4.
  5. ^ a b Potter, John (9 September 2021). "How Can Value Investors Profit in the Crypto Ecosystem?". finance.yahoo.com. Retrieved 19 September 2021.{{cite web}}: CS1 maint: url-status (link)
  6. ^ a b c Nountu, Thierry Mefenza (28 November 2017). Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures (Thèse de doctorat thesis).
  7. ^ a b c d e f g Hofheinz, Dennis; Jager, Tibor (30 October 2015). Verifiable Random Functions from Standard Assumptions. Theory of Cryptography Conference (published 19 December 2015). pp. 336–362. doi:10.1007/978-3-662-49096-9_14. ISBN 978-3-662-49096-9.
  8. ^ Barak, Boaz; Ong, Shien Jin; Vadhan, Salil (2007-01-01). "Derandomization in Cryptography" (PDF). SIAM Journal on Computing. 37 (2): 380–400. doi:10.1137/050641958. ISSN 0097-5397. Retrieved 2 September 2021.
  9. ^ Boneh, Dan; Waters, Brent (2013). Sako, Kazue; Sarkar, Palash (eds.). "Constrained Pseudorandom Functions and Their Applications". Advances in Cryptology - ASIACRYPT 2013. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 280–300. doi:10.1007/978-3-642-42045-0_15. ISBN 978-3-642-42045-0. Retrieved 2 September 2021.
  10. ^ a b Esgin, Muhammed F.; Kuchta, Veronika; Sakzad, Amin; Steinfeld, Ron; Zhang, Zhenfei; Sun, Shifeng; Chu, Shumo (24 March 2021). "Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand". Cryptology ePrint Archive. Retrieved 26 August 2021.
  11. ^ Schorn, Eric (2020-02-24). "Reviewing Verifiable Random Functions". NCC Group Research. Retrieved 2021-09-04.
  12. ^ Micali, Silvio; Reyzin, Leonid (2001). Kilian, Joe (ed.). "Soundness in the Public-Key Model". Advances in Cryptology — CRYPTO 2001. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 542–565. doi:10.1007/3-540-44647-8_32. ISBN 978-3-540-44647-7.
  13. ^ Dodis, Yevgeniy (2002). Desmedt, Yvo G. (ed.). "Efficient Construction of (Distributed) Verifiable Random Functions". Public Key Cryptography — PKC 2003. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 1–17. doi:10.1007/3-540-36288-6_1. ISBN 978-3-540-36288-3.
  14. ^ Goldberg, Sharon. "NSEC5: Provably Preventing DNSSEC Zone Enumeration". www.cs.bu.edu. Retrieved 2021-08-26.
  15. ^ "Ouroboros Protocol - Stake pool course". cardano-foundation.gitbook.io. 2021. Archived from the original on 11 March 2021. Retrieved 4 September 2021.
  16. ^ "Randomness · Polkadot Wiki". wiki.polkadot.network. 14 August 2021. Retrieved 4 September 2021.{{cite web}}: CS1 maint: url-status (link)
  17. ^ a b Hanke, Timo; Movahedi, Mahnush; Williams, Dominic (23 January 2018). "DFINITY Technology Overview Series Consensus System" (PDF). dfinity.org. Archived (PDF) from the original on 8 May 2018. Retrieved 19 August 2021.
  18. ^ a b c d "Algorand Protocol Overview". www.algorand.com. Retrieved 2021-08-15.
  19. ^ a b c Gorbunov, Sergey; Reyzin, L.; Papadopoulos, D.; Vcelak, J. (9 October 2018). "Algorand Releases First Open-Source Code of Verifiable Random Function". www.algorand.com. Retrieved 2021-08-15.{{cite web}}: CS1 maint: url-status (link)
  20. ^ Goldberg, S.; Reyzin, L.; Papadopoulos, D.; Vcelak, J. (17 May 2021). "draft-irtf-cfrg-vrf-09". datatracker.ietf.org. Retrieved 4 September 2021.{{cite web}}: CS1 maint: url-status (link)
  21. ^ "GitHub - witnet/vrf-solidity: Verifiable Random Function (VRF) library written in Solidity". GitHub. Retrieved 2021-08-26.
  22. ^ a b c "Verifiable Randomness for Blockchain Smart Contracts". Chainlink Blog. 12 May 2020. Retrieved 15 August 2020.{{cite web}}: CS1 maint: url-status (link)
  23. ^ Lan, Rongjian (2021-07-09). "Introducing Harmony Verifiable Random Function (VRF)". Medium. Retrieved 2021-09-04.
  24. ^ Oraichain (16 July 2021). "Introducing VRF — Verifiable Random Function on Oraichain Mainnet". Medium. Retrieved 4 September 2021.{{cite web}}: CS1 maint: url-status (link)