Fastest JavaScript/WebAssembly verifier

Quick details

• Problem: Implement the Bowe--Gabizon verifier for MNT6-753 to run in the browser using JavaScript and/or WebAssembly.
• Prize:
  • Fastest at end of competition when run on Firefox: $10,000

The Bowe--Gabizon SNARK is a variation on the Groth16 SNARK. This challenge involves implementing the verifier algorithm for the Bowe--Gabizon SNARK using JavaScript or WebAssembly so that it can be run in a browser.

We'll use Typescript to give a specification of the functions your JavaScript program should implement.

The Bowe--Gabizon verifier consists of several functions. You can, if you choose, implement only these algorithms and default implementations will be provided for the rest.

We'll call the top-level verifier algorithm boweGabizonVerifier. Here is a "call graph" of functions used by boweGabizonVerifier:

• boweGabizonVerifier
• hashToGroup
  • pedersenHash
  • groupMap
• boweGabizonVerifierCore

So, boweGabizonVerifier calls into hashToGroup and boweGabizonVerifierCore. hashToGroup in turn calls into pedersenHash and groupMap.

You can implement as many of these functions as you like. If you implement a function, any implementations of "children functions" will be ignored and that function will be used.

For example, if you want to replace everything, you can implement boweGabizonVerifier.

If you only want to replace the Pedersen hash, you can just implement pedersenHash and the rest of the functions will be filled in with default implementations.

Submission format

Your submission be a file called main.js containing implementations of any of the following 5 functions:

function boweGabizonVerifier(
  vk : VerificationKey,
  input : Fr,
  proof : Proof) : boolean {
  ...
};

function groupMap (x : Fq) : AffineG1 {
  ...
};

function pedersenHash (ts : Array<[boolean, boolean, boolean]>) : Fq {
  ...
};

function hashToGroup (
  a : AffineG1,
  b : AffineG2,
  c : AffineG1,
  deltaPrime : AffineG2) : AffineG1 {
  ...
}

function verifierCore (
  vk : VerificationKey,
  input : Fr,
  proof : ExtendedProof) : boolean {
  ...
};

where the types are defined as follows, with Fq representing an element of MNT4-753.\mathbb{F}_q. Please see

• this page for specifications of the behavior of boweGabizonVerifier and verifierCore.
• this page for specifications of the behavior of pedersenHash, groupMap, and hashToGroup.

// An array of length 24.
type Fq = Uint32Array

type Fr = Fq;

type Fq3 = {
  a : Fq,
  b : Fq,
  c : Fq,
};

type Fq6 = {
  a : Fq3,
  b : Fq3,
};

type AffinePoint<F> = {
  x : F,
  y : F,
};

type AffineG1 = AffinePoint<Fq>;
type AffineG2 = AffinePoint<Fq3>;

type Proof = {
  a          : AffineG1,
  b          : AffineG2,
  c          : AffineG1,
  deltaPrime : AffineG2,
  z          : AffineG1,
};

type ExtendedProof = {
  a          : AffineG1,
  b          : AffineG2,
  c          : AffineG1,
  deltaPrime : AffineG2,
  z          : AffineG1,
  yS         : AffineG1,
};

type VerificationKey = {
  alphaBeta : Fq6,
  delta : AffineG2,
  query : Array<AffineG1>,
};

Starter code

• You can find a complete OCaml implementation (which compiles to JavaScript with js_of_ocaml) here.
• This TypeScript/JavaScript spec is a great place to get started.
• You can find TypeScript/JavaScript implementations of pedersenHash, groupMap, and hashToGroup. here, with the implementation of finite-field arithmetic stubbed out.