BLS12_381 G1 fromHex() Instantiation Bug

[holgerd77]

We are currently switchign to use @noble/curves as default for the BLS precompiles, see ethereumjs/ethereumjs-monorepo#3471.

Right now I am implementing the precompile for mapping an FP element to a G1 point (also see EIP).

Not yet working, I was trying to use the bls12_381.G1.ProjectivePoint.fromHex() method for this.

Beside the question that I am not 100% sure if this is the right way to do it there might be a bug in the method implementation:

Using @noble/curves v1.4.0 gives following error on this test:

import { bls12_381 } from '@noble/curves/bls12-381'
bls12_381.G1.ProjectivePoint.fromHex('010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748')
bls12_381.G1.ProjectivePoint.fromHex('11'.repeat(48)) // alternative

Uncaught Error: Invalid point G1, expected 48/96 bytes
    at fromBytes (/ethereumjs-monorepo/packages/evm/node_modules/@noble/curves/src/bls12-381.ts:1179:15)
    at Function.fromHex (/ethereumjs-monorepo/packages/evm/node_modules/@noble/curves/src/abstract/weierstrass.ts:318:34)
    at /ethereumjs-monorepo/packages/evm/src/precompiles/<repl>.ts:1:42
    at Script.runInThisContext (node:vm:136:12)
    at runInContext (/.nvm/versions/node/v20.12.2/lib/node_modules/ts-node/src/repl.ts:673:19)
    at Object.execCommand (/.nvm/versions/node/v20.12.2/lib/node_modules/ts-node/src/repl.ts:639:28)
    at /.nvm/versions/node/v20.12.2/lib/node_modules/ts-node/src/repl.ts:661:47
    at Array.reduce (<anonymous>)
    at appendCompileAndEvalInput (/.nvm/versions/node/v20.12.2/lib/node_modules/ts-node/src/repl.ts:661:23)
    at evalCodeInternal (/.nvm/versions/node/v20.12.2/lib/node_modules/ts-node/src/repl.ts:222:12)

I guess this should work if I am not overlooking something obvious?

[holgerd77]

Update: ok, I already have the suspicion that I am not doing it right and this would rather expect the point coordinates.

Will have a second look, leaving this open for the moment nevertheless until fully settled.

[holgerd77]

Something like this mapToCurve() method? 🤔

This is not exposed though atm, right?

[paulmillr]

bls.G1.CURVE.mapToCurve([BigInt('0x' + inputHex)]) would probably do it.

However executing it with vector 2 from https://eips.ethereum.org/assets/eip-2537/map_fp_to_G1_bls.json errors bad point: not in prime-order subgroup for me.

The output of the vector is 128 bytes: 00000000000000000000000000000000009769f3ab59bfd551d53a5f846b9984c59b97d6842b20a2c565baa167945e3d026a3755b6345df8ec7e6acb6868ae6d000000000000000000000000000000001532c00cf61aa3d0ce3e5aa20c3b531a2abd2c770a790a2613818303c6b830ffc0ecf6c357af3317b9575c567f11cd2c

But G1 element is either compressed 48 bytes (curve coordinate x is 381 (~384) bits - 384/8 = 48), or decompressed 96 bytes (x + y, both 48 bytes).

I don't understand what the output means if it's not a point.

[holgerd77]

🙏

Thanks for having a quick look! mapToCurve does not seem to be exported:

Regarding the test vectors, these describe the input and output formats required by the EVM and this still needs some transformation, e.g. for the above these are the two 48 byte coordinate values as concatenated bytes each padded to 64 bytes (if I am not mistaken).

[paulmillr]

The types are not exported, but it's available if you use it in JS (type-less) script, or REPL - can be used for debugging.

I will fix it.

[holgerd77]

Ah, sorry, I might be thinking a bit too much in TypeScript terms. But exporting would definitely help!

Side note: I also had to copy over the type for Fp here https://github.com/ethereumjs/ethereumjs-monorepo/pull/3471/files#diff-e18a5424ae2839a6fae5329b0620e49ba50854c2653d207cf8e21ab4d1dbefdb (line 22, sorry, can't deep-link since GitHub is folding the file due to diff size), maybe that's also something to export?

I've now applied the usage of mapToCurve() to the implementation, see line 467, same file, if you are interested.

Results are still different from the test vectors though, so e.g. for the first bls_g1map_ test vector:

stdout | test/precompiles/eip-2537-bls.spec.ts > Precompiles: map_fp_to_G1_bls.json > bls_g1map_
Direct result Noble (ProjectivePoint)
{
  x: 2651141094918884883245946750082163419780511923462098120393192671331038429847241762506451968056272389809307136423689n,
  y: 3877564604549600802964132537294381446492072628340998558677591803218630687606854818909123819118480929847725344378738n
}
Serialized EVM byte result
0x0000000000000000000000000000000011398d3b324810a1b093f8e35aa8571cced95858207e7f49c4fd74656096d61d8a2f9a23cdb18a4dd11cd1d66f41f7090000000000000000000000000000000019316b6fb2ba7717355d5d66a361899057e1e84a6823039efc7beccefe09d023fb2713b1c415fcf278eb0c39a89b4f72

Expected (to be compared with last value (EVM result)):

00000000000000000000000000000000184bb665c37ff561a89ec2122dd343f20e0f4cbcaec84e3c3052ea81d1834e192c426074b02ed3dca4e7676ce4ce48ba0000000000000000000000000000000004407b8d35af4dacc809927071fc0405218f1401a6d15af775810e4e460064bcc9468beeba82fdc751be70476c888bf3

I had a closer look at the EIP again:

