ristretto255.go

// Copyright 2019 The Go Authors. All rights reserved.
// Copyright 2019 George Tankersley. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package ristretto255 implements the group of prime order
//
//     2**252 + 27742317777372353535851937790883648493
//
// as specified in draft-hdevalence-cfrg-ristretto-01.
//
// All operations are constant time unless otherwise specified.
package ristretto255

import (
	"bytes"
	"encoding/base64"
	"errors"

	"filippo.io/edwards25519"
	"filippo.io/edwards25519/field"
)

// Constants from draft-hdevalence-cfrg-ristretto-01, Section 3.1. See
// TestConstants for their decimal values.
var (
	d, _ = new(field.Element).SetBytes([]byte{
		0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
		0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
		0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
		0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52,
	})
	sqrtM1, _ = new(field.Element).SetBytes([]byte{
		0xb0, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4,
		0x78, 0xe4, 0x2f, 0xad, 0x06, 0x18, 0x43, 0x2f,
		0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b,
		0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b,
	})
	sqrtADMinusOne, _ = new(field.Element).SetBytes([]byte{
		0x1b, 0x2e, 0x7b, 0x49, 0xa0, 0xf6, 0x97, 0x7e,
		0xbd, 0x54, 0x78, 0x1b, 0x0c, 0x8e, 0x9d, 0xaf,
		0xfd, 0xd1, 0xf5, 0x31, 0xc9, 0xfc, 0x3c, 0x0f,
		0xac, 0x48, 0x83, 0x2b, 0xbf, 0x31, 0x69, 0x37,
	})
	invSqrtAMinusD, _ = new(field.Element).SetBytes([]byte{
		0xea, 0x40, 0x5d, 0x80, 0xaa, 0xfd, 0xc8, 0x99,
		0xbe, 0x72, 0x41, 0x5a, 0x17, 0x16, 0x2f, 0x9d,
		0x40, 0xd8, 0x01, 0xfe, 0x91, 0x7b, 0xc2, 0x16,
		0xa2, 0xfc, 0xaf, 0xcf, 0x05, 0x89, 0x6c, 0x78,
	})
	oneMinusDSQ, _ = new(field.Element).SetBytes([]byte{
		0x76, 0xc1, 0x5f, 0x94, 0xc1, 0x09, 0x7c, 0xe2,
		0x0f, 0x35, 0x5e, 0xcd, 0x38, 0xa1, 0x81, 0x2c,
		0xe4, 0xdf, 0x70, 0xbe, 0xdd, 0xab, 0x94, 0x99,
		0xd7, 0xe0, 0xb3, 0xb2, 0xa8, 0x72, 0x90, 0x02,
	})
	dMinusOneSQ, _ = new(field.Element).SetBytes([]byte{
		0x20, 0x4d, 0xed, 0x44, 0xaa, 0x5a, 0xad, 0x31,
		0x99, 0x19, 0x1e, 0xb0, 0x2c, 0x4a, 0x9e, 0xd2,
		0xeb, 0x4e, 0x9b, 0x52, 0x2f, 0xd3, 0xdc, 0x4c,
		0x41, 0x22, 0x6c, 0xf6, 0x7a, 0xb3, 0x68, 0x59,
	})
)

var (
	zero     = new(field.Element)
	one      = new(field.Element).One()
	two      = new(field.Element).Add(one, one)
	minusOne = new(field.Element).Subtract(zero, one)
)

// Element is an element of the ristretto255 prime-order group.
type Element struct {
	r edwards25519.Point
}

// NewElement returns a new Element set to the identity value.
//
// Deprecated: use NewIdentityElement. This API will be removed before v1.0.0.
func NewElement() *Element {
	return NewIdentityElement()
}

// NewIdentityElement returns a new Element set to the identity value.
func NewIdentityElement() *Element {
	e := &Element{}
	e.r.Set(edwards25519.NewIdentityPoint())
	return e
}

// NewGeneratorElement returns a new Element set to the canonical generator.
func NewGeneratorElement() *Element {
	e := &Element{}
	e.r.Set(edwards25519.NewGeneratorPoint())
	return e
}

// Set sets the value of e to x and returns e.
func (e *Element) Set(x *Element) *Element {
	*e = *x
	return e
}

// Equal returns 1 if e is equivalent to ee, and 0 otherwise.
//
// Note that Elements must not be compared in any other way.
func (e *Element) Equal(ee *Element) int {
	X1, Y1, _, _ := e.r.ExtendedCoordinates()
	X2, Y2, _, _ := ee.r.ExtendedCoordinates()

	var f0, f1 field.Element

	f0.Multiply(X1, Y2) // x1 * y2
	f1.Multiply(Y1, X2) // y1 * x2
	out := f0.Equal(&f1)

	f0.Multiply(Y1, Y2) // y1 * y2
	f1.Multiply(X1, X2) // x1 * x2
	out = out | f0.Equal(&f1)

	return out
}

