Efficient threshold BLS & Encryption onchain

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.

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, translated to the threshold setting.

There are many references on the web that will explain BLS signatures. This post 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.

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), 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

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

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

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 that explains in depth how this all works.

In this situation, the trade off is as follow:

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

We want the best of both worlds:

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

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.

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):

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

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

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

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.

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}$.

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$

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).

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.