Introduction

Verifiable randomness is critical in various applications, especially in cryptography and web3. (Pseudo)random numbers are routinely utilized to generate encryption keys and safeguard sensitive data, powering web3 in a way we know it. It is done to prevent the predictability of these keys, as their compromise could lead to a breach in the security of encrypted information.

The PowerAgent V2 design uses random Keepers’ selection for the same purpose as key generation - to ensure the unpredictability of the next Keeper assigned to execute a particular job. This approach significantly reduces potential attack vectors on the network, increasing its security. Here is our prior work, an overview of Keeper selection algorithms and known on-chain randomness sources: https://github.com/powerpool-finance/powerpool-research/blob/main/PowerPool_Keeper_selection_algorithms.pdf

On Ethereum and other PoS-consensus networks, such as Gnosis Chain randomness required for Keeper selection is derived from the prevrandao field submitted with each block. However, on networks lacking an Ethereum PoS consensus mechanism (e.g., Polygon, Arbitrum One, Optimism, and some other Ethereum rollups), the PowerAgent contract must connect to a secure and verifiable pseudorandom number generator (PRNG).

By developing its PRNG and proper on-chain verification, PowerPool DAO will be able to expand multi-chain and deploy PowerAgent on any EVM-compatible L1/L2/L3 network.

In this article, we will explore the system design, mathematical foundations, and implementation approach of the PowerPool VRF (verifiable random function) and its use as a source of randomness for PowerAgent and any third-party protocol.

