Multi-exponentiation

Quick details

• Problem: Compute the multi-exponentiation of an array of (scalar, curve-point) pairs for the 4 relevant groups.
• Prize:

Problem specification

The following problem is defined for any choice of (G, Scalar) in

• MNT4753: (MNT4753.(G_1), 𝔽_MNT4753.r)
• MNT4753: (MNT4753.(G_2), 𝔽_MNT4753.r)
• MNT6753: (MNT6753.(G_1), 𝔽_MNT6753.r)
• MNT6753: (MNT6753.(G_2), 𝔽_MNT6753.r)

You can click on the above types to see how they will be represented in the files given to your program. uint64 values are represented in little-endian byte order. Arrays are represented as sequences of values, with no length prefix and no separators between elements. Structs are also represented this way.

Parameters

The parameters will be generated once and your submission will be allowed to preprocess them in any way you like before being invoked on multiple inputs.

• n : uint64
• g : Array(G, n)

Input

• s : Array(Scalar, n)

  Elements of s will be represented in standard form as a little-endian array of 12 64-bit unsigned limbs. This form is more likely to be useful than Montgomery representation for this problem.

Output

• y : G

Expected behavior

The output should be the multiexponentiation with the scalars s on the bases g. In other words, the group element s[0] * g[0] + s[1] * g[1] + ... + s[n - 1] * g[n - 1].

In pseduocode, something like

var g = [g0, g1, .., gn];

var multiexp = (s) => {
  var res = G_identity;
  for (var i = 0; i < s.length; ++i) {
    var sg = G_scale(s[i], g[i]);
    res = G_add(res, sg);
  }
  return res;
}

Submission guidelines

Your submission will be run and evaluated as follows.

0. The submission-runner will randomly generate the parameters and save them to files PATH_TO_MNT4753_PARAMETERS and PATH_TO_MNT4753_PARAMETERS and PATH_TO_MNT6753_PARAMETERS and PATH_TO_MNT6753_PARAMETERS.

1. Your binary main will be run with

       ./main MNT4753 preprocess PATH_TO_MNT4753_PARAMETERS
   ./main MNT4753 preprocess PATH_TO_MNT4753_PARAMETERS
   ./main MNT6753 preprocess PATH_TO_MNT6753_PARAMETERS
   ./main MNT6753 preprocess PATH_TO_MNT6753_PARAMETERS

   where PATH_TO_X_PARAMETERS will be replaced by the actual path.

   Your binary can at this point, if you like, do some preprocessing of the parameters and save any state it would like to files ./MNT4753_preprocessed and ./MNT4753_preprocessed and ./MNT6753_preprocessed and ./MNT6753_preprocessed.

2. The submission runner will generate a random sequence of inputs, saved to a file PATH_TO_INPUTS.

3. Your binary will be compiled with ./build.sh. This step should produce a binary ./main.

4. Your binary will be invoked with

       ./main MNT4753 compute PATH_TO_MNT4753_PARAMETERS PATH_TO_INPUTS PATH_TO_OUTPUTS
   ./main MNT4753 compute PATH_TO_MNT4753_PARAMETERS PATH_TO_INPUTS PATH_TO_OUTPUTS
   ./main MNT6753 compute PATH_TO_MNT6753_PARAMETERS PATH_TO_INPUTS PATH_TO_OUTPUTS
   ./main MNT6753 compute PATH_TO_MNT6753_PARAMETERS PATH_TO_INPUTS PATH_TO_OUTPUTS

   and 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.

   It can, if it likes, read the preprocessed files created in step 1 in order to help it solve the problem.

Reference implementation

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.