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