g1.go

package bls12381

import (
	"fmt"
	"io"
	"math/big"

	"github.com/pkg/errors"

	"github.com/coinbase/kryptology/internal"
	"github.com/coinbase/kryptology/pkg/core/curves/native"
)

var (
	g1x = fp{
		0x5cb38790fd530c16,
		0x7817fc679976fff5,
		0x154f95c7143ba1c1,
		0xf0ae6acdf3d0e747,
		0xedce6ecc21dbf440,
		0x120177419e0bfb75,
	}
	g1y = fp{
		0xbaac93d50ce72271,
		0x8c22631a7918fd8e,
		0xdd595f13570725ce,
		0x51ac582950405194,
		0x0e1c8c3fad0059c0,
		0x0bbc3efc5008a26a,
	}
	curveG1B = fp{
		0xaa270000000cfff3,
		0x53cc0032fc34000a,
		0x478fe97a6b0a807f,
		0xb1d37ebee6ba24d7,
		0x8ec9733bbf78ab2f,
		0x09d645513d83de7e,
	}
	osswuMapA = fp{
		0x2f65aa0e9af5aa51,
		0x86464c2d1e8416c3,
		0xb85ce591b7bd31e2,
		0x27e11c91b5f24e7c,
		0x28376eda6bfc1835,
		0x155455c3e5071d85,
	}
	osswuMapB = fp{
		0xfb996971fe22a1e0,
		0x9aa93eb35b742d6f,
		0x8c476013de99c5c4,
		0x873e27c3a221e571,
		0xca72b5e45a52d888,
		0x06824061418a386b,
	}
	osswuMapC1 = fp{
		0xee7fbfffffffeaaa,
		0x07aaffffac54ffff,
		0xd9cc34a83dac3d89,
		0xd91dd2e13ce144af,
		0x92c6e9ed90d2eb35,
		0x0680447a8e5ff9a6,
	}
	osswuMapC2 = fp{
		0x43b571cad3215f1f,
		0xccb460ef1c702dc2,
		0x742d884f4f97100b,
		0xdb2c3e3238a3382b,
		0xe40f3fa13fce8f88,
		0x0073a2af9892a2ff,
	}
	oswwuMapZ = fp{
		0x886c00000023ffdc,
		0x0f70008d3090001d,
		0x77672417ed5828c3,
		0x9dac23e943dc1740,
		0x50553f1b9c131521,
		0x078c712fbe0ab6e8,
	}
	oswwuMapXd1  = *((&fp{}).Mul(&oswwuMapZ, &osswuMapA))
	negOsswuMapA = *(&fp{}).Neg(&osswuMapA)

	g1IsoXNum = []fp{
		{
			0x4d18b6f3af00131c,
			0x19fa219793fee28c,
			0x3f2885f1467f19ae,
			0x23dcea34f2ffb304,
			0xd15b58d2ffc00054,
			0x0913be200a20bef4,
		},
		{
			0x898985385cdbbd8b,
			0x3c79e43cc7d966aa,
			0x1597e193f4cd233a,
			0x8637ef1e4d6623ad,
			0x11b22deed20d827b,
			0x07097bc5998784ad,
		},
		{
			0xa542583a480b664b,
			0xfc7169c026e568c6,
			0x5ba2ef314ed8b5a6,
			0x5b5491c05102f0e7,
			0xdf6e99707d2a0079,
			0x0784151ed7605524,
		},
		{
			0x494e212870f72741,
			0xab9be52fbda43021,
			0x26f5577994e34c3d,
			0x049dfee82aefbd60,
			0x65dadd7828505289,
			0x0e93d431ea011aeb,
		},
		{
			0x90ee774bd6a74d45,
			0x7ada1c8a41bfb185,
			0x0f1a8953b325f464,
			0x104c24211be4805c,
			0x169139d319ea7a8f,
			0x09f20ead8e532bf6,
		},
		{
			0x6ddd93e2f43626b7,
			0xa5482c9aa1ccd7bd,
			0x143245631883f4bd,
			0x2e0a94ccf77ec0db,
			0xb0282d480e56489f,
			0x18f4bfcbb4368929,
		},
		{
			0x23c5f0c953402dfd,
			0x7a43ff6958ce4fe9,
			0x2c390d3d2da5df63,
			0xd0df5c98e1f9d70f,
			0xffd89869a572b297,
			0x1277ffc72f25e8fe,
		},
		{
			0x79f4f0490f06a8a6,
			0x85f894a88030fd81,
			0x12da3054b18b6410,
			0xe2a57f6505880d65,
			0xbba074f260e400f1,
			0x08b76279f621d028,
		},
		{
			0xe67245ba78d5b00b,
			0x8456ba9a1f186475,
			0x7888bff6e6b33bb4,
			0xe21585b9a30f86cb,
			0x05a69cdcef55feee,
			0x09e699dd9adfa5ac,
		},
		{
			0x0de5c357bff57107,
			0x0a0db4ae6b1a10b2,
			0xe256bb67b3b3cd8d,
			0x8ad456574e9db24f,
			0x0443915f50fd4179,
			0x098c4bf7de8b6375,
		},
		{
			0xe6b0617e7dd929c7,
			0xfe6e37d442537375,
			0x1dafdeda137a489e,
			0xe4efd1ad3f767ceb,
			0x4a51d8667f0fe1cf,
			0x054fdf4bbf1d821c,
		},
		{
			0x72db2a50658d767b,
			0x8abf91faa257b3d5,
			0xe969d6833764ab47,
			0x464170142a1009eb,
			0xb14f01aadb30be2f,
			0x18ae6a856f40715d,
		},
	}
	g1IsoXDen = []fp{
		{
			0xb962a077fdb0f945,
			0xa6a9740fefda13a0,
			0xc14d568c3ed6c544,
			0xb43fc37b908b133e,
			0x9c0b3ac929599016,
			0x0165aa6c93ad115f,
		},
		{
			0x23279a3ba506c1d9,
			0x92cfca0a9465176a,
			0x3b294ab13755f0ff,
			0x116dda1c5070ae93,
			0xed4530924cec2045,
			0x083383d6ed81f1ce,
		},
		{
			0x9885c2a6449fecfc,
			0x4a2b54ccd37733f0,
			0x17da9ffd8738c142,
			0xa0fba72732b3fafd,
			0xff364f36e54b6812,
			0x0f29c13c660523e2,
		},
		{
			0xe349cc118278f041,
			0xd487228f2f3204fb,
			0xc9d325849ade5150,
			0x43a92bd69c15c2df,
			0x1c2c7844bc417be4,
			0x12025184f407440c,
		},
		{
			0x587f65ae6acb057b,
			0x1444ef325140201f,
			0xfbf995e71270da49,
			0xccda066072436a42,
			0x7408904f0f186bb2,
			0x13b93c63edf6c015,
		},
		{
			0xfb918622cd141920,
			0x4a4c64423ecaddb4,
			0x0beb232927f7fb26,
			0x30f94df6f83a3dc2,
			0xaeedd424d780f388,
			0x06cc402dd594bbeb,
		},
		{
			0xd41f761151b23f8f,
			0x32a92465435719b3,
			0x64f436e888c62cb9,
			0xdf70a9a1f757c6e4,
			0x6933a38d5b594c81,
			0x0c6f7f7237b46606,
		},
		{
			0x693c08747876c8f7,
			0x22c9850bf9cf80f0,
			0x8e9071dab950c124,
			0x89bc62d61c7baf23,
			0xbc6be2d8dad57c23,
			0x17916987aa14a122,
		},
		{
			0x1be3ff439c1316fd,
			0x9965243a7571dfa7,
			0xc7f7f62962f5cd81,
			0x32c6aa9af394361c,
			0xbbc2ee18e1c227f4,
			0x0c102cbac531bb34,
		},
		{
			0x997614c97bacbf07,
			0x61f86372b99192c0,
			0x5b8c95fc14353fc3,
			0xca2b066c2a87492f,
			0x16178f5bbf698711,
			0x12a6dcd7f0f4e0e8,
		},
		{
			0x760900000002fffd,
			0xebf4000bc40c0002,
			0x5f48985753c758ba,
			0x77ce585370525745,
			0x5c071a97a256ec6d,
			0x15f65ec3fa80e493,
		},
	}
	g1IsoYNum = []fp{
		{
			0x2b567ff3e2837267,
			0x1d4d9e57b958a767,
			0xce028fea04bd7373,
			0xcc31a30a0b6cd3df,
			0x7d7b18a682692693,
			0x0d300744d42a0310,
		},
		{
			0x99c2555fa542493f,
			0xfe7f53cc4874f878,
			0x5df0608b8f97608a,
			0x14e03832052b49c8,
			0x706326a6957dd5a4,
			0x0a8dadd9c2414555,
		},
		{
			0x13d942922a5cf63a,
			0x357e33e36e261e7d,
			0xcf05a27c8456088d,
			0x0000bd1de7ba50f0,
			0x83d0c7532f8c1fde,
			0x13f70bf38bbf2905,
		},
		{
			0x5c57fd95bfafbdbb,
			0x28a359a65e541707,
			0x3983ceb4f6360b6d,
			0xafe19ff6f97e6d53,
			0xb3468f4550192bf7,
			0x0bb6cde49d8ba257,
		},
		{
			0x590b62c7ff8a513f,
			0x314b4ce372cacefd,
			0x6bef32ce94b8a800,
			0x6ddf84a095713d5f,
			0x64eace4cb0982191,
			0x0386213c651b888d,
		},
		{
			0xa5310a31111bbcdd,
			0xa14ac0f5da148982,
			0xf9ad9cc95423d2e9,
			0xaa6ec095283ee4a7,
			0xcf5b1f022e1c9107,
			0x01fddf5aed881793,
		},
		{
			0x65a572b0d7a7d950,
			0xe25c2d8183473a19,
			0xc2fcebe7cb877dbd,
			0x05b2d36c769a89b0,
			0xba12961be86e9efb,
			0x07eb1b29c1dfde1f,
		},
		{
			0x93e09572f7c4cd24,
			0x364e929076795091,
			0x8569467e68af51b5,
			0xa47da89439f5340f,
			0xf4fa918082e44d64,
			0x0ad52ba3e6695a79,
		},
		{
			0x911429844e0d5f54,
			0xd03f51a3516bb233,
			0x3d587e5640536e66,
			0xfa86d2a3a9a73482,
			0xa90ed5adf1ed5537,
			0x149c9c326a5e7393,
		},
		{
			0x462bbeb03c12921a,
			0xdc9af5fa0a274a17,
			0x9a558ebde836ebed,
			0x649ef8f11a4fae46,
			0x8100e1652b3cdc62,
			0x1862bd62c291dacb,
		},
		{
			0x05c9b8ca89f12c26,
			0x0194160fa9b9ac4f,
			0x6a643d5a6879fa2c,
			0x14665bdd8846e19d,
			0xbb1d0d53af3ff6bf,
			0x12c7e1c3b28962e5,
		},
		{
			0xb55ebf900b8a3e17,
			0xfedc77ec1a9201c4,
			0x1f07db10ea1a4df4,
			0x0dfbd15dc41a594d,
			0x389547f2334a5391,
			0x02419f98165871a4,
		},
		{
			0xb416af000745fc20,
			0x8e563e9d1ea6d0f5,
			0x7c763e17763a0652,
			0x01458ef0159ebbef,
			0x8346fe421f96bb13,
			0x0d2d7b829ce324d2,
		},
		{
			0x93096bb538d64615,
			0x6f2a2619951d823a,
			0x8f66b3ea59514fa4,
			0xf563e63704f7092f,
			0x724b136c4cf2d9fa,
			0x046959cfcfd0bf49,
		},
		{
			0xea748d4b6e405346,
			0x91e9079c2c02d58f,
			0x41064965946d9b59,
			0xa06731f1d2bbe1ee,
			0x07f897e267a33f1b,
			0x1017290919210e5f,
		},
		{
			0x872aa6c17d985097,
			0xeecc53161264562a,
			0x07afe37afff55002,
			0x54759078e5be6838,
			0xc4b92d15db8acca8,
			0x106d87d1b51d13b9,
		},
	}
	g1IsoYDen = []fp{
		{
			0xeb6c359d47e52b1c,
			0x18ef5f8a10634d60,
			0xddfa71a0889d5b7e,
			0x723e71dcc5fc1323,
			0x52f45700b70d5c69,
			0x0a8b981ee47691f1,
		},
		{
			0x616a3c4f5535b9fb,
			0x6f5f037395dbd911,
			0xf25f4cc5e35c65da,
			0x3e50dffea3c62658,
			0x6a33dca523560776,
			0x0fadeff77b6bfe3e,
		},
		{
			0x2be9b66df470059c,
			0x24a2c159a3d36742,
			0x115dbe7ad10c2a37,
			0xb6634a652ee5884d,
			0x04fe8bb2b8d81af4,
			0x01c2a7a256fe9c41,
		},
		{
			0xf27bf8ef3b75a386,
			0x898b367476c9073f,
			0x24482e6b8c2f4e5f,
			0xc8e0bbd6fe110806,
			0x59b0c17f7631448a,
			0x11037cd58b3dbfbd,
		},
		{
			0x31c7912ea267eec6,
			0x1dbf6f1c5fcdb700,
			0xd30d4fe3ba86fdb1,
			0x3cae528fbee9a2a4,
			0xb1cce69b6aa9ad9a,
			0x044393bb632d94fb,
		},
		{
			0xc66ef6efeeb5c7e8,
			0x9824c289dd72bb55,
			0x71b1a4d2f119981d,
			0x104fc1aafb0919cc,
			0x0e49df01d942a628,
			0x096c3a09773272d4,
		},
		{
			0x9abc11eb5fadeff4,
			0x32dca50a885728f0,
			0xfb1fa3721569734c,
			0xc4b76271ea6506b3,
			0xd466a75599ce728e,
			0x0c81d4645f4cb6ed,
		},
		{
			0x4199f10e5b8be45b,
			0xda64e495b1e87930,
			0xcb353efe9b33e4ff,
			0x9e9efb24aa6424c6,
			0xf08d33680a237465,
			0x0d3378023e4c7406,
		},
		{
			0x7eb4ae92ec74d3a5,
			0xc341b4aa9fac3497,
			0x5be603899e907687,
			0x03bfd9cca75cbdeb,
			0x564c2935a96bfa93,
			0x0ef3c33371e2fdb5,
		},
		{
			0x7ee91fd449f6ac2e,
			0xe5d5bd5cb9357a30,
			0x773a8ca5196b1380,
			0xd0fda172174ed023,
			0x6cb95e0fa776aead,
			0x0d22d5a40cec7cff,
		},
		{
			0xf727e09285fd8519,
			0xdc9d55a83017897b,
			0x7549d8bd057894ae,
			0x178419613d90d8f8,
			0xfce95ebdeb5b490a,
			0x0467ffaef23fc49e,
		},
		{
			0xc1769e6a7c385f1b,
			0x79bc930deac01c03,
			0x5461c75a23ede3b5,
			0x6e20829e5c230c45,
			0x828e0f1e772a53cd,
			0x116aefa749127bff,
		},
		{
			0x101c10bf2744c10a,
			0xbbf18d053a6a3154,
			0xa0ecf39ef026f602,
			0xfc009d4996dc5153,
			0xb9000209d5bd08d3,
			0x189e5fe4470cd73c,
		},
		{
			0x7ebd546ca1575ed2,
			0xe47d5a981d081b55,
			0x57b2b625b6d4ca21,
			0xb0a1ba04228520cc,
			0x98738983c2107ff3,
			0x13dddbc4799d81d6,
		},
		{
			0x09319f2e39834935,
			0x039e952cbdb05c21,
			0x55ba77a9a2f76493,
			0xfd04e3dfc6086467,
			0xfb95832e7d78742e,
			0x0ef9c24eccaf5e0e,
		},
		{
			0x760900000002fffd,
			0xebf4000bc40c0002,
			0x5f48985753c758ba,
			0x77ce585370525745,
			0x5c071a97a256ec6d,
			0x15f65ec3fa80e493,
		},
	}
)

