Repository: ethereum/py_ecc

Issue:
FQP initialization should take the mod of input coefficients
Full context: https://github.com/ethereum/eth2.0-specs/issues/508

### What is wrong?

For BN and BLS, FQP object should take the modulo of the input during initialization.

Test case:

```python
from py_ecc.optimized_bls12_381 import FQ, FQ2

x = FQ(-1)
y = FQ2([-1,-1])

print(x) # 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786
print(y) # (-1, -1)
```

This is used in  `modular_squareroot` part of Eth2.0 spec (https://github.com/ethereum/eth2.0-specs/blob/928f9772fa51ed2e251b99c4795097da976c4bde/specs/bls_signature.md#modular_squareroot) and Trinity (https://github.com/ethereum/trinity/blob/a1b0f058e7bc8e385c8dac3164c49098967fd5bb/eth2/_utils/bls.py#L63-L77)

### How can it be fixed

Take the mod of the inputs in FQP `__init__`

https://github.com/ethereum/py_ecc/blob/e9c42c76f1cc4f535dedec01b4c7ab2a59e46119/py_ecc/optimized_bls12_381/optimized_field_elements.py#L126-L133

Like it's done for FQ

https://github.com/ethereum/py_ecc/blob/e9c42c76f1cc4f535dedec01b4c7ab2a59e46119/py_ecc/optimized_bls12_381/optimized_field_elements.py#L25-L31


Discussion:

Patch:
diff --git a/py_ecc/optimized_bls12_381/optimized_field_elements.py b/py_ecc/optimized_bls12_381/optimized_field_elements.py
index 3f537bb..b65f138 100644
--- a/py_ecc/optimized_bls12_381/optimized_field_elements.py
+++ b/py_ecc/optimized_bls12_381/optimized_field_elements.py
@@ -239,7 +239,10 @@ class FQP(object):
 # The quadratic extension field
 class FQ2(FQP):
     def __init__(self, coeffs):
-        self.coeffs = tuple(coeffs)
+        if isinstance(coeffs[0], int):
+            self.coeffs = tuple(coeff % field_modulus for coeff in coeffs)
+        else:
+            self.coeffs = tuple(coeffs)
         self.modulus_coeffs = (1, 0)
         self.mc_tuples = [(0, 1)]
         self.degree = 2
@@ -249,7 +252,10 @@ class FQ2(FQP):
 # The 12th-degree extension field
 class FQ12(FQP):
     def __init__(self, coeffs):
-        self.coeffs = tuple(coeffs)
+        if isinstance(coeffs[0], int):
+            self.coeffs = tuple(coeff % field_modulus for coeff in coeffs)
+        else:
+            self.coeffs = tuple(coeffs)
         self.modulus_coeffs = FQ12_modulus_coeffs
         self.mc_tuples = FQ12_mc_tuples
         self.degree = 12
diff --git a/py_ecc/optimized_bn128/optimized_field_elements.py b/py_ecc/optimized_bn128/optimized_field_elements.py
index b414c02..b830b1a 100644
--- a/py_ecc/optimized_bn128/optimized_field_elements.py
+++ b/py_ecc/optimized_bn128/optimized_field_elements.py
@@ -150,9 +150,13 @@ class FQP(object):
 
     def __init__(self,
                  coeffs: Sequence[IntOrFQ],
-                 modulus_coeffs: Sequence[IntOrFQ]=None) -> None:
+                 modulus_coeffs: Sequence[IntOrFQ] = None) -> None:
         assert len(coeffs) == len(modulus_coeffs)
-        self.coeffs = coeffs
+
+        if isinstance(coeffs[0], int):
+            self.coeffs = [coeff % field_modulus for coeff in coeffs]
+        else:
+            self.coeffs = list(coeffs)
         # The coefficients of the modulus, without the leading [1]
         self.modulus_coeffs = modulus_coeffs
         # The degree of the extension field
@@ -225,8 +229,8 @@ class FQP(object):
     def inv(self) -> "FQP":
         lm, hm = [1] + [0] * self.degree, [0] * (self.degree + 1)
         low, high = (
+            self.coeffs + [0],
             # Ignore mypy yelling about the inner types for the lists being incompatible
-            cast(List[IntOrFQ], list(self.coeffs + [0])),  # type: ignore
             cast(List[IntOrFQ], list(self.modulus_coeffs + [1])),  # type: ignore
         )
         low, high = list(self.coeffs + [0]), self.modulus_coeffs + [1]  # type: ignore


Test patch:
diff --git a/tests/test_bn128_and_bls12_381.py b/tests/test_bn128_and_bls12_381.py
index 09be997..93342b7 100644
--- a/tests/test_bn128_and_bls12_381.py
+++ b/tests/test_bn128_and_bls12_381.py
@@ -29,6 +29,7 @@ def FQ12(lib):
 def field_modulus(lib):
     return lib.field_modulus
 
+
 @pytest.fixture
 def G1(lib):
     return lib.G1
@@ -124,6 +125,7 @@ def test_FQ_object(FQ, field_modulus):
     assert FQ(2) / FQ(7) + FQ(9) / FQ(7) == FQ(11) / FQ(7)
     assert FQ(2) * FQ(7) + FQ(9) * FQ(7) == FQ(11) * FQ(7)
     assert FQ(9) ** field_modulus == FQ(9)
+    assert FQ(-1).n > 0
 
 
 def test_FQ2_object(FQ2, field_modulus):
@@ -131,11 +133,18 @@ def test_FQ2_object(FQ2, field_modulus):
     f = FQ2([1, 2])
     fpx = FQ2([2, 2])
     one = FQ2.one()
+    z1, z2 = FQ2([-1, -1]).coeffs
     assert x + f == fpx
     assert f / f == one
     assert one / f + x / f == (one + x) / f
     assert one * f + x * f == (one + x) * f
     assert x ** (field_modulus ** 2 - 1) == one
+    if isinstance(z1, int):
+        assert z1 > 0
+        assert z2 > 0
+    else:
+        assert z1.n > 0
+        assert z2.n > 0
 
 
 def test_FQ12_object(FQ12, field_modulus):
@@ -143,10 +152,15 @@ def test_FQ12_object(FQ12, field_modulus):
     f = FQ12([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
     fpx = FQ12([2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
     one = FQ12.one()
+    zs = FQ12([-1]*12).coeffs
     assert x + f == fpx
     assert f / f == one
     assert one / f + x / f == (one + x) / f
     assert one * f + x * f == (one + x) * f
+    if isinstance(zs[0], int):
+        assert all(z > 0 for z in zs)
+    else:
+        assert all(z.n > 0 for z in zs)
     # This check takes too long
     # assert x ** (field_modulus ** 12 - 1) == one
 
@@ -184,6 +198,7 @@ def test_Z1_object(add, eq, double, FQ, G1, is_inf, multiply, neg, twist, Z1):
     assert eq(Z1, multiply(Z1, 3))
     assert is_inf(neg(Z1))
 
+
 def test_Z2_object(add, eq, double, FQ2, G2, is_inf, multiply, neg, twist, Z2):
     assert eq(G2, add(G2, Z2))
     assert eq(Z2, double(Z2))
@@ -194,6 +209,7 @@ def test_Z2_object(add, eq, double, FQ2, G2, is_inf, multiply, neg, twist, Z2):
     assert is_inf(neg(Z2))
     assert is_inf(twist(Z2))
 
+
 def test_none_point(lib, neg, twist):
     if lib not in [optimized_bn128, optimized_bls12_381]:
         pytest.skip()