IntersectMBO / IntersectMBO/plutus
Tests for canonicity of field elements in compressed BLS12-381 points
- Dominant language
- Haskell
- Stars
- 1.6k
- Forks
- 508
- Avg merge
- 3d 10h
- Merged PRs (30d)
- 22
Description
[Migrated from PLT-8308]
The Plutus Core BLS12-381 builtins provide compressed serialisation for points in the G1 and G2 groups, where a compressed point stores only the x-coordinate of a point. This is a number modulo a 381-bit prime q for G1, and two such numbers for G2. There is room in this format for numbers n with q < n < 2^381-1, and such values should be rejected since they are non-canonical. The blst library apparently [checks](https://github.com/supranational/blst/blob/bb8fb99e39866e05d973ca55580524078c558aed/src/e1.c#L245) that elements are canonical, but we should add some tests that this is the case. It might be a challenge to find such numbers though: we require a number x with 0 <= x < 2^381-q (approximately) such that x is the x-coordinate of a point in G1: x+q would then still fit into the encoding format . We can probably generate elements of G1 by generating random points in the curve E1 and clearing the cofactor, but the probability that the x-coordinate of a random point would be sufficiently small to fit into the problematic interval is very small. Some research and experimentation will be required.
We need at least one point in G1 (and ideally at least one in G2) with a sufficiently small x-coordinate to admit a non-canonical encoding, and we need tests that such encodings are rejected by the uncompression primitive(s).
Contributor guide
Assessment
This issue has not been assessed yet.