path: root/veto/veto.go

package veto

import (
	"bytes"
	"crypto/rand"
	"crypto/sha512"
	"encoding/base64"
	"encoding/json"
	"fmt"
	"io"
	"slices"

	curve "filippo.io/edwards25519"
)

var b64 = base64.StdEncoding.WithPadding(base64.NoPadding)

type point curve.Point
type scalar curve.Scalar

// Representation of a vote with veto (true)
type Vote struct {
	veto    bool
	private struct {
		id *scalar
		x  *scalar
		r  *scalar
	}
	com *Commitment
}

// Commitment represents the public data sent by a participant
// in round 1 of the protocol.  It is generated out of a Vote.
type Commitment struct {
	Id     *point `json:"index"`
	Points struct {
		X *point
		R *point
	} `json:"points"`
	Proofs struct {
		X *Proof
		R *Proof
	} `json:"proofs"`
}

// A Schnorr signature to prove knowledge of v for given g^v and i.
// Choosing a scalar v randomly, the signature consists of (V, r) with
//
//	V := g^v, with randomly chosen v
//	 r := (v - x*h), with h := H(g, g^v, g^x, i), where i is given by the context.
//
// Verification of the signature is by comparing V =?= g^r * g^(x*h)
type Proof struct {
	PV *point  `json:"V"`
	Sr *scalar `json:"r"`
	Id *point  `json:"id"`
}

func randomScalar(random io.Reader) (*scalar, error) {
	var buf [64]byte
	if random == nil {
		random = rand.Reader
	}
	random.Read(buf[:])
	s, e := new(curve.Scalar).SetUniformBytes(buf[:])
	return (*scalar)(s), e
}

func (s *scalar) point() *point {
	p := new(curve.Point).ScalarBaseMult((*curve.Scalar)(s))
	return (*point)(p)
}

func (p *point) Bytes() []byte {
	return ((*curve.Point)(p)).Bytes()
}

func one() *point {
	return (*point)(curve.NewIdentityPoint())
}

type points []*point

func (pts points) prod() (product *point) {
	product = (*point)(curve.NewIdentityPoint())
	for _, p := range pts {
		product = product.mult(p)
	}
	return product
}

// Return p (*) q in group
func (p *point) mult(q *point) *point {
	// The implementation in edwards25519 uses addition for the group operation.
	r := new(curve.Point).Add((*curve.Point)(p), (*curve.Point)(q))
	return (*point)(r)
}

// Return n*P , for n scalar, and P point
func (p *point) scalarMult(s *scalar) *point {
	r := new(curve.Point).ScalarMult((*curve.Scalar)(s), (*curve.Point)(p))
	return (*point)(r)
}

// Return p^(-1)
func (p *point) inv() *point {
	n := new(curve.Point).Negate((*curve.Point)(p))
	return (*point)(n)
}

func (s *scalar) Bytes() []byte {
	return ((*curve.Scalar)(s)).Bytes()
}

func (p *point) equal(q *point) bool {
	return ((*curve.Point)(p)).Equal((*curve.Point)(q)) == 1

}

// Generates the proof, aka Schnorr signature, for given priv and i.
// Choosing a scalar v randomly, the signature consists of (V, r) with
//
//	V := g^v, with randomly chosen v
//	 r := (v - x*h), with h := H(g, g^v, g^x, i), where i is given by the context.
//
// Verification of the signature is by comparing V =?= g^r * g^(x*h)
func (x *scalar) proof(id *point) (pr *Proof, e error) {
	pr = &Proof{Id: id}

	// choose random v
	v, e := randomScalar(nil)
	if e != nil {
		return nil, e
	}

	// calculate g^v
	pr.PV = v.point()

	// calculate g^x
	gx := x.point()

	// calculate h := H(g, g^v, g^x, i)
	h, e := hash(pr.PV, gx, id)
	if e != nil {
		return nil, e
	}

	// Calculate r := v - x*h
	xh := new(curve.Scalar).Multiply((*curve.Scalar)(x), h)
	r := new(curve.Scalar).Subtract((*curve.Scalar)(v), xh)
	pr.Sr = (*scalar)(r)

	return pr, nil
}

// Calculate  h := H(g, g^v, g^x, i)
func hash(gv, gx *point, id *point) (*curve.Scalar, error) {
	h512 := sha512.New()
	h512.Write(curve.NewGeneratorPoint().Bytes())
	h512.Write(gv.Bytes())
	h512.Write(gx.Bytes())
	h512.Write(id.Bytes())
	hb := h512.Sum(nil)
	return new(curve.Scalar).SetUniformBytes(hb)
}

func combineErr(es ...error) error {
	var re error
	for _, e := range es {
		if e != nil {
			if re == nil {
				re = e
			} else {
				re = fmt.Errorf("%v and %v", re, e)
			}
		}
	}
	return re
}

