1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.