123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434 |
- // Copyright 2020 The go-ethereum Authors
- // This file is part of the go-ethereum library.
- //
- // The go-ethereum library is free software: you can redistribute it and/or modify
- // it under the terms of the GNU Lesser General Public License as published by
- // the Free Software Foundation, either version 3 of the License, or
- // (at your option) any later version.
- //
- // The go-ethereum library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU Lesser General Public License for more details.
- //
- // You should have received a copy of the GNU Lesser General Public License
- // along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
- package bls12381
- import (
- "errors"
- "math"
- "math/big"
- )
- // PointG1 is type for point in G1.
- // PointG1 is both used for Affine and Jacobian point representation.
- // If z is equal to one the point is considered as in affine form.
- type PointG1 [3]fe
- func (p *PointG1) Set(p2 *PointG1) *PointG1 {
- p[0].set(&p2[0])
- p[1].set(&p2[1])
- p[2].set(&p2[2])
- return p
- }
- // Zero returns G1 point in point at infinity representation
- func (p *PointG1) Zero() *PointG1 {
- p[0].zero()
- p[1].one()
- p[2].zero()
- return p
- }
- type tempG1 struct {
- t [9]*fe
- }
- // G1 is struct for G1 group.
- type G1 struct {
- tempG1
- }
- // NewG1 constructs a new G1 instance.
- func NewG1() *G1 {
- t := newTempG1()
- return &G1{t}
- }
- func newTempG1() tempG1 {
- t := [9]*fe{}
- for i := 0; i < 9; i++ {
- t[i] = &fe{}
- }
- return tempG1{t}
- }
- // Q returns group order in big.Int.
- func (g *G1) Q() *big.Int {
- return new(big.Int).Set(q)
- }
- func (g *G1) fromBytesUnchecked(in []byte) (*PointG1, error) {
- p0, err := fromBytes(in[:48])
- if err != nil {
- return nil, err
- }
- p1, err := fromBytes(in[48:])
- if err != nil {
- return nil, err
- }
- p2 := new(fe).one()
- return &PointG1{*p0, *p1, *p2}, nil
- }
- // FromBytes constructs a new point given uncompressed byte input.
- // FromBytes does not take zcash flags into account.
- // Byte input expected to be larger than 96 bytes.
- // First 96 bytes should be concatenation of x and y values.
- // Point (0, 0) is considered as infinity.
- func (g *G1) FromBytes(in []byte) (*PointG1, error) {
- if len(in) != 96 {
- return nil, errors.New("input string should be equal or larger than 96")
- }
- p0, err := fromBytes(in[:48])
- if err != nil {
- return nil, err
- }
- p1, err := fromBytes(in[48:])
- if err != nil {
- return nil, err
- }
- // check if given input points to infinity
- if p0.isZero() && p1.isZero() {
- return g.Zero(), nil
- }
- p2 := new(fe).one()
- p := &PointG1{*p0, *p1, *p2}
- if !g.IsOnCurve(p) {
- return nil, errors.New("point is not on curve")
- }
- return p, nil
- }
- // DecodePoint given encoded (x, y) coordinates in 128 bytes returns a valid G1 Point.
- func (g *G1) DecodePoint(in []byte) (*PointG1, error) {
- if len(in) != 128 {
- return nil, errors.New("invalid g1 point length")
- }
- pointBytes := make([]byte, 96)
- // decode x
- xBytes, err := decodeFieldElement(in[:64])
- if err != nil {
- return nil, err
- }
- // decode y
- yBytes, err := decodeFieldElement(in[64:])
- if err != nil {
- return nil, err
- }
- copy(pointBytes[:48], xBytes)
- copy(pointBytes[48:], yBytes)
- return g.FromBytes(pointBytes)
- }
- // ToBytes serializes a point into bytes in uncompressed form.
- // ToBytes does not take zcash flags into account.
- // ToBytes returns (0, 0) if point is infinity.
- func (g *G1) ToBytes(p *PointG1) []byte {
- out := make([]byte, 96)
- if g.IsZero(p) {
- return out
- }
- g.Affine(p)
- copy(out[:48], toBytes(&p[0]))
- copy(out[48:], toBytes(&p[1]))
- return out
- }
- // EncodePoint encodes a point into 128 bytes.
- func (g *G1) EncodePoint(p *PointG1) []byte {
- outRaw := g.ToBytes(p)
- out := make([]byte, 128)
- // encode x
- copy(out[16:], outRaw[:48])
- // encode y
- copy(out[64+16:], outRaw[48:])
- return out
- }
- // New creates a new G1 Point which is equal to zero in other words point at infinity.
- func (g *G1) New() *PointG1 {
- return g.Zero()
- }
- // Zero returns a new G1 Point which is equal to point at infinity.
- func (g *G1) Zero() *PointG1 {
- return new(PointG1).Zero()
- }
- // One returns a new G1 Point which is equal to generator point.
- func (g *G1) One() *PointG1 {
- p := &PointG1{}
- return p.Set(&g1One)
- }
- // IsZero returns true if given point is equal to zero.
- func (g *G1) IsZero(p *PointG1) bool {
- return p[2].isZero()
- }
- // Equal checks if given two G1 point is equal in their affine form.
- func (g *G1) Equal(p1, p2 *PointG1) bool {
- if g.IsZero(p1) {
- return g.IsZero(p2)
- }
- if g.IsZero(p2) {
- return g.IsZero(p1)
- }
- t := g.t
- square(t[0], &p1[2])
- square(t[1], &p2[2])
- mul(t[2], t[0], &p2[0])
- mul(t[3], t[1], &p1[0])
- mul(t[0], t[0], &p1[2])
- mul(t[1], t[1], &p2[2])
- mul(t[1], t[1], &p1[1])
- mul(t[0], t[0], &p2[1])
- return t[0].equal(t[1]) && t[2].equal(t[3])
- }
- // InCorrectSubgroup checks whether given point is in correct subgroup.
- func (g *G1) InCorrectSubgroup(p *PointG1) bool {
- tmp := &PointG1{}
- g.MulScalar(tmp, p, q)
- return g.IsZero(tmp)
- }
- // IsOnCurve checks a G1 point is on curve.
- func (g *G1) IsOnCurve(p *PointG1) bool {
- if g.IsZero(p) {
- return true
- }
- t := g.t
- square(t[0], &p[1])
- square(t[1], &p[0])
- mul(t[1], t[1], &p[0])
- square(t[2], &p[2])
- square(t[3], t[2])
- mul(t[2], t[2], t[3])
- mul(t[2], b, t[2])
- add(t[1], t[1], t[2])
- return t[0].equal(t[1])
- }
- // IsAffine checks a G1 point whether it is in affine form.
- func (g *G1) IsAffine(p *PointG1) bool {
- return p[2].isOne()
- }
- // Add adds two G1 points p1, p2 and assigns the result to point at first argument.
- func (g *G1) Affine(p *PointG1) *PointG1 {
- if g.IsZero(p) {
- return p
- }
- if !g.IsAffine(p) {
- t := g.t
- inverse(t[0], &p[2])
- square(t[1], t[0])
- mul(&p[0], &p[0], t[1])
- mul(t[0], t[0], t[1])
- mul(&p[1], &p[1], t[0])
- p[2].one()
- }
- return p
- }
- // Add adds two G1 points p1, p2 and assigns the result to point at first argument.
- func (g *G1) Add(r, p1, p2 *PointG1) *PointG1 {
- // http://www.hyperelliptic.org/EFD/gp/auto-shortw-jacobian-0.html#addition-add-2007-bl
- if g.IsZero(p1) {
- return r.Set(p2)
- }
- if g.IsZero(p2) {
- return r.Set(p1)
- }
- t := g.t
- square(t[7], &p1[2])
- mul(t[1], &p2[0], t[7])
- mul(t[2], &p1[2], t[7])
- mul(t[0], &p2[1], t[2])
- square(t[8], &p2[2])
- mul(t[3], &p1[0], t[8])
- mul(t[4], &p2[2], t[8])
- mul(t[2], &p1[1], t[4])
- if t[1].equal(t[3]) {
- if t[0].equal(t[2]) {
- return g.Double(r, p1)
- }
- return r.Zero()
- }
- sub(t[1], t[1], t[3])
- double(t[4], t[1])
- square(t[4], t[4])
- mul(t[5], t[1], t[4])
- sub(t[0], t[0], t[2])
- double(t[0], t[0])
- square(t[6], t[0])
- sub(t[6], t[6], t[5])
- mul(t[3], t[3], t[4])
- double(t[4], t[3])
- sub(&r[0], t[6], t[4])
- sub(t[4], t[3], &r[0])
- mul(t[6], t[2], t[5])
- double(t[6], t[6])
- mul(t[0], t[0], t[4])
- sub(&r[1], t[0], t[6])
- add(t[0], &p1[2], &p2[2])
- square(t[0], t[0])
- sub(t[0], t[0], t[7])
- sub(t[0], t[0], t[8])
- mul(&r[2], t[0], t[1])
- return r
- }
- // Double doubles a G1 point p and assigns the result to the point at first argument.
- func (g *G1) Double(r, p *PointG1) *PointG1 {
- // http://www.hyperelliptic.org/EFD/gp/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
- if g.IsZero(p) {
- return r.Set(p)
- }
- t := g.t
- square(t[0], &p[0])
- square(t[1], &p[1])
- square(t[2], t[1])
- add(t[1], &p[0], t[1])
- square(t[1], t[1])
- sub(t[1], t[1], t[0])
- sub(t[1], t[1], t[2])
- double(t[1], t[1])
- double(t[3], t[0])
- add(t[0], t[3], t[0])
- square(t[4], t[0])
- double(t[3], t[1])
- sub(&r[0], t[4], t[3])
- sub(t[1], t[1], &r[0])
- double(t[2], t[2])
- double(t[2], t[2])
- double(t[2], t[2])
- mul(t[0], t[0], t[1])
- sub(t[1], t[0], t[2])
- mul(t[0], &p[1], &p[2])
- r[1].set(t[1])
- double(&r[2], t[0])
- return r
- }
- // Neg negates a G1 point p and assigns the result to the point at first argument.
- func (g *G1) Neg(r, p *PointG1) *PointG1 {
- r[0].set(&p[0])
- r[2].set(&p[2])
- neg(&r[1], &p[1])
- return r
- }
- // Sub subtracts two G1 points p1, p2 and assigns the result to point at first argument.
- func (g *G1) Sub(c, a, b *PointG1) *PointG1 {
- d := &PointG1{}
- g.Neg(d, b)
- g.Add(c, a, d)
- return c
- }
- // MulScalar multiplies a point by given scalar value in big.Int and assigns the result to point at first argument.
- func (g *G1) MulScalar(c, p *PointG1, e *big.Int) *PointG1 {
- q, n := &PointG1{}, &PointG1{}
- n.Set(p)
- l := e.BitLen()
- for i := 0; i < l; i++ {
- if e.Bit(i) == 1 {
- g.Add(q, q, n)
- }
- g.Double(n, n)
- }
- return c.Set(q)
- }
- // ClearCofactor maps given a G1 point to correct subgroup
- func (g *G1) ClearCofactor(p *PointG1) {
- g.MulScalar(p, p, cofactorEFFG1)
- }
- // MultiExp calculates multi exponentiation. Given pairs of G1 point and scalar values
- // (P_0, e_0), (P_1, e_1), ... (P_n, e_n) calculates r = e_0 * P_0 + e_1 * P_1 + ... + e_n * P_n
- // Length of points and scalars are expected to be equal, otherwise an error is returned.
- // Result is assigned to point at first argument.
- func (g *G1) MultiExp(r *PointG1, points []*PointG1, powers []*big.Int) (*PointG1, error) {
- if len(points) != len(powers) {
- return nil, errors.New("point and scalar vectors should be in same length")
- }
- var c uint32 = 3
- if len(powers) >= 32 {
- c = uint32(math.Ceil(math.Log10(float64(len(powers)))))
- }
- bucketSize, numBits := (1<<c)-1, uint32(g.Q().BitLen())
- windows := make([]*PointG1, numBits/c+1)
- bucket := make([]*PointG1, bucketSize)
- acc, sum := g.New(), g.New()
- for i := 0; i < bucketSize; i++ {
- bucket[i] = g.New()
- }
- mask := (uint64(1) << c) - 1
- j := 0
- var cur uint32
- for cur <= numBits {
- acc.Zero()
- bucket = make([]*PointG1, (1<<c)-1)
- for i := 0; i < len(bucket); i++ {
- bucket[i] = g.New()
- }
- for i := 0; i < len(powers); i++ {
- s0 := powers[i].Uint64()
- index := uint(s0 & mask)
- if index != 0 {
- g.Add(bucket[index-1], bucket[index-1], points[i])
- }
- powers[i] = new(big.Int).Rsh(powers[i], uint(c))
- }
- sum.Zero()
- for i := len(bucket) - 1; i >= 0; i-- {
- g.Add(sum, sum, bucket[i])
- g.Add(acc, acc, sum)
- }
- windows[j] = g.New()
- windows[j].Set(acc)
- j++
- cur += c
- }
- acc.Zero()
- for i := len(windows) - 1; i >= 0; i-- {
- for j := uint32(0); j < c; j++ {
- g.Double(acc, acc)
- }
- g.Add(acc, acc, windows[i])
- }
- return r.Set(acc), nil
- }
- // MapToCurve given a byte slice returns a valid G1 point.
- // This mapping function implements the Simplified Shallue-van de Woestijne-Ulas method.
- // https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06
- // Input byte slice should be a valid field element, otherwise an error is returned.
- func (g *G1) MapToCurve(in []byte) (*PointG1, error) {
- u, err := fromBytes(in)
- if err != nil {
- return nil, err
- }
- x, y := swuMapG1(u)
- isogenyMapG1(x, y)
- one := new(fe).one()
- p := &PointG1{*x, *y, *one}
- g.ClearCofactor(p)
- return g.Affine(p), nil
- }
|