NEPs
NEPs copied to clipboard
NEP-488: Precompile for BLS12-381 curve operations
A pre-compiled NEAR runtime functions for operations on BLS12-381 curve. It is a necessary set to efficiently perform operations such as BLS signature and zkSNARKs verifications.
Related PR: https://github.com/near/NEPs/pull/446
NEP Status (Updated by NEP Moderators)
Status: Approved
Meeting Recording: https://bit.ly/41V49Ke
SME reviews:
- [x] @abacabadabacaba: https://github.com/near/NEPs/pull/488#pullrequestreview-1795690930
- [x] @michelabdalla: https://github.com/near/NEPs/pull/488#pullrequestreview-1787306183
Protocol Work Group voting indications (❔ | 👍 | 👎 ):
- 👍 @birchmd: https://github.com/near/NEPs/pull/488#issuecomment-1877316766
- 👍 @mfornet: https://github.com/near/NEPs/pull/488#issuecomment-1877572145
- 👍 @mm-near: https://github.com/near/NEPs/pull/488#issuecomment-1884317079
- 👍 @bowenwang1996: https://github.com/near/NEPs/pull/488#issuecomment-1876028151
Thank you @olga24912 for submitting this NEP.
As a moderator, I reviewed this NEP and it meets the proposed template guidelines. I am moving this NEP to the REVIEW stage and would like to ask the @near/wg-protocol working group members to assign 2 Technical Reviewers to complete a technical review (see expectations below).
Just for clarity, Technical Reviewers play a crucial role in scaling NEAR ecosystem as they provide their in-depth expertise in the niche topic while work group members can stay on guard of the NEAR ecosystem. The discussions may get too deep and it would be inefficient for each WG member to dive into every single comment, so NEAR Developer Governance designed this process that includes subject matter experts helping us to scale by writing a summary with the raised concerns and how they were addressed.
Technical Review Guidelines
-
First, review the proposal within one week. If you have any suggestions that could be fixed, leave them as comments to the author. It may take a couple of iterations to resolve any open comments.
-
Second, once all the suggestions are addressed, produce a Technical Summary, which helps the working group members make a weighted decision faster. Without the summary, the working group will have to read the whole discussion and potentially miss some details.
Technical Summary guidelines:
-
A recommendation for the working group if the NEP is ready for voting (it could be approving or rejecting recommendation). Please note that this is the reviewer's personal recommendation.
-
A summary of benefits that surfaced in previous discussions. This should include a concise list of all the benefits that others raised, not just the ones that the reviewer personally agrees with.
-
A summary of concerns or blockers, along with their current status and resolution. Again, this should reflect the collective view of all commenters, not just the reviewer's perspective.
Here is a nice example and a template for your convenience:
### Recommendation
Add recommendation
### Benefits
* Benefit
* Benefit
### Concerns
| # | Concern | Resolution | Status |
| - | - | - | - |
| 1 | Concern | Resolution | Status |
| 2 | Concern | Resolution | Status |
Please tag the @near/nep-moderators once you are done, so we can move this NEP to the voting stage. Thanks again.
As a protocol working group member, I nominate @abacabadabacaba and @mfornet as technical reviewers for this NEP.
The quality of the document looks great, thanks for writing this @olga24912. I did a high level review and left few comments/suggestions about the text.
TIL that markdown supports references nicely, and GitHub renders them properly. I recommend using that: Example -- Reference
With regard to the technical part I need to give another pass, but I'm not qualified to review the crypto part of this document, so I'll relay on @abacabadabacaba for this, and hopefully some other people with experience in this area could chime in, since the importance of getting this right.
links fixed
@mfornet Thank you for your comments and review! Actually, this proposal should not be so difficult: I tried to give all context and all the necessary references. I am sure you are qualified enough. But this NEP is extremely long, and figuring out all that can be time-consuming. Let me know if I can help you somehow with this NEP and if you need any clarification.
As a technical reviewer, I find this NEP suitable for NEAR, subject to the following changes:
- The functions
bls12381_g{1,2}_sum
should take a list of (point, sign) pairs, similar to the existing API for alt_bn128. This will allow to negate points without having to pay for a scalar multiplication, and without having to implement it in WebAssembly. - For functions taking an array, empty input should not be an error, as there is a well-defined result for this case.
- The specification should be self-contained. In particular, the description of the mapping of field elements to points should be included, instead of linking to EIP-2537.
- Math and code formatting should be used consistently. I propose to use math formatting for all mathematical things (such as constants and formulas), and use code formatting for function signatures and code snippets. Also, the constants should preferably be in decimal.
- There are multiple smaller issues with language and style, which should be fixed after the bigger issues. Things like incorrect use of vocabulary ("wildly used"), incorrect spacing (no space before opening parentheses), inconsistent use of names (bn254 vs BN254 vs alt-bn128), incorrect terminology (precompiles are in Ethereum, in NEAR there are host functions), inconsistencies (the same function is called
bls12381_pairing
in one place andbls12381_pairing_check
in another), and so on.
@olga24912 @mfornet @birchmd
As a technical reviewer, I find this NEP suitable for NEAR, subject to the following changes:
- The functions
bls12381_g{1,2}_sum
should take a list of (point, sign) pairs, similar to the existing API for alt_bn128. This will allow to negate points without having to pay for a scalar multiplication, and without having to implement it in WebAssembly.- For functions taking an array, empty input should not be an error, as there is a well-defined result for this case.
- The specification should be self-contained. In particular, the description of the mapping of field elements to points should be included, instead of linking to EIP-2537.
- Math and code formatting should be used consistently. I propose to use math formatting for all mathematical things (such as constants and formulas), and use code formatting for function signatures and code snippets. Also, the constants should preferably be in decimal.
- There are multiple smaller issues with language and style, which should be fixed after the bigger issues. Things like incorrect use of vocabulary ("wildly used"), incorrect spacing (no space before opening parentheses), inconsistent use of names (bn254 vs BN254 vs alt-bn128), incorrect terminology (precompiles are in Ethereum, in NEAR there are host functions), inconsistencies (the same function is called
bls12381_pairing
in one place andbls12381_pairing_check
in another), and so on.@olga24912 @mfornet @birchmd
Thank you, @abacabadabacaba, for your review! I agree with all comments. It can take some time to resolve all of them. I will try to fix it as fast as possible and will write here as I progress.
- The functions
bls12381_g{1,2}_sum
should take a list of (point, sign) pairs, similar to the existing API for alt_bn128. This will allow to negate points without having to pay for a scalar multiplication, and without having to implement it in WebAssembly.
fixed: https://github.com/near/NEPs/pull/488/commits/bb845d6e586c232eea7d8ee68d9755bd89a0b00d
- For functions taking an array, empty input should not be an error, as there is a well-defined result for this case.
fixed: https://github.com/near/NEPs/pull/488/commits/55f9d993a7913c57b84c2657ccfcc549022d6a89
- The specification should be self-contained. In particular, the description of the mapping of field elements to points should be included, instead of linking to EIP-2537.
fixed: https://github.com/near/NEPs/pull/488/commits/a24a22671abe312f867d284ee7a390149a22e070
- Math and code formatting should be used consistently. I propose to use math formatting for all mathematical things (such as constants and formulas), and use code formatting for function signatures and code snippets. Also, the constants should preferably be in decimal.
fixed: https://github.com/near/NEPs/pull/488/commits/0e9b7b9efaccc3036af44e8eaebb5278db1447c7
- There are multiple smaller issues with language and style, which should be fixed after the bigger issues. Things like incorrect use of vocabulary ("wildly used"), incorrect spacing (no space before opening parentheses), inconsistent use of names (bn254 vs BN254 vs alt-bn128), incorrect terminology (precompiles are in Ethereum, in NEAR there are host functions), inconsistencies (the same function is called
bls12381_pairing
in one place andbls12381_pairing_check
in another), and so on.
Fixed:
- https://github.com/aurora-is-near/NEPs/commit/910d27080a59d7689ef81a143f84edec8f1d82ed
- https://github.com/aurora-is-near/NEPs/commit/71caeb45690c9796226ca48439e91e2c40bab4b2
- https://github.com/aurora-is-near/NEPs/commit/079e156d7339b63819ac7798a71334ae93d15df1
- https://github.com/aurora-is-near/NEPs/commit/d124617958d9b6d6c2c529ec70f019ab6b096988
- https://github.com/aurora-is-near/NEPs/commit/bd1c469aa0341db132bd808dacb19fe349816bef
Thanks @Karkunow for proofreading and editing
@abacabadabacaba @frol @mfornet @birchmd
All comments are addressed and PR is ready for rereview.
As a working group member, I nominate @michelabdalla and @Ekleog as subject matter experts to review this NEP.
CC: @Ekleog-NEAR in case you are not following the other github account.
I’m doing my best to review, but considering the size of the NEP I haven’t been able to complete within 24 hours. Will keep reviewing until I’m done with what I can do :)
I can already say, I have zero prior knowledge of bls12-381 curves (and little knowledge of elliptic curves’ detailed internals), so I’ll let @michelabdalla judge the cryptography side, and maybe @abacabadabacaba who already reviewed the previous #446 can also chip in?
PS: @akhi3030 You’re right that I don’t follow my OSS github account, I currently have an answer time around 2-3 months there 😅 thank you for the ping!
@Ekleog-NEAR: thanks for providing and update. I also agree that it is not possible to sensibly review this PR within 24hrs. To add some more context, we are also in the process of engaging an external consult to do a security audit of the actual implementation.
@olga24912 I found two additional problems with the current specification:
-
Currently, the functions return an error if any input is invalid. This is problematic, because checking whether the input is valid is difficult, in some cases about as difficult as executing the functions themselves. In EIP-2537, the precompiles also revert in case of invalid input, but EVM makes it easy to handle this. In contrast, in NEAR, if a host function returns an error, the entire execution is reverted. If Aurora were to use these host functions to implement EIP-2537, either the entire transaction would revert if at any point during the execution there is an attempt to use an EIP-2537 precompile with an invalid input, or Aurora would need to perform expensive checks, which would negate much of the advantage of using the host functions in the first place. I propose to make it so that the functions only return a failure if the parameters
value_len
/value_ptr
/register_id
are themselves invalid. When the data in memory is incorrect (e.g. point not on the curve), these functions should instead return an error code, which can be handled by the calling contract. -
Currently, the functions
bls12381_map_fp_to_g{1,2}
require the input elements to be already reduced modulo $p$. But when checking a BLS signature, the input to those functions is a hash, which is not reduced modulo $p$. Therefore, an implementation of BLS signatures would need to perform this reduction in WASM, which is not optimal. I propose to change these functions to include the reduction modulo $p$, and also to make it possible to pass longer inputs because that's needed to implement the current BLS signature standard (which AFAIK uses 64 bytes of hash output per element). By the way, did anyone actually try to implement the BLS signatures using the proposed API? If not, it would be nice to do so, because it would highlight any missing functionality like this.
@akhi3030 It would be great if it's not just the implementation that is audited, but also the specification. It is much easier to make a secure implementation when it is based on a design that is well done in terms of security, so it is better to make sure that this is the case while we can still change it fairly easily.
@akhi3030 It would be great if it's not just the implementation that is audited, but also the specification. It is much easier to make a secure implementation when it is based on a design that is well done in terms of security, so it is better to make sure that this is the case while we can still change it fairly easily.
Thanks for the note @abacabadabacaba. I will make sure that the specification is also audited.
@olga24912, @bowenwang1996, @akhi3030, @Ekleog-NEAR, @abacabadabacaba: hi all, just wanted to let you know that it's fine for me to review it and I already started working on it. I should be able to submit my review by early next week.
@Ekleog-NEAR
One question from my side: I see a lot of functions, while bn254 only needed
alt_bn128_g1_multiexp
,alt_bn128_g1_sum
andalt_bn128_pairing_check
. Why do we need so many more functions (in particular the map functions), if bls12-381 is only supposed to replace bn254?
Because we want to support more use cases. In particular, BLS signatures require a hash-to-point function, and point decompression functions allow passing compressed points as input, which are smaller.
BLS signatures require a hash-to-point function
Do I understand correctly that hash-to-point requires the two map functions, as they’re the ones I was wondering about?
and point decompression functions allow passing compressed points as input, which are smaller.
Stupid question maybe, but do we actually have significant gains in having compressed points? It seems like the gain is less than 256 bytes per point, which is not that expensive considering our costs. Do we even need to support compressed points in the API at all?
General comments:
Due to several advances in the Number Field Sieve algorithms for the discrete log problem and their impact on the security of BN254 curves, BLS12-381 curves have become more widely used. In this NEP, @olga24912 proposes a set of host functions for the BLS12-381 curve to assist the implementation of protocols and algorithms that use this curve, such as the verification of BLS signatures (which require hashing to the curve) and of zkSNARKs. In this respect, this NEP plays a similar role to Near as EIP-2537 does for Ethereum and the set of functions being considered in the current NEP are largely based on those proposed in EIP-2537.
Overall, I am in favor of adding host functions for the BLS12-381 curve to nearcore as I believe that this is a worthwhile effort. In my opinion, this specification is well described and motivated, and provide enough details for the implementation of the host functions being proposed. The main question, however, that needs to be answered before finalizing such a specification is whether the set of functions is the right one to support BLS signatures and zkSNARKs. As @abacabadabacaba already pointed out, BLS signatures would need to additionally hash messages to field elements and this is currently not covered in the current specification.
Specific comments:
As mentioned by @Ekleog-NEAR, certain parts of the specification, such as definitions of subgroups and field extensions, could be omitted and replaced with appropriate references.
Regarding testing scenarios for the implementation, the current specification divides these into two parts: error cases and test cases. While the error cases for the functions are clear and largely based on those proposed in EIP-2537, the same cannot be said about the test cases. Currently, it is not clear to me that these tests cover well the error cases and the correctness of the implementation.
Regarding the set of host functions, it may be better for the specification to also provide functions to map random bits to a point in the curve instead of only providing a function from the finite field to the curve because this will be needed by the BLS signature scheme. This could be done by either by changing the current map-to-curve function, which seems to be the solution suggested by @abacabadabacaba, and by having separate functions that map bit strings to the appropriate finite field (Fp or Fp2). It is not clear to me which option would be more useful.
Here are a few questions that it would be nice to answer before finalizing this specification:
- In addition to affine coordinates, should this NEP also provide support for other representations such as homogeneous or Jacobian projective coordinates? As stated by Wahby and Boneh (reference 30), this can be quite helpful in avoiding divisions.
- Should this NEP also provide functions for mapping bit strings to field elements? This could facilitate the implementation of BLS verification since one first needs to hash the message to a field element before mapping the latter to a curve point.
- Why is not constant-time implementation a focus of this NEP? This is one of the main concerns addressed by Wahby and Boneh (reference 30) and is strongly recommended in the current hash-to-curve RFC draft [RFC 9360] to avoid leaking information via side channels.
Minor comments:
In the Fp1-to-G1 mapping, the values of the parameters A and B used to define an intermediary curve as well as the constants used to compute the isogeny from the intermediary curve to the curve E(Fp) used in BLS12-381 are given in decimal notation. I would recommend describing these in hexadecimal notation so that the consistency between the current specification and the one given in EIP-2537 Map-To-Curve specification (reference 28) can be easily checked. The same recommendation applies to the values used in the Fp2-to-G2 mapping.
When describing how to set the bits in the first byte to indicate if the encoding is compressed, if it is a point at infinity, or the sign of the y value for compressed encodings, I would recommend to clearly state that the “first”, “second”, and “third” bits on a byte refers to the highest, second-highest, and third-highest order bits in that byte to avoid confusion.
For Compressed points on twisted curve E'(Fp2), shouldn’t you use the formula for E’ when computing the y coordinate? The current specification is using the same formular for E(Fp) and E'(Fp2)
The bls12381_g1_sum
is supposed to compute the sum of an arbitrary number of points in G1, represented in uncompressed encoding, together with a sign value. Currently, this function does not specify a limit on the number of points that can be added and computes the number of terms based on the length of input being provided. It is not clear to me that this is a safe approach and I would personally prefer seeing a hard limit on the number of elements in the summation to avoid unexpected behavior. A similar comment applies to the other host functions being proposed.
As mentioned before, while the different error cases being proposed for the host functions seem appropriate, the same cannot be said about the testing cases. Currently, they are described very precisely (e.g., “Too many points for sum” in the bls12381_g1_sum
specification) and it is not clear to me that these are exhaustive.
Regarding gas estimates, I was wondering if it is possible to have more concrete estimates for the gas consumption or if this will only be estimated later once a concrete implementation is proposed. The current specification seems to follow the pattern for NEP-98 for BN254 host functions so I guess this is how it works.
Why is not constant-time implementation a focus of this NEP? This is one of the main concerns addressed by Wahby and Boneh (reference 30) and is strongly recommended in the current hash-to-curve RFC draft [RFC 9360] to avoid leaking information via side channels.
I can speak on this one: the computation is performed on-chain, which means that it is performed on publicly-accessible data and points only, that is archived and readable by anyone in the world forever.
It will probably make sense to switch to a constant-time implementation if we ever switch to a contract running scheme that would allow sealing inputs or state behind zero-knowledge proofs or similar, but currently I don’t think we’d gain anything by having a constant-time implementation, because anyone can just make a few http requests to get the inputs to the computation anyway.
thanks for providing and update. I also agree that it is not possible to sensibly review this PR within 24hrs. To add some more context, we are also in the process of engaging an external consult to do a security audit of the actual implementation.
Hi @akhi3030 I am not sure that this is a good time for an implementation audit. The current implementation is just a proof of concept. To make sure that these host functions are possible and easy to implement and for a better understanding of how it works.
I expect that this NEP will change a few times as a result the implementation will change as well. If we start auditing it now, we will need to audit it a second time when the NEP will be accepted.
- Currently, the functions return an error if any input is invalid. This is problematic, because checking whether the input is valid is difficult, in some cases about as difficult as executing the functions themselves. In EIP-2537, the precompiles also revert in case of invalid input, but EVM makes it easy to handle this. In contrast, in NEAR, if a host function returns an error, the entire execution is reverted. If Aurora were to use these host functions to implement EIP-2537, either the entire transaction would revert if at any point during the execution there is an attempt to use an EIP-2537 precompile with an invalid input, or Aurora would need to perform expensive checks, which would negate much of the advantage of using the host functions in the first place. I propose to make it so that the functions only return a failure if the parameters
value_len
/value_ptr
/register_id
are themselves invalid. When the data in memory is incorrect (e.g. point not on the curve), these functions should instead return an error code, which can be handled by the calling contract.
@abacabadabacaba, sounds reasonable. I will fix it.
- Currently, the functions
bls12381_map_fp_to_g{1,2}
require the input elements to be already reduced modulo p. But when checking a BLS signature, the input to those functions is a hash, which is not reduced modulo p. Therefore, an implementation of BLS signatures would need to perform this reduction in WASM, which is not optimal. I propose to change these functions to include the reduction modulo p, and also to make it possible to pass longer inputs because that's needed to implement the current BLS signature standard (which AFAIK uses 64 bytes of hash output per element). By the way, did anyone actually try to implement the BLS signatures using the proposed API? If not, it would be nice to do so, because it would highlight any missing functionality like this.
@abacabadabacaba here you can find the implementation of BLS-signature verification based on these host functions: https://github.com/olga24912/bls-signature-verificaion-poc
I tested it with BLS-signature from Ethereum Light Client Updates. It is exactly the signature that we would like to verify in Rainbow Bridge. In this case, the message hashing inside the contract takes 2TGas and it is acceptable for us.
Two main reasons don't include hashing into this proposal:
- it is possible to do just inside the contract. At least in our case.
- hash function can be implemented differently depending on specific task
I suggest not including the hash functions in this NEP. The NEP is extremely big already now, and it is better not to do it even more complicated without serious reason.
Overall, the motivation seems reasonable to me. I think the specification is, this time, too detailed: re-explaining what subgroups and order are should be in the mathematical spec for bls12-381, which should probably not be copy-pasted here but directly referenced. Looking at EIP-2537, it seems to have hit the right balance between "specify every technical detail" and "do not copy the bls12-381 cryptography paper".
@Ekleog-NEAR
Maybe by explaining what a group and order are, I have gone too far...
Without specific domain knowledge, it is impossible to understand this NEP and what these host functions doing. My idea was to provide some mathematical context at least on the definition level to make it possible to understand this paper.
All the definitions were introduced into one section with a summary at the end. I expect, that if the reader is already familiar with all these terms, he can just skip this section. Otherwise, it can be useful for him. I don't think that this section makes this proposal more difficult to understand.
No, it wasn't just copy-pasted from one place. And I don't know the paper which explained exactly what I want.
I can suggest creating supplementary notes and separating this section fully from this NEP. But I don't know what is the best practice for creating NEP's supplementary....
One question from my side: I see a lot of functions, while bn254 only needed
alt_bn128_g1_multiexp
,alt_bn128_g1_sum
andalt_bn128_pairing_check
. Why do we need so many more functions (in particular the map functions), if bls12-381 is only supposed to replace bn254? If I understand correctly, it opens up other theoretical use cases, but we’re not seeing them yet. Or maybe you already know of practical use cases that would benefit immediately from it? If so, could you expand on the motivation section?
@Ekleog-NEAR, good question.
We need these host functions to verify the BLS signatures on NEAR to verify Ethereum Light Client Updates. We need for bridge between Ethereum and NEAR. There the BLS signature is written on top of the BLS12-381 and we do not have the option to use other curves. And it is a new issue. Before Ethereum used PoW, not PoS, and it was easy to verify the block correctness, and we don't need to verify any BLS-signatures. So, from this point of view, the BLS-signature verification is a new use case.
List of functions that we need to verify the BLS signature:
- map_fp2_to_g2
- g2_sum
- g1_sum
- g1_decompress
- g2_decompress (we can avoid using it)
- pairing_check
I don't need, for example, multiexp functions, but it is useful for zkSNARKs verifiers. Also, I need extra functions to be compatible with EIP-2537.
But if we will support only 6 functions listed before, I will already be happy. Because my main goal -- verification of specific BLS signatures on NEAR.
BLS-signature verification functions take as input (msg, signature, pks). Signature and public keys are already points from the correct subgroup. But the message -- it is just a bytes array. We should transform the message to the correct space. And for doing that we first should hash the message, second -- map it to G2 subgroup. To do that we need this function.
I guess that alt-bn128 is mostly used for zkSNARKs verifications. But now we also need to verify BLS-signatures.
Did I answer your question?
Yes, thank you! And you’re right that considering we need these functions, then we should add the others already in the NEP for symmetry, as well as for a good parallel with our bn254 implementation. Could you add the explanation to the NEP text itself, so that it’s not lost in the middle of the github discussion? :)
I’ll be happy to give a round 2 of review once @michelabdalla has reviewed and both our reviews’ comments have been either discussed or handled, feel free to ping me again then :)
@Ekleog-NEAR Thank you for the enormous amount of work you have done by reviewing this NEP!
Hi @abacabadabacaba, @Ekleog-NEAR, and @michelabdalla thank you so much for agreeing to review this NEP. Per the NEP workflow, the expectation is for you to complete the review within one week, but given the complexity of this NEP, I think we should extend it to 2 weeks at least (December 1st, 2023). Please find additional guidelines below.
Just for clarity, Technical Reviewers play a crucial role in scaling NEAR ecosystem as they provide their in-depth expertise in the niche topic while work group members can stay on guard of the NEAR ecosystem. The discussions may get too deep and it would be inefficient for each WG member to dive into every single comment, so NEAR Developer Governance designed this process that includes subject matter experts helping us to scale by writing a summary with the raised concerns and how they were addressed.
Technical Review Guidelines
-
First, review the proposal. If you have any suggestions that could be fixed, leave them as comments to the author. It may take a couple of iterations to resolve any open comments.
-
Second, once all the suggestions are addressed, produce a Technical Summary, which helps the working group members make a weighted decision faster. Without the summary, the working group will have to read the whole discussion and potentially miss some details.
-
A recommendation for the working group if the NEP is ready for voting (it could be approving or rejecting recommendation). Please note that this is the reviewer's personal recommendation.
-
A summary of benefits that surfaced in previous discussions. This should include a concise list of all the benefits that others raised, not just the ones that the reviewer personally agrees with.
-
A summary of concerns or blockers, along with their current status and resolution. Again, this should reflect the collective view of all commenters, not just the reviewer's perspective.
-
Here is a nice example and a template for your convenience:
## Example
### Recommendation
Add recommendation
### Benefits
Benefit
Benefit
### Concerns
| # | Concern | Resolution | Status |
| - | - | - | - |
| 1 | Concern | Resolution | Status |
| 2 | Concern | Resolution | Status |
Please tag the @near/nep-moderators once you are done, so we can move this NEP to the voting stage. Thanks again.