Prysm: Attempt a BLS12-381 Implementation in Go

[rauljordan]

Hi all,

We are currently planning on using go-bls for our BLS-12-381 signature aggregation library to use throughout our repository. There has been some discussion on creating a pure Go implementation of the system as that would bring a massive benefit to our client and to the general public. Specifically, we wouldn't be relying on CGo bindings, no underlying C dependencies to install on specific machine architectures, and we would have an easier time testing and attracting open source contributors.

We are requesting a bounty for this problem for someone to implement this in a separate repository, as this implementation would be incredibly beneficial beyond just for Prysm.

[meyer9]

In progress here: http://github.com/phoreproject/bls

This is using the bn128 curve, but I plan to change it to add bls12-381 once I write some basic tests and benchmarks.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

__Work has been started__.

These users each claimed they can complete the work by 2 weeks, 6 days ago.
Please review their action plans below:

1) mestorlx has applied to start work _(Funders only: approve worker | reject worker)_.

I guess somebody is working on this already. https://github.com/phoreproject/bls
If not I would like to take it.

Learn more on the Gitcoin Issue Details page.

2) meyer9 has been approved to start work.

I've already finished a BN128 implementation in Go and am now extending it to BLS12-381.

Learn more on the Gitcoin Issue Details page.

[mestorlx]

I understand that @meyer9 is working on this.
If not I would like to take it.

[ceresstation]

Hey @meyer9 just approved you, keep us updated :)

[meyer9]

So I'm working on implementing the FQ, FQ2, and FQ12 elements in Go. I have some of the tests done, but there are still a bunch more possible.

I'll start working on the curve functions now (double, multiply, addition). That should take a couple of days.

Then, I can add the pairing functions (miller_loop, final_exponentiate) and then the BLS functions shouldn't be too difficult after that (hash_to_G2, privtopub, sign, verify, aggregate_sigs, aggregate_pubs, compress/decompress_g1/g2).

[meyer9]

Curve functions are done now.

BenchmarkG1MulAssign-8               100          12379944 ns/op
BenchmarkG1AddAssign-8             30000             44257 ns/op
BenchmarkG1AddAssignMixed-8        50000             32705 ns/op
BenchmarkG2MulAssign-8                30          40261811 ns/op
BenchmarkG2AddAssign-8             10000            177137 ns/op
BenchmarkG2AddAssignMixed-8        10000            129402 ns/op

Initial tests show about 4x the time of the Rust implementation. Could easily be improved.

[meyer9]

The library is technically "working" now. Completely unoptimized benchmarks (10-1000x worse than Rust):

BenchmarkG2Prepare-8                         300           3751069 ns/op
BenchmarkMillerLoop-8                        100          12964086 ns/op
BenchmarkFinalExponentiation-8                20          57748203 ns/op
BenchmarkPairing-8                            20         138394434 ns/op
BenchmarkFQ12Add-8                        200000              9018 ns/op
BenchmarkFQ12Sub-8                        200000              9096 ns/op
BenchmarkFQ12Mul-8                         10000            246328 ns/op
BenchmarkFQ12Square-8                      10000            226776 ns/op
BenchmarkFQ12Inverse-8                      2000            816954 ns/op
BenchmarkFQ2Add-8                        2000000              1051 ns/op
BenchmarkFQ2Sub-8                        2000000               881 ns/op
BenchmarkFQ2Mul-8                         300000              4788 ns/op
BenchmarkFQ2Square-8                      300000              7065 ns/op
BenchmarkFQ2Inverse-8                       3000            534928 ns/op
BenchmarkFQ6Add-8                         300000              4583 ns/op
BenchmarkFQ6Sub-8                         500000              5243 ns/op
BenchmarkFQ6Mul-8                          20000            106760 ns/op
BenchmarkFQ6Square-8                       50000             31720 ns/op
BenchmarkFQ6Inverse-8                       3000            912435 ns/op
BenchmarkFQAdd-8                         3000000               391 ns/op
BenchmarkFQSub-8                        10000000               443 ns/op
BenchmarkFQMul2-8                        2000000              1125 ns/op
BenchmarkFQSquare-8                      1000000              2417 ns/op
BenchmarkFQInverse-8                        3000            507476 ns/op
BenchmarkFQNegate-8                      5000000               297 ns/op
BenchmarkFQSqrt-8                           2000            768863 ns/op
BenchmarkG1MulAssign-8                       200          10831393 ns/op
BenchmarkG1AddAssign-8                     50000             22454 ns/op
BenchmarkG1AddAssignMixed-8               100000             20108 ns/op
BenchmarkG2MulAssign-8                       100          24253110 ns/op
BenchmarkG2AddAssign-8                     20000            175948 ns/op
BenchmarkG2AddAssignMixed-8                20000             69970 ns/op

