Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

Question

zk-STARKs make use of FRI for low degree testing of polynomials.

The zk-STARKs paper states on page 11:

we stress that ZK-STARK could also operate over prime fields but we have not realized this in code

With a footnote

the FRI system requires p to contain a sufficiently large multiplicative subgroup of order $2^{t+\mathcal{O}(1)}$; such prime fields abound, as implied by Linnik’s Theorem.

This helpful blog post which explains and implements code similar to libSTARK states:

STARKs “in real life” (ie. as implemented in Eli and co’s production implementations) tend to use binary fields and not prime fields for application-specific efficiency reasons

If binary fields give some kind of advantage, what advantage do they provide?

Answer 1

Caution: This answer is about the basics of why binary fields $\Bbb F_{2^k}$ are sometime preferred to prime fields $\Bbb Z_{p}$. It does not cover the specifics there may be for zk-STARKs, libSTARK or FRI.

Binary fields allow the use of XOR rather than addition with carry, and carry-less multiplication. That makes computations of field arithmetic easier, because carries requires code (for large arguments as used in cryptography, especially for SIMD implementations including SSEn), or circuitry, thus power and time. Removing carries removes the need for a trade-of between simplicity and propagation delay in carry lookahead, which is significant for wide-word hardware implementations.

The estimation of a quotient in modular reduction is simpler for a binary field: it can't be off-by-one as occurs in ordinary multi-digit Euclidean division, which makes constant-time implementations easy, removing a possible side-channel.

Squaring in a binary field can be reduced to bit rotation by using a normal basis representation for the field. This in turn allows more efficient scalar multiplication on Elliptic Curve groups defined on some Koblitz curves over binary fields.

Answer 2

Short answer: Recall that in EC-based protocols, the security of the protocol depends on the choice of the field characteristic and order of the elliptic curve group, as well as the discrete log assumption.

Therefore, since STARKs don't use ECC and use hashing and bit-shifting instead, it (somewhat) doesn't matter which field characteristic is chosen, so just choose the one that is most performant.

Binary Field arithmetic is significantly more performant than other fields due to the optimizations that can be done. The mathematical operations for hashing and bit-shifting are all done in a binary field.

With regards to the optimizations involved, it's complicated. But you can take a look at this to get you started: http://www.cs.utsa.edu/~wagner/laws/FFM.html

Note that addition is almost never the issue, it's usually multiplication and field inversions. In a prime-order field, multiplication is simply bigint multiplication, but there are algorithms that allow to compute multiplicative inverses faster than O(q), for q = p^n the field order.

In binary fields this is all much much faster than in general prime-characteristic extension fields.