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