zkExp: Zero-Knowledge Succinct Exponentiation Proofs

Abstract

We present zkExp (Zero-Knowledge Succinct Exponentiation Proofs), the first zero-knowledge proof system achieving asymptotically efficient bounds for batched exponentiation: <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mo stretchy="false">~</mml:mo> </mml:mover> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mi>ℓ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> prover time, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> verification time, and constant-size (160–256 B) proofs. For statements <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>y</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>g</mml:mi> <mml:mrow> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> ) with private exponents <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> </mml:math> , zkExp introduces four innovations to overcome long-standing scalability barriers: (1) trace-based square-and-multiply encoding, (2) lazy sumcheck for exponentiation constraints, (3) hybrid FFT decomposition reducing memory from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , and (4) sliding-window batching enabling single-proof aggregation via KZG commitments. The protocol is computationally sound under the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> -Generalized Diffie–Hellman Exponent (GDHE) assumption and achieves computational zero-knowledge in the random oracle model. Proofs remain 160–256 B regardless of parameter sizes, with constant verification (3.5 ms). For 4096-bit exponents, prover overhead is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>16.3</mml:mn> <mml:mi>×</mml:mi> </mml:mrow> </mml:math> (dropping to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1.35</mml:mn> <mml:mi>×</mml:mi> </mml:mrow> </mml:math> in 1000-batch settings), while Ethereum verification costs <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>~</mml:mi> <mml:mn>267</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> gas for 1000 exponentiations, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>10</mml:mn> <mml:mi>×</mml:mi> </mml:mrow> </mml:math> cheaper than ECDSA, with memory consumption below 1.1 MB. zkExp is the first protocol to match theoretical lower bounds for exponentiation proofs while enabling practical deployment in zero-knowledge rollups, anonymous credentials, and on-chain threshold cryptography.