// G1 is a point in g1
type G1 struct {
	x, y, z fp
}

// Random creates a random point on the curve
// from the specified reader
func (g1 *G1) Random(reader io.Reader) (*G1, error) {
	var seed [native.WideFieldBytes]byte
	n, err := reader.Read(seed[:])

	if err != nil {
		return nil, errors.Wrap(err, "random could not read from stream")
	}
	if n != native.WideFieldBytes {
		return nil, fmt.Errorf("insufficient bytes read %d when %d are needed", n, WideFieldBytes)
	}
	dst := []byte("BLS12381G1_XMD:SHA-256_SSWU_RO_")
	return g1.Hash(native.EllipticPointHasherSha256(), seed[:], dst), nil
}

// Hash uses the hasher to map bytes to a valid point
func (g1 *G1) Hash(hash *native.EllipticPointHasher, msg, dst []byte) *G1 {
	var u []byte
	var u0, u1 fp
	var r0, r1, q0, q1 G1

	switch hash.Type() {
	case native.XMD:
		u = native.ExpandMsgXmd(hash, msg, dst, 128)
	case native.XOF:
		u = native.ExpandMsgXof(hash, msg, dst, 128)
	}

	var buf [WideFieldBytes]byte
	copy(buf[:64], internal.ReverseScalarBytes(u[:64]))
	u0.SetBytesWide(&buf)
	copy(buf[:64], internal.ReverseScalarBytes(u[64:]))
	u1.SetBytesWide(&buf)

	r0.osswu3mod4(&u0)
	r1.osswu3mod4(&u1)
	q0.isogenyMap(&r0)
	q1.isogenyMap(&r1)
	g1.Add(&q0, &q1)
	return g1.ClearCofactor(g1)
}