// FromUniformBytes maps the 64-byte slice b to e uniformly and
// deterministically, and returns e. This can be used for hash-to-group
// operations or to obtain a random element.
//
// Deprecated: use SetUniformBytes. This API will be removed before v1.0.0.
func (e *Element) FromUniformBytes(b []byte) *Element {
	if _, err := e.SetUniformBytes(b); err != nil {
		panic(err.Error())
	}
	return e
}

// SetUniformBytes deterministically sets e to an uniformly distributed value
// given 64 uniformly distributed random bytes.
//
// This can be used for hash-to-group operations or to obtain a random element.
func (e *Element) SetUniformBytes(b []byte) (*Element, error) {
	if len(b) != 64 {
		return nil, errors.New("ristretto255: SetUniformBytes input is not 64 bytes long")
	}

	f := &field.Element{}

	f.SetBytes(b[:32])
	point1 := &Element{}
	mapToPoint(&point1.r, f)

	f.SetBytes(b[32:])
	point2 := &Element{}
	mapToPoint(&point2.r, f)

	return e.Add(point1, point2), nil
}

// mapToPoint implements MAP from Section 3.2.4 of draft-hdevalence-cfrg-ristretto-00.
func mapToPoint(out *edwards25519.Point, t *field.Element) {
	// r = SQRT_M1 * t^2
	r := &field.Element{}
	r.Multiply(sqrtM1, r.Square(t))

	// u = (r + 1) * ONE_MINUS_D_SQ
	u := &field.Element{}
	u.Multiply(u.Add(r, one), oneMinusDSQ)

	// c = -1
	c := &field.Element{}
	c.Set(minusOne)

	// v = (c - r*D) * (r + D)
	rPlusD := &field.Element{}
	rPlusD.Add(r, d)
	v := &field.Element{}
	v.Multiply(v.Subtract(c, v.Multiply(r, d)), rPlusD)

	// (was_square, s) = SQRT_RATIO_M1(u, v)
	s := &field.Element{}
	_, wasSquare := s.SqrtRatio(u, v)

	// s_prime = -CT_ABS(s*t)
	sPrime := &field.Element{}
	sPrime.Negate(sPrime.Absolute(sPrime.Multiply(s, t)))

	// s = CT_SELECT(s IF was_square ELSE s_prime)
	s.Select(s, sPrime, wasSquare)
	// c = CT_SELECT(c IF was_square ELSE r)
	c.Select(c, r, wasSquare)

	// N = c * (r - 1) * D_MINUS_ONE_SQ - v
	N := &field.Element{}
	N.Multiply(c, N.Subtract(r, one))
	N.Subtract(N.Multiply(N, dMinusOneSQ), v)

	s2 := &field.Element{}
	s2.Square(s)

	// w0 = 2 * s * v
	w0 := &field.Element{}
	w0.Add(w0, w0.Multiply(s, v))
	// w1 = N * SQRT_AD_MINUS_ONE
	w1 := &field.Element{}
	w1.Multiply(N, sqrtADMinusOne)
	// w2 = 1 - s^2
	w2 := &field.Element{}
	w2.Subtract(one, s2)
	// w3 = 1 + s^2
	w3 := &field.Element{}
	w3.Add(one, s2)

	// return (w0*w3, w2*w1, w1*w3, w0*w2)
	var X, Y, Z, T field.Element
	X.Multiply(w0, w3)
	Y.Multiply(w2, w1)
	Z.Multiply(w1, w3)
	T.Multiply(w0, w2)
	if _, err := out.SetExtendedCoordinates(&X, &Y, &Z, &T); err != nil {
		panic("ristretto255: internal error: MAP generated invalid coordinates")
	}
}

// Encode appends the 32 bytes canonical encoding of e to b
// and returns the result.
//
// Deprecated: use Bytes. This API will be removed before v1.0.0.
func (e *Element) Encode(b []byte) []byte {
	ret, out := sliceForAppend(b, 32)
	e.bytes(out)
	return ret
}

// sliceForAppend takes a slice and a requested number of bytes. It returns a
// slice with the contents of the given slice followed by that many bytes and a
// second slice that aliases into it and contains only the extra bytes. If the
// original slice has sufficient capacity then no allocation is performed.
func sliceForAppend(in []byte, n int) (head, tail []byte) {
	if total := len(in) + n; cap(in) >= total {
		head = in[:total]
	} else {
		head = make([]byte, total)
		copy(head, in)
	}
	tail = head[len(in):]
	return
}

// Bytes returns the 32 bytes canonical encoding of e.
func (e *Element) Bytes() []byte {
	// Bytes is outlined to let the allocation happen on the stack of the caller.
	b := make([]byte, 32)
	return e.bytes(b)
}

