1package circuitcompiler
  2
  3import (
  4	"errors"
  5	"math/big"
  6	"strconv"
  7
  8	"github.com/arnaucube/go-snark/r1csqap"
  9)
 10
 11// Circuit is the data structure of the compiled circuit
 12type Circuit struct {
 13	NVars         int
 14	NPublic       int
 15	NSignals      int
 16	Inputs        []string
 17	Signals       []string
 18	PublicSignals []string
 19	Witness       []*big.Int
 20	Constraints   []Constraint
 21	R1CS          struct {
 22		A [][]*big.Int
 23		B [][]*big.Int
 24		C [][]*big.Int
 25	}
 26}
 27
 28// Constraint is the data structure of a flat code operation
 29type Constraint struct {
 30	// v1 op v2 = out
 31	Op      string
 32	V1      string
 33	V2      string
 34	Out     string
 35	Literal string
 36
 37	Inputs []string // in func declaration case
 38}
 39
 40func indexInArray(arr []string, e string) int {
 41	for i, a := range arr {
 42		if a == e {
 43			return i
 44		}
 45	}
 46	return -1
 47}
 48func isValue(a string) (bool, int) {
 49	v, err := strconv.Atoi(a)
 50	if err != nil {
 51		return false, 0
 52	}
 53	return true, v
 54}
 55func insertVar(arr []*big.Int, signals []string, v string, used map[string]bool) ([]*big.Int, map[string]bool) {
 56	isVal, value := isValue(v)
 57	valueBigInt := big.NewInt(int64(value))
 58	if isVal {
 59		arr[0] = new(big.Int).Add(arr[0], valueBigInt)
 60	} else {
 61		if !used[v] {
 62			panic(errors.New("using variable before it's set"))
 63		}
 64		arr[indexInArray(signals, v)] = new(big.Int).Add(arr[indexInArray(signals, v)], big.NewInt(int64(1)))
 65	}
 66	return arr, used
 67}
 68func insertVarNeg(arr []*big.Int, signals []string, v string, used map[string]bool) ([]*big.Int, map[string]bool) {
 69	isVal, value := isValue(v)
 70	valueBigInt := big.NewInt(int64(value))
 71	if isVal {
 72		arr[0] = new(big.Int).Add(arr[0], valueBigInt)
 73	} else {
 74		if !used[v] {
 75			panic(errors.New("using variable before it's set"))
 76		}
 77		arr[indexInArray(signals, v)] = new(big.Int).Add(arr[indexInArray(signals, v)], big.NewInt(int64(-1)))
 78	}
 79	return arr, used
 80}
 81
 82// GenerateR1CS generates the R1CS polynomials from the Circuit
 83func (circ *Circuit) GenerateR1CS() ([][]*big.Int, [][]*big.Int, [][]*big.Int) {
 84	// from flat code to R1CS
 85
 86	var a [][]*big.Int
 87	var b [][]*big.Int
 88	var c [][]*big.Int
 89
 90	used := make(map[string]bool)
 91	for _, constraint := range circ.Constraints {
 92		aConstraint := r1csqap.ArrayOfBigZeros(len(circ.Signals))
 93		bConstraint := r1csqap.ArrayOfBigZeros(len(circ.Signals))
 94		cConstraint := r1csqap.ArrayOfBigZeros(len(circ.Signals))
 95
 96		// if existInArray(constraint.Out) {
 97		if used[constraint.Out] {
 98			panic(errors.New("out variable already used: " + constraint.Out))
 99		}
100		used[constraint.Out] = true
101		if constraint.Op == "in" {
102			for i := 0; i < len(constraint.Inputs); i++ {
103				aConstraint[indexInArray(circ.Signals, constraint.Out)] = new(big.Int).Add(aConstraint[indexInArray(circ.Signals, constraint.Out)], big.NewInt(int64(1)))
104				aConstraint, used = insertVar(aConstraint, circ.Signals, constraint.Out, used)
105				bConstraint[0] = big.NewInt(int64(1))
106			}
107			continue
108
109		} else if constraint.Op == "+" {
110			cConstraint[indexInArray(circ.Signals, constraint.Out)] = big.NewInt(int64(1))
111			aConstraint, used = insertVar(aConstraint, circ.Signals, constraint.V1, used)
112			aConstraint, used = insertVar(aConstraint, circ.Signals, constraint.V2, used)
113			bConstraint[0] = big.NewInt(int64(1))
114		} else if constraint.Op == "-" {
115			cConstraint[indexInArray(circ.Signals, constraint.Out)] = big.NewInt(int64(1))
116			aConstraint, used = insertVarNeg(aConstraint, circ.Signals, constraint.V1, used)
117			aConstraint, used = insertVarNeg(aConstraint, circ.Signals, constraint.V2, used)
118			bConstraint[0] = big.NewInt(int64(1))
119		} else if constraint.Op == "*" {
120			cConstraint[indexInArray(circ.Signals, constraint.Out)] = big.NewInt(int64(1))
121			aConstraint, used = insertVar(aConstraint, circ.Signals, constraint.V1, used)
122			bConstraint, used = insertVar(bConstraint, circ.Signals, constraint.V2, used)
123		} else if constraint.Op == "/" {
124			cConstraint, used = insertVar(cConstraint, circ.Signals, constraint.V1, used)
125			cConstraint[indexInArray(circ.Signals, constraint.Out)] = big.NewInt(int64(1))
126			bConstraint, used = insertVar(bConstraint, circ.Signals, constraint.V2, used)
127		}
128
129		a = append(a, aConstraint)
130		b = append(b, bConstraint)
131		c = append(c, cConstraint)
132
133	}
134	return a, b, c
135}
136
137func grabVar(signals []string, w []*big.Int, vStr string) *big.Int {
138	isVal, v := isValue(vStr)
139	vBig := big.NewInt(int64(v))
140	if isVal {
141		return vBig
142	} else {
143		return w[indexInArray(signals, vStr)]
144	}
145}
146
147// CalculateWitness calculates the Witness of a Circuit based on the given inputs
148func (circ *Circuit) CalculateWitness(inputs []*big.Int) ([]*big.Int, error) {
149	if len(inputs) != len(circ.Inputs) {
150		return []*big.Int{}, errors.New("given inputs != circuit.Inputs")
151	}
152	w := r1csqap.ArrayOfBigZeros(len(circ.Signals))
153	w[0] = big.NewInt(int64(1))
154	for i, input := range inputs {
155		w[i+2] = input
156	}
157	for _, constraint := range circ.Constraints {
158		if constraint.Op == "in" {
159		} else if constraint.Op == "+" {
160			w[indexInArray(circ.Signals, constraint.Out)] = new(big.Int).Add(grabVar(circ.Signals, w, constraint.V1), grabVar(circ.Signals, w, constraint.V2))
161		} else if constraint.Op == "-" {
162			w[indexInArray(circ.Signals, constraint.Out)] = new(big.Int).Sub(grabVar(circ.Signals, w, constraint.V1), grabVar(circ.Signals, w, constraint.V2))
163		} else if constraint.Op == "*" {
164			w[indexInArray(circ.Signals, constraint.Out)] = new(big.Int).Mul(grabVar(circ.Signals, w, constraint.V1), grabVar(circ.Signals, w, constraint.V2))
165		} else if constraint.Op == "/" {
166			w[indexInArray(circ.Signals, constraint.Out)] = new(big.Int).Div(grabVar(circ.Signals, w, constraint.V1), grabVar(circ.Signals, w, constraint.V2))
167		}
168	}
169	return w, nil
170}