// Identity returns the identity point
func (g1 *G1) Identity() *G1 {
	g1.x.SetZero()
	g1.y.SetOne()
	g1.z.SetZero()
	return g1
}

// Generator returns the base point
func (g1 *G1) Generator() *G1 {
	g1.x.Set(&g1x)
	g1.y.Set(&g1y)
	g1.z.SetOne()
	return g1
}

// IsIdentity returns true if this point is at infinity
func (g1 *G1) IsIdentity() int {
	return g1.z.IsZero()
}

// IsOnCurve determines if this point represents a valid curve point
func (g1 *G1) IsOnCurve() int {
	// Y^2 Z = X^3 + b Z^3
	var lhs, rhs, t fp
	lhs.Square(&g1.y)
	lhs.Mul(&lhs, &g1.z)

	rhs.Square(&g1.x)
	rhs.Mul(&rhs, &g1.x)
	t.Square(&g1.z)
	t.Mul(&t, &g1.z)
	t.Mul(&t, &curveG1B)
	rhs.Add(&rhs, &t)

	return lhs.Equal(&rhs)
}

// InCorrectSubgroup returns 1 if the point is torsion free, 0 otherwise
func (g1 *G1) InCorrectSubgroup() int {
	var t G1
	t.multiply(g1, &fqModulusBytes)
	return t.IsIdentity()
}

