Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BLS verification?

Question

I asked this in the Ethereum StackExchange yesterday but I figured it would be more appropriate to ask it here.

I am looking into implementing some operations for the BLS signature scheme in Solidity, using the new precompiled contracts for pairing operations released with Ethereum Byzantium, but I am not sure whether it is possible.

---

According to the BLS paper, page 310, to verify a BLS signature $s \in F_q$ corresponding to public key $V \in G_2$ and message $M$:

1. Find $y \in F_q$ with $\sigma = (s, y)$.
2. Compute $R \leftarrow MapToGroup(M) \in G_1$.
3. Test if either $e(\sigma, Q) = e(R, V)$ or $e(\sigma, Q)^{-1} = e(R, V)$.

---

Ethereum has added a few precompiled contracts for operations on the bn128 curve:

1. Addition
2. Scalar multiplication
3. Pairing check: Given an input $(a_1, b_1, a_2, b_2, \cdots, a_k, b_k) \in (G_1 \times G_2)^k$, returns whether $log_{P_1}(a_1) \cdot log_{P_2}(b_1) + \cdots + log_{P_1}(a_k) \cdot log_{P_2}(b_k) = 0$ (in $F_q$)

---

Supposing we have $R$ and $\sigma$, is step 3 possible using the precompiled contracts (with other Solidity functionality)? I am not sure I can find a formulation since there is no implementation for evaluating the pairing function $e$ itself.

Answer 1

Let $P_1$ be generator of $G_1$ and $P_2$ generator of $G_2$. Let $f:(G_1 \times G_2)^k\rightarrow\{0,1\}$ be Ethereum pairing check operation.

Given $\sigma,R \in G_1$ and $V\in G_2$ it is possible to check if $e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)$ is true with Ethereum built-in operations, you just check check whether:

• $f(\sigma, P_2, -R, V)$ is true or
• $f(\sigma, P_2, R, V)$ is true

Why this works:

• Let $\sigma=sP_1, R=rP_1, V=vP_2$. So $s=log_{P_1}(\sigma),r=log_{P_1}(R)$ and $v=log_{P_2}(V)$. Also please note that $\forall i\in\{1,2\}\forall a\in G_i:(-a)P_i=-(aP_i)$ and from that $-log_{P_i}(aP_i)=log_{P_i}(-aP_i)$
• $e(\sigma, P_2)=e(sP_1, P_2)=e(P_1,P_2)^s$
• $e(R,V)=e(rP_1, vP_2)=e(P_1, P_2)^{rv}$
• $e(R,V)^{-1}=e(rP_1, vP_2)^{-1}=e(P_1, P_2)^{-rv}$
• $e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff s=rv \vee s=-rv$
• $s=rv \vee s=-rv \iff s-rv=0 \vee s+rv=0$
• $s-rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-R)log_{P_2}(V) = f(\sigma, P_2, -R, V)$
• $s+rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(R)log_{P_2}(V)= f(\sigma, P_2, R, V)$
• $s-rv=0 \vee s+rv=0 \iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$
• $e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$

Said that, the paper you're citing is based on symmetric (type-1) pairing. In ethereum BN curve is used in asymmetric (type-3) setting so you have to use version of BLS that is adapted to that. Fortunately, there is one proved secure: BLS-3b on page 11 of https://eprint.iacr.org/2009/060.pdf. You have:

• private key $x\in F_q$
• public key $(W=P_1^x, X=P_2^x)$
• hash-to-point function: $H:\{0,1\}^*\rightarrow G_1$
• signature $\sigma=H(m)^x\in G_1$
• you verify using $e(\sigma, P_2)=e(H(m),X)$

Verification again can be done using Ethereum pairings:

• $e(\sigma, P_2)=e(H(m),X) \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-H(m))log_{P_2}(X)=0$
• $e(\sigma, P_2)=e(H(m),X) \iff f(\sigma, P_1, -H(m), X)$

Please note that $W$ is used neither in signing nor verification but is required for security proof. There is version without it (BLS-3), where public key is just $X=P_2^x$, but you can't construct proof with it even though assumption here is weaker than in BLS-3b.