Fast finite field arithmetic in Golang

goff (go finite field) is a unix-like tool that generates fast field arithmetic in Go.

We introduced goff in this article: the project came from the need to have performant field operations in Go. For most moduli, goff outperforms math/big and optimized libraries written in C++ or Rust.

In particular, goff modular multiplication is blazingly fast. "Faster big-integer modular multiplication for most moduli" explains the algorithmic optimization we discovered and implemented, and presents some benchmarks.

Warning

goff has not been audited and is provided as-is, use at your own risk. In particular, goff makes no security guarantees such as constant time implementation or side-channel attack resistance.

goff generates code optimized for 64bits architectures

Getting started

Install goff

# dependencies
go get golang.org/x/tools/cmd/goimports

# goff
go install github.com/consensys/goff

Usage

$ goff

running goff version 0.1.0-alpha

Usage:
  goff [flags]

Flags:
  -b, --benches          set to true to generate montgomery multiplication (CIOS, FIPS, noCarry) benchmarks
  -e, --element string   name of the generated struct and file
  -h, --help             help for goff
  -m, --modulus string   field modulus (base 10)
  -o, --output string    destination path to create output files
  -p, --package string   package name in generated files
      --version          version for goff

goff -- a short example

Running

goff -m 21888242871...94645226208583 -o ./bn256/ -p bn256 -e Element

outputs three .go files in ./bn256/

• element.go
• element_test.go
• arith.go

The generated type has an API that's similar with big.Int

Example API signature

// Mul z = x * y mod q
func (z *Element) Mul(x, y *Element) *Element {

and can be used like so:

var a, b Element
a.SetUint64(2)
b.SetString("984896738")

a.Mul(a, b) // alternatively: a.MulAssign(b)

a.Sub(a, a)
 .Add(a, b)
 .Inv(a)
 
b.Exp(b, 42)
b.Neg(b)

Benchmarks

# for BN256 or BLS377
cd examples/bls377 # or cd examples/bn256

go test -c

./bls377.test -test.run=NONE -test.bench="." -test.count=10 -test.benchtime=1s -test.cpu=1 . | tee bls377.txt

benchstat bls377.txt 

For the modular multiplication with varying modulus size

cd benches/generated
./benchmark.sh
benchstat cios.txt
benchstat fips.txt
benchstat nocarry.txt

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting pull requests to us. Get in touch: zkteam@consensys.net

Versioning

We use SemVer for versioning. For the versions available, see the tags on this repository.

License

This project is licensed under the Apache 2 License - see the LICENSE file for details