// Add adds this point to another point.
func (g1 *G1) Add(arg1, arg2 *G1) *G1 {
	// Algorithm 7, https://eprint.iacr.org/2015/1060.pdf
	var t0, t1, t2, t3, t4, x3, y3, z3 fp

	t0.Mul(&arg1.x, &arg2.x)
	t1.Mul(&arg1.y, &arg2.y)
	t2.Mul(&arg1.z, &arg2.z)
	t3.Add(&arg1.x, &arg1.y)
	t4.Add(&arg2.x, &arg2.y)
	t3.Mul(&t3, &t4)
	t4.Add(&t0, &t1)
	t3.Sub(&t3, &t4)
	t4.Add(&arg1.y, &arg1.z)
	x3.Add(&arg2.y, &arg2.z)
	t4.Mul(&t4, &x3)
	x3.Add(&t1, &t2)
	t4.Sub(&t4, &x3)
	x3.Add(&arg1.x, &arg1.z)
	y3.Add(&arg2.x, &arg2.z)
	x3.Mul(&x3, &y3)
	y3.Add(&t0, &t2)
	y3.Sub(&x3, &y3)
	x3.Double(&t0)
	t0.Add(&t0, &x3)
	t2.MulBy3b(&t2)
	z3.Add(&t1, &t2)
	t1.Sub(&t1, &t2)
	y3.MulBy3b(&y3)
	x3.Mul(&t4, &y3)
	t2.Mul(&t3, &t1)
	x3.Sub(&t2, &x3)
	y3.Mul(&y3, &t0)
	t1.Mul(&t1, &z3)
	y3.Add(&t1, &y3)
	t0.Mul(&t0, &t3)
	z3.Mul(&z3, &t4)
	z3.Add(&z3, &t0)

	g1.x.Set(&x3)
	g1.y.Set(&y3)
	g1.z.Set(&z3)
	return g1
}

