go-snark/groth16/groth16.go
groth16/groth16.goRaw
1// implementation of https://eprint.iacr.org/2016/260.pdf
2
3package groth16
4
5import (
6 "math/big"
7
8 "github.com/arnaucube/go-snark/bn128"
9 "github.com/arnaucube/go-snark/circuitcompiler"
10 "github.com/arnaucube/go-snark/fields"
11 "github.com/arnaucube/go-snark/r1csqap"
12)
13
14// Setup is the data structure holding the Trusted Setup data. The Setup.Toxic sub struct must be destroyed after the GenerateTrustedSetup function is completed
15type Setup struct {
16 Toxic struct {
17 T *big.Int // trusted setup secret
18 Kalpha *big.Int
19 Kbeta *big.Int
20 Kgamma *big.Int
21 Kdelta *big.Int
22 }
23
24 // public
25 Pk struct { // Proving Key
26 BACDelta [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to l
27 Z []*big.Int
28 G1 struct {
29 Alpha [3]*big.Int
30 Beta [3]*big.Int
31 Delta [3]*big.Int
32 At [][3]*big.Int // {a(τ)} from 0 to m
33 BACGamma [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m
34 }
35 G2 struct {
36 Beta [3][2]*big.Int
37 Gamma [3][2]*big.Int
38 Delta [3][2]*big.Int
39 BACGamma [][3][2]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m
40 }
41 PowersTauDelta [][3]*big.Int // powers of τ encrypted in G1 curve, divided by δ
42 }
43 Vk struct {
44 IC [][3]*big.Int
45 G1 struct {
46 Alpha [3]*big.Int
47 }
48 G2 struct {
49 Beta [3][2]*big.Int
50 Gamma [3][2]*big.Int
51 Delta [3][2]*big.Int
52 }
53 }
54}
55
56// ProofGroth contains the parameters to proof the zkSNARK
57type ProofGroth struct {
58 PiA [3]*big.Int
59 PiB [3][2]*big.Int
60 PiC [3]*big.Int
61}
62
63type utils struct {
64 Bn bn128.Bn128
65 FqR fields.Fq
66 PF r1csqap.PolynomialField
67}
68
69// Utils is the data structure holding the BN128, FqR Finite Field over R, PolynomialField, that will be used inside the snarks operations
70var Utils = prepareUtils()
71
72func prepareUtils() utils {
73 bn, err := bn128.NewBn128()
74 if err != nil {
75 panic(err)
76 }
77 // new Finite Field
78 fqR := fields.NewFq(bn.R)
79 // new Polynomial Field
80 pf := r1csqap.NewPolynomialField(fqR)
81
82 return utils{
83 Bn: bn,
84 FqR: fqR,
85 PF: pf,
86 }
87}
88
89// GenerateTrustedSetup generates the Trusted Setup from a compiled Circuit. The Setup.Toxic sub data structure must be destroyed
90func GenerateTrustedSetup(witnessLength int, circuit circuitcompiler.Circuit, alphas, betas, gammas [][]*big.Int) (Setup, error) {
91 var setup Setup
92 var err error
93
94 // generate random t value
95 setup.Toxic.T, err = Utils.FqR.Rand()
96 if err != nil {
97 return Setup{}, err
98 }
99
100 setup.Toxic.Kalpha, err = Utils.FqR.Rand()
101 if err != nil {
102 return Setup{}, err
103 }
104 setup.Toxic.Kbeta, err = Utils.FqR.Rand()
105 if err != nil {
106 return Setup{}, err
107 }
108 setup.Toxic.Kgamma, err = Utils.FqR.Rand()
109 if err != nil {
110 return Setup{}, err
111 }
112 setup.Toxic.Kdelta, err = Utils.FqR.Rand()
113 if err != nil {
114 return Setup{}, err
115 }
116
117 // z pol
118 zpol := []*big.Int{big.NewInt(int64(1))}
119 for i := 1; i < len(alphas)-1; i++ {
120 zpol = Utils.PF.Mul(
121 zpol,
122 []*big.Int{
123 Utils.FqR.Neg(
124 big.NewInt(int64(i))),
125 big.NewInt(int64(1)),
126 })
127 }
128 setup.Pk.Z = zpol
129 zt := Utils.PF.Eval(zpol, setup.Toxic.T)
130 invDelta := Utils.FqR.Inverse(setup.Toxic.Kdelta)
131 ztinvDelta := Utils.FqR.Mul(invDelta, zt)
132
133 // encrypt t values with curve generators
134 // powers of tau divided by delta
135 var ptd [][3]*big.Int
136 ini := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, ztinvDelta)
137 ptd = append(ptd, ini)
138 tEncr := setup.Toxic.T
139 for i := 1; i < len(zpol); i++ {
140 ptd = append(ptd, Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, Utils.FqR.Mul(tEncr, ztinvDelta)))
141 tEncr = Utils.FqR.Mul(tEncr, setup.Toxic.T)
142 }
143 // powers of τ encrypted in G1 curve, divided by δ
144 // (G1 * τ) / δ
145 setup.Pk.PowersTauDelta = ptd
146
147 setup.Pk.G1.Alpha = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kalpha)
148 setup.Pk.G1.Beta = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kbeta)
149 setup.Pk.G1.Delta = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kdelta)
150 setup.Pk.G2.Beta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kbeta)
151 setup.Pk.G2.Delta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kdelta)
152
153 setup.Vk.G1.Alpha = Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, setup.Toxic.Kalpha)
154 setup.Vk.G2.Beta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kbeta)
155 setup.Vk.G2.Gamma = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kgamma)
156 setup.Vk.G2.Delta = Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, setup.Toxic.Kdelta)
157
158 for i := 0; i < len(circuit.Signals); i++ {
159 // Pk.G1.At: {a(τ)} from 0 to m
160 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
161 a := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, at)
162 setup.Pk.G1.At = append(setup.Pk.G1.At, a)
163
164 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
165 g1bt := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, bt)
166 g2bt := Utils.Bn.G2.MulScalar(Utils.Bn.G2.G, bt)
167 // G1.BACGamma: {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m in G1
168 setup.Pk.G1.BACGamma = append(setup.Pk.G1.BACGamma, g1bt)
169 // G2.BACGamma: {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m in G2
170 setup.Pk.G2.BACGamma = append(setup.Pk.G2.BACGamma, g2bt)
171 }
172
173 zero3 := [3]*big.Int{Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero(), Utils.Bn.G1.F.Zero()}
174 for i := 0; i < circuit.NPublic+1; i++ {
175 setup.Pk.BACDelta = append(setup.Pk.BACDelta, zero3)
176 }
177 for i := circuit.NPublic + 1; i < circuit.NVars; i++ {
178 // TODO calculate all at, bt, ct outside, to avoid repeating calculations
179 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
180 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
181 ct := Utils.PF.Eval(gammas[i], setup.Toxic.T)
182 c := Utils.FqR.Mul(
183 invDelta,
184 Utils.FqR.Add(
185 Utils.FqR.Add(
186 Utils.FqR.Mul(at, setup.Toxic.Kbeta),
187 Utils.FqR.Mul(bt, setup.Toxic.Kalpha),
188 ),
189 ct,
190 ),
191 )
192 g1c := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, c)
193
194 // Pk.BACDelta: {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to l
195 setup.Pk.BACDelta = append(setup.Pk.BACDelta, g1c)
196 }
197
198 for i := 0; i <= circuit.NPublic; i++ {
199 at := Utils.PF.Eval(alphas[i], setup.Toxic.T)
200 bt := Utils.PF.Eval(betas[i], setup.Toxic.T)
201 ct := Utils.PF.Eval(gammas[i], setup.Toxic.T)
202 ic := Utils.FqR.Mul(
203 Utils.FqR.Inverse(setup.Toxic.Kgamma),
204 Utils.FqR.Add(
205 Utils.FqR.Add(
206 Utils.FqR.Mul(at, setup.Toxic.Kbeta),
207 Utils.FqR.Mul(bt, setup.Toxic.Kalpha),
208 ),
209 ct,
210 ),
211 )
212 g1ic := Utils.Bn.G1.MulScalar(Utils.Bn.G1.G, ic)
213 // used in verifier
214 setup.Vk.IC = append(setup.Vk.IC, g1ic)
215 }
216
217 return setup, nil
218}