Now that we've implemented arithmetic in a prime-order field in a previous challenge, we can implement field extension arithmetic, which we'll need for multi-exponentiation.
Let's review what exactly a field extension is. The actual operations needed are actually pretty simple, so if you just want to get started coding, you can safely skip this section.
A field extension of a field \mathbb{F} is another field \mathbb{F}' which contains \mathbb{F}. To use a familiar example, \mathbb{R}, the field of real numbers is a field extension of the field \mathbb{Q} of rational numbers.
In the SNARK challenge and in cryptography in general, we work with finite fields, and the extension fields we'll consider will be finite fields as well.
The simplest kind of field extension and the one we'll implement here is called a quadratic extension. The idea is the following. First we'll start with our prime order field \mathbb{F}_q where q is MNT4753.q. Then, we'll pick a number in \mathbb{F}_q which does not have a square root in \mathbb{F}_q. In our case, we'll use 13.
Now we can define the field we call \mathbb{F}_q[x] / (x^2 = 13). This is the field obtained by adding an "imaginary" square root x for 13 to \mathbb{F}_q. It's a lot like how the complex numbers are constructed from the real numbers by adding an "imaginary" square root i for -1 to \mathbb{R}.
Like the complex numbers, the elements of \mathbb{F}_q[x] / (x^2 = 13) are sums of the form a_0 + a_1 x where a_0 and a_1 are elements of \mathbb{F}_q. This is a field extension of \mathbb{F}_q since \mathbb{F}_q is contained in this field as the elements with a_1 = 0. For short, we call this field \mathbb{F}_{q^2} since it has q^2 elements.
In code, you can think of an element of \mathbb{F}_{q^2} as a pair (a0, a1) where each of a_0, a_1 is an element of \mathbb{F}_q or a struct { a0 : Fq, a1 : Fq }.
This problem will have you implement addition and multiplication for \mathbb{F}_{q^2}. Addition and multiplication are defined how you might expect:
\displaystyle \begin{aligned} (a_0 + a_1 x) + (b_0 + b_1 x) &= (a_0 + b_0 ) + (a_1 + b_1 )x \\ (a_0 + a_1 x) (b_0 + b_1 x) &= a_0 b_0 + a_1 b_0 x + a_0 b_1 x + a_1 b_1 x^2 \\ &= a_0 b_0 + a_1 b_0 x + a_0 b_1 x + 13 a_1 b_1 \\ &= (a_0 b_0 + 13 a_1 b_1 ) + (a_1 b_0 + a_0 b_1 ) x \end{aligned}
In pseduo-code, this would be
var alpha = fq(13);
var fq2_add = (a, b) => {
return {
a: fq_add(a.a0, b.a0),
b: fq_add(a.a0, b.a0)
};
};
var fq2_mul = (a, b) => {
var a0_b0 = fq_mul(a.a0, b.a0);
var a1_b1 = fq_mul(a.a1, b.a1);
var a1_b0 = fq_mul(a.a1, b.a0);
var a0_b1 = fq_mul(a.a0, b.a1);
return {
a0: fq_add(a0_b0, fq_mul(a1_b1, alpha)),
a1: fq_add(a1_b0, a0_b1)
};
};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.
The output should be have z[i] = x[i] * y[i] where * is multiplication in the field 𝔽MNT4753.q2 as described above.
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.
The pseduocode above does 4 \mathbb{F}_q multiplications, 1 multiplication by 13 (which can be made much cheaper than a general multiplication if it is special-cased), and 2 additions.
If you want to get the most efficiency, it's good to reduce the number of multiplications, as they are much more costly than additions. There is a trick to do so, described in section 3 of this paper but let's go through it here. The net result of the trick is that we'll get down to 3 multiplications, 1 multiplication by 13, and 5 additions/subtractions. So we need to do more additions and subtractions, but we do one less multiplication, which is a big win.
In pseudo-code, the trick is
var fq2_mul = (a, b) => {
var a0_b0 = fq_mul(a.a0, b.a0);
var a1_b1 = fq_mul(a.a1, b.a1);
var a0_plus_a1 = fq_add(a.a0, a.a1);
var b0_plus_b1 = fq_add(b.a0, b.a1);
var c = fq_mul(a0_plus_a1, b0_plus_b1);
return {
a0: fq_add(a0_b0, fq_mul(a1_b1, alpha)),
a1: fq_sub(fq_sub(c, a0_b0), a1_b1)
};
};