7

BGLS [1] is an aggregate signature scheme by Boneh et al., that allows aggregation of signatures on n different messages from n different signers. What I want to achieve is to verify such signatures in a smart contract.

Verification of a single signature (a BLS signature) is done through checking equality e(g1, σ) == e(v, h), where:

  • e : G1 x G2 -> GT is a bilinear pairing/mapping
  • g1 is a generator of G1
  • σ is the signature
  • v is the public key of the signer
  • h is the hash of the signed message

Using the new precompiled contract bn256Pairing introduced in Byzantium (and also bn256Add and bn256ScalarMul), we can check the equality and verify the signature.

Problem:
Now, to verify an aggregate signature, we need to compute:
e(g1, σ) == product of e(vi, hi) for all signers i
where vi and hi are the public key and hashed message of signer i.

This seems to be more difficult as we must actually calculate the pairings en multiply them before checking the equality. However, the precompiled contract only allows for checking equality. Also, I found an implementation on GitHub (Project-Arda/bgls-on-evm [2]), but it only seems capable of verifying single signatures.

Question:
Does anyone have a suggestion on how to verify this aggregate signature in Solidity?

Note: BGLS is originally not compatible with the type 3 pairings that are supported by Ethereum, but the scheme can be modified as suggested by Chatterjee et al. [3].

References:

Update (8 July 2018):

An example of how I verify BLS and BGLS signatures in Solidity is found at https://gist.github.com/BjornvdLaan/ca6dd4e3993e1ef392f363ec27fe74c4

Improve this question

1 Answer 1

Reset to default
4

I think this is actually just a notational issue. In the original paper the groups are written multiplicatively, while the groups in the Ethereum docs are written additively.

In particular, 

e(g1, σ) = e(g1, x1*h1+x2*h2+...) = x1*e(g1,h1) + x2*e(g1,h2)+...+xn*e(g1,hn)

Then you can do the check simply by using the n-ary pairing check

e(-g1, σ, v1, h1, v2, h2, ..., vn, hn)
Improve this answer
6
  • Hi Tjaden, thanks for your answer! I will try this in the coming days and either accept your answer or come back with comments.
    – Saffie
    Jun 17, 2018 at 20:23
  • I tested your solution for 2 and 3 signers, and it is working. Thanks a lot!
    – Saffie
    Jun 21, 2018 at 7:54
  • @Saffie, Do you know how to verify the BLS in etherum if the pairing is based on discrete logarithmic as described in the original paper of BLS as follows Let PG be a pairing group generator that on input $1^k$ outputs descriptions of multiplicative groups $G_1$ and $G_T$ of prime order $p$ where $|p| =k$. Let and let $g \in G_1^{*}$ and $G_{1}^{*}=G_{1} \backslash\{1\}$ .The generated groups are such that there exists an admissible bilinear map $e : G_1 × G_1 → G_T$, meaning that (1) for all $a, b ∈ Z_p$ it holds that $e(g^a,g^b )=e(g,g)^{ab}$ (2) $e(g,g)≠1$
    – Mohamed
    Jun 12, 2019 at 9:01
  • The original paper gives a construction that works in any gap-DH group with a pairing function. Ethereum only supports the bn256 groups so you don't worry about the pairing group generator, there's only one pairing group you can use
    – Tjaden Hess
    Jun 12, 2019 at 11:04
  • Exactly what @TjadenHess comments. I specifically used an edited version of the BLS scheme that supports the pairing that is supported by Ethereum. You can also review my comments and findings in my paper: researchgate.net/publication/…
    – Saffie
    Jun 12, 2019 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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