Support BN curves in the BLS aggregate signature

[chancharles92]

BLS signature on ethereum (uses BN256 curve)

• Not implemented in [blst](https://docs.rs/blst/0.3.10/blst/index.html) rust library we are using now
• Problem: hash to curve algorithm not specified in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve for the BN256 curve, even though some generic approach is described at https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-09#section-3
• Solutions
  • Use https://github.com/arkworks-rs/algebra/blob/1f7b3c6b215e98fa3130b39d2967f6b43df41e04/ec/src/hashing/map_to_curve_hasher.rs#L49

cc @philippecamacho @mrain

[philippecamacho]

Update regarding hashing to curve.

Context

We need to implement a hash to curve algorithm for the pairing friendly curve currently supported by Ethereum which is Bn254. We can either implement the naive method sometimes called "hash and pray" that consists of taking a field element $x$ , plugging it into the elliptic curve equation and hoping it is a quadratic residue. If not we try with $x+1$, if this fails again we try with $x+2$ and so on and so forth. This method takes only a few iterations as the probability of failure for k attempts heuristically is $2^{-k}$. A problem of this approach is that the time to compute the hash value is not constant which may leak information about the input or allow for some DoS attack if the hash function is computed inside a smart contract and an attacker is able to find an input $x$ so that $k$ is large.

Constant time hashing functions

Other hashing methods that are constant time exist though.

• According to https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve#section-6.6.3 the Wahby and Boneh (WB) method can be adapted to the Bn254 curve. In practice though it requires some effort because the arkworks library does not support this hashing (or any) method for Bn254 out of the box. IIUC the steps to extend this method we would need to:
  • Run the sage script described in appendix A WB of to compute the isogeny to a curve $E': y^2=x^ 3+ax+b$ with $a \cdot b \neq 0$ where the original curve $E$ is Bn254.
  • Take the isogeny parameters in plug them into arkworks trait WBConfig.
  • Instantiate and use the map_to_curver_hasherstruct.

This seems a lot of work and implementing the hash to curve in solidity will be quite hard as well.

• Another option would be to implement Fouque-Tibouchi, not sure how much work this means in practice as suggested in https://hackmd.io/@liangcc/bls-solidity#Hash-to-curve

Decision

I think the hash and pray method is fine for now, as the hashed message is public and DoS attacks do not seem a concern. We can switch to a better (constant time) hash to curve algorithm later.

Later we may even use EIP-3068 directly that implements the Fouque-Tibouchi algorithm.

cc @chancharles92 @sveitser

[sveitser]

Sounds reasonable. I'm okay with #️⃣ and 🙏.

[alxiong]

I wonder if we don't need to do hash to curve inside the contract, (due to the special constraint that everybody sign the same message in our context), then would it affect our decision on which HashToCurve algorithm to implement?

On the task #373 , I'm thinking maybe I should simply go with Fouque-Tibouchi (or adapted WB)?

cc @philippecamacho @chancharles92 WDYT?