[meyer9]

benchmark                          old ns/op     new ns/op     delta
BenchmarkG2Prepare-8               3751069       2970174       -20.82%
BenchmarkMillerLoop-8              12964086      9743896       -24.84%
BenchmarkFinalExponentiation-8     57748203      39083178      -32.32%
BenchmarkPairing-8                 138394434     68271278      -50.67%

[meyer9]

Further optimized the modular multiplication function. This is about as good as we can get without a uint384 library for Go (which I'm also in the process of writing). This can then utilize Montgomery Modulus Reduction to run modular multiplication operations (over 50% of the work load) much faster.

BenchmarkPairing-8           300          48401932 ns/op        23629842 B/op     365559 allocs/op

This is still about 25x worse than ZCash's rust implementation (2 million ns vs 50 million ns). From the cpu profile of this test, 46% of the time is spent dividing numbers (modulo) and 23% of the time is spent allocating memory. So, we should be able to cut out about 70% of the time here.

[meyer9]

Implemented BLS functions:

BenchmarkBLSAggregateSignature-8           50000             40005 ns/op
BenchmarkBLSSign-8                           100          16457803 ns/op
BenchmarkBLSVerify-8                           5         225395060 ns/op

Aggregating 200,000 signatures would take 8 seconds.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

__Work for 600.0 DAI (600.0 USD @ $1.0/DAI) has been submitted by__:

1. @meyer9

@ceresstation please take a look at the submitted work:

• PR by @meyer9

---

• Learn more on the Gitcoin Issue Details page
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $33,960.43 more funded OSS Work available on the Gitcoin Issue Explorer

[meyer9]

So it looks like I can speed this up by a lot by using fixed uint384/uint256 numbers. I'm working on that in the fqrepr branch.

[meyer9]

Not finished quite yet, but that improved speed by approx. 4x:

BenchmarkBLSAggregateSignature-8          100000             13050 ns/op
BenchmarkBLSSign-8                           500           2900119 ns/op
BenchmarkBLSVerify-8                          50          59291751 ns/op

Can verify about 20 signatures a second, sign 300 messages a second, and aggregate about 80000 signatures a second.

[rauljordan]

What target numbers are you aiming to get for it to be considered "done" in your eyes? Btw isn't the verification benchmark not too important as we'll just be verifying one aggregate sig anyways?

[meyer9]

I'd say this is about as optimized as I can make it. The tests aren't quite passing, but that's probably just some small bug. Verifying isn't too important, but still good to make sure it can handle a decent amount. Every block submitted needs to run signature verification (whether it is valid or not), so too slow might cause a DoS vulnerability.

[rauljordan]

Hey Julian, thanks for all the work on this - we understand all the extra optimization work is out of scope of the bounty. We are happy to award you for the work. @ceresstation we can end this bounty and award to @meyer9.

[prestonvanloon]

@ceresstation Please do not award the bounty until a proper license has been added to the code. Otherwise no one can use this work.

@meyer9 Please https://github.com/phoreproject/bls/issues/1

[meyer9]

done. thanks.

by the way, the tests work in the master branch, just not the optimized one.

[prestonvanloon]

Thanks @meyer9. Great work!

[prestonvanloon]

@ceresstation I think this is complete. Thanks for another successful task on gitcoin everyone!

[ceresstation]

Thanks @meyer9 + @prestonvanloon, paying this out now!

[gitcoinbot]

⚡️ A *Focus* Kudos has been sent to @meyer9 for this issue from @ceresstation. ⚡️ The sender had the following public comments: > Awesome job! Nice work @meyer9! To redeem your Kudos, login to Gitcoin at https://gitcoin.co/explorer and select 'Claim Kudos' from dropdown menu in the top right, or check your email for a link to the Kudos redemption page.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

__The funding of 600.0 DAI (600.0 USD @ $1.0/DAI) attached to this issue has been approved & issued to @meyer9.__

• Learn more on the Gitcoin Issue Details page
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $44,583.77 more funded OSS Work available on the Gitcoin Issue Explorer

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

__The funding of 600.0 DAI (600.0 USD @ $1.0/DAI) attached to this issue has been approved & issued to @meyer9.__

• Learn more on the Gitcoin Issue Details page
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $44,283.77 more funded OSS Work available on the Gitcoin Issue Explorer