Unveiling the zkRand Demo

The research in this article is provided by Enya Labs as part of their contributions to Boba Network. Written By: Jia Liu

In our previous article, we introduced a distributed randomness beacon, now referred to as zkRand, built from threshold cryptography, zkSNARKs, and BLS signatures. Today, we are unveiling our first demonstration to showcase the system’s end-to-end workflow.

Our zkRand has many applications in decentralized networks, such as verifiable lotteries and leader election in distributed consensus protocols. Let’s briefly recap what our zkRand does. zkRand is a $t$-out-of-$n$ threshold protocol that enables $n$ distributed members to collaboratively create random outputs. The random outputs are guaranteed to meet the following security properties:

• Public verifiability: A cryptographic proof can be verified by anyone to ensure that the pseudorandom value $v$ is accurately computed. There’s no need to rely on any party to produce the random value honestly.
• Pseudo-randomness: the distribution of $v$ is indistinguishable from random. No one can predicate the value of $v$ before it’s created, nor can anyone manipulate the value of $v$ for their benefit.
• Uniqueness: the output pseudorandom value $v$ is deterministic for a given public input $x$. Uniqueness is essential for certain decentralized applications, such as selecting the next block proposer or the next set of validators in a consensus protocol. Uniqueness guarantees a deterministic choice for the next block, and without it, the blockchain will fork and fail to reach consensus.

Our zkRand protocol consists of two main components:

• Non-interactive distributed key generation (NI-DKG): This key setup process is run among $n$ members. The goal is to establish global public parameters, which includes a global public key $gpk$ and a set of verification keys $vk_1, vk_2, …, vk_n$. Each member $i$ contributes to the randomness of the global public parameters by creating a pair $(pp_i, zk_i)$, where $pp_i$ is a public parameter sampled by the member and $zk_i$ is the zero knowledge proof demonstrating that $pp_i$ is correctly generated. Once the process concludes, anyone can derive $(gpk, vk_1, …, vk_n)$ from the published $(pp_1, pp_2, …, pp_n)$. Each member $i$ is able to derive a secret share $sk_i$ that corresponds to its verification key $vk_i$. The term ‘non-interactive’ signifies that members send only one message, eliminating the need for multiple message exchanges, which simplifies the protocol’s practical implementation. We use zk-SNARKs for $zk_i$ to guarantee the validity of $pp_i$ generated by each participant. If any $zk_i$ is invalid, $pp_i$ will not be included in the generation of the global public parameters. A lower bound $m$, with $t< m\leq n$, can be established for accepting the NI-DKG as successful, i.e., when the number of valid $\{pp_i\}_i$ is at least $m$. Note that each member $i$ will obtain a pair $(vk_i, sk_i)$ regardless of whether their $pp_i$ is valid or not.
• Randomness generation: Once the keys are set up, members can collaborate to compute pseudorandom values over multiple rounds. Each round is uniquely identified by a public input $x$, such as a timestamp or counter. Each member $i$ computes a partial evaluation $\sigma_i$ and a proof $\pi_i$ on the input $x$ using its secret share $sk_i$. A threshold number of these partial evaluations $\{(\sigma_i, \pi_i)\}_i$ can be combined to produce the final pseudorandom value $v$ and a proof $\pi$ which can be verified by checking if $\text{verify}(x, v, \pi, gpk) = 1$ using the global public key $gpk$. The combination process doesn’t require any secret information and thus can be performed by any party. The pseudorandom output $v$ is deterministic for each public input $x$, meaning only one value of $v$ will pass the verification equation. However, the value remains unpredictable until it is created. This process can be repeated to generate more random outputs by updating $x$ with a different input.

In our demo, we use smart contracts to coordinate the computation of the above components. The contract stores and verifies all the public parameters, partial evaluations and final pseudorandom values. The main contract that puts together everything is contracts/zkdvrf.sol. Our demo follows the workflow below:

In the demo, we set $(t,n) = (3, 5)$, i.e., 5 members with a threshold of 3. An operator deploys the contract and includes the addresses of all members in the contract to facilitate their participation. Each member registers on the contract by providing their member public key, generated on the Grumpkin curve. These public keys are used in the subsequent NI-DKG protocol.

Once all the members register, the operator initiates the NI-DKG process. Each member creates $(pp_i, zk_i)$ and submits it to the contract by calling the function submitPublicParams(uint256[] calldata pp, bytes calldata zkProof). Once all the members submit, the operator marks NI-DKG as complete and retrieves the public parameters from the contract to compute $gpk$ off-chain. The operator can then call the contract function computeVk(Pairing.G2Point calldata gpk) to compute the verification keys $(vk_1, ..., vk_n)$ and verify $gpk$ onchain.

Next, the operator begins the randomness generation process by initiating the value of public input $x$. In the demo, we use block.timestamp as public inputs, but this will be replacd with something more predicable like a counter in the future in order to enable applications to refer to a random using its corresponding public input before the random is created. Each member computes a partial evaluation on $x$ and a proof and submits the data to the contract using submitPartialEval(IPseudoRand.PartialEval memory pEval). When $t=3$ partial evaluations are submitted, the operator retrieves the evaluations from the contract and combines them into the final pseudorandom value $v$ with a proof $\pi$. Regardless of which $t$ members submit the partial evaluations, the result of $(v, \pi)$ remains the same. The combination process is linear of $t$ and is performed offchain. The operator then submits $(v,\pi)$ to the contract by calling submitRandom(IPseudoRand.PseudoRandom memory pseudo). This function verifies and stores $(v,\pi)$ which can be used by other applications like gaming, lotteries, and so on.

The step-by-step instructions to run our demo are available here: https://github.com/bobanetwork/zkdvrf/blob/main/README.md#running-the-demo.

References:

[1] https://bobanetwork.medium.com/distributed-randomness-beacon-d3a7d39c9f45