PowerPool VRF’s algorithm is based on the “Making NSEC5 Practical for DNSSEC” 2017 paper by Dimitrios Papadopoulos, et al. paper (and consequently the RFC 9381 proposal https://datatracker.ietf.org/doc/rfc9381; a IETF proposal for standard VRF computation) with several measures to increase its efficiency.

Its architecture is split into an on-chain and an off-chain component:

The key property leveraged here is that the decisional Diffie-Hellman assumption holds in secp256k1. This means it is infeasible to distinguish between some random element in the group and an element produced by multiplying an extant element with a scalar (i.e., for known $a$ and $b$, $g^a*g^b$ looks random). Therefore, the desideratum is a group product with a specially produced compound scalar, and the proof is along the lines of Chaum-Pedersen (for generator base and base of generator product with one of component scalars). The algorithm proceeds in the following way:

Setup

During the setup, the group with hard DDHP (decisional Diffie-Hellman problem) G is chosen. RFC 9381 advises P-256 and Edwards25519 curves, but we employ the natively available on-chain secp256k1, since it is possible to do cheap ECMUL (elliptic curve multiplication) with secp256k1 on-chain (with the precision of 20 trailing bytes of the hash) by using ECRECOVER (EVM precompile for recovering a signer address from a digital signature), as outlined by V. Buterin in https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384:

Unfortunately, the secp256k1 precompile outputs the truncated hash of $Q$, and not $Q$ itself.

The group implies the following parameters:

1. Its generator

2. Its (prime) order

3. The order of the underlying Galois field

In addition, functions with the following signatures are agreed upon:

• $H_1:Z$→$G_{1}$

• $H_2:G$→ Z

Where $Z_{20}$ contains bytelength-20 integers. In particular, we take $H_3$ to be keccak256 with 20-byte truncation implied by ECRECOVER abuse, and $H_2$ to be regular keccak256.

For $H_1$, we take the fast (polylog in field size) hash-to-curve algorithm of 22480516.pdf (iacr.org). The algorithm consists of iteratively hashing the input with the public key and some linearly increasing nonce until the hash yields a valid candidate value of $x$, i.e., a value which, in case of secp256k1, has $x^3+7$ a quadratic residue in the underlying field. We pick the positive branch for $y$.

Proof generation

The proof is generated off-chain. The selection of the randomness submitter is planned to be implemented by registering an interval job with PowerAgent, wherein every so often, a submitter must refresh the entire random words pool. In this way, PowerAgent will automate its PRNG.

Algorithmically, the proof generation looks in the following way:

Let’s explain the steps:

• $x$ is a private key, corresponding to the public key PK.

• $a$ seeds the resultant random value; it may well be taken as non-uniform random and even a non-random value at the submitter’s discretion (though the latter will constitute a vulnerability for the submitter), since the on-chain randomness is produced by way of applying hash functions (modeling random oracles) and performing double group multiplication, where one of the multiplicands is set to be random (so the randomness and its uniform distribution are secured; the former - by the DDHA (decisional Diffie-Hellman assumption), the latter - by random oracle models of hash functions).

• $y$ is the seed for producing the random number on-chain; it can be seen that it is indistinguishable on-chain from a random value, since it is produced as $h^x$, where ℎ is a group point and therefore corresponds to group multiplication with some other scalar; therefore, knowledge of $g^x$ or $h$ does not disturb apparent randomness of the value thus begotten. *$k$ *and 

Proof verification

Proof verification will have been done on-chain at the time of submission.

As stated before, ECMUL can be restricted to trailing 20 bytes for reasons of ECRECOVER usage. The $u$ and $v$ are reminiscent of the Schnorr protocol and equal $g^k$, $h^k$ for correct proofs (which can be verified easily by simple arithmetic).

Randomness generation

When the source of randomness has been verified, the random number is generated simply by taking the hash of the $\gamma$ value.

The generalized nature of PowerPool VRF

PowerPool VRF can be used by any third-party protocol or dApp built on top of L1/L2/L3 network PowerAgent v2 is deployed.

Twitter | Discord | YouTube |Telegram | CMC Community | Debank | Medium

Introduction

Verifiable randomness is critical in various applications, especially in cryptography and web3. (Pseudo)random numbers are routinely utilized to generate encryption keys and safeguard sensitive data, powering web3 in a way we know it. It is done to prevent the predictability of these keys, as their compromise could lead to a breach in the security of encrypted information.

The PowerAgent V2 design uses random Keepers’ selection for the same purpose as key generation - to ensure the unpredictability of the next Keeper assigned to execute a particular job. This approach significantly reduces potential attack vectors on the network, increasing its security. Here is our prior work, an overview of Keeper selection algorithms and known on-chain randomness sources: https://github.com/powerpool-finance/powerpool-research/blob/main/PowerPool_Keeper_selection_algorithms.pdf

On Ethereum and other PoS-consensus networks, such as Gnosis Chain randomness required for Keeper selection is derived from the prevrandao field submitted with each block. However, on networks lacking an Ethereum PoS consensus mechanism (e.g., Polygon, Arbitrum One, Optimism, and some other Ethereum rollups), the PowerAgent contract must connect to a secure and verifiable pseudorandom number generator (PRNG).

By developing its PRNG and proper on-chain verification, PowerPool DAO will be able to expand multi-chain and deploy PowerAgent on any EVM-compatible L1/L2/L3 network.

In this article, we will explore the system design, mathematical foundations, and implementation approach of the PowerPool VRF (verifiable random function) and its use as a source of randomness for PowerAgent and any third-party protocol.

PowerPool VRF’s algorithm is based on the “Making NSEC5 Practical for DNSSEC” 2017 paper by Dimitrios Papadopoulos, et al. paper (and consequently the RFC 9381 proposal https://datatracker.ietf.org/doc/rfc9381; a IETF proposal for standard VRF computation) with several measures to increase its efficiency.

Its architecture is split into an on-chain and an off-chain component:

The key property leveraged here is that the decisional Diffie-Hellman assumption holds in secp256k1. This means it is infeasible to distinguish between some random element in the group and an element produced by multiplying an extant element with a scalar (i.e., for known $a$ and $b$, $g^a*g^b$ looks random). Therefore, the desideratum is a group product with a specially produced compound scalar, and the proof is along the lines of Chaum-Pedersen (for generator base and base of generator product with one of component scalars). The algorithm proceeds in the following way:

Setup

During the setup, the group with hard DDHP (decisional Diffie-Hellman problem) G is chosen. RFC 9381 advises P-256 and Edwards25519 curves, but we employ the natively available on-chain secp256k1, since it is possible to do cheap ECMUL (elliptic curve multiplication) with secp256k1 on-chain (with the precision of 20 trailing bytes of the hash) by using ECRECOVER (EVM precompile for recovering a signer address from a digital signature), as outlined by V. Buterin in https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384:

Unfortunately, the secp256k1 precompile outputs the truncated hash of $Q$, and not $Q$ itself.

The group implies the following parameters:

1. Its generator

2. Its (prime) order

3. The order of the underlying Galois field

In addition, functions with the following signatures are agreed upon:

• $H_1:Z$→$G_{1}$

• $H_2:G$→ Z

Where $Z_{20}$ contains bytelength-20 integers. In particular, we take $H_3$ to be keccak256 with 20-byte truncation implied by ECRECOVER abuse, and $H_2$ to be regular keccak256.

For $H_1$, we take the fast (polylog in field size) hash-to-curve algorithm of 22480516.pdf (iacr.org). The algorithm consists of iteratively hashing the input with the public key and some linearly increasing nonce until the hash yields a valid candidate value of $x$, i.e., a value which, in case of secp256k1, has $x^3+7$ a quadratic residue in the underlying field. We pick the positive branch for $y$.

Proof generation

The proof is generated off-chain. The selection of the randomness submitter is planned to be implemented by registering an interval job with PowerAgent, wherein every so often, a submitter must refresh the entire random words pool. In this way, PowerAgent will automate its PRNG.

Algorithmically, the proof generation looks in the following way:

Let’s explain the steps:

• $x$ is a private key, corresponding to the public key PK.

• $a$ seeds the resultant random value; it may well be taken as non-uniform random and even a non-random value at the submitter’s discretion (though the latter will constitute a vulnerability for the submitter), since the on-chain randomness is produced by way of applying hash functions (modeling random oracles) and performing double group multiplication, where one of the multiplicands is set to be random (so the randomness and its uniform distribution are secured; the former - by the DDHA (decisional Diffie-Hellman assumption), the latter - by random oracle models of hash functions).

• $y$ is the seed for producing the random number on-chain; it can be seen that it is indistinguishable on-chain from a random value, since it is produced as $h^x$, where ℎ is a group point and therefore corresponds to group multiplication with some other scalar; therefore, knowledge of $g^x$ or $h$ does not disturb apparent randomness of the value thus begotten. *$k$ *and 

Proof verification

Proof verification will have been done on-chain at the time of submission.

As stated before, ECMUL can be restricted to trailing 20 bytes for reasons of ECRECOVER usage. The $u$ and $v$ are reminiscent of the Schnorr protocol and equal $g^k$, $h^k$ for correct proofs (which can be verified easily by simple arithmetic).

Randomness generation

When the source of randomness has been verified, the random number is generated simply by taking the hash of the $\gamma$ value.

The generalized nature of PowerPool VRF

PowerPool VRF can be used by any third-party protocol or dApp built on top of L1/L2/L3 network PowerAgent v2 is deployed.

Twitter | Discord | YouTube |Telegram | CMC Community | Debank | Medium