func (e *Element) bytes(b []byte) []byte {
	X, Y, Z, T := e.r.ExtendedCoordinates()
	tmp := &field.Element{}

	// u1 = (z0 + y0) * (z0 - y0)
	u1 := &field.Element{}
	u1.Add(Z, Y).Multiply(u1, tmp.Subtract(Z, Y))

	// u2 = x0 * y0
	u2 := &field.Element{}
	u2.Multiply(X, Y)

	// Ignore was_square since this is always square
	// (_, invsqrt) = SQRT_RATIO_M1(1, u1 * u2^2)
	invSqrt := &field.Element{}
	invSqrt.SqrtRatio(one, tmp.Square(u2).Multiply(tmp, u1))

	// den1 = invsqrt * u1
	// den2 = invsqrt * u2
	den1, den2 := &field.Element{}, &field.Element{}
	den1.Multiply(invSqrt, u1)
	den2.Multiply(invSqrt, u2)
	// z_inv = den1 * den2 * t0
	zInv := &field.Element{}
	zInv.Multiply(den1, den2).Multiply(zInv, T)

	// ix0 = x0 * SQRT_M1
	// iy0 = y0 * SQRT_M1
	ix0, iy0 := &field.Element{}, &field.Element{}
	ix0.Multiply(X, sqrtM1)
	iy0.Multiply(Y, sqrtM1)
	// enchanted_denominator = den1 * INVSQRT_A_MINUS_D
	enchantedDenominator := &field.Element{}
	enchantedDenominator.Multiply(den1, invSqrtAMinusD)

	// rotate = IS_NEGATIVE(t0 * z_inv)
	rotate := tmp.Multiply(T, zInv).IsNegative()

	// x = CT_SELECT(iy0 IF rotate ELSE x0)
	// y = CT_SELECT(ix0 IF rotate ELSE y0)
	x, y := &field.Element{}, &field.Element{}
	x.Select(iy0, X, rotate)
	y.Select(ix0, Y, rotate)
	// z = z0
	z := Z
	// den_inv = CT_SELECT(enchanted_denominator IF rotate ELSE den2)
	denInv := &field.Element{}
	denInv.Select(enchantedDenominator, den2, rotate)

	// y = CT_NEG(y, IS_NEGATIVE(x * z_inv))
	isNegative := tmp.Multiply(x, zInv).IsNegative()
	y.Select(tmp.Negate(y), y, isNegative)

	// s = CT_ABS(den_inv * (z - y))
	s := tmp.Subtract(z, y).Multiply(tmp, denInv).Absolute(tmp)

	// Return the canonical little-endian encoding of s.
	copy(b, s.Bytes())
	return b
}

var errInvalidEncoding = errors.New("ristretto255: invalid element encoding")

// Decode sets e to the decoded value of in. If in is not a 32 byte canonical
// encoding, Decode returns an error, and the receiver is unchanged.
//
// Deprecated: use SetCanonicalBytes. This API will be removed before v1.0.0.
func (e *Element) Decode(in []byte) error {
	_, err := e.SetCanonicalBytes(in)
	return err
}

// SetCanonicalBytes sets e to the decoded value of in. If in is not a canonical
// encoding of s, SetCanonicalBytes returns nil and an error and the receiver is
// unchanged.
func (e *Element) SetCanonicalBytes(in []byte) (*Element, error) {
	if len(in) != 32 {
		return nil, errInvalidEncoding
	}

	// First, interpret the string as an integer s in little-endian representation.
	s := &field.Element{}
	s.SetBytes(in)

	// If the resulting value is >= p, decoding fails.
	if !bytes.Equal(s.Bytes(), in) {
		return nil, errInvalidEncoding
	}

	// If IS_NEGATIVE(s) returns TRUE, decoding fails.
	if s.IsNegative() == 1 {
		return nil, errInvalidEncoding
	}

	// ss = s^2
	sSqr := &field.Element{}
	sSqr.Square(s)

	// u1 = 1 - ss
	u1 := &field.Element{}
	u1.Subtract(one, sSqr)

	// u2 = 1 + ss
	u2 := &field.Element{}
	u2.Add(one, sSqr)

	// u2_sqr = u2^2
	u2Sqr := &field.Element{}
	u2Sqr.Square(u2)

	// v = -(D * u1^2) - u2_sqr
	v := &field.Element{}
	v.Square(u1).Multiply(v, d).Negate(v).Subtract(v, u2Sqr)

	// (was_square, invsqrt) = SQRT_RATIO_M1(1, v * u2_sqr)
	invSqrt, tmp := &field.Element{}, &field.Element{}
	_, wasSquare := invSqrt.SqrtRatio(one, tmp.Multiply(v, u2Sqr))

	// den_x = invsqrt * u2
	// den_y = invsqrt * den_x * v
	denX, denY := &field.Element{}, &field.Element{}
	denX.Multiply(invSqrt, u2)
	denY.Multiply(invSqrt, denX).Multiply(denY, v)

	// x = CT_ABS(2 * s * den_x)
	// y = u1 * den_y
	// t = x * y
	var X, Y, Z, T field.Element
	X.Multiply(two, s).Multiply(&X, denX).Absolute(&X)
	Y.Multiply(u1, denY)
	Z.One()
	T.Multiply(&X, &Y)

	// If was_square is FALSE, or IS_NEGATIVE(t) returns TRUE, or y = 0, decoding fails.
	if wasSquare == 0 || T.IsNegative() == 1 || Y.Equal(zero) == 1 {
		return nil, errInvalidEncoding
	}

	// Otherwise, return the internal representation in extended coordinates (x, y, 1, t).
	if _, err := e.r.SetExtendedCoordinates(&X, &Y, &Z, &T); err != nil {
		panic("ristretto255: internal error: DECODE generated invalid coordinates")
	}
	return e, nil
}

