Formally Verified Arguments of Knowledge in Lean

4 Commitment Schemes

4.1 KZG

ArkLib formalizes the KZG polynomial commitment scheme  [ 22 ] and its evaluation binding proof from the extended version  [ 23 ] . Fix a prime \(p\), groups \(G_1,G_2,G_T\) of order \(p\) with generators \(g_1\in G_1\) and \(g_2\in G_2\), and a \(\mathbb {Z}_p\)-bilinear pairing \(e:G_1\times G_2\to G_T\). Fix a maximal degree \(n\). The committed data is a coefficient vector \((a_0,\ldots ,a_n)\in \mathbb {Z}_p^{n+1}\), that is, a polynomial \(f\) of degree at most \(n\); a query is a point \(z\in \mathbb {Z}_p\) and its response is \(f(z)\).

Definition 235 KZG commitment scheme
✓
  • Key generation. Sample a uniform nonzero \(\tau \in \mathbb {Z}_p\). Both keys are the reference string \(\bigl((g_1^{\tau ^i})_{i\leq n},(g_2,g_2^{\tau })\bigr)\).

  • Commitment. \(C=\prod _{i\leq n}(g_1^{\tau ^i})^{a_i}=g_1^{f(\tau )}\).

  • Opening. To open at \(z\) with value \(v\), the prover sends one element \(\pi \in G_1\), the commitment to the quotient \((f(X)-f(z))/(X-z)\).

  • Verification. Accept when \(e(C\cdot g_1^{-v},g_2)=e(\pi ,g_2^{\tau }\cdot g_2^{-z})\).

Theorem 236 KZG correctness
✓
#

If \(|G_1|=p\), the KZG scheme is perfectly correct, with the random oracle started from an empty cache.

Definition 237 \(t\)-SDH
✓

A \(t\)-SDH adversary receives the reference string for \(t=n\) and a uniform nonzero \(\tau \), and outputs \((c,h)\in \mathbb {Z}_p\times G_1\). It wins when \(\tau +c\neq 0\) and \(h=g_1^{1/(\tau +c)}\). For a set \(\mathcal{A}\) of adversaries and \(\varepsilon \geq 0\), the \(t\)-SDH assumption over \(\mathcal{A}\) with error \(\varepsilon \) states that every adversary in \(\mathcal{A}\) wins with probability at most \(\varepsilon \).

Lemma 238 The assumption needs a restricted class
✓
#

If \(g_2\neq 1\) and \(\varepsilon {\lt}1\), the \(t\)-SDH assumption fails over the class of all adversaries: a classical inverse of \(a\mapsto g_2^{a}\) recovers \(\tau \) from the reference string. A meaningful instance restricts \(\mathcal{A}\), for example to generic, algebraic or resource-bounded adversaries.

Assume \(g_1\neq 1\) and \(e(g_1,g_2)\neq 1_{G_T}\). A binding adversary outputs a commitment, a point \(z\), two values \(v_1,v_2\) and two prover states, and then runs the opening prover from each state. It wins when \(v_1\neq v_2\) and both openings are accepted. Uniform queries are forwarded to private sampling, from an empty cache. For every binding adversary \(\mathcal{B}\), the probability that \(\mathcal{B}\) wins is at most the probability that the explicit reduction \(R(\mathcal{B})\) wins the \(t\)-SDH game. Consequently, if the \(t\)-SDH assumption holds over \(\mathcal{A}\) with error \(\varepsilon \) and \(R(\mathcal{B})\in \mathcal{A}\), then \(\mathcal{B}\) wins with probability at most \(\varepsilon \).

An ARSDH adversary receives the same reference string and outputs a set \(S\subseteq \mathbb {Z}_p\) and \(h_1,h_2\in G_1\). With \(Z_S(X)=\prod _{s\in S}(X-s)\), it wins when \(|S|=n+1\), \(Z_S(\tau )\neq 0\), \(h_1\neq 1\) and \(h_2=h_1^{1/Z_S(\tau )}\). A function-binding adversary outputs a commitment and \(L\) query-value pairs, and wins when every opening is accepted but no polynomial of degree at most \(n\) takes all \(L\) values. Assume \(n\geq 1\), \(p\geq n+2\), \(g_1\neq 1\) and \(e(g_1,g_2)\neq 1_{G_T}\). Then every function-binding adversary wins with probability at most the ARSDH success probability of an explicit reduction, and at most \(\varepsilon \) when ARSDH holds with error \(\varepsilon \) over a class containing that reduction.

4.2 Nonrecursive Hachi

