VDF

Verifiable Delay Function (commonly referred as VDF) are cryptographic function $f : \Chi \rightarrow Y$ that take a prescribed amount of time to compute. For every $x \in \Chi$ there is unique valid output $y \in Y$. However, verification is several orders of magnitudes faster to verify.

We refer as time a number of sequential operations that are performed on a single computing component. VDF are constructed such that, even when accessing a theoretically infinite amount a parallel computing power, VDF evaluation is only faster by an $\epsilon$ margin.

We use this construction in our work to ensure a user provided a given amount of work (varying according to the quantification of its behavior) for a low cost since no amount of parallel computing can benefit a user in this blockchain setting.

The VDF that interest us has been proposed by Wesolowski and is based on modular exponentiation in an RSA group. Find more info on Wesolowski, B. (2019, May). Efficient verifiable delay functions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 379-407). Springer, Cham.

Algorithms

VDF consist of a tuple of three algorithms:

Setup

Given a security parameter outputs the public parameters necessary for the computation and verification of VDF

Eval

Taking public parameters, a prescribed amount of time and a challenge $x$, computes a value $y$ and its verification proof $\pi$.

Verify

Given public parameters, value $y$ and the computation proof $\pi$, either accept that $y$ is the correct evaluation of the VDF for $x$ using the proof $\pi$.

Properties

To qualify, a VDF must satisfy three properties we will not describe formally:

• $\epsilon$-evaluation time, meaning that given an amount of time the function will run for this amount of time, with only an epsilon small margin.
• Sequentiality, no parallel algorithm, running on a machine with a lot of parallel computing capacity, runs significantly faster than the sequential algorithm using a single unit of computation.
• Uniqueness, for every input $x$ there exist a unique output $y$ that verifies.

Our usage

In our construction we incorporate a VDF as a consensus method. Working like a PoW lottery we use a lot less of computing power. More importantly, it rewards green behavior since the required computation time, as in number of sequential operations to perform in the Eval algorithm is biased in favor of more important green behavior. Using the quantifiable property of proofs of behavior we reduce the required time by a factor of this quantification. Yet, randomness in the lottery is still part of the equation, as we can see in the following equation, a hash function is used to both chain the preceding block but also provide randomness in the lottery.

This delay parameter is :

H_i = \frac{\delta \cdot H(\beta || \pi_m) } t = \frac{\delta \cdot H_i}_{\textsf{Quantify}(\pi_m)}

where δ is a difficulty parameter, $H(\cdot)$ is a cryptographic hash function.