Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting

The five-minute read

One action, walked through

1. Commit to vectors.
2. Recurse on the inner product by folding the vectors in half.
3. The verifier checks a logarithmic transcript against the discrete-log assumption.
4. How does the proof grow with the circuit?

The argument, unpacked

What has to be true

• Logarithmic is not constant size. Groth16 is still shorter.
• The discrete-log assumption is the one that fails against a quantum adversary.
• This is not PLONK.

What happened after the paper

Bulletproofs cite this compression. Later folding schemes are a further branch, not this paper.

What to check before you use the idea

• Is there a trusted setup?
• How does the proof grow with the circuit?
• Which assumption does soundness use?

Terms

Inner product

A sum of pairwise products. The argument proves it without sending the vectors.

Discrete log

The assumption that a group element does not reveal its exponent.

The problem the paper names

Pairing-based SNARKs were short and needed a setup. Discrete-log arguments were transparent and too large.

What the design proposes

• No structured reference string.
• The prover and verifier pay in group operations.
• The argument is what Bulletproofs later specialised for ranges.

How the mechanism is specified

• Commit to vectors.
• Recurse on the inner product by folding the vectors in half.
• The verifier checks a logarithmic transcript against the discrete-log assumption.

What this page does not treat as proven

• Logarithmic is not constant size. Groth16 is still shorter.
• The discrete-log assumption is the one that fails against a quantum adversary.
• This is not PLONK.

Why a venture studio still reads it

When someone says the proof has no setup, ask whether they mean this family or a hash-based STARK. The assumptions are different.