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