ArkLib formalizes a nonrecursive variant of the Hachi lattice-based multilinear polynomial commitment  [ 25 ] , which builds on Greyhound  [ 26 ] . The recursive opening of the paper, which carries each iteration’s evaluation claim to the next ring instead of closing it, is not formalized. Section 5.4 covers the extension-field packing that the scheme uses.

Throughout, \(R_q=\mathbb {Z}_q[X]/(X^{2^\alpha }+1)\). The committed data is a multilinear polynomial over \(R_q\) in \(r+m\) variables, and a query is an evaluation point. Honest range parameters consist of a balanced digit base \(b\), a ball radius \(\gamma \) and a zero-check digit base \(b_0\), subject to

\[ 1{\lt}b\leq q/2,\qquad 1{\lt}b_0\leq q/2,\qquad \lfloor b/2\rfloor \leq \gamma ,\qquad \lfloor b_0/2\rfloor \leq \gamma \leq b_0-1. \]

The remaining parameters are the challenge weight \(\omega \), the digit count \(\tau \) and bound \(z_{\max }\) for the folded witness, a sumcheck dimension \(M\), and a ring homomorphism \(\mathbb {Z}_q\to \mathbb {F}\) into the field over which the sumcheck runs. Write \(\delta _b=\lceil \log _b q\rceil \), and write \(\mu _0\) and \(n_0\) for the column and row counts of the linear relation that the ring-switching step produces.

Key generation samples the public matrices of the inner-outer Ajtai commitment. The committer decomposes the coefficients in balanced base \(b\) and commits with the inner and outer matrices. The opening proves an evaluation claim through the chain: input adapter, bridge, quadratic evaluation, ring switching to a linear relation, lift, batching, nested zero-check and sumcheck. A terminal step closes the chain: the prover sends the lifted witness in the clear and the verifier checks the reduced evaluation claim on it. The opening is therefore not succinct. The scheme is generic in the commitment used by the lift step. The concrete instance commits to the lifted witness with an Ajtai matrix of \(\mu _0+n_0\lceil \log _{b_0}q\rceil \) columns, whose quotient block is decomposed in base \(b_0\).

Assume

  • \(z_{\max }\leq (b-1-\lfloor b/2\rfloor )\sum _{e{\lt}\tau }b^{e}\), the positive capacity of \(\tau \) balanced base-\(b\) digits;

  • \(2^{r}\, \omega \, \lfloor b/2\rfloor \leq z_{\max }\) and \(\tau {\gt}0\);

  • \(\delta _b{\gt}0\), \(2^\alpha {\gt}0\) and \(b_0{\gt}0\);

  • \((\mu _0+n_0\lceil \log _{b_0}q\rceil )\cdot 2^{\alpha }\leq 2^{M+1}\);

  • \(b_0-1\leq \gamma \).

Then, for every lift commitment, every initial oracle state and every implementation of the uniform oracle, the scheme is perfectly correct. The same holds for the concrete instance. The opening reduction alone is perfectly complete under these assumptions together with \(\kappa \geq 1\) and a bound \(\beta ^2\geq 2^m\delta _b\, 2^\alpha \lfloor b/2\rfloor ^2\) on its auxiliary parameters \(\kappa \) and \(\beta ^2\).

With the honest range constraint \(\gamma \leq b_0-1\), the last assumption forces \(\gamma =b_0-1\).

Soundness.

The soundness side is formalized for the reduction chain, not for the scheme. Each subprotocol carries a coordinate-wise special soundness certificate whose extraction may instead output an escape event: a Module-SIS solution for the public matrices, or a collision in the lift commitment.

Assume \(q\equiv 5\pmod8\), \((2\omega )^2{\lt}q\), \(\tau {\gt}0\), \(2^\alpha {\gt}0\), \(b-1\leq \gamma \), \(1{\lt}b\leq q/2\), \(\lfloor b/2\rfloor \leq \gamma \), \((\mu _0+n_0\lceil \log _b q\rceil )\cdot 2^{\alpha }\leq 2^{m_0}\) and \(n_0\leq 2^{m_1}\). Then the verifier of one iteration, from the bridge through the final sumcheck evaluation, is coordinate-wise special sound with escape, from the polynomial-evaluation relation to the reduced evaluation claim on the committed table. Appending the terminal check gives the complete evaluation argument with the composed certificate.

Binding of the scheme and knowledge soundness of its opening, as commitment-scheme properties, are not formalized. The scheme’s terminal verifier and the soundness-side terminal check use the same decision procedure.