1package prover
  2
  3import (
  4	"crypto/rand"
  5	"math"
  6	"math/big"
  7	"sync"
  8
  9	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
 10	"github.com/iden3/go-circom-prover-verifier/types"
 11	"github.com/iden3/go-iden3-crypto/ff"
 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	proof.A = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 72	proof.B = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 73	proof.C = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 74	proofBG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 75
 76	var waitGroup sync.WaitGroup
 77	waitGroup.Add(4)
 78	go func(wg *sync.WaitGroup) {
 79		for i := 0; i < pk.NVars; i++ {
 80			proof.A = new(bn256.G1).Add(proof.A, new(bn256.G1).ScalarMult(pk.A[i], w[i]))
 81		}
 82		wg.Done()
 83	}(&waitGroup)
 84	go func(wg *sync.WaitGroup) {
 85		for i := 0; i < pk.NVars; i++ {
 86			proof.B = new(bn256.G2).Add(proof.B, new(bn256.G2).ScalarMult(pk.B2[i], w[i]))
 87		}
 88		wg.Done()
 89	}(&waitGroup)
 90	go func(wg *sync.WaitGroup) {
 91		for i := 0; i < pk.NVars; i++ {
 92			proofBG1 = new(bn256.G1).Add(proofBG1, new(bn256.G1).ScalarMult(pk.B1[i], w[i]))
 93		}
 94		wg.Done()
 95	}(&waitGroup)
 96	go func(wg *sync.WaitGroup) {
 97		for i := pk.NPublic + 1; i < pk.NVars; i++ {
 98			proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.C[i], w[i]))
 99		}
100		wg.Done()
101	}(&waitGroup)
102	waitGroup.Wait()
103
104	h := calculateH(pk, w)
105
106	var waitGroup2 sync.WaitGroup
107	waitGroup2.Add(2)
108	go func(wg *sync.WaitGroup) {
109		proof.A = new(bn256.G1).Add(proof.A, pk.VkAlpha1)
110		proof.A = new(bn256.G1).Add(proof.A, new(bn256.G1).ScalarMult(pk.VkDelta1, r))
111
112		proof.B = new(bn256.G2).Add(proof.B, pk.VkBeta2)
113		proof.B = new(bn256.G2).Add(proof.B, new(bn256.G2).ScalarMult(pk.VkDelta2, s))
114
115		proofBG1 = new(bn256.G1).Add(proofBG1, pk.VkBeta1)
116		proofBG1 = new(bn256.G1).Add(proofBG1, new(bn256.G1).ScalarMult(pk.VkDelta1, s))
117		wg.Done()
118	}(&waitGroup2)
119	go func(wg *sync.WaitGroup) {
120		for i := 0; i < len(h); i++ {
121			proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.HExps[i], h[i]))
122		}
123		wg.Done()
124	}(&waitGroup2)
125	waitGroup2.Wait()
126
127	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(proof.A, s))
128	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(proofBG1, r))
129	rsneg := new(big.Int).Mod(new(big.Int).Neg(new(big.Int).Mul(r, s)), types.R) // fAdd & fMul
130	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.VkDelta1, rsneg))
131
132	pubSignals := w[1 : pk.NPublic+1]
133
134	return &proof, pubSignals, nil
135}
136
137func calculateH(pk *types.Pk, w types.Witness) []*big.Int {
138	m := pk.DomainSize
139	polAT := arrayOfZeroes(m)
140	polBT := arrayOfZeroes(m)
141
142	for i := 0; i < pk.NVars; i++ {
143		for j := range pk.PolsA[i] {
144			polAT[j] = fAdd(polAT[j], fMul(w[i], pk.PolsA[i][j]))
145		}
146		for j := range pk.PolsB[i] {
147			polBT[j] = fAdd(polBT[j], fMul(w[i], pk.PolsB[i][j]))
148		}
149	}
150	polATe := utils.BigIntArrayToElementArray(polAT)
151	polBTe := utils.BigIntArrayToElementArray(polBT)
152
153	polASe := ifft(polATe)
154	polBSe := ifft(polBTe)
155
156	r := int(math.Log2(float64(m))) + 1
157	roots := newRootsT()
158	roots.setRoots(r)
159	for i := 0; i < len(polASe); i++ {
160		polASe[i] = ff.NewElement().Mul(polASe[i], roots.roots[r][i])
161		polBSe[i] = ff.NewElement().Mul(polBSe[i], roots.roots[r][i])
162	}
163
164	polATodd := fft(polASe)
165	polBTodd := fft(polBSe)
166
167	polABT := arrayOfZeroesE(len(polASe) * 2)
168	for i := 0; i < len(polASe); i++ {
169		polABT[2*i] = ff.NewElement().Mul(polATe[i], polBTe[i])
170		polABT[2*i+1] = ff.NewElement().Mul(polATodd[i], polBTodd[i])
171	}
172
173	hSeFull := ifft(polABT)
174
175	hSe := hSeFull[m:]
176	return utils.ElementArrayToBigIntArray(hSe)
177}