veto: commitment(round1), round2 and veto check implemented

The core elements to resemble the calculation of the AV-net protocol is ready,
Votes generate Commitments, calculate the Proofs for the X's, R's, calculate
the data for round2 and calculate the final vote, according to the paper.

2 files changed, 424 insertions, 0 deletions

diff --git a/veto/veto.go b/veto/veto.go
new file mode 100644
index 0000000..f4faa38
--- /dev/null
+++ b/veto/veto.go
@@ -0,0 +1,329 @@
+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)
+}
\ No newline at end of file
diff --git a/veto/veto_test.go b/veto/veto_test.go
new file mode 100644
index 0000000..847c7a0
--- /dev/null
+++ b/veto/veto_test.go
@@ -0,0 +1,95 @@
+package veto
+
+import (
+	"math/rand"
+	"testing"
+)
+
+func TestVoteGeneration(t *testing.T) {
+
+	for i := range 100 {
+		veto := i%3 == 1
+		vote, e := newVoteWithRand(veto, nil)
+
+		if e != nil {
+			t.Fatalf("unexpected error: %v", e)
+		}
+		if vote.veto != veto {
+			t.Fatalf("expected veto %t, but got %t", veto, vote.veto)
+		}
+		com := vote.Commitment()
+		if !com.VerifyProofs() {
+			t.Fatalf("Proofs not correct! %+v", com)
+		}
+	}
+}
+
+func TestRound2NoVeto(t *testing.T) {
+	var (
+		vs   = []*Vote{}
+		cs   = []*Commitment{}
+		gcys = []*point{}
+		num  = 100
+	)
+	for i := range num {
+		vote, e := newVoteWithRand(false, nil)
+
+		if e != nil {
+			t.Fatalf("unexpected error: %v", e)
+		}
+		com := vote.Commitment()
+		if !com.VerifyProofs() {
+			t.Fatalf("Proofs not correct for %d! %+v", i, com)
+		}
+		vs = append(vs, vote)
+		cs = append(cs, com)
+	}
+
+	for i := range num {
+		gcy, e := vs[i].Round2(cs)
+		t.Logf("gcy: %v, e: %v", gcy, e)
+		if e != nil {
+			t.Fatalf("Error calculating Round2: %v", e)
+		}
+		gcys = append(gcys, gcy)
+	}
+
+	if (points)(gcys).IsVetoed() {
+		t.Fatalf("veto expected, but got didn't")
+	}
+}
+
+func TestRound2WithVeto(t *testing.T) {
+	var (
+		vs    = []*Vote{}
+		cs    = []*Commitment{}
+		gcys  = []*point{}
+		num   = 100
+		index = int(rand.Int31n(int32(num)))
+	)
+	for i := range num {
+		vote, e := newVoteWithRand(i == index, nil)
+		if e != nil {
+			t.Fatalf("unexpected error: %v", e)
+		}
+		com := vote.Commitment()
+		if !com.VerifyProofs() {
+			t.Fatalf("Proofs not correct for %d! %+v", i, com)
+		}
+		vs = append(vs, vote)
+		cs = append(cs, com)
+	}
+
+	for i := range num {
+		gcy, e := vs[i].Round2(cs)
+		t.Logf("gcy: %v, e: %v", gcy, e)
+		if e != nil {
+			t.Fatalf("Error calculating Round2: %v", e)
+		}
+		gcys = append(gcys, gcy)
+	}
+
+	if !(points)(gcys).IsVetoed() {
+		t.Fatalf("not vetoed, but should!")
+	}
+}
\ No newline at end of file