Generalize fields and curves

[vbuterin]

Currently, there are separate folders and files for bn128 and bls-12-381, with ~90% duplicated code.

It should be possible to generalize this more, creating a generic prime field class much like there is a semi-generic FQP class, as well as generic elliptic curves, and then only have separate files for the two existing curve types to define curve parameters and twist formulas and the slightly different pairing functions.

[Bhargavasomu]

@vbuterin I am interested in generalizing and making the code flexible, could you please tell me the source of this whole codebase, such as a research paper or something. It would help me better in the understanding.

[vbuterin]

Elliptic curve pairings in general:

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

BN128:

ethereum/EIPs#197

BLS-12-381:

https://z.cash/blog/new-snark-curve/
https://github.com/zkcrypto/pairing/tree/master/src/bls12_381

[Bhargavasomu]

The following things come to my mind.

• The classes FQ, FQP, FQ2 and FQ12 need not be reinitialized every time as they are not dependent on the type of curve or extension. So probably we could have these created in field_elements.py and we could use them everywhere (bn128, optimized_bn128, bls, optimized_bls).
• We could also have a general class BaseCurve, and then maybe every curve (bn128_curve, optimized_bn128_curve, ...) could inherit this and make the changes specific to the inherited class.
• We should probably move the constants into a seperate file (constants.py)
• We should also remove the assert statements which are not part of any function, but are part of the script in general, as shown
  

  py_ecc/py_ecc/bn128/bn128_pairing.py

  Lines 74 to 83 in 067a402

  	assert linefunc(one, two, one) == FQ(0)
  	assert linefunc(one, two, two) == FQ(0)
  	assert linefunc(one, two, three) != FQ(0)
  	assert linefunc(one, two, negthree) == FQ(0)
  	assert linefunc(one, negone, one) == FQ(0)
  	assert linefunc(one, negone, negone) == FQ(0)
  	assert linefunc(one, negone, two) != FQ(0)
  	assert linefunc(one, one, one) == FQ(0)
  	assert linefunc(one, one, two) != FQ(0)
  	assert linefunc(one, one, negtwo) == FQ(0)

• Also the type hinting should be further generalized wherever possible (in terms of removing redundant types; like Optimized_FQPoint2D could be replaced by FQPoint2D). Similary the type hinting should be carried out for the bs12_381 and optimized_bs12_381 submodules.

Also the only difference I see in all the curves is

• Difference in the constants such as b, b2, b12, G2, G12 ...
• Difference in the twist function

@vbuterin are my facts right or am I missing anything.
@pipermerriam is the above design ok?

[pipermerriam]

Design seems 👍

Removing all of the runtime assertions would be nice, but lets make sure that they are all still executed as part of the test suite.

[Bhargavasomu]

@vbuterin in the twist function of bn128 and optimized_bn128, we are multiplying x by w^2 and y by w^3, whereas we should actually be dividing right? I think this is a bug (please correct me if I am wrong). Could you please follow up on this? (We are doing correctly by dividing in the case of bls_12_381 curve). Attaching the snippet for reference.

py_ecc/py_ecc/bn128/bn128_curve.py

Lines 139 to 140 in 212b193

	# Divide x coord by w**2 and y coord by w**3
	return (nx * w ** 2, ny * w**3)

[vbuterin]

@vbuterin in the twist function of bn128 and optimized_bn128, we are multiplying x by w^2 and y by w^3, whereas we should actually be dividing right? I think this is a bug (please correct me if I am wrong). Could you please follow up on this

Yeah, that seems like a mistake....

Here's the math: if in G2, y**2 - x**3 == b2 == b * w**6. In G12, b12 = b, and to achieve that we divide y by w**3 and x by x**2, so we get (y/w**3)**2 - (x/w**2)**3 = y**2 / w**6 - x**3 / w**6 = (y**2 - x**3) / w**6 = b * w**6 / w**6 = b. So division is correct.

[vbuterin]

bls, optimized_bls

I'd say keep the names as bls12_381. "BLS" by itself seems like it would refer to Boneh-Lynn-Shacham signatures, which can be done over any pairing-equipped elliptic curve (yeah, I know that's confusing... did you know that BLS as in BLS-12-381 stands for something completely different, "Barreto-Lynn-Scott"?)

[pipermerriam]

@Bhargavasomu if you've got any reference materials for the math of these functions please feel free to toss links to them in the README.

[Bhargavasomu]

@vbuterin we have another issue with the constants(b, b2, b12, G1, G2) we are using in bn128 and optimized_bn128. This is because I tried to replace multiplication by division in the twist function of both the curves, and I ended up with the following error.

This error occurs because after changing the twist function, the point G12 (which is generated by using the twist function) is no more on the bn128 curve characterized by b12 and hence the assertion fails. Attaching the snippet for reference.

py_ecc/py_ecc/bn128/bn128_curve.py

Lines 143 to 145 in b014882

	G12 = twist(cast(Point2D[FQP], G2))
	# Check that the twist creates a point that is on the curve
	assert is_on_curve(G12, b12)

To fix this, I believe we need to adjust the values of our constants. I don't know how to fix them and hence need your help on this. Thanks.

EDIT : By constants, we might also need to review the correctness of ate_loop_count, log_ate_loop_count, pseudo_binary_encoding

[Bhargavasomu]

Also piggybacking in the same thread, the following tests have been failing after I have changed the multiplication to division, on both bn128 and optimized_bn128.

• test_G12_object
• test_pairing_bilinearity_on_G1
• test_pairing_bilinearity_on_G2
• test_pairing_composit_check
  I don't know how to fix these either and would greatly appreciate help.

[Bhargavasomu]

@vbuterin, my apologies for pinging you multiple times. But I would greatly appreciate your help regarding how to adjust the constants, in regards to the above comments.

[vbuterin]

OK, I think I figured it out. In the bn128 curve, b2 = b / w**6. In the bls_12_381 curve, b2 = b * w**6. That's why it's different in the two documents and works in both.