// Sub subtracts the two points
func (g1 *G1) Sub(arg1, arg2 *G1) *G1 {
	var t G1
	t.Neg(arg2)
	return g1.Add(arg1, &t)
}

// Double this point
func (g1 *G1) Double(a *G1) *G1 {
	// Algorithm 9, https://eprint.iacr.org/2015/1060.pdf
	var t0, t1, t2, x3, y3, z3 fp

	t0.Square(&a.y)
	z3.Double(&t0)
	z3.Double(&z3)
	z3.Double(&z3)
	t1.Mul(&a.y, &a.z)
	t2.Square(&a.z)
	t2.MulBy3b(&t2)
	x3.Mul(&t2, &z3)
	y3.Add(&t0, &t2)
	z3.Mul(&t1, &z3)
	t1.Double(&t2)
	t2.Add(&t2, &t1)
	t0.Sub(&t0, &t2)
	y3.Mul(&t0, &y3)
	y3.Add(&y3, &x3)
	t1.Mul(&a.x, &a.y)
	x3.Mul(&t0, &t1)
	x3.Double(&x3)

	e := a.IsIdentity()
	g1.x.CMove(&x3, t0.SetZero(), e)
	g1.z.CMove(&z3, &t0, e)
	g1.y.CMove(&y3, t0.SetOne(), e)
	return g1
}

// Mul multiplies this point by the input scalar
func (g1 *G1) Mul(a *G1, s *native.Field) *G1 {
	bytes := s.Bytes()
	return g1.multiply(a, &bytes)
}

