1package edwards_curve
  2
  3import (
  4	"fmt"
  5	"math/big"
  6
  7	"github.com/consensys/gnark/frontend"
  8	"github.com/consensys/gnark/std/math/emulated"
  9)
 10
 11func New[T, S emulated.FieldParams](api frontend.API) (*Curve[T, S], error) {
 12	var t T
 13	var s S
 14	var gxb, gyb *big.Int
 15	var A, D *big.Int
 16	_, is_25519_t := any(t).(Ed25519)
 17	_, is_25519_s := any(s).(Ed25519Scalars)
 18	if is_25519_t && is_25519_s {
 19		// https://neuromancer.sk/std/other/Ed25519
 20		gxb = newBigInt("216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A")
 21		gyb = newBigInt("6666666666666666666666666666666666666666666666666666666666666658")
 22		A = newBigInt("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec")
 23		D = newBigInt("52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3")
 24	} else {
 25		return nil, fmt.Errorf("unknown curve")
 26	}
 27	return newCurve[T, S](
 28		api,
 29		emulated.NewElement[T](A),
 30		emulated.NewElement[T](D),
 31		emulated.NewElement[T](gxb),
 32		emulated.NewElement[T](gyb))
 33}
 34
 35func newBigInt(s string) *big.Int {
 36	result, success := new(big.Int).SetString(s, 16)
 37	if !success {
 38		panic("invalid bigint")
 39	}
 40	return result
 41}
 42
 43// TODO: could also have a type constraint for curve parameters (fields,
 44// equation and generator). But for now we don't do arbitrary curves.
 45
 46type Curve[T, S emulated.FieldParams] struct {
 47	a emulated.Element[T]
 48	d emulated.Element[T]
 49
 50	// api is the native api, we construct it ourselves to be sure
 51	api frontend.API
 52	// baseApi is the api for point operations
 53	baseApi frontend.API
 54	// scalarApi is the api for scalar operations
 55	scalarApi frontend.API
 56
 57	g AffinePoint[T]
 58}
 59
 60func (c *Curve[T, S]) Generator() AffinePoint[T] {
 61	return c.g
 62}
 63
 64func newCurve[T, S emulated.FieldParams](api frontend.API, a, d, Gx, Gy emulated.Element[T]) (*Curve[T, S], error) {
 65	ba, err := emulated.NewField[T](api)
 66	if err != nil {
 67		return nil, fmt.Errorf("new base api: %w", err)
 68	}
 69	sa, err := emulated.NewField[S](api)
 70	if err != nil {
 71		return nil, fmt.Errorf("new scalar api: %w", err)
 72	}
 73	return &Curve[T, S]{
 74		a: a,
 75		d: d,
 76		api:       api,
 77		baseApi:   ba,
 78		scalarApi: sa,
 79		g: AffinePoint[T]{
 80			X: Gx,
 81			Y: Gy,
 82		},
 83	}, nil
 84}
 85
 86type AffinePoint[T emulated.FieldParams] struct {
 87	X, Y emulated.Element[T]
 88}
 89
 90func (c *Curve[T, S]) Neg(p AffinePoint[T]) AffinePoint[T] {
 91	return AffinePoint[T]{
 92		X: p.X,
 93		Y: c.baseApi.Neg(p.Y).(emulated.Element[T]),
 94	}
 95}
 96
 97func (c *Curve[T, S]) AssertIsEqual(p, q AffinePoint[T]) {
 98	c.baseApi.AssertIsEqual(p.X, q.X)
 99	c.baseApi.AssertIsEqual(p.Y, q.Y)
100}
101
102func (c *Curve[T, S]) AssertIsOnCurve(p AffinePoint[T]) {
103	xx := c.baseApi.Mul(p.X, p.X)
104	yy := c.baseApi.Mul(p.Y, p.Y)
105	axx := c.baseApi.Mul(xx, c.a)
106	lhs := c.baseApi.Add(axx, yy)
107
108	dxx := c.baseApi.Mul(xx, c.d)
109	dxxyy := c.baseApi.Mul(dxx, yy)
110	rhs := c.baseApi.Add(dxxyy, 1)
111
112	c.baseApi.AssertIsEqual(lhs, rhs)
113}
114
115func (c *Curve[T, S]) Add(q, r AffinePoint[T]) AffinePoint[T] {
116	// u = (x1 + y1) * (x2 + y2)
117	u1 := c.baseApi.Mul(q.X, c.a)
118	u1 = c.baseApi.Sub(q.Y, u1)
119	u2 := c.baseApi.Add(r.X, r.Y)
120	u := c.baseApi.Mul(u1, u2)
121
122	// v0 = x1 * y2
123	v0 := c.baseApi.Mul(r.Y, q.X)
124
125	// v1 = x2 * y1
126	v1 := c.baseApi.Mul(r.X, q.Y)
127
128	// v2 = d * v0 * v1
129	v2 := c.baseApi.Mul(c.d, v0, v1)
130
131	var px, py frontend.Variable
132
133	// x = (v0 + v1) / (1 + v2)
134	px = c.baseApi.Add(v0, v1)
135	px = c.baseApi.DivUnchecked(px, c.baseApi.Add(1, v2))
136
137	// y = (u + a * v0 - v1) / (1 - v2)
138	py = c.baseApi.Mul(c.a, v0)
139	py = c.baseApi.Sub(py, v1)
140	py = c.baseApi.Add(py, u)
141	py = c.baseApi.DivUnchecked(py, c.baseApi.Sub(1, v2))
142
143	return AffinePoint[T]{
144		X: px.(emulated.Element[T]),
145		Y: py.(emulated.Element[T]),
146	}
147}
148
149func (c *Curve[T, S]) Double(p AffinePoint[T]) AffinePoint[T] {
150	u := c.baseApi.Mul(p.X, p.Y)
151	v := c.baseApi.Mul(p.X, p.X)
152	w := c.baseApi.Mul(p.Y, p.Y)
153
154	n1 := c.baseApi.Mul(2, u)
155	av := c.baseApi.Mul(v, c.a)
156	n2 := c.baseApi.Sub(w, av)
157	d1 := c.baseApi.Add(w, av)
158	d2 := c.baseApi.Sub(2, d1)
159
160	px := c.baseApi.DivUnchecked(n1, d1)
161	py := c.baseApi.DivUnchecked(n2, d2)
162
163	return AffinePoint[T]{
164		X: px.(emulated.Element[T]),
165		Y: py.(emulated.Element[T]),
166	}
167}
168
169func (c *Curve[T, S]) Select(b frontend.Variable, p, q AffinePoint[T]) AffinePoint[T] {
170	x := c.baseApi.Select(b, p.X, q.X)
171	y := c.baseApi.Select(b, p.Y, q.Y)
172	return AffinePoint[T]{
173		X: x.(emulated.Element[T]),
174		Y: y.(emulated.Element[T]),
175	}
176}
177
178func (c *Curve[T, S]) ScalarMul(p AffinePoint[T], s emulated.Element[S]) AffinePoint[T] {
179	res := p
180	acc := c.Double(p)
181
182	sBits := c.scalarApi.ToBinary(s)
183	for i := 1; i < len(sBits); i++ {
184		tmp := c.Add(res, acc)
185		res = c.Select(sBits[i], tmp, res)
186		acc = c.Double(acc)
187	}
188
189	tmp := c.Add(res, c.Neg(p))
190	res = c.Select(sBits[0], res, tmp)
191	return res
192}