1package prover
  2
  3import (
  4	"crypto/rand"
  5	"math"
  6	"math/big"
  7
  8	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
  9	"github.com/iden3/go-circom-prover-verifier/types"
 10	"github.com/iden3/go-iden3-crypto/ff"
 11	"github.com/iden3/go-iden3-crypto/utils"
 12)
 13
 14// Proof is the data structure of the Groth16 zkSNARK proof
 15type Proof struct {
 16	A *bn256.G1
 17	B *bn256.G2
 18	C *bn256.G1
 19}
 20
 21// Pk holds the data structure of the ProvingKey
 22type Pk struct {
 23	A          []*bn256.G1
 24	B2         []*bn256.G2
 25	B1         []*bn256.G1
 26	C          []*bn256.G1
 27	NVars      int
 28	NPublic    int
 29	VkAlpha1   *bn256.G1
 30	VkDelta1   *bn256.G1
 31	VkBeta1    *bn256.G1
 32	VkBeta2    *bn256.G2
 33	VkDelta2   *bn256.G2
 34	HExps      []*bn256.G1
 35	DomainSize int
 36	PolsA      []map[int]*big.Int
 37	PolsB      []map[int]*big.Int
 38	PolsC      []map[int]*big.Int
 39}
 40
 41// Witness contains the witness
 42type Witness []*big.Int
 43
 44// R is the mod of the finite field
 45var R, _ = new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)
 46
 47func randBigInt() (*big.Int, error) {
 48	maxbits := R.BitLen()
 49	b := make([]byte, (maxbits/8)-1)
 50	_, err := rand.Read(b)
 51	if err != nil {
 52		return nil, err
 53	}
 54	r := new(big.Int).SetBytes(b)
 55	rq := new(big.Int).Mod(r, R)
 56
 57	return rq, nil
 58}
 59
 60// GenerateProof generates the Groth16 zkSNARK proof
 61func GenerateProof(pk *types.Pk, w types.Witness) (*types.Proof, []*big.Int, error) {
 62	var proof types.Proof
 63
 64	r, err := randBigInt()
 65	if err != nil {
 66		return nil, nil, err
 67	}
 68	s, err := randBigInt()
 69	if err != nil {
 70		return nil, nil, err
 71	}
 72
 73	proof.A = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 74	proof.B = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 75	proof.C = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 76	proofBG1 := new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 77
 78	for i := 0; i < pk.NVars; i++ {
 79		proof.A = new(bn256.G1).Add(proof.A, new(bn256.G1).ScalarMult(pk.A[i], w[i]))
 80		proof.B = new(bn256.G2).Add(proof.B, new(bn256.G2).ScalarMult(pk.B2[i], w[i]))
 81		proofBG1 = new(bn256.G1).Add(proofBG1, new(bn256.G1).ScalarMult(pk.B1[i], w[i]))
 82	}
 83
 84	for i := pk.NPublic + 1; i < pk.NVars; i++ {
 85		proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.C[i], w[i]))
 86	}
 87
 88	proof.A = new(bn256.G1).Add(proof.A, pk.VkAlpha1)
 89	proof.A = new(bn256.G1).Add(proof.A, new(bn256.G1).ScalarMult(pk.VkDelta1, r))
 90
 91	proof.B = new(bn256.G2).Add(proof.B, pk.VkBeta2)
 92	proof.B = new(bn256.G2).Add(proof.B, new(bn256.G2).ScalarMult(pk.VkDelta2, s))
 93
 94	proofBG1 = new(bn256.G1).Add(proofBG1, pk.VkBeta1)
 95	proofBG1 = new(bn256.G1).Add(proofBG1, new(bn256.G1).ScalarMult(pk.VkDelta1, s))
 96
 97	h := calculateH(pk, w)
 98
 99	for i := 0; i < len(h); i++ {
100		proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.HExps[i], h[i]))
101	}
102	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(proof.A, s))
103	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(proofBG1, r))
104	rsneg := new(big.Int).Mod(new(big.Int).Neg(new(big.Int).Mul(r, s)), R) // fAdd & fMul
105	proof.C = new(bn256.G1).Add(proof.C, new(bn256.G1).ScalarMult(pk.VkDelta1, rsneg))
106
107	pubSignals := w[1 : pk.NPublic+1]
108
109	return &proof, pubSignals, nil
110}
111
112func calculateH(pk *types.Pk, w types.Witness) []*big.Int {
113	m := pk.DomainSize
114	polAT := arrayOfZeroes(m)
115	polBT := arrayOfZeroes(m)
116
117	for i := 0; i < pk.NVars; i++ {
118		for j := range pk.PolsA[i] {
119			polAT[j] = fAdd(polAT[j], fMul(w[i], pk.PolsA[i][j]))
120		}
121		for j := range pk.PolsB[i] {
122			polBT[j] = fAdd(polBT[j], fMul(w[i], pk.PolsB[i][j]))
123		}
124	}
125	polATe := utils.BigIntArrayToElementArray(polAT)
126	polBTe := utils.BigIntArrayToElementArray(polBT)
127
128	polASe := ifft(polATe)
129	polBSe := ifft(polBTe)
130
131	r := int(math.Log2(float64(m))) + 1
132	roots := newRootsT()
133	roots.setRoots(r)
134	for i := 0; i < len(polASe); i++ {
135		polASe[i] = ff.NewElement().Mul(polASe[i], roots.roots[r][i])
136		polBSe[i] = ff.NewElement().Mul(polBSe[i], roots.roots[r][i])
137	}
138
139	polATodd := fft(polASe)
140	polBTodd := fft(polBSe)
141
142	polABT := arrayOfZeroesE(len(polASe) * 2)
143	for i := 0; i < len(polASe); i++ {
144		polABT[2*i] = ff.NewElement().Mul(polATe[i], polBTe[i])
145		polABT[2*i+1] = ff.NewElement().Mul(polATodd[i], polBTodd[i])
146	}
147
148	hSeFull := ifft(polABT)
149
150	hSe := hSeFull[m:]
151	return ElementArrayToBigIntArray(hSe)
152}