nizk/stage1: NIZK proofs for commit phase

Implemented the NIZK for the B.a) Commit on page 4

2 files changed, 148 insertions, 0 deletions

diff --git a/nizk/stage1/stage1.go b/nizk/stage1/stage1.go
new file mode 100644
index 0000000..3b97887
--- /dev/null
+++ b/nizk/stage1/stage1.go
@@ -0,0 +1,131 @@
+package stage1
+
+import (
+	"crypto/sha512"
+
+	"kesim.org/seal/curve"
+)
+
+// This is a construction of a proof of a statement of the form
+// σ ==	   [(Φ = g^(αβ))   && (A = g^α) && (Β = g^β)]
+//		|| [(Φ = g^(αβ+1)) && (A = g^α) && (Β = g^β)]
+// for given Φ, A and B
+
+type Scalar = curve.Curve25519Scalar
+type Point = curve.Curve25519Point
+
+var Curve = curve.Curve25519
+var g = Curve.Generator()
+var one = Curve.ScalarOne()
+
+type Statement struct {
+	α    *Scalar
+	β    *Scalar
+	plus bool
+	*Commitment
+}
+
+type Commitment struct {
+	Φ *Point
+	A *Point
+	B *Point
+}
+
+func NewStatement(α, β *Scalar, plus bool) *Statement {
+	return &Statement{
+		α:          α,
+		β:          β,
+		plus:       plus,
+		Commitment: commitment(α, β, plus),
+	}
+}
+
+func commitment(α, β *Scalar, plus bool) *Commitment {
+	var Φ *Point
+	φ := α.Mul(β)
+
+	if plus {
+		Φ = g.Exp(φ.Add(one))
+	} else {
+		Φ = g.Exp(φ)
+	}
+	return &Commitment{
+		Φ: Φ,
+		A: g.Exp(α),
+		B: g.Exp(β),
+	}
+}
+
+func (s *Statement) Commit() *Commitment {
+	return s.Commitment
+}
+
+type Proof struct {
+	Ch  [2]*Scalar
+	Rho [2]*Scalar
+}
+
+func (s *Statement) Proof() *Proof {
+	var ε [2][2]*Point
+	var r1, r2, ω *Scalar
+	r1 = Curve.RandomScalar()
+	r2 = Curve.RandomScalar()
+	ω = Curve.RandomScalar()
+
+	if s == nil {
+		panic("s is nil")
+	} else if ω == nil {
+		panic("ω is nil")
+	}
+
+	if s.plus {
+		ε[0][0] = g.Exp(r1)
+		ε[0][1] = s.B.Exp(r1).Mul(g.Exp(ω))
+		ε[1][0] = g.Exp(r2)
+		ε[1][1] = s.B.Exp(r2)
+	} else {
+		ε[0][0] = g.Exp(r1)
+		ε[0][1] = s.B.Exp(r1)
+		ε[1][0] = g.Exp(r2).Mul(s.A.Exp(ω))
+		ε[1][1] = s.B.Exp(r2).Mul(s.Φ.Div(g).Exp(ω))
+	}
+
+	ch := challenge(g, s.Φ, s.A, s.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
+	pr := &Proof{}
+
+	if s.plus {
+		pr.Ch[0] = ω
+		pr.Ch[1] = ch.Sub(ω)
+		pr.Rho[0] = r1.Sub(s.α.Mul(pr.Ch[0]))
+		pr.Rho[1] = r2.Sub(s.α.Mul(pr.Ch[1]))
+	} else {
+		pr.Ch[0] = ch.Sub(ω)
+		pr.Ch[1] = ω
+		pr.Rho[0] = r1.Sub(s.α.Mul(pr.Ch[0]))
+		pr.Rho[1] = r2
+	}
+
+	return pr
+}
+
+func challenge(points ...*Point) *Scalar {
+	h512 := sha512.New()
+	for _, p := range points {
+		h512.Write(p.Bytes())
+	}
+	ch, e := Curve.ScalarFromBytes(h512.Sum(nil))
+	if e != nil {
+		panic(e)
+	}
+	return ch
+}
+
+func (c *Commitment) Verify(p *Proof) bool {
+	var ε [2][2]*Point
+	ε[0][0] = g.Exp(p.Rho[0]).Mul(c.A.Exp(p.Ch[0]))
+	ε[0][1] = c.B.Exp(p.Rho[0]).Mul(c.Φ.Exp(p.Ch[0]))
+	ε[1][0] = g.Exp(p.Rho[1]).Mul(c.A.Exp(p.Ch[1]))
+	ε[1][1] = c.B.Exp(p.Rho[1]).Mul(c.Φ.Div(g).Exp(p.Ch[1]))
+	ch := challenge(g, c.Φ, c.A, c.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
+	return p.Ch[0].Add(p.Ch[1]).Equal(ch)
+}
diff --git a/nizk/stage1/stage1_test.go b/nizk/stage1/stage1_test.go
new file mode 100644
index 0000000..928cfc1
--- /dev/null
+++ b/nizk/stage1/stage1_test.go
@@ -0,0 +1,17 @@
+package stage1
+
+import "testing"
+
+func TestStatement(t *testing.T) {
+	var α, β = Curve.RandomScalar(), Curve.RandomScalar()
+
+	st1, st2 := NewStatement(α, β, true), NewStatement(α, β, false)
+	c1, c2 := st1.Commit(), st2.Commit()
+	pr1, pr2 := st1.Proof(), st2.Proof()
+	if !c1.Verify(pr1) {
+		t.Fatal("Could not verify st1 with c1 and pr1, plus=true case")
+	}
+	if !c2.Verify(pr2) {
+		t.Fatal("Could not verify st2 with c2 and pr2, plus=false case")
+	}
+}