go-snark/groth16/groth16.go
groth16/groth16.goRaw
1// implementation of https://eprint.iacr.org/2016/260.pdf
2
3package groth16
4
5import (
6 "fmt"
7 "math/big"
8
9 "github.com/arnaucube/go-snark/bn128"
10 "github.com/arnaucube/go-snark/circuitcompiler"
11 "github.com/arnaucube/go-snark/fields"
12 "github.com/arnaucube/go-snark/r1csqap"
13)
14
15// Setup is the data structure holding the Trusted Setup data. The Setup.Toxic sub struct must be destroyed after the GenerateTrustedSetup function is completed
16type Setup struct {
17 Toxic struct {
18 T *big.Int // trusted setup secret
19 Kalpha *big.Int
20 Kbeta *big.Int
21 Kgamma *big.Int
22 Kdelta *big.Int
23 }
24
25 // public
26 Pk struct { // Proving Key
27 BACDelta [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m
28 Z []*big.Int
29 G1 struct {
30 Alpha [3]*big.Int
31 Beta [3]*big.Int
32 Delta [3]*big.Int
33 At [][3]*big.Int // {a(τ)} from 0 to m
34 BACGamma [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m
35 }
36 G2 struct {
37 Beta [3][2]*big.Int
38 Gamma [3][2]*big.Int
39 Delta [3][2]*big.Int
40 BACGamma [][3][2]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m
41 }
42 PowersTauDelta [][3]*big.Int // powers of τ encrypted in G1 curve, divided by δ
43 }
44 Vk struct {
45 IC [][3]*big.Int
46 G1 struct {
47 Alpha [3]*big.Int
48 }
49 G2 struct {
50 Beta [3][2]*big.Int
51 Gamma [3][2]*big.Int
52 Delta [3][2]*big.Int
53 }
54 }
55}
56
57// Proof contains the parameters to proof the zkSNARK
58type Proof struct {
59 PiA [3]*big.Int
60 PiB [3][2]*big.Int
61 PiC [3]*big.Int
62}
63
64type utils struct {
65 Bn bn128.Bn128
66 FqR fields.Fq
67 PF r1csqap.PolynomialField
68}
69
70// Utils is the data structure holding the BN128, FqR Finite Field over R, PolynomialField, that will be used inside the snarks operations
71var Utils = prepareUtils()
72
73func prepareUtils() utils {
74 bn, err := bn128.NewBn128()
75 if err != nil {
76 panic(err)
77 }
78 // new Finite Field
79 fqR := fields.NewFq(bn.R)
80 // new Polynomial Field
81 pf := r1csqap.NewPolynomialField(fqR)
82
83 return utils{
84 Bn: bn,
85 FqR: fqR,
86 PF: pf,
87 }
88}
89
90// GenerateTrustedSetup generates the Trusted Setup from a compiled Circuit. The Setup.Toxic sub data structure must be destroyed
91func GenerateTrustedSetup(witnessLength int, circuit circuitcompiler.Circuit, alphas, betas, gammas [][]*big.Int) (Setup, error) {
92 var setup Setup
93 var err error
94
95 // generate random t value
96 setup.Toxic.T, err = Utils.FqR.Rand()
97 if err != nil {
98 return Setup{}, err
99 }
100
101 setup.Toxic.Kalpha, err = Utils.FqR.Rand()
102 if err != nil {
103 return Setup{}, err
104 }
105 setup.Toxic.Kbeta, err = Utils.FqR.Rand()
106 if err != nil {
107 return Setup{}, err
108 }
109 setup.Toxic.Kgamma, err = Utils.FqR.Rand()
110 if err != nil {
111 return Setup{}, err
112 }
113 setup.Toxic.Kdelta, err = Utils.FqR.Rand()
114 if err != nil {
115 return Setup{}, err
116 }
117
118 // z pol
119 zpol := []*big.Int{big.NewInt(int64(1))}
120 for i := 1; i < len(alphas)-1; i++ {
121 zpol = Utils.PF.Mul(
122 zpol,
123 []*big.Int{
124 Utils.FqR.Neg(
125 big.NewInt(int64(i))),
126 big.NewInt(int64(1)),
127 })
128 }
129 setup.Pk.Z = zpol
130 zt := Utils.PF.Eval(zpol, setup.Toxic.T)
131 invDelta := Utils.FqR.Inverse(setup.Toxic.Kdelta)
132 ztinvDelta := Utils.FqR.Mul(invDelta, zt)
133
134 // encrypt t values with curve generators
135 // powers of tau divided by delta
136 var ptd [][3]*big.Int
137 ini := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, ztinvDelta)
138 ptd = append(ptd, ini)
139 tEncr := setup.Toxic.T
140 for i := 1; i < len(zpol); i++ {
141 ptd = append(ptd, Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, Utils.FqR.Mul(tEncr, ztinvDelta)))
142 tEncr = Utils.FqR.Mul(tEncr, setup.Toxic.T)
143 }
144 // powers of τ encrypted in G1 curve, divided by δ
145 // (G1 * τ) / δ
146 setup.Pk.PowersTauDelta = ptd
147
148 setup.Pk.G1.Alpha = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kalpha)
149 setup.Pk.G1.Beta = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kbeta)
150 setup.Pk.G1.Delta = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kdelta)
151 setup.Pk.G2.Beta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kbeta)
152 setup.Pk.G2.Delta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kdelta)
153
154 setup.Vk.G1.Alpha = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kalpha)
155 setup.Vk.G2.Beta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kbeta)
156 setup.Vk.G2.Gamma = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kgamma)
157 setup.Vk.G2.Delta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kdelta)
158
159 for i := 0; i < len(circuit.Signals); i++ {
160 // Pk.G1.At: {a(τ)} from 0 to m
161 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
162 a := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, at)
163 setup.Pk.G1.At = append(setup.Pk.G1.At, a)
164
165 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
166 g1bt := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, bt)
167 g2bt := Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, bt)
168 // G1.BACGamma: {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m in G1
169 setup.Pk.G1.BACGamma = append(setup.Pk.G1.BACGamma, g1bt)
170 // G2.BACGamma: {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m in G2
171 setup.Pk.G2.BACGamma = append(setup.Pk.G2.BACGamma, g2bt)
172 }
173
174 zero3 := [3]*big.Int{Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero()}
175 for i := 0; i < circuit.NPublic+1; i++ {
176 setup.Pk.BACDelta = append(setup.Pk.BACDelta, zero3)
177 }
178 for i := circuit.NPublic + 1; i < circuit.NVars; i++ {
179 // TODO calculate all at, bt, ct outside, to avoid repeating calculations
180 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
181 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
182 ct := Utils.PF.Eval(gammas[i], setup.Toxic.T)
183 c := Utils.FqR.Mul(
184 invDelta,
185 Utils.FqR.Add(
186 Utils.FqR.Add(
187 Utils.FqR.Mul(at, setup.Toxic.Kbeta),
188 Utils.FqR.Mul(bt, setup.Toxic.Kalpha),
189 ),
190 ct,
191 ),
192 )
193 g1c := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, c)
194
195 // Pk.BACDelta: {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m
196 setup.Pk.BACDelta = append(setup.Pk.BACDelta, g1c)
197 }
198
199 for i := 0; i <= circuit.NPublic; i++ {
200 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
201 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
202 ct := Utils.PF.Eval(gammas[i], setup.Toxic.T)
203 ic := Utils.FqR.Mul(
204 Utils.FqR.Inverse(setup.Toxic.Kgamma),
205 Utils.FqR.Add(
206 Utils.FqR.Add(
207 Utils.FqR.Mul(at, setup.Toxic.Kbeta),
208 Utils.FqR.Mul(bt, setup.Toxic.Kalpha),
209 ),
210 ct,
211 ),
212 )
213 g1ic := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, ic)
214 // used in verifier
215 setup.Vk.IC = append(setup.Vk.IC, g1ic)
216 }
217
218 return setup, nil
219}
220
221// GenerateProofs generates all the parameters to proof the zkSNARK from the Circuit, Setup and the Witness
222func GenerateProofs(circuit circuitcompiler.Circuit, setup Setup, w []*big.Int, px []*big.Int) (Proof, error) {
223 var proof Proof
224 proof.PiA = [3]*big.Int{Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero()}
225 proof.PiB = Utils.Bn.Fq6.Zero()
226 proof.PiC = [3]*big.Int{Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero()}
227
228 r, err := Utils.FqR.Rand()
229 if err != nil {
230 return Proof{}, err
231 }
232 s, err := Utils.FqR.Rand()
233 if err != nil {
234 return Proof{}, err
235 }
236
237 // piBG1 will hold all the same than proof.PiB but in G1 curve
238 piBG1 := [3]*big.Int{Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero()}
239
240 for i := 0; i < circuit.NVars; i++ {
241 proof.PiA = Utils.Bn.G1.Add(proof.PiA, Utils.Bn.G1.MulScalar(setup.Pk.G1.At[i], w[i]))
242 piBG1 = Utils.Bn.G1.Add(piBG1, Utils.Bn.G1.MulScalar(setup.Pk.G1.BACGamma[i], w[i]))
243 proof.PiB = Utils.Bn.G2.Add(proof.PiB, Utils.Bn.G2.MulScalar(setup.Pk.G2.BACGamma[i], w[i]))
244 }
245 for i := circuit.NPublic + 1; i < circuit.NVars; i++ {
246 proof.PiC = Utils.Bn.G1.Add(proof.PiC, Utils.Bn.G1.MulScalar(setup.Pk.BACDelta[i], w[i]))
247 }
248
249 // piA = (Σ from 0 to m (pk.A * w[i])) + pk.Alpha1 + r * δ
250 proof.PiA = Utils.Bn.G1.Add(proof.PiA, setup.Pk.G1.Alpha)
251 deltaR := Utils.Bn.G1.MulScalar(setup.Pk.G1.Delta, r)
252 proof.PiA = Utils.Bn.G1.Add(proof.PiA, deltaR)
253
254 // piBG1 = (Σ from 0 to m (pk.B1 * w[i])) + pk.g1.Beta + s * δ
255 // piB = piB2 = (Σ from 0 to m (pk.B2 * w[i])) + pk.g2.Beta + s * δ
256 piBG1 = Utils.Bn.G1.Add(piBG1, setup.Pk.G1.Beta)
257 proof.PiB = Utils.Bn.G2.Add(proof.PiB, setup.Pk.G2.Beta)
258 deltaSG1 := Utils.Bn.G1.MulScalar(setup.Pk.G1.Delta, s)
259 piBG1 = Utils.Bn.G1.Add(piBG1, deltaSG1)
260 deltaSG2 := Utils.Bn.G2.MulScalar(setup.Pk.G2.Delta, s)
261 proof.PiB = Utils.Bn.G2.Add(proof.PiB, deltaSG2)
262
263 hx := Utils.PF.DivisorPolynomial(px, setup.Pk.Z) // maybe move this calculation to a previous step
264
265 // piC = (Σ from l+1 to m (w[i] * (pk.g1.Beta + pk.g1.Alpha + pk.C)) + h(tau)) / δ) + piA*s + r*piB - r*s*δ
266 for i := 0; i < len(hx); i++ {
267 proof.PiC = Utils.Bn.G1.Add(proof.PiC, Utils.Bn.G1.MulScalar(setup.Pk.PowersTauDelta[i], hx[i]))
268 }
269 proof.PiC = Utils.Bn.G1.Add(proof.PiC, Utils.Bn.G1.MulScalar(proof.PiA, s))
270 proof.PiC = Utils.Bn.G1.Add(proof.PiC, Utils.Bn.G1.MulScalar(piBG1, r))
271 negRS := Utils.FqR.Neg(Utils.FqR.Mul(r, s))
272 proof.PiC = Utils.Bn.G1.Add(proof.PiC, Utils.Bn.G1.MulScalar(setup.Pk.G1.Delta, negRS))
273
274 return proof, nil
275}
276
277// VerifyProof verifies over the BN128 the Pairings of the Proof
278func VerifyProof(setup Setup, proof Proof, publicSignals []*big.Int, debug bool) bool {
279
280 icPubl := setup.Vk.IC[0]
281 for i := 0; i < len(publicSignals); i++ {
282 icPubl = Utils.Bn.G1.Add(icPubl, Utils.Bn.G1.MulScalar(setup.Vk.IC[i+1], publicSignals[i]))
283 }
284
285 if !Utils.Bn.Fq12.Equal(
286 Utils.Bn.Pairing(proof.PiA, proof.PiB),
287 Utils.Bn.Fq12.Mul(
288 Utils.Bn.Pairing(setup.Vk.G1.Alpha, setup.Vk.G2.Beta),
289 Utils.Bn.Fq12.Mul(
290 Utils.Bn.Pairing(icPubl, setup.Vk.G2.Gamma),
291 Utils.Bn.Pairing(proof.PiC, setup.Vk.G2.Delta)))) {
292 if debug {
293 fmt.Println("❌ groth16 verification not passed")
294 }
295 return false
296 }
297 if debug {
298 fmt.Println("✓ groth16 verification passed")
299 }
300
301 return true
302}