diff options
| -rw-r--r-- | veto/veto.go | 329 | ||||
| -rw-r--r-- | veto/veto_test.go | 95 | ||||
| -rw-r--r-- | vote/vote.go | 233 | ||||
| -rw-r--r-- | vote/vote_test.go | 25 |
4 files changed, 424 insertions, 258 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 diff --git a/vote/vote.go b/vote/vote.go deleted file mode 100644 index 97367c0..0000000 --- a/vote/vote.go +++ /dev/null @@ -1,233 +0,0 @@ -package vote - -import ( - "bytes" - "crypto/rand" - "crypto/sha512" - "encoding/base64" - "encoding/json" - "fmt" - "io" - - curve "filippo.io/edwards25519" -) - -var b64 = base64.StdEncoding.WithPadding(base64.NoPadding) - -type point curve.Point -type scalar curve.Scalar - -// Representation of a vote (true or false) of an individual. -// The .Commitment is sent as data for round1 of the protocol. -type Vote struct { - bit bool - private struct { - id *scalar - x *scalar - r *scalar - } - - Commitment -} - -// Commitment represents the public data sent by a participant -// in round 1 of the protocol. -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) -} - -// 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(((*curve.Point)(gv)).Bytes()) - h512.Write(((*curve.Point)(gx)).Bytes()) - h512.Write(((*curve.Point)(id)).Bytes()) - hb := h512.Sum(nil) - return new(curve.Scalar).SetUniformBytes(hb) -} - -// Generate the proofs for both, the g^x and g^r points. -func (v *Vote) genProofs() (e error) { - v.Proofs.X, e = v.private.x.proof(v.Id) - if e != nil { - return e - } - v.Proofs.R, e = v.private.r.proof(v.Id) - return e -} - -// 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 := new(curve.Point).Add((*curve.Point)(gr), gxh) - - // Return true if g^v == g^r*g^(x*h) - return ((*curve.Point)(V)).Equal(grgxh) == 1 -} - -func combineErr(e1, e2 error) error { - if e1 == nil && e2 == nil { - return nil - } else if e1 != nil { - if e2 == nil { - return e1 - } - return fmt.Errorf("%v and %v", e1, e2) - } - return e2 -} - -// Verify verifies the proofs for both, g^x and g^r -func (v *Vote) VerifyProofs() (ok bool) { - okX := verifyProof(v.Proofs.X.PV, v.Points.X, v.Proofs.X.Sr, v.Id) - okR := verifyProof(v.Proofs.R.PV, v.Points.R, v.Proofs.R.Sr, v.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(bit bool, rand io.Reader) (vote *Vote, e error) { - vote = &Vote{ - bit: bit, - } - - vote.private.id, e = randomScalar(rand) - if e != nil { - return nil, e - } - vote.private.x, e = randomScalar(rand) - if e != nil { - return nil, e - } - vote.private.r, e = randomScalar(rand) - if e != nil { - return nil, e - } - - vote.Commitment.Id = vote.private.id.point() - vote.Commitment.Points.X = vote.private.x.point() - vote.Commitment.Points.R = vote.private.r.point() - - e = vote.genProofs() - - return vote, nil -} - -// 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) -} - -func (p *point) String() string { - return b64.EncodeToString(((*curve.Point)(p)).Bytes()) -} - -func (s *scalar) String() string { - return b64.EncodeToString(((*curve.Scalar)(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() -} diff --git a/vote/vote_test.go b/vote/vote_test.go deleted file mode 100644 index 437dbe5..0000000 --- a/vote/vote_test.go +++ /dev/null @@ -1,25 +0,0 @@ -package vote - -import ( - "testing" -) - -func TestVoteGeneration(t *testing.T) { - - for i := range 100 { - bit := i%3 == 1 - vote, e := newVoteWithRand(bit, nil) - - if e != nil { - t.Fatalf("unexpected error: %v", e) - } - if vote.bit != bit { - t.Fatalf("expected vote %t, but got %t", bit, vote.bit) - } - if !vote.VerifyProofs() { - t.Fatalf("Proofs not correct! %+v", vote) - } - - t.Logf("Generated %s\n", vote) - } -} |