func (g1 *G1) multiply(a *G1, bytes *[native.FieldBytes]byte) *G1 {
	var p G1
	precomputed := [16]*G1{}
	precomputed[0] = new(G1).Identity()
	precomputed[1] = new(G1).Set(a)
	for i := 2; i < 16; i += 2 {
		precomputed[i] = new(G1).Double(precomputed[i>>1])
		precomputed[i+1] = new(G1).Add(precomputed[i], a)
	}
	p.Identity()
	for i := 0; i < 256; i += 4 {
		// Brouwer / windowing method. window size of 4.
		for j := 0; j < 4; j++ {
			p.Double(&p)
		}
		window := bytes[32-1-i>>3] >> (4 - i&0x04) & 0x0F
		p.Add(&p, precomputed[window])
	}
	return g1.Set(&p)
}

// MulByX multiplies by BLS X using double and add
func (g1 *G1) MulByX(a *G1) *G1 {
	// Skip first bit since its always zero
	var s, t, r G1
	r.Identity()
	t.Set(a)

	for x := paramX >> 1; x != 0; x >>= 1 {
		t.Double(&t)
		s.Add(&r, &t)
		r.CMove(&r, &s, int(x&1))
	}
	// Since BLS_X is negative, flip the sign
	return g1.Neg(&r)
}

// ClearCofactor multiplies by (1 - z), where z is the parameter of BLS12-381, which
// [suffices to clear](https://ia.cr/2019/403) the cofactor and map
// elliptic curve points to elements of G1.
func (g1 *G1) ClearCofactor(a *G1) *G1 {
	var t G1
	t.MulByX(a)
	return g1.Sub(a, &t)
}

// Neg negates this point
func (g1 *G1) Neg(a *G1) *G1 {
	g1.Set(a)
	g1.y.CNeg(&a.y, -(a.IsIdentity() - 1))
	return g1
}

// Set copies a into g1
func (g1 *G1) Set(a *G1) *G1 {
	g1.x.Set(&a.x)
	g1.y.Set(&a.y)
	g1.z.Set(&a.z)
	return g1
}

// BigInt returns the x and y as big.Ints in affine
func (g1 *G1) BigInt() (x, y *big.Int) {
	var t G1
	t.ToAffine(g1)
	x = t.x.BigInt()
	y = t.y.BigInt()
	return
}

// SetBigInt creates a point from affine x, y
// and returns the point if it is on the curve
func (g1 *G1) SetBigInt(x, y *big.Int) (*G1, error) {
	var xx, yy fp
	var pp G1
	pp.x = *(xx.SetBigInt(x))
	pp.y = *(yy.SetBigInt(y))

	if pp.x.IsZero()&pp.y.IsZero() == 1 {
		pp.Identity()
		return g1.Set(&pp), nil
	}

	pp.z.SetOne()

	// If not the identity point and not on the curve then invalid
	if (pp.IsOnCurve()&pp.InCorrectSubgroup())|(xx.IsZero()&yy.IsZero()) == 0 {
		return nil, fmt.Errorf("invalid coordinates")
	}
	return g1.Set(&pp), nil
}

// ToCompressed serializes this element into compressed form.
func (g1 *G1) ToCompressed() [FieldBytes]byte {
	var out [FieldBytes]byte
	var t G1
	t.ToAffine(g1)
	xBytes := t.x.Bytes()
	copy(out[:], internal.ReverseScalarBytes(xBytes[:]))
	isInfinity := byte(g1.IsIdentity())
	// Compressed flag
	out[0] |= 1 << 7
	// Is infinity
	out[0] |= (1 << 6) & -isInfinity
	// Sign of y only set if not infinity
	out[0] |= (byte(t.y.LexicographicallyLargest()) << 5) & (isInfinity - 1)
	return out
}

// FromCompressed deserializes this element from compressed form.
func (g1 *G1) FromCompressed(input *[FieldBytes]byte) (*G1, error) {
	var xFp, yFp fp
	var x [FieldBytes]byte
	var p G1
	compressedFlag := int((input[0] >> 7) & 1)
	infinityFlag := int((input[0] >> 6) & 1)
	sortFlag := int((input[0] >> 5) & 1)

	if compressedFlag != 1 {
		return nil, errors.New("compressed flag must be set")
	}

	if infinityFlag == 1 {
		return g1.Identity(), nil
	}

	copy(x[:], internal.ReverseScalarBytes(input[:]))
	// Mask away the flag bits
	x[FieldBytes-1] &= 0x1F
	_, valid := xFp.SetBytes(&x)

	if valid != 1 {
		return nil, errors.New("invalid bytes - not in field")
	}

	yFp.Square(&xFp)
	yFp.Mul(&yFp, &xFp)
	yFp.Add(&yFp, &curveG1B)

	_, wasSquare := yFp.Sqrt(&yFp)
	if wasSquare != 1 {
		return nil, errors.New("point is not on the curve")
	}

	yFp.CNeg(&yFp, yFp.LexicographicallyLargest()^sortFlag)
	p.x.Set(&xFp)
	p.y.Set(&yFp)
	p.z.SetOne()
	if p.InCorrectSubgroup() == 0 {
		return nil, errors.New("point is not in correct subgroup")
	}
	return g1.Set(&p), nil
}