It seems there is a very specific definition of how a mapping is done in the context of the EIP. Is the mapping you expose in the library actually matching that? Or is this at least similar to your mapping and would it be somewhat easy [tm] to adopt? 😬

[holgerd77]

(so, and maybe some "instructions" how to read this noble.ts file from my implementation:

There is still a lot of MCL code in it, since I use this for the implementation to run in parallel and compare results. So all *N* appended functions are the new Noble function. The more generic functions on top (like BLS12_381_FromG2PointN() e.g. are mostly for converting from/to the EVM input/output formats.

At the end of the file there is a class NobleBLS which implements an EVMBLSInterface and this is the entrypoint for the precompile implementations.)

[holgerd77]

Ok, but seems your implementation is relatively close to the algorithm stated already?

mapToCurve: (scalars: bigint[]) => {
  const { x, y } = G1_SWU(Fp.create(scalars[0]));
  return isogenyMapG1(x, y);
}

Can't fully judge though.

[holgerd77]

Ah, sorry, I'll stop soon, but also just to let you know: so what already basically works atm are the g1add, g1mul, g2add and g2mul precompiles. 🙂

[paulmillr]

I've just added eip2537 vectors that pass, check out 7d04544

[holgerd77]

Oh, how cool is that! Looks good as far as I can judge!

This needs a release, right?

I have now also added basic integrations for the msm precompiles, using a naive implementation (the EIP mentions an optimized algorithm Pippenger's algorithm which should be used, but I would assume that @noble/curves likely (?) does not support that (which would not be too grave, nice to have mid term, but for now already good if things are working at all)).

So, msm also generally seems to work (some 0/infinity cases still failing, but otherwise tests pass). 🙂

[paulmillr]

I don't want to release something which would need a new release to fix bugs after they appear in monorepo.

The suggestion is that we polish it until everything is smooth. Could you use the unreleased version for now? There are 3 different ways:

1. Fork it, commit "built" output to github (remove from gitignore), point npm package.json to github commit
2. Clone it, use build directory to build single bundled file, use that single file for now (no typescript)
3. Clone it, npm install, npm run build, then do npm pack to create noble-curves.tgz and npm install this .tgz archive in monorepo: npm install noble-curves.tgz

[holgerd77]

Makes sense! Done: https://github.com/holgerd77/noble-curves/tree/build-1b1fe7f

Tests (for mapFpToG1) passes! 🙂

Great! 🎉

Will report back for G2.

[holgerd77]

Oh wait, I used MCL. 🤦

Wait...

[holgerd77]

Typing seems to be a bit more complicated, is there a way to get this to a ProjPointType<bigint>?

[holgerd77]

I can also change my BLS12_381_fromG1PointN() method to expect an AffinePoint, that works as well, was wondering though if this is intended.

So: it works, final confirmation (for G1)! 🎉

[holgerd77]

Ah, ok, so for G2 it is not working yet:

This still seems to need some generalization.

[paulmillr]

Have you managed to find finalExponentiate? It’s a method on Fp12. Fp12 is created with pairing.

[holgerd77]

Will look into pairing likely tomorrow, thanks for the pointer

[paulmillr]

fp2 to g2 fixed in 5fcd71a

[holgerd77]

https://github.com/holgerd77/noble-curves/tree/build-5fcd71a

🙏

[holgerd77]

Aaaaaannd pairing precompile basically working as well! 🎉

Thanks a lot for your help so far! 🙏

I have some 0/infinity edge cases still missing (in total 8/131 of our local tests are still failing), but I think we definitely have a PoC that all works!

I think I'll take the whole next week still for cleaning things up, fixing the last tests and generally looking at edge cases, since all this is pretty complex and I think deserves some more attention still.

So no need to imminently rush a release (as you want), maybe we can target end of next week, would that work? Or still rather too early?

[paulmillr]

maybe we can target end of next week, would that work

Of course.

What's up with pairing(G1, 0) == pairing(0, G2)? I assume 0 is zero point. The error is pairing is not available for ZERO point - I don't think it's valid at all.

I think the error needs to be try-catched at your level.

https://eips.ethereum.org/EIPS/eip-2537#abi-for-pairing-check

If any input is the infinity point, pairing result will be 1. Protocols may want to check and reject infinity points prior to calling the precompile.

The question is whether noble has valid behavior; or not.

[holgerd77]

Ah, thanks, yeah, that was easy to add:

if (G1 === bls12_381.G1.ProjectivePoint.ZERO || G2 === bls12_381.G2.ProjectivePoint.ZERO) {
  return ONE_BUFFER
}

I've a few more of these 0/infinity cases in other precompiles as well, will try to fix them throughout the morning.

[holgerd77]

Ok, all local tests with Noble passing!! 🎉

After a second thought, if you could bring forward a release that would actually help me on the process. I would feel comfortable enough on the changes from my side.

Thing is that with my GitHub integration, installed versions for @noble/curves seem to unluckily interfere, with the library being integrated from within ethereum-cryptography (in the old version) and then by my direct GitHub fork link, and I had to monkey-patch this (copy code into node_modules directly), otherwise the EVM was falling back to the old version.

This should go away with an npm integration and with this I could then properly with the official cross-client BLS tests from https://github.com/ethereum/tests, which gets easier when I can trigger the CI by pushing the code (atm the build fails).

[paulmillr]

I will publish the release today.

[paulmillr]

https://github.com/paulmillr/noble-curves/releases/tag/1.4.1

[paulmillr]

actually https://github.com/paulmillr/noble-curves/releases/tag/1.4.2

[paulmillr]

and keep an eye on ethereum/js-ethereum-cryptography#113