Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BLS verification? 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$: 


Find $y \in F_q$ with $\sigma = (s, y)$.
Compute $R \leftarrow MapToGroup(M) \in G_1$.
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: 


Addition
Scalar multiplication
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.
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.