--- title: goff - fast modular arithmetic in Go description: goff (go finite field) is a tool that generates pure Go source code for fast modular arithmetic operations for any modulus. Developed at ConsenSys by Gautam Botrel, Gus Gutoski and Thomas Piellard. image: https://i.imgur.com/iAj7POt.png --- # Introducing `goff`: fast modular arithmetic in Go <img style="display: block;margin: auto;" width="60%" src="https://i.imgur.com/UUppBSP.png"> #### We are proud to introduce `goff` (go finite field): a tool that generates pure Go source code for fast modular arithmetic operations for any modulus. ### `goff` at a glance * `goff` produces pure Go code (no assembly^[until [this PR](https://github.com/ConsenSys/goff/pull/13)]) that is competitive with state-of-the-art libraries written in C++, Rust, or assembly. * Modular multiplication is especially fast in `goff`. :fire: We discovered and implemented an algorithmic improvement that yields a 10%--15% speed gain over state-of-the-art algorithms. See our article [Faster big-integer modular multiplication for most moduli](https://hackmd.io/@zkteam/modular_multiplication) for details and benchmarks. * The source code for `goff` is [available on GitHub](https://github.com/consensys/goff) under the [Apache 2.0 License](https://www.apache.org/licenses/LICENSE-2.0.html). :::info **Edit (Sept 2020)**: [you will find up to date benchmarks here](https://github.com/ConsenSys/gurvy#benchmarks). ::: :::warning :warning: **Warning** :warning: `goff` has not been independently audited and is provided "as-is". Use `goff` at your own risk. `goff` offers no security guarantees such as constant-time implementation or side-channel attack resistance. ::: ## `goff`: a short example The command ```bash goff -o ./bn256/ -p bn256 -e Element -m 21888242871839275222246405745257275088696311157297823662689037894645226208583 ``` outputs three Go source files in `./bn256/`: * `element.go` * `element_test.go` * `arith.go` These files define a Go type (`Element` in this example) that behaves similarly to `big.Int` from the Go standard library. For example, modular multiplication has the following signature: ```go // Mul z = x * y mod q func (z *Element) Mul(x, y *Element) *Element ``` It can be used like so: ```go 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) ``` :arrow_right: Visit our [GitHub repository](https://github.com/consensys/goff) for details on how to install and use `goff`. ## Why not use `math/big`? The Go standard library provides a `math/big` package capable of modular arithmetic. Why didn't we use it? Our journey started with `math/big` but we quickly noticed that `math/big` is 10 times slower than optimized libraries written in Rust or C++ for several reasons: * `big.Int` is a general-purpose library. It is not targeted for modular arithmetic, so core operations such as integer multiplication do not take advantage of fast algorithms for this task. * `big.Int` is meant to handle integers of varying size. Integers are stored as slices, and these slices are constantly expanding and shrinking in memory. * `big.Int` memory usage patterns induce significant overhead from Go's garbage collector. ### The cost of garbage collection It is interesting to see just how much overhead is incurred from garbage collection. Consider the following program^[adapted from [Avoiding high GC overhead with large heaps](https://blog.gopheracademy.com/advent-2018/avoid-gc-overhead-large-heaps/)], which allocates a slice of 100M `big.Int`: ```go= func main() { a := make([]big.Int, 1e8) for i := 0; i < 10; i++ { start := time.Now() runtime.GC() fmt.Printf("GC took %s\n", time.Since(start)) } runtime.KeepAlive(a) } ``` This program tells us that garbage collection takes 190ms each time it’s invoked, just to iterate through the slice. We can reduce this to 100 microseconds by replacing `big.Int` with `[4]uint64`, as arrays (not slices) are ignored by the garbage collector: ```go a := make([][4]uint64, 1e8) ``` ### The inescapable conclusion: build it ourselves In many cryptographic applications (including [our application](https://hackmd.io/@zkteam/gnark) to zero-knowledge proofs) the modulus is fixed and known in advance. This knowledge makes it practical to store multi-precision integers in fixed-size arrays, which allows us to avoid costly memory allocations. Of course, the use of arrays instead of `big.Int` means that we must implement our own arithmetic. But we need to do this anyway in order to take advantage of fast algorithms for modular arithmetic. We could not have achieved state-of-the-art prformance any other way. ## How fast is `goff`? In this article we focus on modular multiplication, which is the most performance-critical operation in many cryptographic applications. `goff` automatically generates rudimentary benchmark code in `element_test.go`. A deep dive into benchmarks can be found in our companion article [Faster big-integer modular multiplication for most moduli](https://hackmd.io/@zkteam/modular_multiplication#Benchmarks). Those benchmarks show that `goff` outperforms other optimized libraries written in Rust, C++, or assembly. Most other `goff` operations (addition, subtraction, etc) are also competitive with state-of-the-art. (The modular inverse operation is an exception---we didn't bother to optimize it because it's rarely invoked in our setting.) ### High performance Go: case study in modular multiplication For a 6-word modulus, we shrinked execution time of the modular multiplication from roughly `500ns` to `50ns`, a 10x improvement. How did we do it?^[[Dave Cheney's workshop materials](https://dave.cheney.net/high-performance-go-workshop/gophercon-2019.html) is a great resource for high-performance Go.] #### Avoid memory allocations, garbage collection ==`500ns` $\to$ `160ns`== As discussed above, avoiding memory allocations using fixed size arrays instead of `big.Int` yields a significant performance improvment. #### Prefer `math/bits` over assembly [`math/bits`](https://golang.org/pkg/math/bits/) provides blazingly fast `uint64` addition, subtraction and multiplication. The Go compiler can recognize some function signatures (like the ones in `math/bits`) and replace them with the best platform-specific instructions. Thanks to these [Go compiler intrinsics](https://dave.cheney.net/2019/08/20/go-compiler-intrinsics), we quickly eliminated the need to write assembly code. There are several advantages to avoiding the use of assembly code. For example: * Assembly is not easy to maintain, nor to test across platforms. * The Go compiler won’t inline assembly code, but will inline `math/bits` functions. Go does not allow developers to force the compiler to inline a function, which can hurt performance in some cases. However, since `goff` generates Go source code, we are able to bypass this restriction and force inlining simply by instructing `goff` to replicate certain code snippets thoughout the codebase. #### Flatten `for` loops ==`160ns` $\to$ `90ns`== The Go compiler implements every `for` loop with `JMP` and `CMP` instructions, even if the number of iterations is known at compile-time. (Example: `for i:=0; i<6; i++`.) To combat this, `goff` code generation uses templates to unroll loops: ```go {{- range $i := .NbWordsIndexesFull}} z[{{$i}}] = x[{{$i}}] {{- end}} ``` Loop flattening may not always be the best option, and can become impractical as the code size grows due to caching issues. But we used it to considerable advantage in `goff`. #### Dissassemble and optimize low-level arithmetics ==`90ns` $\to$ `65ns`== In the algorithm we implemented for modular multiplication, most of the work is done by a function that computes: $$(hi, lo) = a*b + c + d$$ Our initial implementations looked like this: ```go func madd2(a, b, c, d uint64) (hi uint64, lo uint64) { a, b = bits.Mul64(a, b) lo, c = bits.Add64(c, d, 0) lo, hi = bits.Add64(b, lo, 0) hi, _ = bits.Add64(a, c, hi) return } ``` The above code runs in `1.6ns`. You might think here there isn't much room for improvement. Surprisingly, *adding* an instruction made it run in `1.1ns`: ```go // madd2 hi, lo = a*b + c + d func madd2(a, b, c, d uint64) (hi uint64, lo uint64) { var carry uint64 hi, lo = bits.Mul64(a, b) c, carry = bits.Add64(c, d, 0) hi, _ = bits.Add64(hi, 0, carry) lo, carry = bits.Add64(lo, c, 0) hi, _ = bits.Add64(hi, 0, carry) return } ``` The assembly output of the first version showed `SBBQ` and `NEGQ` instructions that we didn't expect. Turns out CPUs have a [special register to store the carry](https://en.wikipedia.org/wiki/Carry_flag) from the `ADD`, and "saving it for later" is counter-productive. #### Do less ==`65ns` $\to$ `50ns`== Hunting these last nanoseconds came from an algorithmic improvment described in [our companion article](https://hackmd.io/@zkteam/modular_multiplication#Implementation), and from trimming the edges. Typically, the first iteration of a `for` loop may have some variables always set to 0, or the final iteration may write directly to the result, avoiding a few extra copies. Some tricks are obvious, like: ```go // IsZero returns z == 0 func (z *Element) IsZero() bool { return (z[3] | z[2] | z[1] | z[0]) == 0 } ``` instead of ```go // IsZero returns z == 0 func (z *Element) IsZero() bool { return z[3] == 0 && z[2] == 0 && z[1] == 0 && z[0] == 0 } ``` And some are more obscure. Like scoping variables (it's a hint to the compiler that it doesn't need to `MOV` an un-needed value) or cache misses. #### Cache friendliness There is a lot to say about CPU caches---[here is good read](https://lwn.net/Articles/252125/), and not many (any?) tools in Go to help developers understand what's happening. A widely known rule of thumb that helped us make `goff` faster: consider memory access patterns. CPUs fetch an entire line in the cache at a time---consider using what you access immediatly, and not scattered accross a function. #### A strange example: 3 variables or a length-3 array? `goff` with a 12-word (768-bit) modulus, declaring (1) ```go var c [3]uint64 ``` or (2) ```go var c0, c1, c2 uint64 ``` will result in an execution time of the modular multiplication of `~800ns`(1) or `~220ns`(2) !:exploding_head: Yet, for moduli smaller than 11 words, (1) is faster than (2). We would love to know why. :slightly_smiling_face: #### Generating x64 assembly ==`50ns` $\to$ `33ns`== (:exploding_head:) More on that [here](https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf). ## What's next? Our main focus is [`gnark`](https://hackmd.io/@zkteam/gnark), a fast library for zero-knowledge proofs. Work on `gnark` may drive more effort into [`goff`](https://github.com/consensys/goff) in the coming months. Next steps for `goff` include: - templates (code generation) clean up - extensive testing - constant time version of some APIs - further optimizations for specific modulus sizes - security audit :+1: [Issues](https://github.com/consensys/goff/issues), new features suggestions and PRs are welcome. --- <img style="float:left;width:90px;margin-right:20px;" src="https://i.imgur.com/tYQ8i9r.png"> *`goff` was written by [Gautam Botrel](https://www.linkedin.com/in/gautam-botrel/), [Gus Gutoski](https://www.linkedin.com/in/ggutoski/), and [Thomas Piellard](https://www.linkedin.com/in/thomas-piellard-53b881129/).* *We’re a research team at [ConsenSys](https://consensys.net/). If you are interested in our work (fast finite field arithmetic, elliptic curve pairings, zero-knowledge proofs), [give us a shout](mailto:zkteam@consensys.net).*
Last changed by  
 