// Verifies that g^v == g^r*g^(x*h)
func verifyProof(V *point, Gx *point, r *scalar, id *point) (ok bool) {
	// Calculate h = H(g, g^v, g^x, id)
	h, e := hash(V, Gx, id)
	if e != nil {
		return false
	}

	// Calculate g^(x*h) = (g^x)^h
	gxh := new(curve.Point).ScalarMult(h, (*curve.Point)(Gx))

	// Calculate g^r
	gr := r.point()

	// Calculate g^r*g^(x*h)
	// Note that the edwards25519 package uses Addtion as the group
	grgxh := gr.mult((*point)(gxh))

	// Return true if g^v == g^r*g^(x*h)
	return V.equal(grgxh)
}

// Verify verifies the proofs for both, g^x and g^r
func (c *Commitment) VerifyProofs() (ok bool) {
	okX := verifyProof(c.Proofs.X.PV, c.Points.X, c.Proofs.X.Sr, c.Id)
	okR := verifyProof(c.Proofs.R.PV, c.Points.R, c.Proofs.R.Sr, c.Id)
	return okX && okR
}

// Generates a vote with commitments and proofs and takes the input for
// the randomness from the given io.Reader
func newVoteWithRand(veto bool, rand io.Reader) (v *Vote, e error) {
	v = &Vote{
		veto: veto,
	}
	var e1, e2, e3 error

	v.private.id, e1 = randomScalar(rand)
	v.private.x, e2 = randomScalar(rand)
	v.private.r, e3 = randomScalar(rand)

	e = combineErr(e1, e2, e3)
	if e != nil {
		return nil, e
	}

	c := new(Commitment)
	v.com = c
	c.Id = v.private.id.point()
	c.Points.X = v.private.x.point()
	c.Points.R = v.private.r.point()
	c.Proofs.X, e1 = v.private.x.proof(c.Id)
	c.Proofs.R, e2 = v.private.r.proof(c.Id)

	return v, combineErr(e1, e2)
}

// NewVote generates a vote for given bit and index, taking crypt/Reader as
// source for randomness
func NewVote(bit bool) (vote *Vote, e error) {
	return newVoteWithRand(bit, nil)
}

// Generate the commitment to the Vote
func (v *Vote) Commitment() *Commitment {
	return v.com
}

func (p *point) String() string {
	return b64.EncodeToString(p.Bytes())
}

func (s *scalar) String() string {
	return b64.EncodeToString(s.Bytes())
}

func (s *scalar) MarshalJSON() ([]byte, error) {
	return []byte(fmt.Sprintf(`"%s"`, s)), nil

}
func (p *point) MarshalJSON() ([]byte, error) {
	return []byte(fmt.Sprintf(`"%s"`, p)), nil
}

func (c *Commitment) String() string {
	buf := &bytes.Buffer{}
	dec := json.NewEncoder(buf)
	dec.SetIndent("", "  ")
	e := dec.Encode(c)
	if e != nil {
		return fmt.Sprintf("<error encoding: %v>", e)
	}
	return buf.String()
}

type coms []*Commitment

func (coms coms) prod() (product *point) {
	product = (*point)(curve.NewIdentityPoint())
	for _, com := range coms {
		product = product.mult(com.Points.X)
	}
	return product
}

// For a given slice of commitments of length n, compute
//
//	g^y_i = Prod(g^x_j, 1, i-1)/Prod(g^x_j, i+1, n)
func (coms coms) computeGy(index int) *point {
	gy1 := coms[:index].prod()
	gy2 := coms[index+1:].prod().inv()
	return gy1.mult(gy2)
}

func (v *Vote) Round2(participants []*Commitment) (gcy *point, e error) {
	var c int
	for _, p := range participants {
		if p.Id.equal(v.com.Id) {
			c += 1
		}
	}
	if c == 0 {
		return nil, fmt.Errorf("/me(%s) not in participants", v.com.Id)
	} else if c > 1 {
		return nil, fmt.Errorf("/me(%s) %d times in participants", v.com.Id, c)
	}

	slices.SortStableFunc(participants, func(a, b *Commitment) int {
		return bytes.Compare(a.Id.Bytes(), b.Id.Bytes())
	})

	index := slices.IndexFunc(participants, func(c *Commitment) bool { return c.Id.equal(v.com.Id) })
	if index < 0 {
		// Should not happen!
		return nil, fmt.Errorf("Wait, what!? Couldn't find /me(%s) after sorting!", v.com.Id)
	}
	gy := (coms(participants)).computeGy(index)

	if v.veto {
		return gy.scalarMult(v.private.r), nil
	}
	return gy.scalarMult(v.private.x), nil
}

func (pts points) IsVetoed() bool {
	product := pts.prod()
	one := one()
	return !one.equal(product)
}