go-circom-prover-verifier/prover/prover.go
prover/prover.goRaw
1package prover
2
3import (
4 "crypto/rand"
5 "math"
6 "math/big"
7 "runtime"
8 "sync"
9
10 bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
11 "github.com/iden3/go-circom-prover-verifier/types"
12 "github.com/iden3/go-iden3-crypto/utils"
13 //"fmt"
14)
15
16// Proof is the data structure of the Groth16 zkSNARK proof
17type Proof struct {
18 A *bn256.G1
19 B *bn256.G2
20 C *bn256.G1
21}
22
23// Pk holds the data structure of the ProvingKey
24type Pk struct {
25 A []*bn256.G1
26 B2 []*bn256.G2
27 B1 []*bn256.G1
28 C []*bn256.G1
29 NVars int
30 NPublic int
31 VkAlpha1 *bn256.G1
32 VkDelta1 *bn256.G1
33 VkBeta1 *bn256.G1
34 VkBeta2 *bn256.G2
35 VkDelta2 *bn256.G2
36 HExps []*bn256.G1
37 DomainSize int
38 PolsA []map[int]*big.Int
39 PolsB []map[int]*big.Int
40 PolsC []map[int]*big.Int
41}
42
43// Witness contains the witness
44type Witness []*big.Int
45
46// Group Size
47const (
48 GSIZE = 6
49)
50
51func randBigInt() (*big.Int, error) {
52 maxbits := types.R.BitLen()
53 b := make([]byte, (maxbits/8)-1)
54 _, err := rand.Read(b)
55 if err != nil {
56 return nil, err
57 }
58 r := new(big.Int).SetBytes(b)
59 rq := new(big.Int).Mod(r, types.R)
60
61 return rq, nil
62}
63
64// GenerateProof generates the Groth16 zkSNARK proof
65func GenerateProof(pk *types.Pk, w types.Witness) (*types.Proof, []*big.Int, error) {
66 var proof types.Proof
67
68 r, err := randBigInt()
69 if err != nil {
70 return nil, nil, err
71 }
72 s, err := randBigInt()
73 if err != nil {
74 return nil, nil, err
75 }
76
77 // BEGIN PAR
78 numcpu := runtime.NumCPU()
79
80 proofA := arrayOfZeroesG1(numcpu)
81 proofB := arrayOfZeroesG2(numcpu)
82 proofC := arrayOfZeroesG1(numcpu)
83 proofBG1 := arrayOfZeroesG1(numcpu)
84 gsize := GSIZE
85 var wg1 sync.WaitGroup
86 wg1.Add(numcpu)
87 for _cpu, _ranges := range ranges(pk.NVars, numcpu) {
88 // split 1
89 go func(cpu int, ranges [2]int) {
90 proofA[cpu] = ScalarMultNoDoubleG1(pk.A[ranges[0]:ranges[1]],
91 w[ranges[0]:ranges[1]],
92 proofA[cpu],
93 gsize)
94 proofB[cpu] = ScalarMultNoDoubleG2(pk.B2[ranges[0]:ranges[1]],
95 w[ranges[0]:ranges[1]],
96 proofB[cpu],
97 gsize)
98 proofBG1[cpu] = ScalarMultNoDoubleG1(pk.B1[ranges[0]:ranges[1]],
99 w[ranges[0]:ranges[1]],
100 proofBG1[cpu],
101 gsize)
102 min_lim := pk.NPublic+1
103 if ranges[0] > pk.NPublic+1 {
104 min_lim = ranges[0]
105 }
106 if ranges[1] > pk.NPublic + 1 {
107 proofC[cpu] = ScalarMultNoDoubleG1(pk.C[min_lim:ranges[1]],
108 w[min_lim:ranges[1]],
109 proofC[cpu],
110 gsize)
111 }
112 wg1.Done()
113 }(_cpu, _ranges)
114 }
115 wg1.Wait()
116 // join 1
117 for cpu := 1; cpu < numcpu; cpu++ {
118 proofA[0].Add(proofA[0], proofA[cpu])
119 proofB[0].Add(proofB[0], proofB[cpu])
120 proofC[0].Add(proofC[0], proofC[cpu])
121 proofBG1[0].Add(proofBG1[0], proofBG1[cpu])
122 }
123 proof.A = proofA[0]
124 proof.B = proofB[0]
125 proof.C = proofC[0]
126 // END PAR
127
128 h := calculateH(pk, w)
129
130 proof.A.Add(proof.A, pk.VkAlpha1)
131 proof.A.Add(proof.A, new(bn256.G1).ScalarMult(pk.VkDelta1, r))
132
133 proof.B.Add(proof.B, pk.VkBeta2)
134 proof.B.Add(proof.B, new(bn256.G2).ScalarMult(pk.VkDelta2, s))
135
136 proofBG1[0].Add(proofBG1[0], pk.VkBeta1)
137 proofBG1[0].Add(proofBG1[0], new(bn256.G1).ScalarMult(pk.VkDelta1, s))
138
139 proofC = arrayOfZeroesG1(numcpu)
140 var wg2 sync.WaitGroup
141 wg2.Add(numcpu)
142 for _cpu, _ranges := range ranges(len(h), numcpu) {
143 // split 2
144 go func(cpu int, ranges [2]int) {
145 proofC[cpu] = ScalarMultNoDoubleG1(pk.HExps[ranges[0]:ranges[1]],
146 h[ranges[0]:ranges[1]],
147 proofC[cpu],
148 gsize)
149 wg2.Done()
150 }(_cpu, _ranges)
151 }
152 wg2.Wait()
153 // join 2
154 for cpu := 1; cpu < numcpu; cpu++ {
155 proofC[0].Add(proofC[0], proofC[cpu])
156 }
157 proof.C.Add(proof.C, proofC[0])
158
159 proof.C.Add(proof.C, new(bn256.G1).ScalarMult(proof.A, s))
160 proof.C.Add(proof.C, new(bn256.G1).ScalarMult(proofBG1[0], r))
161 rsneg := new(big.Int).Mod(new(big.Int).Neg(new(big.Int).Mul(r, s)), types.R)
162 proof.C.Add(proof.C, new(bn256.G1).ScalarMult(pk.VkDelta1, rsneg))
163
164 pubSignals := w[1 : pk.NPublic+1]
165
166 return &proof, pubSignals, nil
167}
168
169func calculateH(pk *types.Pk, w types.Witness) []*big.Int {
170 m := pk.DomainSize
171 polAT := arrayOfZeroes(m)
172 polBT := arrayOfZeroes(m)
173
174 numcpu := runtime.NumCPU()
175
176 var wg1 sync.WaitGroup
177 wg1.Add(2)
178 go func() {
179 for i := 0; i < pk.NVars; i++ {
180 for j := range pk.PolsA[i] {
181 polAT[j] = fAdd(polAT[j], fMul(w[i], pk.PolsA[i][j]))
182 }
183 }
184 wg1.Done()
185 }()
186 go func() {
187 for i := 0; i < pk.NVars; i++ {
188 for j := range pk.PolsB[i] {
189 polBT[j] = fAdd(polBT[j], fMul(w[i], pk.PolsB[i][j]))
190 }
191 }
192 wg1.Done()
193 }()
194 wg1.Wait()
195 polATe := utils.BigIntArrayToElementArray(polAT)
196 polBTe := utils.BigIntArrayToElementArray(polBT)
197
198 polASe := ifft(polATe)
199 polBSe := ifft(polBTe)
200
201 r := int(math.Log2(float64(m))) + 1
202 roots := newRootsT()
203 roots.setRoots(r)
204
205 var wg2 sync.WaitGroup
206 wg2.Add(numcpu)
207 for _cpu, _ranges := range ranges(len(polASe), numcpu) {
208 go func(cpu int, ranges [2]int) {
209 for i := ranges[0]; i < ranges[1]; i++ {
210 polASe[i].Mul(polASe[i], roots.roots[r][i])
211 polBSe[i].Mul(polBSe[i], roots.roots[r][i])
212 }
213 wg2.Done()
214 }(_cpu, _ranges)
215 }
216 wg2.Wait()
217
218 polATodd := fft(polASe)
219 polBTodd := fft(polBSe)
220
221 polABT := arrayOfZeroesE(len(polASe) * 2)
222 var wg3 sync.WaitGroup
223 wg3.Add(numcpu)
224 for _cpu, _ranges := range ranges(len(polASe), numcpu) {
225 go func(cpu int, ranges [2]int) {
226 for i := ranges[0]; i < ranges[1]; i++ {
227 polABT[2*i].Mul(polATe[i], polBTe[i])
228 polABT[2*i+1].Mul(polATodd[i], polBTodd[i])
229 }
230 wg3.Done()
231 }(_cpu, _ranges)
232 }
233 wg3.Wait()
234
235 hSeFull := ifft(polABT)
236
237 hSe := hSeFull[m:]
238 return utils.ElementArrayToBigIntArray(hSe)
239}
240
241func ranges(n, parts int) [][2]int {
242 s := make([][2]int, parts)
243 p := float64(n) / float64(parts)
244 for i := 0; i < parts; i++ {
245 a, b := int(float64(i)*p), int(float64(i+1)*p)
246 s[i] = [2]int{a, b}
247 }
248 return s
249}