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