go-snark/snark.go
snark.goRaw
1package snark
2
3import (
4 "fmt"
5 "math/big"
6 "os"
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 Ka *big.Int // prover
19 Kb *big.Int // prover
20 Kc *big.Int // prover
21 Kbeta *big.Int
22 Kgamma *big.Int
23 RhoA *big.Int
24 RhoB *big.Int
25 RhoC *big.Int
26 }
27
28 // public
29 G1T [][3]*big.Int // t encrypted in G1 curve
30 G2T [][3][2]*big.Int // t encrypted in G2 curve
31 Pk struct { // Proving Key pk:=(pkA, pkB, pkC, pkH)
32 A [][3]*big.Int
33 B [][3][2]*big.Int
34 C [][3]*big.Int
35 Kp [][3]*big.Int
36 Ap [][3]*big.Int
37 Bp [][3]*big.Int
38 Cp [][3]*big.Int
39 }
40 Vk struct {
41 Vka [3][2]*big.Int
42 Vkb [3]*big.Int
43 Vkc [3][2]*big.Int
44 A [][3]*big.Int
45 G1Kbg [3]*big.Int // g1 * Kbeta * Kgamma
46 G2Kbg [3][2]*big.Int // g2 * Kbeta * Kgamma
47 G2Kg [3][2]*big.Int // g2 * Kgamma
48 Vkz [3][2]*big.Int
49 }
50}
51
52// Proof contains the parameters to proof the zkSNARK
53type Proof struct {
54 PiA [3]*big.Int
55 PiAp [3]*big.Int
56 PiB [3][2]*big.Int
57 PiBp [3]*big.Int
58 PiC [3]*big.Int
59 PiCp [3]*big.Int
60 PiH [3]*big.Int
61 PiKp [3]*big.Int
62 PublicSignals []*big.Int
63}
64
65// GenerateTrustedSetup generates the Trusted Setup from a compiled Circuit. The Setup.Toxic sub data structure must be destroyed
66func GenerateTrustedSetup(bn bn128.Bn128, fqR fields.Fq, pf r1csqap.PolynomialField, witnessLength int, circuit circuitcompiler.Circuit, alphas, betas, gammas [][]*big.Int, zx []*big.Int) (Setup, error) {
67 var setup Setup
68 var err error
69 // generate random t value
70 setup.Toxic.T, err = fqR.Rand()
71 if err != nil {
72 return Setup{}, err
73 }
74
75 // k for calculating pi' and Vk
76 setup.Toxic.Ka, err = fqR.Rand()
77 if err != nil {
78 return Setup{}, err
79 }
80 setup.Toxic.Kb, err = fqR.Rand()
81 if err != nil {
82 return Setup{}, err
83 }
84 setup.Toxic.Kc, err = fqR.Rand()
85 if err != nil {
86 return Setup{}, err
87 }
88
89 // generate Kβ (Kbeta) and Kγ (Kgamma)
90 setup.Toxic.Kbeta, err = fqR.Rand()
91 if err != nil {
92 return Setup{}, err
93 }
94 setup.Toxic.Kgamma, err = fqR.Rand()
95 if err != nil {
96 return Setup{}, err
97 }
98
99 // generate ρ (Rho): ρA, ρB, ρC
100 setup.Toxic.RhoA, err = fqR.Rand()
101 if err != nil {
102 return Setup{}, err
103 }
104 setup.Toxic.RhoB, err = fqR.Rand()
105 if err != nil {
106 return Setup{}, err
107 }
108 setup.Toxic.RhoC = fqR.Mul(setup.Toxic.RhoA, setup.Toxic.RhoB)
109
110 // encrypt t values with curve generators
111 var gt1 [][3]*big.Int
112 var gt2 [][3][2]*big.Int
113 for i := 0; i < witnessLength; i++ {
114 tPow := fqR.Exp(setup.Toxic.T, big.NewInt(int64(i)))
115 tEncr1 := bn.G1.MulScalar(bn.G1.G, tPow)
116 gt1 = append(gt1, tEncr1)
117 tEncr2 := bn.G2.MulScalar(bn.G2.G, tPow)
118 gt2 = append(gt2, tEncr2)
119 }
120 // gt1: g1, g1*t, g1*t^2, g1*t^3, ...
121 // gt2: g2, g2*t, g2*t^2, ...
122 setup.G1T = gt1
123 setup.G2T = gt2
124
125 setup.Vk.Vka = bn.G2.MulScalar(bn.G2.G, setup.Toxic.Ka)
126 setup.Vk.Vkb = bn.G1.MulScalar(bn.G1.G, setup.Toxic.Kb)
127 setup.Vk.Vkc = bn.G2.MulScalar(bn.G2.G, setup.Toxic.Kc)
128
129 /*
130 Verification keys:
131 - Vk_betagamma1: setup.G1Kbg = g1 * Kbeta*Kgamma
132 - Vk_betagamma2: setup.G2Kbg = g2 * Kbeta*Kgamma
133 - Vk_gamma: setup.G2Kg = g2 * Kgamma
134 */
135 kbg := fqR.Mul(setup.Toxic.Kbeta, setup.Toxic.Kgamma)
136 setup.Vk.G1Kbg = bn.G1.MulScalar(bn.G1.G, kbg)
137 setup.Vk.G2Kbg = bn.G2.MulScalar(bn.G2.G, kbg)
138 setup.Vk.G2Kg = bn.G2.MulScalar(bn.G2.G, setup.Toxic.Kgamma)
139
140 // for i := 0; i < circuit.NSignals; i++ {
141 for i := 0; i < circuit.NVars; i++ {
142 at := pf.Eval(alphas[i], setup.Toxic.T)
143 a := bn.G1.MulScalar(bn.G1.G, at)
144 setup.Pk.A = append(setup.Pk.A, a)
145 if i <= circuit.NPublic {
146 setup.Vk.A = append(setup.Vk.A, a)
147 }
148
149 bt := pf.Eval(betas[i], setup.Toxic.T)
150 bg1 := bn.G1.MulScalar(bn.G1.G, bt)
151 bg2 := bn.G2.MulScalar(bn.G2.G, bt)
152 setup.Pk.B = append(setup.Pk.B, bg2)
153
154 ct := pf.Eval(gammas[i], setup.Toxic.T)
155 c := bn.G1.MulScalar(bn.G1.G, ct)
156 setup.Pk.C = append(setup.Pk.C, c)
157
158 kt := fqR.Add(fqR.Add(at, bt), ct)
159 k := bn.G1.Affine(bn.G1.MulScalar(bn.G1.G, kt))
160
161 ktest := bn.G1.Affine(bn.G1.Add(bn.G1.Add(a, bg1), c))
162 if !bn.Fq2.Equal(k, ktest) {
163 os.Exit(1)
164 return setup, err
165 }
166
167 setup.Pk.Ap = append(setup.Pk.Ap, bn.G1.MulScalar(a, setup.Toxic.Ka))
168 setup.Pk.Bp = append(setup.Pk.Bp, bn.G1.MulScalar(bg1, setup.Toxic.Kb))
169 setup.Pk.Cp = append(setup.Pk.Cp, bn.G1.MulScalar(c, setup.Toxic.Kc))
170 k_ := bn.G1.MulScalar(bn.G1.G, kt)
171 setup.Pk.Kp = append(setup.Pk.Kp, bn.G1.MulScalar(k_, setup.Toxic.Kbeta))
172 }
173 setup.Vk.Vkz = bn.G2.MulScalar(bn.G2.G, pf.Eval(zx, setup.Toxic.T))
174
175 return setup, nil
176}
177
178// GenerateProofs generates all the parameters to proof the zkSNARK from the Circuit, Setup and the Witness
179func GenerateProofs(bn bn128.Bn128, f fields.Fq, circuit circuitcompiler.Circuit, setup Setup, hx []*big.Int, w []*big.Int) (Proof, error) {
180 var proof Proof
181 proof.PiA = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
182 proof.PiAp = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
183 proof.PiB = bn.Fq6.Zero()
184 proof.PiBp = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
185 proof.PiC = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
186 proof.PiCp = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
187 proof.PiH = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
188 proof.PiKp = [3]*big.Int{bn.G1.F.Zero(), bn.G1.F.Zero(), bn.G1.F.Zero()}
189
190 for i := circuit.NPublic + 1; i < circuit.NVars; i++ {
191 proof.PiA = bn.G1.Add(proof.PiA, bn.G1.MulScalar(setup.Pk.A[i], w[i]))
192 proof.PiAp = bn.G1.Add(proof.PiAp, bn.G1.MulScalar(setup.Pk.Ap[i], w[i]))
193 }
194
195 for i := 0; i < circuit.NVars; i++ {
196 proof.PiB = bn.G2.Add(proof.PiB, bn.G2.MulScalar(setup.Pk.B[i], w[i]))
197 proof.PiBp = bn.G1.Add(proof.PiBp, bn.G1.MulScalar(setup.Pk.Bp[i], w[i]))
198
199 proof.PiC = bn.G1.Add(proof.PiC, bn.G1.MulScalar(setup.Pk.C[i], w[i]))
200 proof.PiCp = bn.G1.Add(proof.PiCp, bn.G1.MulScalar(setup.Pk.Cp[i], w[i]))
201
202 proof.PiKp = bn.G1.Add(proof.PiKp, bn.G1.MulScalar(setup.Pk.Kp[i], w[i]))
203 }
204
205 for i := 0; i < len(hx); i++ {
206 proof.PiH = bn.G1.Add(proof.PiH, bn.G1.MulScalar(setup.G1T[i], hx[i]))
207 }
208 proof.PublicSignals = w[1 : circuit.NPublic+1]
209
210 return proof, nil
211}
212
213// VerifyProof verifies over the BN128 the Pairings of the Proof
214func VerifyProof(bn bn128.Bn128, circuit circuitcompiler.Circuit, setup Setup, proof Proof) bool {
215
216 // e(piA, Va) == e(piA', g2)
217 pairingPiaVa := bn.Pairing(proof.PiA, setup.Vk.Vka)
218 pairingPiapG2 := bn.Pairing(proof.PiAp, bn.G2.G)
219 if !bn.Fq12.Equal(pairingPiaVa, pairingPiapG2) {
220 return false
221 } else {
222 fmt.Println("✓ e(piA, Va) == e(piA', g2), valid knowledge commitment for A")
223 }
224
225 // e(Vb, piB) == e(piB', g2)
226 pairingVbPib := bn.Pairing(setup.Vk.Vkb, proof.PiB)
227 pairingPibpG2 := bn.Pairing(proof.PiBp, bn.G2.G)
228 if !bn.Fq12.Equal(pairingVbPib, pairingPibpG2) {
229 return false
230 } else {
231 fmt.Println("✓ e(Vb, piB) == e(piB', g2), valid knowledge commitment for B")
232 }
233
234 // e(piC, Vc) == e(piC', g2)
235 pairingPicVc := bn.Pairing(proof.PiC, setup.Vk.Vkc)
236 pairingPicpG2 := bn.Pairing(proof.PiCp, bn.G2.G)
237 if !bn.Fq12.Equal(pairingPicVc, pairingPicpG2) {
238 return false
239 } else {
240 fmt.Println("✓ e(piC, Vc) == e(piC', g2), valid knowledge commitment for C")
241 }
242
243 // Vkx, to then calculate Vkx+piA
244 vkxpia := setup.Vk.A[0]
245 for i := 0; i < circuit.NPublic; i++ {
246 vkxpia = bn.G1.Add(vkxpia, bn.G1.MulScalar(setup.Vk.A[i+1], proof.PublicSignals[i]))
247 }
248
249 // e(Vkx+piA, piB) == e(piH, Vkz) * e(piC, g2)
250 if !bn.Fq12.Equal(
251 bn.Pairing(bn.G1.Add(vkxpia, proof.PiA), proof.PiB),
252 bn.Fq12.Mul(
253 bn.Pairing(proof.PiH, setup.Vk.Vkz),
254 bn.Pairing(proof.PiC, bn.G2.G))) {
255 return false
256 } else {
257 fmt.Println("✓ e(Vkx+piA, piB) == e(piH, Vkz) * e(piC, g2), QAP disibility checked")
258 }
259
260 // e(Vkx+piA+piC, g2KbetaKgamma) * e(g1KbetaKgamma, piB)
261 // == e(piK, g2Kgamma)
262 piApiC := bn.G1.Add(bn.G1.Add(vkxpia, proof.PiA), proof.PiC)
263 pairingPiACG2Kbg := bn.Pairing(piApiC, setup.Vk.G2Kbg)
264 pairingG1KbgPiB := bn.Pairing(setup.Vk.G1Kbg, proof.PiB)
265 pairingL := bn.Fq12.Mul(pairingPiACG2Kbg, pairingG1KbgPiB)
266 pairingR := bn.Pairing(proof.PiKp, setup.Vk.G2Kg)
267 if !bn.Fq12.Equal(pairingL, pairingR) {
268 return false
269 } else {
270 fmt.Println("✓ e(Vkx+piA+piC, g2KbetaKgamma) * e(g1KbetaKgamma, piB) == e(piK, g2Kgamma)")
271 }
272
273 return true
274}