# Efficient threshold BLS & Encryption

*This post explains an inherent tension between threshold BLS signature and Elgamal encryption for onchain verification, and then presents a way to augment such threshold network such that a smart contract can efficiently verify a signature and decrypt/verify encryption onchain.*

*21/03/23, Nicolas Gailly, [Cryptonet team](https://cryptonet.org), [Protocol Labs](https://protocol.ai).*

## Introduction

For encryption/decryption and signing, we (usually) require a group, i.e. a single elliptic curve. However, using pairings, we have to choose between $\mathbb{G_1}$ and $\mathbb{G_2}$ (and even $\mathbb{G_t}$), each group have their pros and cons depending on the cryptographic protocol we want to use. In practice, $\mathbb{G_1}$ is usually preferred given it is much shorter and faster to compute in it, than its counter-parties.

This choice of group comes up when designing threshold networks. Indeed, there is a distributed key lying in a group $\mathbb{G}$ which could be any of the three groups aforementioned. In particular, when using pairing equipped curves, a threshold network can be used to create threshold BLS signatures but it can also be used as a decryption oracle. In the latter, users encrypts towards the threshold network and push the encryption on-chain.

This posts shows the pros and cons of using $\mathbb{G_1}$ and $\mathbb{G_2}$ for each and shows there is a tension between the two. This posts then shows a simple solution to get the best of both worlds. The technique is heavily inspired by a post by Kobi Gurkan on efficient [multisignature verification onchain](https://geometry.xyz/notebook/Optimized-BLS-multisignatures-on-EVM), translated to the threshold setting.

## Reminder on the cryptographic schemes

### BLS Signatures

There are many references on the web that will explain BLS signatures. [This post](https://xn--2-umb.com/22/bls-signatures/) by Remco Bloemen is one of them!

**Workflow**: user creates a signature and push it onchain. The smart contract will verify the validity of this signature.

### Hashed El Gamal

For succinctness and simplicity, we present this CCA version of El Gamal encryption scheme. Note that are many versions and also IBE based encryption scheme (such as the one used for [timelock encryption](https://eprint.iacr.org/2023/189.pdf)), that will expose the same problem laid in this post.

**Workflow**: a user encrypts a message, and push it onchain. The smart contract will verify the “validity” of this ciphertext.

Assume we have a generic group $\mathbb{G}$, then

- Encryption of msg *m* is happening on $\mathbb{G}$ bundled with a DLEQ proof $\pi_{\mathbb{G}}$ (such as the one used in [Privacy Pass by Cloudflare](https://blog.cloudflare.com/privacy-pass-the-math/)) lying in group $\mathbb{G}$.
- $\{rG, H(rP) \oplus m, \pi_{\mathbb{G}}\}$
* Verification of the correctness of the ciphertext involves verifying the DLEQ proof using group operations on $G$. We do not show it here for succinctness.
* **Verification of this proof is done on the smart contract !**

*Purpose of the DLEQ proof*:
- **CCA security**: and more informally, to prove the author of the ciphertext really created it, i.e. that he knows the secret random scalar $r$ used for encryption.
- **Replay protection**: because we can embed a public identifier of the author inside the DLEQ transcript, it is not possible for anyone else to submit the same ciphertext.

## Distributed Key Generation

Such protocol is used to generate a distributed private key, such that each node has a share of it, but no one individually can recover the private key. The public key is known. The set of all nodes can act as if it was a single entity. Let’s assume we have

- $n$ participants, with a threshold of $t$
- a distributed public key $P=xG \in \mathbb{G_1}$, with each node having a share $x_i\in\mathbb{F_r}$
- The “public share” can also be computed publicly $X_i=x_iG_1\in\mathbb{G_1}$

To recover the private key $x$, the network would need to come together and compute:

$$
x = \sum_t L_i(0) x_i
$$

where $L_i(0)$ is the i-th Lagrange polynomial over this set evaluated at point 0.

We invite you to read for example the [documentation of drand](https://drand.love/docs/cryptography/) that explains in depth how this all works.

## Pubkey in $\mathbb{G_1}$, Signature in $\mathbb{G_2}$

- Threshold network public key $P=xG_1$
- Encryption to threshold network: $\{rG_1, H(rP) \oplus  m, \pi_{\mathbb{G_1}}\}$
- BLS signature *σ* verification from network:
- $e(P,H_2(m)) == e(G_1,\sigma)$ where $\sigma = xH_2(m) \in \mathbb{G_2}$
- This is *computed on the smart contract* !

In this situation, the trade off is as follow:

- 🚀 **DLEQ proof verification is FAST** because only group operations in $\mathbb{G_1}$ are involved.
- ⌛ **BLS signature verification is SLOW** because of the the hash-to-curve $H_2(m)$ operations which requires to handle operations in $\mathbb{F_{q^2}}$. This is especially relevant in context of blockchain where smart contract operations are usually costly.

## Pubkey in $\mathbb{G_2}$, Signature in $\mathbb{G_1}$

- Threshold network public key $P=xG_2$
- Encryption to threshold network: $\{rG_2, H(rP) \oplus m, \pi_{\mathbb{G_2}}\}$
- BLS signature *σ* verification from network:
- $e(H_1(m),P) == e(\sigma,G_2)$ where $\sigma = xH_1(m) \in \mathbb{G_1}$

In this situation, the trade off is on the *************opposite side*************:

- ⌛ **DLEQ verification is SLOW** because group operations in $\mathbb{G_2}$ are involved. It is especially relevant in the context of blockchain where we want to verify this DLEQ proof onchain.
- 🚀 **BLS signature verification is FAST** because the hash-to-curve operation $H_1(m)$ is fast, as it only involves $\mathbb{F_q}$ operations.

## Goal
**We want the best of both worlds**:

- “Encryption to public key”, especially the DLEQ proof, to lie on $\mathbb{G_1}$ to get cheap decryption/verification
- “Signature public key” on $\mathbb{G_2}$ to get cheap signature verification
- Still having the *same* “secret key” behind

The end user now have to use the corresponding key depending on which protocol he needs.

*Why not two separate network/keys then?*

We could simply have two threshold networks, one with a key on $\mathbb{G_1}$ and one with a key on $\mathbb{G_2}$. Unfortunately, this brings its lot of problems too.
- First and foremost, the two networks may not have the *same* participants (this is due to the distributed key generation protocol, that may evict some bad players during the execution). In threshold networks, one critical property is the majority assumption therefore, you need to know both network have the same composition to trust both all together are secure, to treat it as “one network”.
- Related to that, it’s harder to maintain two networks than one, and even harder to maintain them in sync. Each time there is a resharing (where membership changes), you might end up again in a situation where the membership are different in the two networks.
- It might be possible to implement a DKG that operate on the same secret, on both groups, at the same time, but this does not exist to my knowledge so far. The scheme described below is far more simpler than a full blownup DKG.

**In the following solution** each node only need to keep the same secret share, but express the public distributed key differently according to the operation to use. That allows us to *keep the same trust assumption for the system.* The nice thing about this solution is that it can be implemented on top of an already existing threshold network. No modification to the DKG protocol is required !

## Creating a $\mathbb{G_2}$ key from the $\mathbb{G_1}$ key
*The goal is to have a second public key $P’=xG_2 \in \mathbb{G_2}$, using the same share, representing the same secret key alongside* $P = xG_1 \in \mathbb{G_1}$ *!*

The network must perform the following steps (off chain):

1. Each node creates its symmetrical version of its public share on $\mathbb{G_2}$ and broadcasts it:
1. $X_{i}' = x_iG_2\in\mathbb{G_2}$
2. everyone (including third parties) can verify the validity of the new share using the following equations:

$$
(a)\; e(X_i,G_2) == e(G_1,X_i') \\ \Leftrightarrow \\ e(G_1,G_2)^{x_i} == e(G_1,G_2)^{x_i}
$$

1. The “public key in $\mathbb{G_2}$ can be recovered via regular Lagrange interpolation

$$
(b)\; P' = xG_2 = \sum_t L_i(0)X_i'
$$

**This key** $P’$ **can now be used for BLS signature on** $\mathbb{G_2}$ **!**

### Verification on chain of the equivalence

*How does the contract know what is the new* $P’$ *? How can he verify it is correct ?*

We assume the contract already knows the original distributed key *P*.
An aggregator that performs (*a*) and (*b*) can submit $P’$ on chain. Contract then only need to perform a simple pairing check

$$
e(P,G_2) == e(G_1,P')
$$

This works because both have the same dlog / secret key !

### Eviction of malicious node

*A node might not generate its second version of its share or give an invalid one. How do you attest of that fact to the smart contract so he can be slashed / excluded ?*

Given we now have “cheap” BLS signature, the threshold network (who have a majority of honest nodes) can “BLS sign” on the eviction of this node !

Another solution would for the contract to check equation (*a*) using the malicious node values but that might be more expensive to perform because the smart contract may not know $X_i$ in advance. Indeed, this requires evaluating the distributed public polynomial and this is linear in the threshold.

## Acknowledgements

Thanks to Rosario Gennaro for help on the proof sketch, and Kobi Gurkan for his post on the idea of translating between $\mathbb{G_1}$ and $\mathbb{G_2}$.

## Appendix: Proof Sketch

### Publishing keys in both group is safe

Assume we have groups $\mathbb{G}_1, \mathbb{G}_2,\mathbb{G}_T$ and a pairing function $e: \mathbb{G}_1 \times \mathbb{G}_2 \longrightarrow \mathbb{G}_T$

Let $P_1=xG_1 \in \mathbb{G}_1 \textrm{ and } P_2=xG_2 \in \mathbb{G}_2$

$P_2$ is the public key of a BLS signature scheme where a message $m$ is signed by first hashing it into $\mathbb{G_1}$ as $M = H(m)\in\mathbb{G_1}$ and the signature is computed as $S=xM\in\mathbb{G}_1$

The verification is $e(S,G_2)=e(M,P_2)$

$P_1$ is the public key of a Hashed ElGamal encryption scheme where the encryption of a message $m$ is computed as $(\alpha,\beta)$ with $\alpha=rG_1$ and $\beta=\hat{H}(rP_1) \oplus m$ together with a DLEQ proof $\pi$. Decryption is performed only if the proof holds and $m=\beta \oplus \hat{H}(x\alpha)$. The DLEQ proof provides another group element $\gamma=r\hat{G}_1$ and proves that $\log_{G_1}\alpha = \log_{\hat{G}_1}\gamma$.

Let’s assume the following problem is hard in $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$

> Given $P_1=xG_1,A=aG_1,P_2=xG_2 \textrm{ compute } B=(ax)G_1$
>

This is the ***Augmented Computational Diffie-Hellman problem*** in $\mathbb{G_1}$ where we account for the fact that $P_2$ is also known to the adversary.

The aCDH problem is what is needed to prove BLS in Asymmetric Pairings setting (see page 15 of [Boneh et al](http://cyber.biu.ac.il/wp-content/uploads/2017/01/Boneh-basics-of-pairings-4.pdf)).

### Using same secret key for both BLS and El Gamal is safe

We need to show that the simultaneous security of BLS (unforgeable under chosen message attack) and Hashed ElGamal (under chosen ciphertext attack).

Our simulator is given $P_1$, $A$, $P_2$ from the aCDH problem. It sets $P_2$ as the BLS public key, $P_1$ as the Hashed ElGamal public key and sets $\hat{G}_1=\lambda P_1$ for a random $\lambda$

When the adversary is given $P_1,P_2$ and asks for a signature on a message $m$ the simulator sets $M=H(m)=rG_1$ for a random $r$ and then the signature is $S=rP_1$.

If the adversary queries a ciphertext $(\alpha=rG_1,\beta,\gamma,\pi)$ to the decryptor, the simulator answers $\bot$if the proof is not valid. Otherwise we know that $\gamma=r\hat{G}_1=r \lambda P_1$ and therefore $rP_1=\lambda^{-1} \gamma$ and $m=\beta \oplus \hat{H}(\lambda^{-1} \gamma)$

On the message $\hat{m}$ that the adversary wants to forge (which is guessed at random by the simulator), the simulator sets $\hat{M}=H(\hat{m})=A$ then the signature output by the forger must be $\hat{S}=xA=B$ as desired.

If the adversary issues a “distinguishing query” on Hashed ElGamal by presenting two messages $m_0,m_1$, the simulator chooses $b \in \{0,1\}$ at random and encrypts $m_b$ as $(\alpha=A,\beta = \hat{r} \oplus m_b, \gamma, \pi)$ where $\hat{r}$ is a random string, $\gamma$ is a random group element and $\pi$ is a simulated proof that $\log_{G_1} \alpha = \log_{\hat{G}_1} \gamma$. Note that the simulator is implicitly defining $H(B)=\hat{r}$ in the above simulation (implicitly since it does not know $B$). If the adversary guesses $b$ with probability better than 1/2 it must have queried B to the random oracle. Note that the simulator can detect when B is queried since $e(A,P_2)=e(B,G_2)$ so when that queries happens it answers with $H(B)=\hat{r}$ and outputs B as the desired solution.