// ToUncompressed serializes this element into uncompressed form.
func (g1 *G1) ToUncompressed() [WideFieldBytes]byte {
	var out [WideFieldBytes]byte
	var t G1
	t.ToAffine(g1)
	xBytes := t.x.Bytes()
	yBytes := t.y.Bytes()
	copy(out[:FieldBytes], internal.ReverseScalarBytes(xBytes[:]))
	copy(out[FieldBytes:], internal.ReverseScalarBytes(yBytes[:]))
	isInfinity := byte(g1.IsIdentity())
	out[0] |= (1 << 6) & -isInfinity
	return out
}

// FromUncompressed deserializes this element from uncompressed form.
func (g1 *G1) FromUncompressed(input *[WideFieldBytes]byte) (*G1, error) {
	var xFp, yFp fp
	var t [FieldBytes]byte
	var p G1
	infinityFlag := int((input[0] >> 6) & 1)

	if infinityFlag == 1 {
		return g1.Identity(), nil
	}

	copy(t[:], internal.ReverseScalarBytes(input[:FieldBytes]))
	// Mask away top bits
	t[FieldBytes-1] &= 0x1F

	_, valid := xFp.SetBytes(&t)
	if valid == 0 {
		return nil, errors.New("invalid bytes - x not in field")
	}
	copy(t[:], internal.ReverseScalarBytes(input[FieldBytes:]))
	_, valid = yFp.SetBytes(&t)
	if valid == 0 {
		return nil, errors.New("invalid bytes - y not in field")
	}

	p.x.Set(&xFp)
	p.y.Set(&yFp)
	p.z.SetOne()

	if p.IsOnCurve() == 0 {
		return nil, errors.New("point is not on the curve")
	}
	if p.InCorrectSubgroup() == 0 {
		return nil, errors.New("point is not in correct subgroup")
	}
	return g1.Set(&p), nil
}

// ToAffine converts the point into affine coordinates
func (g1 *G1) ToAffine(a *G1) *G1 {
	var wasInverted int
	var zero, x, y, z fp
	_, wasInverted = z.Invert(&a.z)
	x.Mul(&a.x, &z)
	y.Mul(&a.y, &z)

	g1.x.CMove(&zero, &x, wasInverted)
	g1.y.CMove(&zero, &y, wasInverted)
	g1.z.CMove(&zero, z.SetOne(), wasInverted)
	return g1
}

// GetX returns the affine X coordinate
func (g1 *G1) GetX() *fp {
	var t G1
	t.ToAffine(g1)
	return &t.x
}

// GetY returns the affine Y coordinate
func (g1 *G1) GetY() *fp {
	var t G1
	t.ToAffine(g1)
	return &t.y
}

// Equal returns 1 if the two points are equal 0 otherwise.
func (g1 *G1) Equal(rhs *G1) int {
	var x1, x2, y1, y2 fp
	var e1, e2 int

	// This technique avoids inversions
	x1.Mul(&g1.x, &rhs.z)
	x2.Mul(&rhs.x, &g1.z)

	y1.Mul(&g1.y, &rhs.z)
	y2.Mul(&rhs.y, &g1.z)

	e1 = g1.z.IsZero()
	e2 = rhs.z.IsZero()

	// Both at infinity or coordinates are the same
	return (e1 & e2) | (^e1 & ^e2)&x1.Equal(&x2)&y1.Equal(&y2)
}

// CMove sets g1 = arg1 if choice == 0 and g1 = arg2 if choice == 1
func (g1 *G1) CMove(arg1, arg2 *G1, choice int) *G1 {
	g1.x.CMove(&arg1.x, &arg2.x, choice)
	g1.y.CMove(&arg1.y, &arg2.y, choice)
	g1.z.CMove(&arg1.z, &arg2.z, choice)
	return g1
}

