aleo-education icon indicating copy to clipboard operation
aleo-education copied to clipboard

Is using an elliptic curve on BLS12-377's prime subgroup order safe?

Open niooss-ledger opened this issue 3 years ago • 0 comments

Hello, While doing Aleo exercices I noticed something strange with the code which defines a "zero" point: https://github.com/AleoHQ/aleo-education/blob/d6013a0ba18377eaf86f645db00bf93e62287a7d/hangman/src/main.leo#L105-L106

The value used for y is 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001, which is the correct "base field modulus" of BLS12-377 (https://eips.ethereum.org/EIPS/eip-2539), but in Leo this value is truncated. When displaying the content of digest.y in the program:

console.log("digest.y = {}", digest.y);

The output is:

digest.y = 9586122913090633729

This is because defining the number as field takes the value modulo the "Main subgroup order" 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001. This can be seen in the following Python code:

>>> base_field_modulus = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
>>> subgroup_order = 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001
>>> base_field_modulus % subgroup_order
9586122913090633729

More generally, the Point circuit in hangman/src/main.leo represents a point with coordinates modulo subgroup_order instead of base_field_modulus. This leads to two questions:

  • Is this curve "safe" to use? Usually in EC cryptography, there are important concepts such as "the curve order" and "working in the large prime subgroup of the curve" to perform operations in a safe way.
  • Being able to compute real BLS12-377 points in Leo sounds useful. Is there a way to achieve this? (By having numbers modulo base_field_modulus instead of subgroup_order)?

By the way, thanks for this educational content! It is a great way to learn about ZK-based systems such as Aleo.

niooss-ledger avatar Dec 03 '21 09:12 niooss-ledger