gnark
We’re a research team @Consensys / Linea. We work on zero knowledge proof systems.
4036

Read more

What changes for BW6-761?

Authors: Youssef El Housni (ConsenSys, GRACE) and Aurore Guillevic (Inria, Aarhus University) Last year in [HG20], we introduced the BW6-761 curve which is a pairing-friendly curve that forms a 2-chain with BLS12-377 (previously introduced in ZEXE). That is, BW6-761 has a subgroup order $r$ precisely equal to the characteristic $q$ of the base field on which BLS12-377 is defined. In a recent work [HG21], we generalised the curve construction, the pairing formulas ($e : \mathbb{G}_1 \times \mathbb{G}_2 → \mathbb{G}_T$) and the group operations to any BW6 curve defined on top of any BLS12 curve, forming a family of 2-chain pairing-friendly curves. We also investigated other possible 2-chain families, and much more (read the paper!). Since BW6-761 is already implemented in few projects (gnark-crypto, arkworks, EY/libff, kilic/bw6 and constantine) and is used in production (Celo, Aleo), natural questions arise: What changes for BW6-761 after this work? Is the new formulas backward-compatible with the current implementations? If not, does it worth switching? The new general construction where BW6-761 would fall, is coherent with the groups operations and pairing formulae found previously in [HG20]. However, we found new pairing algorithms that are faster. In this note, we try to shed light on the differences and the backward compatibilty. Pairing computation Given $P \in \mathbb{G}_1$ and $Q \in \mathbb{G}_2$, a pairing computation for BW6 is

