Paper 2024/198

Distributed Randomness using Weighted VRFs

Sourav Das, University of Illinois at Urbana Champaign
Benny Pinkas, Aptos Labs, Bar-Ilan University
Alin Tomescu, Aptos Labs
Zhuolun Xiang, Aptos Labs

Generating and integrating shared randomness into a blockchain can expand applications and strengthen security. We aim to have validators generating blockchain randomness autonomously, and fresh shared randomness is generated for each block. We focus on proof-of-stake blockchains, where each validator has a different amount of stake (aka weight). Such chains introduce a weighted threshold setting where subset authorization relies on the cumulative weight of validators rather than the subset size. We introduce three cryptographic protocols to enable generating shared randomness in a weighted setting: A publicly verifiable secret sharing scheme (PVSS) which is weighted and aggregatable, a weighted distributed key generation protocol (DKG), and a weighted verifiable unpredictable function (VUF). Importantly, in the VUF protocol, which is the protocol that is run most frequently, the computation and communication costs of participants are independent of their weight. This feature is crucial for scalability. We implemented our schemes on top of Aptos blockchain, which is a proof-of-stake blockchain deployed in production. Our micro-benchmarks demonstrate that the signing and verification time, as well as the signature size, are independent of the total weight of the parties, whereas the signing time and signature size of the baseline (BLS with virtualization) increase significantly. For instance, our VUF reduces the signature size by factors of 7X and 34X for total weights of 821 and 4053, respectively. We also demonstrate the practicability of our design via an end-to-end evaluation.

Available format(s)
Cryptographic protocols
Publication info
Threshold cryptographypublicly verifiable secret sharingPVSSverifiable random functionVUFVRF
Contact author(s)
souravd2 @ illinois edu
benny @ pinkas net
tomescu alin @ gmail com
xiangzhuolun @ gmail com
2024-02-12: approved
2024-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sourav Das and Benny Pinkas and Alin Tomescu and Zhuolun Xiang},
      title = {Distributed Randomness using Weighted VRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2024/198},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.