// SumOfProducts computes the multi-exponentiation for the specified
// points and scalars and stores the result in `g1`.
// Returns an error if the lengths of the arguments is not equal.
func (g1 *G1) SumOfProducts(points []*G1, scalars []*native.Field) (*G1, error) {
	const Upper = 256
	const W = 4
	const Windows = Upper / W // careful--use ceiling division in case this doesn't divide evenly
	var sum G1
	if len(points) != len(scalars) {
		return nil, fmt.Errorf("length mismatch")
	}

	bucketSize := 1 << W
	windows := make([]G1, Windows)
	bytes := make([][32]byte, len(scalars))
	buckets := make([]G1, bucketSize)

	for i := 0; i < len(windows); i++ {
		windows[i].Identity()
	}

	for i, scalar := range scalars {
		bytes[i] = scalar.Bytes()
	}

	for j := 0; j < len(windows); j++ {
		for i := 0; i < bucketSize; i++ {
			buckets[i].Identity()
		}

		for i := 0; i < len(scalars); i++ {
			// j*W to get the nibble
			// >> 3 to convert to byte, / 8
			// (W * j & W) gets the nibble, mod W
			// 1 << W - 1 to get the offset
			index := bytes[i][j*W>>3] >> (W * j & W) & (1<<W - 1) // little-endian
			buckets[index].Add(&buckets[index], points[i])
		}

		sum.Identity()

		for i := bucketSize - 1; i > 0; i-- {
			sum.Add(&sum, &buckets[i])
			windows[j].Add(&windows[j], &sum)
		}
	}

	g1.Identity()
	for i := len(windows) - 1; i >= 0; i-- {
		for j := 0; j < W; j++ {
			g1.Double(g1)
		}

		g1.Add(g1, &windows[i])
	}
	return g1, nil
}

func (g1 *G1) osswu3mod4(u *fp) *G1 {
	// Taken from section 8.8.1 in
	// <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html>
	var tv1, tv2, tv3, tv4, xd, x1n, x2n, gxd, gx1, y1, y2 fp

	// tv1 = u^2
	tv1.Square(u)
	// tv3 = Z * tv1
	tv3.Mul(&oswwuMapZ, &tv1)
	// tv2 = tv3^2
	tv2.Square(&tv3)
	// xd = tv2 + tv3
	xd.Add(&tv2, &tv3)
	// x1n = xd + 1
	x1n.Add(&xd, &r)
	// x1n = x1n * B
	x1n.Mul(&x1n, &osswuMapB)
	// xd = -A * xd
	xd.Mul(&negOsswuMapA, &xd)
	// xd = CMOV(xd, Z * A, xd == 0)
	xd.CMove(&xd, &oswwuMapXd1, xd.IsZero())
	// tv2 = xd^2
	tv2.Square(&xd)

	gxd.Mul(&tv2, &xd)
	tv2.Mul(&tv2, &osswuMapA)
	gx1.Square(&x1n)
	gx1.Add(&gx1, &tv2)
	gx1.Mul(&gx1, &x1n)
	tv2.Mul(&osswuMapB, &gxd)

	gx1.Add(&gx1, &tv2)
	tv4.Square(&gxd)
	tv2.Mul(&gx1, &gxd)
	tv4.Mul(&tv4, &tv2)
	y1.pow(&tv4, &osswuMapC1)
	y1.Mul(&y1, &tv2)

	x2n.Mul(&tv3, &x1n)
	y2.Mul(&y1, &osswuMapC2)
	y2.Mul(&y2, &tv1)
	y2.Mul(&y2, u)

	tv2.Square(&y1)
	tv2.Mul(&tv2, &gxd)
	e2 := tv2.Equal(&gx1)

	x2n.CMove(&x2n, &x1n, e2)
	y2.CMove(&y2, &y1, e2)

	e3 := u.Sgn0() ^ y2.Sgn0()
	y2.CNeg(&y2, e3)

	g1.z.SetOne()
	g1.y.Set(&y2)
	_, _ = g1.x.Invert(&xd)
	g1.x.Mul(&g1.x, &x2n)
	return g1
}

func (g1 *G1) isogenyMap(a *G1) *G1 {
	const Degree = 16
	var xs [Degree]fp
	xs[0] = r
	xs[1].Set(&a.x)
	xs[2].Square(&a.x)
	for i := 3; i < Degree; i++ {
		xs[i].Mul(&xs[i-1], &a.x)
	}

	xNum := computeKFp(xs[:], g1IsoXNum)
	xDen := computeKFp(xs[:], g1IsoXDen)
	yNum := computeKFp(xs[:], g1IsoYNum)
	yDen := computeKFp(xs[:], g1IsoYDen)

	g1.x.Invert(&xDen)
	g1.x.Mul(&g1.x, &xNum)

	g1.y.Invert(&yDen)
	g1.y.Mul(&g1.y, &yNum)
	g1.y.Mul(&g1.y, &a.y)
	g1.z.SetOne()
	return g1
}

func computeKFp(xxs []fp, k []fp) fp {
	var xx, t fp
	for i := range k {
		xx.Add(&xx, t.Mul(&xxs[i], &k[i]))
	}
	return xx
}