10/12/2022
Yet another curve, but THE curve for your KZG!

With my co-authors Aurore Guillevic and Diego F. Aranha, we published on ePrint mid-May a survey of elliptic curves for proof systems (ePrint 2022/586). Recently, there have been many tailored constructions of these curves that aim at efficiently implementing different kinds of proof systems. In that survey we provide the reader with a comprehensive view on existing work and revisit the contributions in terms of efficiency and security. We present an overview at three stages of the process: curves to instantiate a SNARK, curves to instantiate a recursive SNARK, and curves to express an elliptic-curve related statement. In this post, we are only interested in the first case. For pairing-based SNARKs, such as the circuit-specific Groth16 [1], bilinear pairings ($e:\mathbb{G}_1\times \mathbb{G}_2 \rightarrow \mathbb{G}_T$) are needed for the proof verification. For universal SNARKs, such as PLONK [2] or Marlin [3], a polynomial commitment scheme is needed. An example of an efficient one is the Kate-Zaverucha-Goldberg (KZG) scheme [4]. The verifier needs to verify some polynomial openings using bilinear pairings. So far, for both circuit-specific and universal constructions, the verification algorithms boil down mainly to pairing computations. However, the prover work is not the same. For Groth16, it is mainly multi-scalar-multiplications (MSM) in both $\mathbb{G}_1$ and $\mathbb{G}_2$ while for KZG-based schemes it is mainly MSMs in $\mathbb{G}_1$ only. In section 4 of the survey paper, we look at a particular family of pairing-friendly elliptic curves suitable for KZG. We derive algorithm 6 to tailor this family to the SNARK context. Note that KZG is also useful for other compelling applications such as Verkle trees for blockchain stateless clients. Pairing-friendly curves

