1package babyjub
  2
  3import (
  4	"fmt"
  5	"github.com/iden3/go-iden3-crypto/constants"
  6	"github.com/iden3/go-iden3-crypto/utils"
  7	"math/big"
  8)
  9
 10// A is one of the babyjub constants.
 11var A *big.Int
 12
 13// D is one of the babyjub constants.
 14var D *big.Int
 15
 16// Order of the babyjub curve.
 17var Order *big.Int
 18
 19// SubOrder is the order of the subgroup of the babyjub curve that contains the
 20// points that we use.
 21var SubOrder *big.Int
 22
 23// B8 is a base point of the babyjub multiplied by 8 to make it a base point of
 24// the subgroup in the curve.
 25var B8 *Point
 26
 27// init initializes global numbers and the subgroup base.
 28func init() {
 29	A = utils.NewIntFromString("168700")
 30	D = utils.NewIntFromString("168696")
 31
 32	Order = utils.NewIntFromString(
 33		"21888242871839275222246405745257275088614511777268538073601725287587578984328")
 34	SubOrder = new(big.Int).Rsh(Order, 3)
 35
 36	B8 = NewPoint()
 37	B8.X = utils.NewIntFromString(
 38		"17777552123799933955779906779655732241715742912184938656739573121738514868268")
 39	B8.Y = utils.NewIntFromString(
 40		"2626589144620713026669568689430873010625803728049924121243784502389097019475")
 41}
 42
 43// Point represents a point of the babyjub curve.
 44type Point struct {
 45	X *big.Int
 46	Y *big.Int
 47}
 48
 49// NewPoint creates a new Point.
 50func NewPoint() *Point {
 51	return &Point{X: big.NewInt(0), Y: big.NewInt(1)}
 52}
 53
 54// Set copies a Point c into the Point p
 55func (p *Point) Set(c *Point) *Point {
 56	p.X.Set(c.X)
 57	p.Y.Set(c.Y)
 58	return p
 59}
 60
 61// Add adds Point a and b into res
 62func (res *Point) Add(a *Point, b *Point) *Point {
 63	// x = (a.x * b.y + b.x * a.y) * (1 + D * a.x * b.x * a.y * b.y)^-1 mod q
 64	x1a := new(big.Int).Mul(a.X, b.Y)
 65	x1b := new(big.Int).Mul(b.X, a.Y)
 66	x1a.Add(x1a, x1b) // x1a = a.x * b.y + b.x * a.y
 67
 68	x2 := new(big.Int).Set(D)
 69	x2.Mul(x2, a.X)
 70	x2.Mul(x2, b.X)
 71	x2.Mul(x2, a.Y)
 72	x2.Mul(x2, b.Y)
 73	x2.Add(constants.One, x2)
 74	x2.Mod(x2, constants.Q)
 75	x2.ModInverse(x2, constants.Q) // x2 = (1 + D * a.x * b.x * a.y * b.y)^-1
 76
 77	// y = (a.y * b.y + A * a.x * a.x) * (1 - D * a.x * b.x * a.y * b.y)^-1 mod q
 78	y1a := new(big.Int).Mul(a.Y, b.Y)
 79	y1b := new(big.Int).Set(A)
 80	y1b.Mul(y1b, a.X)
 81	y1b.Mul(y1b, b.X)
 82
 83	y1a.Sub(y1a, y1b) // y1a = a.y * b.y - A * a.x * b.x
 84
 85	y2 := new(big.Int).Set(D)
 86	y2.Mul(y2, a.X)
 87	y2.Mul(y2, b.X)
 88	y2.Mul(y2, a.Y)
 89	y2.Mul(y2, b.Y)
 90	y2.Sub(constants.One, y2)
 91	y2.Mod(y2, constants.Q)
 92	y2.ModInverse(y2, constants.Q) // y2 = (1 - D * a.x * b.x * a.y * b.y)^-1
 93
 94	res.X = x1a.Mul(x1a, x2)
 95	res.X = res.X.Mod(res.X, constants.Q)
 96
 97	res.Y = y1a.Mul(y1a, y2)
 98	res.Y = res.Y.Mod(res.Y, constants.Q)
 99
100	return res
101}
102
103// Mul multiplies the Point p by the scalar s and stores the result in res,
104// which is also returned.
105func (res *Point) Mul(s *big.Int, p *Point) *Point {
106	res.X = big.NewInt(0)
107	res.Y = big.NewInt(1)
108	exp := NewPoint().Set(p)
109
110	for i := 0; i < s.BitLen(); i++ {
111		if s.Bit(i) == 1 {
112			res.Add(res, exp)
113		}
114		exp.Add(exp, exp)
115	}
116
117	return res
118}
119
120// InCurve returns true when the Point p is in the babyjub curve.
121func (p *Point) InCurve() bool {
122	x2 := new(big.Int).Set(p.X)
123	x2.Mul(x2, x2)
124	x2.Mod(x2, constants.Q)
125
126	y2 := new(big.Int).Set(p.Y)
127	y2.Mul(y2, y2)
128	y2.Mod(y2, constants.Q)
129
130	a := new(big.Int).Mul(A, x2)
131	a.Add(a, y2)
132	a.Mod(a, constants.Q)
133
134	b := new(big.Int).Set(D)
135	b.Mul(b, x2)
136	b.Mul(b, y2)
137	b.Add(constants.One, b)
138	b.Mod(b, constants.Q)
139
140	return a.Cmp(b) == 0
141}
142
143// InSubGroup returns true when the Point p is in the subgroup of the babyjub
144// curve.
145func (p *Point) InSubGroup() bool {
146	if !p.InCurve() {
147		return false
148	}
149	res := NewPoint().Mul(SubOrder, p)
150	return (res.X.Cmp(constants.Zero) == 0) && (res.Y.Cmp(constants.One) == 0)
151}
152
153// PointCoordSign returns the sign of the curve point coordinate.  It returns
154// false if the sign is positive and false if the sign is negative.
155func PointCoordSign(c *big.Int) bool {
156	if c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1 {
157		return true
158	}
159	return false
160}
161
162func PackPoint(ay *big.Int, sign bool) [32]byte {
163	leBuf := utils.BigIntLEBytes(ay)
164	if sign {
165		leBuf[31] = leBuf[31] | 0x80
166	}
167	return leBuf
168}
169
170// Compress the point into a 32 byte array that contains the y coordinate in
171// little endian and the sign of the x coordinate.
172func (p *Point) Compress() [32]byte {
173	sign := false
174	if PointCoordSign(p.X) {
175		sign = true
176	}
177	return PackPoint(p.Y, sign)
178}
179
180// Decompress a compressed Point into p, and also returns the decompressed
181// Point.  Returns error if the compressed Point is invalid.
182func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
183	sign := false
184	if (leBuf[31] & 0x80) != 0x00 {
185		sign = true
186		leBuf[31] = leBuf[31] & 0x7F
187	}
188	utils.SetBigIntFromLEBytes(p.Y, leBuf[:])
189	if p.Y.Cmp(constants.Q) >= 0 {
190		return nil, fmt.Errorf("p.y >= Q")
191	}
192
193	y2 := new(big.Int).Mul(p.Y, p.Y)
194	y2.Mod(y2, constants.Q)
195	xa := big.NewInt(1)
196	xa.Sub(xa, y2) // xa == 1 - y^2
197
198	xb := new(big.Int).Mul(D, y2)
199	xb.Mod(xb, constants.Q)
200	xb.Sub(A, xb) // xb = A - d * y^2
201
202	if xb.Cmp(big.NewInt(0)) == 0 {
203		return nil, fmt.Errorf("division by 0")
204	}
205	xb.ModInverse(xb, constants.Q)
206	p.X.Mul(xa, xb) // xa / xb
207	p.X.Mod(p.X, constants.Q)
208	p.X.ModSqrt(p.X, constants.Q)
209	if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
210		p.X.Mul(p.X, constants.MinusOne)
211	}
212	p.X.Mod(p.X, constants.Q)
213
214	return p, nil
215}