In this challenge you'll use the field arithmetic built up in this, this and this challenge to implement the group operation for several elliptic curves.
Fix a field \mathbb{F}. For example, one of the fields described on the parameter pages for MNT4-753 and MNT6-753. Then fix numbers a, b in \mathbb{F}. The set of points (x, y) such that y^2 = x^3 + a x + b is called an elliptic curve over the field \mathbb{F}.
Elliptic curves are the essential tool powering SNARKs. They're useful because we can define a kind of "addition" of points on a given curve. This is also called the "group operation" for the curve. Let's define this "addition" as follows using pseudocode, where +, *, / are all taking place in the field \mathbb{F}.
var curve_add = (p, q) => {
var s = (p.y - q.y) / (p.x - q.x);
var x = s*s - p.x - q.x;
return {
x: x,
y: s*(p.x - x) - p.y
};
};Note that this definition doesn't work in the case that p.x = q.x. This case splits into the case p.y = q.y (in which case its called "doubling" and there is a separate formula) and the case p.y = -q.y in which case a special "identity" value should be returned.
For efficiency, one uses a different, more complicated formula for adding curve points. This will be discussed in the techniques section below.
Your implementation should use one or both of the benchmark machine's GPUs to solve this problem. The machine's specifications can be found here.
h4_1 should be g4_1[0] + g4_1[1] + ... + g4_1[n - 1] where + is the group operation for the curve MNT4753.G_1.
h4_2 should be g4_2[0] + g4_2[1] + ... + g4_2[n - 1] where + is the group operation for the curve MNT4753.G_2.
h6_1 should be g6_1[0] + g6_1[1] + ... + g6_1[n - 1] where + is the group operation for the curve MNT6753.G_1.
h6_2 should be g6_2[0] + g6_2[1] + ... + g6_2[n - 1] where + is the group operation for the curve MNT6753.G_2.
Your submission will be run and evaluated as follows.
The submission runner will generate a random sequence of inputs, saved to a file PATH_TO_INPUTS.
Your binary will be compiled with ./build.sh. This step should produce a binary ./main.
Your binary will be invoked with
./main compute PATH_TO_INPUTS PATH_TO_OUTPUTSand its runtime will be recorded. The file PATH_TO_INPUTS will contain a sequence of inputs, each of which is of the form specified in the "Input" section.
It should create a file called "outputs" at the path PATH_TO_OUTPUTS which contains a sequence of outputs, each of which is of the form specified in the "Output" section.
The output of your submitted program will be checked against the reference implementation at this repo here. The "main" file is here. The core algorithm is implemented here.
Please see this page for a more full list of implementation techniques.
Points in the form (x, y) as above are said to be represented using affine coordinates and the above definition is affine curve addition.
There are more efficient ways of adding curve points which use different coordinate systems. The most efficient of these is called Jacobian coordinates. Formulas for addition and doubling in Jacobian coordinates can be found here and a Rust implementation here.
There is a further technique called "mixed addition" which allows one to add a point in Jacobian coordinates to a point in affine coordinates even more efficiently than adding two points in Jacobian coordinates. This technique can yield large efficiency gains but makes taking advantage of parallelism more complicated.
This problem is an instance of a reduction and is inherently parallel.