6/14/2022
BW6 over BLS12-381

Authors: Youssef El Housni (ConsenSys, GRACE) and Aurore Guillevic (inria) Following the recent work on FFT over non-smooth fields (ECFFT), it might be viable to instantiate a SNARK with an elliptic curve of non-smooth subgroup order. Particularly, one layer SNARK composition can be achieved with less constraints for the choice of curves. In this note we propose a 2-chain based on the widely used BL12-381 curve. The outer curve is a BW6 with a subgroup order 2-adicity equal to one. ECFFT For smooth finite fields $\mathbb{F_q}$ (i.e., when $q−1$ factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown. [In a recent work by Ben-Sasson, Carmon, Kopparty and Levit, called ECFFT, the authors proposed a new approach to fast algorithms for polynomial operations over all large finite fields.] The key idea is to replace the group of roots of unity with a set of points $L \subset F$ suitably related to a well-chosen elliptic curve group (the set $L$ itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval $[q+1\pm2\sqrt{q}]$ and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. (From the paper's abstract) 2-chains

6/2/2022
Benchmarking pairing-friendly elliptic curves libraries

last benchmark update: 29/01/21 There are several pairing-friendly elliptic curves libraries used in zero-knowledge proofs (ZKP) projects. Typically, the most important elliptic curve operations in ZKP schemes are "multi scalar multiplication" (MSM) and "pairing product" (PP). This writeup is a try to benchmark and compare the building blocks of these operations in two different architechtures. In fact, since MSM and PP are size-dependant, we focus on timings of mixed addition in G1/G2, doubling in G1/G2, Miller loop and Final exponentiation. The libraries are written in different languages with different software and mathematical optimizations, and with more or less assembly code. The target curves are: BN254, BLS12-381, BLS12-377 and BW6-761. The chosen libraries are:

4/22/2021
Read more from gnark
Published on HackMD