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]) AssertIsZero(p AffinePoint[T]) {
116	c.baseApi.AssertIsEqual(p.X, 0)
117	c.baseApi.AssertIsEqual(p.Y, 1)
118}
119
120func (c *Curve[T, S]) Add(q, r AffinePoint[T]) AffinePoint[T] {
121	// u = (x1 + y1) * (x2 + y2)
122	u1 := c.baseApi.Mul(q.X, c.a)
123	u1 = c.baseApi.Sub(q.Y, u1)
124	u2 := c.baseApi.Add(r.X, r.Y)
125	u := c.baseApi.Mul(u1, u2)
126
127	// v0 = x1 * y2
128	v0 := c.baseApi.Mul(r.Y, q.X)
129
130	// v1 = x2 * y1
131	v1 := c.baseApi.Mul(r.X, q.Y)
132
133	// v2 = d * v0 * v1
134	v2 := c.baseApi.Mul(c.d, v0, v1)
135
136	var px, py frontend.Variable
137
138	// x = (v0 + v1) / (1 + v2)
139	px = c.baseApi.Add(v0, v1)
140	px = c.baseApi.DivUnchecked(px, c.baseApi.Add(1, v2))
141
142	// y = (u + a * v0 - v1) / (1 - v2)
143	py = c.baseApi.Mul(c.a, v0)
144	py = c.baseApi.Sub(py, v1)
145	py = c.baseApi.Add(py, u)
146	py = c.baseApi.DivUnchecked(py, c.baseApi.Sub(1, v2))
147
148	return AffinePoint[T]{
149		X: px.(emulated.Element[T]),
150		Y: py.(emulated.Element[T]),
151	}
152}
153
154func (c *Curve[T, S]) Double(p AffinePoint[T]) AffinePoint[T] {
155	u := c.baseApi.Mul(p.X, p.Y)
156	v := c.baseApi.Mul(p.X, p.X)
157	w := c.baseApi.Mul(p.Y, p.Y)
158
159	n1 := c.baseApi.Add(u, u)
160	av := c.baseApi.Mul(v, c.a)
161	n2 := c.baseApi.Sub(w, av)
162	d1 := c.baseApi.Add(w, av)
163	d2 := c.baseApi.Sub(2, d1)
164
165	px := c.baseApi.DivUnchecked(n1, d1)
166	py := c.baseApi.DivUnchecked(n2, d2)
167
168	return AffinePoint[T]{
169		X: px.(emulated.Element[T]),
170		Y: py.(emulated.Element[T]),
171	}
172}
173
174func (c *Curve[T, S]) Select(b frontend.Variable, p, q AffinePoint[T]) AffinePoint[T] {
175	x := c.baseApi.Select(b, p.X, q.X)
176	y := c.baseApi.Select(b, p.Y, q.Y)
177	return AffinePoint[T]{
178		X: x.(emulated.Element[T]),
179		Y: y.(emulated.Element[T]),
180	}
181}
182
183func (c *Curve[T, S]) ScalarMul(p AffinePoint[T], s emulated.Element[S]) AffinePoint[T] {
184	return c.ScalarMulBinary(p, c.scalarApi.ToBinary(s))
185}
186
187func (c *Curve[T, S]) ScalarMulBinary(p AffinePoint[T], sBits []frontend.Variable) AffinePoint[T] {
188	res := AffinePoint[T]{
189		X: emulated.NewElement[T](0),
190		Y: emulated.NewElement[T](1),
191	}
192	acc := p
193
194	for i := 0; i < len(sBits); i++ {
195		tmp := c.Add(res, acc)
196		res = c.Select(sBits[i], tmp, res)
197		acc = c.Double(acc)
198	}
199
200	return res
201}