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