// ScalarBaseMult sets e = s * B, where B is the canonical generator, and returns e.
func (e *Element) ScalarBaseMult(s *Scalar) *Element {
	e.r.ScalarBaseMult(&s.s)
	return e
}

// ScalarMult sets e = s * p, and returns e.
func (e *Element) ScalarMult(s *Scalar, p *Element) *Element {
	e.r.ScalarMult(&s.s, &p.r)
	return e
}

// MultiScalarMult sets e = sum(s[i] * p[i]), and returns e.
//
// Execution time depends only on the lengths of the two slices, which must match.
func (e *Element) MultiScalarMult(s []*Scalar, p []*Element) *Element {
	if len(p) != len(s) {
		panic("ristretto255: MultiScalarMult invoked with mismatched slice lengths")
	}
	points := make([]*edwards25519.Point, len(p))
	scalars := make([]*edwards25519.Scalar, len(s))
	for i := range s {
		points[i] = &p[i].r
		scalars[i] = &s[i].s
	}
	e.r.MultiScalarMult(scalars, points)
	return e
}

// VarTimeMultiScalarMult sets e = sum(s[i] * p[i]), and returns e.
//
// Execution time depends on the inputs.
func (e *Element) VarTimeMultiScalarMult(s []*Scalar, p []*Element) *Element {
	if len(p) != len(s) {
		panic("ristretto255: VarTimeMultiScalarMult invoked with mismatched slice lengths")
	}
	points := make([]*edwards25519.Point, len(p))
	scalars := make([]*edwards25519.Scalar, len(s))
	for i := range s {
		points[i] = &p[i].r
		scalars[i] = &s[i].s
	}
	e.r.VarTimeMultiScalarMult(scalars, points)
	return e
}

// VarTimeDoubleScalarBaseMult sets e = a * A + b * B, where B is the canonical
// generator, and returns e.
//
// Execution time depends on the inputs.
func (e *Element) VarTimeDoubleScalarBaseMult(a *Scalar, A *Element, b *Scalar) *Element {
	e.r.VarTimeDoubleScalarBaseMult(&a.s, &A.r, &b.s)
	return e
}

// Add sets e = p + q, and returns e.
func (e *Element) Add(p, q *Element) *Element {
	e.r.Add(&p.r, &q.r)
	return e
}

// Subtract sets e = p - q, and returns e.
func (e *Element) Subtract(p, q *Element) *Element {
	e.r.Subtract(&p.r, &q.r)
	return e
}

// Negate sets e = -p, and returns e.
func (e *Element) Negate(p *Element) *Element {
	e.r.Negate(&p.r)
	return e
}

// Zero sets e to the identity element of the group, and returns e.
//
// Deprecated: use NewIdentityElement and Set. This API will be removed before v1.0.0.
func (e *Element) Zero() *Element {
	return e.Set(NewIdentityElement())
}

// Base sets e to the canonical generator specified in
// draft-hdevalence-cfrg-ristretto-01, Section 3, and returns e.
//
// Deprecated: use NewGeneratorElement and Set. This API will be removed before v1.0.0.
func (e *Element) Base() *Element {
	return e.Set(NewGeneratorElement())
}

// MarshalText implements encoding/TextMarshaler interface
func (e *Element) MarshalText() (text []byte, err error) {
	b := e.Encode([]byte{})
	return []byte(base64.StdEncoding.EncodeToString(b)), nil
}

// UnmarshalText implements encoding/TextMarshaler interface
func (e *Element) UnmarshalText(text []byte) error {
	eb, err := base64.StdEncoding.DecodeString(string(text))
	if err == nil {
		return e.Decode(eb)
	}
	return err
}

// String implements the Stringer interface
func (e *Element) String() string {
	result, _ := e.MarshalText()
	return string(result)
}