A genus-95 curve shrinks what the prover sends

The sumcheck protocol sits inside most modern proof systems, and in theory it was generalised long ago from polynomials to tensors of any multiplication code, meaning a code whose pointwise products of codewords lie in a related product code. In practice every system still uses polynomials, and a new paper from authors at Succinct, New York University and Espresso argues that the choice carries a measurable cost.

The cost appears in proof systems over binary fields that target Boolean circuits. Under Reed-Solomon the product of two binary messages is no longer binary, and so the prover's work in the first and most expensive round of sumcheck, the univariate skip, grows by a logarithmic factor.

The authors construct a multiplication code from algebraic geometry that is binary-preserving: the product of two encoded binary messages is a binary message again. Their explicit code over the field of 2 to the 128 carries 64-bit messages to binary product messages of length 222, and its product code has relative distance greater than 1 minus 2 to the minus 119. The code comes from a genus-95 curve over the binary field with 64 rational points, built as a cover of a genus-4 curve. The part of the product message the prover actually sends is more than three times smaller than with Reed-Solomon as used in practice.

They implemented the resulting protocol, which they call the AG skip, inside the Flock proof system. At 2 to the 32 constraints it speeds up the skip round by 2.36 times and the whole zerocheck, previously the prover's most expensive component, by 1.65 times. The work is a preprint, received and approved on 15 October.