Flock: Fast Proving for Batch Boolean Computations

Benedikt Bünz (NYU, Espresso Systems), Ron D. Rothblum (Succinct) and William Wang (NYU), arXiv 2607.27491v1, 29 July 2026, 45 pages. A hash-based post-quantum SNARK built to prove batches of the same Boolean circuit as fast as possible, and the source that makes concrete-efficiency this spoke's organizing question. Read from the PDF with pypdf.

The question is stated outright in the introduction: "What is the smallest concrete overhead that proving can have over native execution?" General-purpose zkVM provers run four to six orders of magnitude slower than native. Flock reports ≈250×.

What it proves

Fix a Boolean circuit F and a simple glue circuit G. Flock proves F(xᵢ, yᵢ) = 0 for all i in a batch of K, plus G over all the inputs and outputs together. The repeated circuit carries the bulk of the work; the glue ties the pieces into a hash chain or a set of Merkle paths.

Restricting to batches is the design decision that pays. Proving many copies of one circuit "obviates the need for expensive permutation or memory checking arguments" that general-purpose systems must carry — so the restriction is not a limitation grudgingly accepted but the source of the speed.

The numbers

Single core of an Apple M4 Max, witness generation included, native throughput measured without the ARM SHA-256/SHA3 acceleration instructions so the comparison is like for like:

Against the field: roughly 9× faster than Binius64 on SHA-256, 7× on Keccak multithreaded, 14× on BLAKE3 against both Binius64 and Plonky3, 1.8× against Hashcaster on Keccak, 40× against Plonky3 on Keccak, and over 500× against NeutronNova. Proofs are under 450 KB for computations with 2³⁰ AND gates (386 KiB for the default "fast" variant at 2¹⁴ Keccak permutations, 200 KiB for a "slim" variant that trades throughput for size) and verify in milliseconds.

Every one of those figures is the authors' own, on one machine, at the batch size where each system peaks (reported per system, which is the fair way to do it). See concrete-efficiency for why the cross-system comparison is the softest part.

How it gets there

The starting point is a Spartan-like PIOP for batch-R1CS over F₂ (binary-fields), with binary extension fields for soundness. R1CS is chosen over Plonkish arithmetization because its witness is smaller — it does not commit to the outputs of addition gates.

The batch reformulation makes the zerocheck the remaining bottleneck (the lincheck across the A, B, C matrices amortizes over the batch dimension and costs under 10% of prover time), so nearly all the optimization lands there. Known techniques are combined — the univariate skip, partially deterministic sumcheck challenges, deferred modular reduction, evaluation at infinity — and then pushed:

• A new set of challenge points that processes log|F| of the individual zerocheck bit claims with roughly two bit-shifts and XORs per input, and does it without tower fields, which the authors call less efficient than direct extensions of F₂. That is a direct disagreement with the tower construction in binius, and this spoke's first (synthesis).
• A degree-64 univariate skip, as in Binius64.

F₂¹²⁸ throughout, Ligerito as the polynomial commitment scheme extended to the list-decoding regime, interleaved Reed–Solomon at rate ½, Johnson-bound proximity gaps plus a little grinding.

What it claims about the world

Post-quantum hash-based signatures are dominated by hashing, so a fast batch hash prover is the thing that makes them affordable. One signature in the stateful multi-signature scheme proposed for Ethereum's quantum transition costs about 160 hash invocations. At Flock's ten-core BLAKE3 throughput that is hashing for roughly 4,000 transactions per second — against Buterin's estimate that 200k hashes per second would suffice for a post-quantum transition. For Bitcoin, which the paper expects to insist on SHA-256, it claims the hashing for 5,000 signatures — a full block — in under 2.5 seconds on consumer hardware.

The paper marks the boundary of that claim itself: these figures count only the hashing inside signature verification, not transaction execution, state access or any other logic.

Security and what it admits

100 bits of soundness by default, with the IOP's round-by-round soundness error at most 2⁻¹⁰⁰ unconditionally, no unproven conjectures; the remaining assumption is the security of SHA-256, used for both Merkle commitments and Fiat–Shamir. A 120-bit variant is benchmarked too.

The limitations section is unusually plain for a performance paper, and worth keeping whole:

• a research prototype, not recommended for production
• batched Boolean R1CS only; the glue circuit is supported for hash chains and Merkle trees, not in general, so signature aggregation "would require additional work"
• tuned for Apple ARM specifically rather than for generality
• succinctness only, no zero-knowledge yet — expected to be addable cheaply

The implementation was co-designed by coding agents

The abstract says the proof-of-concept is "co-designed by coding agents"; the limitations section says the implementation "was heavily AI-assisted and was targeted at demonstrating optimal performance on a specific system." The paper does not say which agents, how much, or which parts, and reports no comparison against a hand-written baseline — so as evidence about agent capability it is a claim, not a measurement. It is still notable that a state-of-the-art prover result now arrives with that sentence in the abstract. The agent-tooling reading belongs to ../agentic-tooling-wiki; the proof system is here.

Related

succinct-argument · concrete-efficiency · binary-fields · binius · irreducible · vitalik-buterin · synthesis