Galois: a JavaScript/WASM library for finite field arithmetic

I originally wrote this library for the genSTARK project, but it evolved into a pretty nifty stand-alone module. The library is here:

High-level features are:

  • Basic modular arithmetic (addition, subtraction, multiplication, inversion, exponentiation).
  • Bulk operations on vectors and matrixes.
  • Basic polynomial operations (addition, subtraction, multiplication, division).
  • Polynomial evaluation and interpolation (using Lagrange and FFT methods).

At this point, only prime fields are supported.

WebAssembly optimization

One of the cool features of the library is a flexible optimization architecture. It is pretty simple to write optimization modules for different types of fields.

So far, I wrote an optimization module in WASM for 128-bit prime fields with modulus of the form 2^{128}-k, where k < 2^{64}.This resulted in the overall speed of up to 6x - 10x as compared to native JavaScript implementation. Here are some high-level benchmarks run on Intel Core i5-7300U @ 2.60GHz (single thread):

Operations/sec JS BigInt (256-bit) JS BigInt (128-bit) WASM (128-bit)
Additions 3,200,000 5,000,000 44,000,000
Multiplications 950,000 1,850,000 16,300,000
Exponentiations 3,200 10,500 97,000

WASM performance can be optimized further. Specifically, SIMD and multi-threaded evaluation is something that I’m planning to implement at some point in the future (once support for these in WASM becomes more mature). But even as is, I believe the numbers are within 2x - 4x of what can be achieved with a native C implementation.

The library is still very new, and there are a bunch of things to fix and improve (see the issues in the repo). So, would appreciate any feedback, help, and support.


Cool! There is some overlap between the features here and what websnark does. I see this is written in Assemblyscript, it would be interesting to compare the benchmarks against websnark.

I’m very interested in a binary field implementation, as it’s something we’d like to benchmark in wasm. We have lots of example applications using prime fields (elliptic curves and SNARKs/pairings etc.), including the STARK implementations using prime fields (genSTARK, and even the starkDEX solidity code), all of which can be ported/compiled to wasm (e.g. this scout STARK example). But we can’t find a STARK implementation using binary fields, and so the performance of binary field arithmetic in wasm is an open question for us.

Thanks! Would love to benchmark this against other implementations - but not sure how to benchmark modular arithmetic ops with websnarks.

As for binary fields - I’ve stubbed it out here, but a workable implementation is probably some time away. I’d like to first stabilize the overall architecture using the prime field implementation (that’s probably another 1 or 2 iterations away). But once the interfaces stabilize, it should be fairly straightforward to plug in a binary field implementation into the existing structure.