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