This is the second of three code-centric blog posts on pairing based cryptography. The first post [1] covered modular arithmetic, finite fields, the embedding degree, and presented an implementation of a 12-degree prime extension field tower. The series will ultimately conclude with a detailed review of the popular BLS12-381 pairing operations found in a variety of applications such as BLS signatures [2]. Support for these operations in an Ethereum precompiled contract has been proposed [3], and support for a related pairing configuration in precompiled contracts is already in operation [4, 5]. For now, this second post introduces the required elliptic curves, describes the implementation of quite a few group/curve operations, shows how the necessary input validation is performed and finishes with a presentation of the sextic twist.
These blog posts complement existing theoretical resources by placing a strong emphasis on actual working code. Everything will be demonstrated inside of just 200 lines [6] of Haskell accompanied by generous comments and whitespace. The source code is available at https://github.com/nccgroup/pairing-bls12381 to facilitate experimentation. We provide line numbers that match the source code in ./Crypto/Pairing_bls12381.hs [7] where all the action takes place. Note that the Filecoin project [8] also has some great examples written in Rust which provide a complementary perspective.
Points, groups, generators and negation
We will define a point on an elliptic curve to consist of either an x and y coordinate pair or the special PointAtInfinity element, as shown below. Note that this type declaration uses the arbitrary type variable a to defer defining the exact type of the underlying coordinates, but does label them ax and ay so we can individually reference them later. The type variable forces each of the coordinate types to be consistent with each other, and the compiler must be told to automatically derive a simplistic equivalence relation Eq along with a trivial ‘print format’ Show function on line 215. While projective point types (e.g., involving three coordinates each) can be faster, we target only affine points due to their simplicity and support for more intuitive geometric reasoning.
In the last blog post, we defined and developed code around a variety of finite fields. This time we will additionally work with groups. A group is defined as consisting of a set along with a binary operation that together satisfy a few properties:
- An operation on two elements of the set results in another element of the set.
- The operation is associative.
- A unique identity element exists.
- An inverse exists for every element.
In our case, the group set consists of points that are valid solutions to the elliptic equations E1: y2 = x3 + 4 and E2: y2 = x3 + 4(u+1). The first equation pertains to group g1 containing points of type Fq1, while the second equation pertains to group g2 containing points of type Fq2. The groups have the same order, and the Fq1 and Fq2 fields were implemented in the first blog post. Later, we will see the PointAtInfinity serving as the identity element for both groups. The generator constants for each group are shown below with the type information in purple. Each one is preceded by a type declaration.
Regarding the above code, each generator constant is wrapped in a Maybe structure which is able to contain Nothing or Just a value, where value must be a point in the relevant field. This is done for constants and functions that are exported. Some of the fixed values shown above are trimmed to avoid tiny fonts; the full values can be found in the source code on GitHub. When the above standard generators are repeatedly added to themselves, they will enumerate every element of their group set and ‘finish’ with the PointAtInfinity.
Our first group function happens to be the very simplest: point negation. As before, we preface the function with its type signature on line 294 below. The text in parenthesis requires that the type variable a must satisfy the Field and Eq interfaces, as all of the fields we implemented earlier do. The signature then indicates the function takes a Point of type a and returns a Point of that same type. An interesting aspect of this approach is that we have specified a function that can take a point consisting of coordinates from any of our four previously implemented fields.
The actual point negation function is implemented on line 295 above. On the left of the central equal sign, we see pattern matching that ‘deconstructs’ individual ax and ay coordinates from a supplied point argument and places these into the x1 and y1 parameters. The right side of the central equal sign constructs an affine point with the x1 coordinate unchanged and the y1 coordinate negated. Recall that the Field interface extends the Num interface, and the latter provides both the fromInteger() constructor and the multiplication * operator needed to operate on y1. Finally, consider the elliptical curve equations above: if a particular x, y combination is a valid solution, then the x, -y combination is also a valid solution due to the y2 term. Hence, we have a valid negated point.
Point addition and doubling
Now things get particularly interesting. Line 270 below declares the type signature of our point addition function. As before, the type variable in parenthesis requires a to meet the Field and Eq interfaces. The type signature then indicates that two Points of type a are passed into the function and one point of the same type returned. Also as before, points of any of our four Field types are permissible function arguments, though in practice we will use only Fq1 and Fq2 here.
The pattern matching on lines 271 and 272 declare that if one of the function arguments is the identity element, then the result is simply the other argument. The clauses are evaluated in the order defined, so by the time line 273 is encountered we are certain to have a point containing individual coordinates that can now be ‘deconstructed’ through more detailed pattern matching. Lines 274 and 275 handle our other two edge cases. First, when both of the x and y coordinates are equal, the Point arguments are equal, and we delegate the calculation to the point doubling function instead. Second, when only the y coordinates differ, the arguments represent two points on a vertical line which sum to PointAtInfinity by definition.
Lines 276-280 above form the meat of the point addition calculation. On line 276 we return an affine point constructed with x3 and y3, where these terms are calculated on line 277 onward. First, the slope is calculated on line 278 and then this is used to calculate x3 and y3.
Next, the point doubling routine below is very similar to what we have already seen. This time the function only takes one argument with the same type constraints that we have already seen, and has only one corner case to handle on line 285. On line 286 we return an affine point constructed with x3 and y3, where these terms are calculated one line 287 onward. First, the slope (tangent) is calculated on line 288 and then this is used to calculate x3 and y3.
Point multiplication
One difference between a field and a group is that the latter only supports one operation rather than two, and in our case that single group operation is addition. However, we can define a function that repeatedly adds the same point together a specified number of times and denote this to be a point multiplied by a scalar. We declare the type signature of this function on line 299 below to accept an integer multiplier and a point multiplicand. Clearly, simple repetitive addition becomes nonviable when the scalar becomes large, so we have to take a double and add approach which is well known in the literature. This approach is why we see a pair of functions below – the first function sets up then initiates a recursive execution of the second function which does the double and add. Note that it is common Haskell style for the names of helper functions to differ by a only single character (typically ') at the end.
We first pattern match the scalar and base arguments on line 300 and then encounter a series of guard clauses. Later we will implement the isOnCurve function that takes a single point argument and returns a boolean true/false based on point validity. Assuming our point is on the curve, when the scalar is positive on line 301, we construct a Maybe (Point a) type with the results of our helper function inside of Just. For a valid point when the scalar is negative on line 302, we first negate both the scalar and the point before calling the helper function exactly as before. The otherwise clause will be executed when the point argument did not lie on the curve, and in this case we return a Nothing (arguably, PointAtInfinity could be returned).
As can be seen in the type signature on line 308 above, our point multiplication helper function takes an integer multiplier, a point multiplicand and a point accumulator. The latter was set-up in the primary function to initially be PointAtInfinity which is our neutral element; think of this as a sort of 0 point initial value that will accumulate as the helper function recursively executes.
If the scalar is odd, line 311 will recursively call this same helper function again with new arguments. These new arguments consist of the scalar divided by 2, a doubled base point, and the base point added into the accumulator. Line 312 is similar and handles the case of an even scalar where the accumulator does not see the addition of the base point. One line 310, we see that when the scalar becomes zero, the function will return the latest accumulator value.
We have now implemented point addition, point negation, (point subtraction via the former two operations) as well as point multiplication. The first and last of these are exported from the module, so the results are delivered inside the Maybe structure.
Point validation
In each of the functions involving points we saw a variety of corner cases handled. Along similar lines, we need functions that validate points are actually on their corresponding curve and belong to a group of the correct order. We will see that this is particularly important when outside values enter our logic via the use of exported functions.
The point multiplication routine described above tests its input point to ensure it is on the curve. The type signature for isOnCurve shown on line 238 below should feel familiar by now. Line 239 considers the PointAtInfinity to be off curve, and line 240 returns the result from checking the curve equation left side is identical to its right side. Line 240 sees us refer to the individual ax and ay coordinates. Note that when a Fq1 point is involved, its mul_nonres() function variant simply returns the value it is given. When a Fq2 point is involved, its mul_nonres() function variant performs a multiplication by u+1. This allows the exact same expression to handle the minor difference between the E1 and E2 curve equations.
We will also need to check that user supplied points are in the correct group of order groupOrder. This is straightforward: on line 245 we perform a multiplication and checks that the result is PointAtInfinity.
Finally we implement the g1Point and g2Point constructors above that are exported for external use. As with other exported functions, their type declaration on lines 249 and 257 indicate their results are wrapped in the Maybe structure. Other than that, the functions simply consume a sufficient number of integers to fully populate their point structure via explicit fromInteger() calls and the resulting point is returned if it is in the correct subgroup. Note that the subgroup check calls the point multiplication function which in turn ensures the point is on the curve, so both checks are covered.
The sextic twist
In the first blog post we said that an embedding degree of 12 was required to allow another group g2 of the correct order matching g1 to emerge. This directly drove us to implement a 12-degree prime extension field that has so far remained unused. It turns out that this Fq12-based group can be mapped from Fq2 for purposes of evaluating operations related to the second elliptic curve equation. This mapping is called the sextic twist [9, 10] and is shown below. We can perform relevant operations in Fq2 and are now able to map into Fq12 as needed. This effectively results in a dramatic reduction of work necessary to perform our curve operations on the second group. We will see much more of this function in the next blog post.
As can be seen in the type declaration above, a Fq2 point is supplied and a Fq12 point is returned. The calculation itself is fairly simple on the surface but does involve calculating the multiplicative inverse of a 12th degree polynomial; fortunately, we will have no need to go in the reverse direction. The 0 and 1 entries on lines 321-323 are supplied to an implicit fromInteger() constructor to create the correct types as required.
What have we learned?
While the first blog post dealt mostly with fields, this blog post focused on points, groups and curves. We declared a point type that could handle all four of our fields as coordinates, and exported the g1 and g2 generators alongside arbitrary g1Point and g2Point constructors, all wrapped in Maybe structures. The resulting points can be used in our implementation of point negation, point addition, point doubling and point multiplication. We implemented the necessary input validation to check that points indeed lie on the curve and are of the correct order. Finally, the sextic twist was implemented to bridge the Fq2 and Fq12 fields, which we will see more of in the next blog post on the pairing operations themselves.
What’s next?
The next post will conclude the series by looking at the implementation and usage of the actual pairing operations themselves. We will see an approach very similar to the double and add strategy used in the above point multiplication implementation employed on a Miller loop. The conclusion will touch on how BLS signatures based on pairing operations work and also present a few even more intriguing operations that can be performed.
References
- https://research.nccgroup.com/2020/07/06/pairing-over-bls12-381-part-1-fields/
- https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/
- https://eips.ethereum.org/EIPS/eip-2537
- https://eips.ethereum.org/EIPS/eip-196
- https://eips.ethereum.org/EIPS/eip-197
- Reported by the cloc tool at https://github.com/AlDanial/cloc
- https://github.com/nccgroup/pairing-bls12381/blob/master/Crypto/Pairing_bls12381.hs
- bls-signatures, pairing, group and ff at https://github.com/filecoin-project
- Guide to Pairing Based Cryptography, El Mrabet Joye, chapter 6
https://www.routledge.com/Guide-to-Pairing-Based-Cryptography/author/p/book/9781498729512 - A note on twists for pairing friendly curves
http://indigo.ie/~mscott/twists.pdf
