A prover that pays only for the bits it uses

A SNARK prover does its arithmetic over a large field for the sake of soundness, even when the values in the witness are only a few bits wide, and that inflates both proving time and memory. Recent work has made individual parts of a SNARK bitwidth-aware, so that narrower witnesses mean faster and lighter proving, but those techniques cover only part of the prover and depend on the structure of particular fields, usually binary ones.

A paper received on 26 October proposes Mikros, a framework for building such SNARKs end to end. Its technique is algebraic vector packing: vectors over a base field are packed into vectors a factor of kappa shorter over an extension field of degree kappa, which turns long relations over the base field into short ones over the extension and makes existing linear-time extension-field protocols bitwidth-aware.

The construction unifies pieces that previously needed separate constructions — bitwidth-aware inner-product proofs, Hadamard-product proofs and polynomial commitment schemes — and adds the first bitwidth-aware grand-product proof, and with it the first bitwidth-aware permutation argument. Composed together they give bitwidth-aware SNARKs for circuit satisfiability over extensions of arbitrary small fields. For a single instance the prover's cost is proportional to the combined bitwidth of the witness entries and the wiring-position encodings; across instances of the same circuit the position encoding is amortised and the per-instance cost follows the witness bitwidth.

The comparison is with Flock, the bitwidth-aware SNARK over binary-extension fields inside which a recent algebraic-geometry result was also measured. Although Mikros does not rely on binary-field structure, its prover is reported 2.19, 2.55 and 1.85 times faster than Flock on batches of 256 SHA-256 compressions, Keccak permutations and BLAKE3 compressions respectively. The work is a preprint.