# Drand Quicknet Verification

## The Drand Quicknet Beacon

### Randomness Production via Threshold BLS Signatures
Drand [[1]](https://drand.love/docs/cryptography) is a distributed randomness beacon that periodically produces 'pulses' of verifiable randomness. It functions as a multiparty computation protocol (MPC) where workers, each members of a semi-trusted set of well-known signers called the "League of Entropy", produces BLS signatures using shares of a secret created through a distributed key generation mechanism. The beacon function in sequential, non-overlapping rounds whose identity is described by a monotonically increasing integer sequence, starting at 0. There are several flavors of drand beacons, however, our description focuses on the Drand "QuickNet" beacon, which uses $\mathbb{G}_1$ as the signature group and $\mathbb{G}_2$ as the public key group using curve BLS12-381. Note that the core optimization we make is in regard to signature verification in this model.

### Beacon Production (Signing Phase)

The idea is to use threshold secret sharing to produce shares known to League of Entropy nodes such that given at least a threshold of signatures on some message $M$, we can obtain a signature on $M$ that can be verified with the beacon's master public key (i.e. the public key $pk = f(0) \cdot G \in \mathbb{G}_2$ where $f$ is the polynomial used to share the secret and $G$ is a generator).

To provide a introductory version, let's simply consider Shamir's secret sharing, where for some $sk \xleftarrow{R} \mathbb{Z}_p^*$ and $f(x) = sk + a_1 x + ... + a_tx^t$ where $0 < t \leq n$, each node has a share $u_i := f(i)$. Let $H: \{0, 1\}^* \to \{0, 1\}^d$ be a cryptographic hash function for some $d > 0$ (e.g. usually 32 in practice) and $H_1: \{0, 1\}^* \to \mathbb{G}_1$ a hash-to-G1 function.

Given a set of nodes $\{W_1, ..., W_n\}$ who each output $\sigma_i = sk_i \cdot H_1(r)$ for a round number $r$, we obtain a signature $\sigma$ on $pk = sk \cdot G$ by interpolating the signatures: $\sigma = \sum_{i \in [k]} \lambda_i \cdot \sigma_i$ where $m \leq k \leq n \in \mathbb{G}_1$ and each $\lambda_i = \prod_{j \in [k]\setminus \{i\}} \frac{-x_j}{x_j - x_i}$ is a Lagrange coefficient for the polynomial $f$ evaluated at $0$.

A **pulse** is then output as $\{\sigma, H(\sigma), r\}$

### Pulse Verification

We can verify the signature by comparing the pairings:

$e(\sigma, g2) == e(Q, pk)$

where $Q = H_1(roundNumber)$, $\sigma$ is the round signature, $g_2$ is a generator of the $\mathbb{G}_2$ group, and $pk$ in the public key associated with the beacon. This works since:

$e(\sigma, g2) = e(sk \cdot Q, g2) = e(Q, sk \cdot g2) = e(Q, pk)$

We note that this can be optimized by computing a multi miller loop and taking its final exponentation, as in [[2]](https://github.com/noislabs/drand-verify/blob/9a760444f1981604c9cbbfaf59b18df70a4168ad/src/verify.rs#L307).

## Multi-Pulse Verification

We now investigate the scenario where we want to verify multiple pulses from drand (for which we know the corresponding round numbers) that need to be verified. The cost of verifying pulses scales linearly with the number of pulses. We can instead aggregate the pulses to more efficiently verify them. However, note that this equality will fail if any single value is incorrect and it will not allow for easy identification of the offending pulse. In order to identify specific invalid signatures in the worst case scenario each siganture must be checked.

Let $\sigma_1, ..., \sigma_m$ be an ordered collection of signatures contained in pulses output from the beacon, where each $\sigma_i$ was output in a round $r_i$ and for any $i < j$, $r_i < r_j$. For each $i$, $\sigma_i = sk * H(r_i)$.

Let $Q = \sum_i H(r_i)$ and $\sigma = \sum_i \sigma_i$. Then we can verify the correctness of the aggregated signature by checking the pairings in the same way as above:

$e(\sigma, g2) == e(Q, pk)$