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