Solidity – Verifying BGLS Aggregate Signatures

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:

• [1]: https://link.springer.com/chapter/10.1007%2F3-540-39200-9_26
• [2]: https://github.com/Project-Arda/bgls-on-evm
• [3]: https://link.springer.com/article/10.1007/s10623-009-9334-7

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