murrax.dev Recently Edited: Learning with ObsidianObject Capabilities Security ModelModal's GPU Glossary

Groth16

Zero-Knowledge Proof system for Quadratic Arithmetic Programs (QAPs) slides

Notation

We denote [A]1=La,[B]2=Ra,[C]1=Oa[A]_1=La, [B]_2=Ra, [C]_1=Oa [A]1∙[B]2[A]_1 \bullet [B]_2 represents the pairing of [A]1[A]_1 and [B]2[B]_2

Motivation

Simply providing the verifier with some [A]1,[B]2,[C]1[A]_1, [B]_2, [C]_1 that satisfy [A]1∙[B]2=[C]1∙[G]2[A]_1\bullet [B]_2=[C]_1 \bullet [G]_2 does not mean the prover satisfied the QAP, as we do not know whether the equation actually represents the QAP.

Preventing Forgery

We add another pairing to the verification equation, s.t. it is now [A]1∙[B]2=[α]1∙[β]2+[C]1∙[G]2[A]_1\bullet [B]_2=[\alpha]_1\bullet [\beta]_2 + [C]_1 \bullet [G]_2 where α,β\alpha,\beta are random secrets generated by the trusted setup.

Semi-public Witness

For our witness aa, we want to be able to publish the first ll elements publicly. This way, we directly show we have the first part of a witness, and then issue a ZK proof for the latter part. This is because the verifier may wish to provide some number of the input variables, and have the prover discover the rest, while ensuring the prover used the input variables provided.

However, we need to be careful and ensure that our scheme does not have a weakness which allows a prover to use the public part of the witness to forge a proof for the latter part.

This is avoided by the trusted setup dividing Ψ1...Ψl\Psi_1...\Psi_l by γ\gamma and Ψl+1...Ψm\Psi_{l+1}...\Psi_m by δ\delta where γ,δ\gamma,\delta are some random scalars generated and kept secret by the trusted setup. Since only the trusted setup knows the discrete log of γ,δ\gamma,\delta, no one else can calculate this division.

The verifier then simply pairs [X]1∙[γ]2[X]_1\bullet[\gamma]_2 and [C]1∙[δ]2[C]_1\bullet[\delta]_2 to cancel out this division.

Enforcing Zero Knowledge

If our input-space for our QAP is small, an attacker can simply keep guessing witnesses until they find one that results in the same proof submitted by the prover. They have then determined the solution the prover has, violating the Zero Knowledge requirement.

To prevent this, the prover salts their proof. They do this by generating two random field elements r,sr,s, and adding them to AA and BB to make them unguessable.

Trusted Setup

The trusted setup calculates

α,β,τ,γ,δ←random scalars[τn−1G1, τn−2G1, ..., τG1, G1]←SRS for G1[τn−1G2, τn−2G2, ..., τG2, G2]←SRS for G2[τn−2t(τ)δ, τn−3t(τ)δ, ..., τt(τ)δ, t(τ)δ]←SRS for h(τ)t(τ)Used with public portion of witness[Ψ1]1=αv1(τ)+βu1(τ)+w1(τ)γG1[Ψ2]1=αv2(τ)+βu2(τ)+w2(τ)γG1⋮[Ψl]1=αvl(τ)+βul(τ)+wl(τ)γG1Used with private portion of witness[Ψl+1]1=αvl+1(τ)+βul+1(1τ)+wl+1(τ)δG1[Ψl+2]1=αvl+2(τ)+βul+2(τ)+wl+2(τ)δG1⋮[Ψm]1=αvm(τ)+βum(τ)+wm(τ)δG1\begin{align} \alpha,\beta,\tau,\gamma,\delta &\leftarrow& \text{random scalars}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ \\ [\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ &\text{Used with public portion of witness}\\ [\Psi_1]_1&=\frac{\alpha v_1(\tau)+\beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1&=\frac{\alpha v_2(\tau)+\beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ \vdots&&\\ [\Psi_l]_1&=\frac{\alpha v_l(\tau)+\beta u_l(\tau) + w_l(\tau)}{\gamma}G_1\\ \\ &&\text{Used with private portion of witness}\\ [\Psi_{l+1}]_1&=\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(1\tau) + w_{l+1}(\tau)}{\delta}G_1\\ [\Psi_{l+2}]_1&=\frac{\alpha v_{l+2}(\tau)+\beta u_{l+2}(\tau) + w_{l+2}(\tau)}{\delta}G_1\\ \vdots&&\\ [\Psi_m]_1&=\frac{\alpha v_m(\tau)+\beta u_m(\tau) + w_m(\tau)}{\delta}G_1\\ \end{align}

The trusted setup then publishes ([α]1, [β]1[β]2, [γ]2, [δ]1[δ]2, SRSG1, SRSG2, [Ψ1]1, [Ψ2]1, ...,[Ψm]1)([\alpha]_1,\ [\beta]_1[\beta]_2,\ [\gamma]_2,\ [\delta]_1[\delta]_2,\ SRS_{G_1},\ SRS_{G_2},\ [\Psi_1]_1,\ [\Psi_2]_1,\ ..., [\Psi_m]_1),

Prover

The prover has a witness aa and generates random scalars r,sr,s.

[A]1=[α]1+∑i=1maiui(τ)+r[δ]1[B]1=[β]1+∑i=1maivi(τ)+s[δ]1[B]2=[β]2+∑i=1maivi(τ)+s[δ]2[C]1=∑i=l+1mai[Ψi]1+h(τ)t(τ)+[A]1s+[B]1r−rs[δ]1\begin{align} [A]_1&=[\alpha]_1+\sum^m_{i=1} a_iu_i(\tau)+r[\delta]_1\\ [B]_1&=[\beta]_1+\sum^m_{i=1} a_iv_i(\tau)+s[\delta]_1\\ [B]_2&=[\beta]_2+\sum^m_{i=1} a_iv_i(\tau)+s[\delta]_2\\ [C]_1&=\sum^m_{i=l+1}{a_i[\Psi_i]_1}+h(\tau)t(\tau) + [A]_1s+[B]_1r-rs[\delta]_1 \end{align}

Publishes ([A]1,[B]2,[C]1,[a1,...,al])([A]_1, [B]_2, [C]_1, [a_1,...,a_l])

Verification

The verifier calculates

[X]1=∑i=1laiΨi[X]_1=\sum_{i=1}^l{a_i\Psi_i}

and checks

[A]1∙[B]2=?[α]1∙[β]2+[X]1∙[γ]2+[C]1∙[δ]2[A]_1\bullet[B]_2 \stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2+[X]_1\bullet[\gamma]_2+[C]_1\bullet[\delta]_2

References