aboutsummaryrefslogtreecommitdiff
path: root/nizk
diff options
context:
space:
mode:
Diffstat (limited to 'nizk')
-rw-r--r--nizk/bench_test.go191
-rw-r--r--nizk/commit.go150
-rw-r--r--nizk/commit_test.go57
-rw-r--r--nizk/doc.go7
-rw-r--r--nizk/schnorr/schnorr.go77
-rw-r--r--nizk/schnorr/schnorr_test.go34
-rw-r--r--nizk/stage1.go196
-rw-r--r--nizk/stage1_test.go56
-rw-r--r--nizk/stage2.go221
-rw-r--r--nizk/stage2_test.go267
-rw-r--r--nizk/vickrey_test.go209
11 files changed, 0 insertions, 1465 deletions
diff --git a/nizk/bench_test.go b/nizk/bench_test.go
deleted file mode 100644
index 3ee30a8..0000000
--- a/nizk/bench_test.go
+++ /dev/null
@@ -1,191 +0,0 @@
-package nizk
-
-import (
- "math/rand"
- "slices"
- "sync"
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-func BenchmarkFromPaper(b *testing.B) {
- bitlength := 5
- vals := []int{
- 0b01010,
- 0b01001,
- 0b00111,
- }
- ids := []Bytes{
- Curve.RandomScalar(),
- Curve.RandomScalar(),
- Curve.RandomScalar(),
- }
-
- for range b.N {
- var bits = [3][]*Bit{}
- for i, b := range vals {
- bits[i] = Int2Bits(ids[i], b, bitlength)
- }
-
- var lost = [3]bool{}
- instage1 := true
- junction := -1
- result := 0
-
- for idx := 0; idx < bitlength; idx++ {
- var c = [3]*StageCommitment{}
- var r = [3]*StageReveal{}
-
- for i, b := range bits {
- c[i] = b[idx].StageCommit()
- }
-
- if instage1 {
- var p = [3]*Stage1Proof{}
- for i := range bits {
- r[i], p[i] = bits[i][idx].RevealStage1(c[0].X, c[1].X, c[2].X)
- if !bits[i][idx].Commitment.VerifyStage1(c[i], r[i], p[i]) {
- b.Fatalf("bits[%d][%d] commitment failed to verify in stage1", i, idx)
- }
- }
-
- Z := Curve.Product(r[0].Z, r[1].Z, r[2].Z)
- if !Id.Equal(Z) {
- junction = idx
- instage1 = false
-
- for i := range bits {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- }
- }
- result |= 1 << (bitlength - 1 - idx)
- }
- } else {
- var bj = [3]*Bit{}
- for i := range bits {
- bj[i] = bits[i][junction]
- }
-
- var p = [3]*Stage2Proof{}
- for i := range bits {
- r[i], p[i] = bits[i][idx].RevealStage2(lost[i], bj[i], c[0].X, c[1].X, c[2].X)
- if !bits[i][idx].Commitment.VerifyStage2(bj[i].StageCommitment, c[i], bj[i].StageReveal, r[i], p[i]) {
- b.Fatalf("bits[%d][%d] commitment failed to verify in stage2, result so far: %05b", i, idx, result)
- }
- }
-
- Z := Curve.Product(r[0].Z, r[1].Z, r[2].Z)
- if !Id.Equal(Z) {
- junction = idx
-
- for i := range bits {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- }
- }
- result |= 1 << (bitlength - 1 - idx)
- }
- }
- }
- if result != vals[0] {
- b.Fatalf("wrong result: %05b, expected: %05b", result, vals[0])
- }
- }
-}
-
-func runSeal(n int, bitlength int, tb testing.TB) {
- var vals = make([]int, n)
- var ids = make([]Bytes, n)
- for i := range n {
- vals[i] = rand.Intn(1<<(bitlength-1) - 1)
- ids[i] = Curve.RandomScalar()
- }
- max := slices.Max(vals)
-
- var bits = make([][]*Bit, n)
- for i, b := range vals {
- bits[i] = Int2Bits(ids[i], b, bitlength)
- }
-
- var c = make([]*StageCommitment, n)
- var Xs = make([]*Point, n)
- var r = make([]*StageReveal, n)
- var p1 = make([]*Stage1Proof, n)
- var Zs = make([]*Point, n)
- var bj = make([]*Bit, n)
- var p2 = make([]*Stage2Proof, n)
- var lost = make([]bool, n)
- stage := stage1
- junction := -1
- result := 0
-
- for idx := range bitlength {
- for i := range n {
- c[i] = bits[i][idx].StageCommit()
- Xs[i] = c[i].X
- if stage == stage2 {
- bj[i] = bits[i][junction]
-
- }
- }
- var wg sync.WaitGroup
- wg.Add(n)
-
- for i := range n {
- go func() {
- defer wg.Done()
-
- if stage == stage1 {
- r[i], p1[i] = bits[i][idx].RevealStage1(Xs...)
- if !bits[i][idx].Commitment.VerifyStage1(c[i], r[i], p1[i]) {
- tb.Fatalf("bits[%d][%d] commitment failed to verify in stage1", i, idx)
- }
- } else {
- r[i], p2[i] = bits[i][idx].RevealStage2(lost[i], bj[i], Xs...)
- if !bits[i][idx].Commitment.VerifyStage2(bj[i].StageCommitment, c[i], bj[i].StageReveal, r[i], p2[i]) {
- tb.Fatalf("bits[%d][%d] commitment failed to verify in stage2, result so far: %05b", i, idx, result)
- }
- }
- Zs[i] = r[i].Z
- }()
- }
- wg.Wait()
-
- Z := Curve.Product(Zs...)
- if !Id.Equal(Z) {
- junction = idx
- stage = stage2
- for i := range bits {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- }
- }
- result |= 1 << (bitlength - 1 - idx)
- }
- }
- if result != max {
- tb.Fatalf("wrong result: %0[1]*[2]b, expected: %0[1]*[3]b", bitlength, result, max)
- }
-}
-
-func benchmarkMulti(n int, bitlength int, b *testing.B) {
- for range b.N {
- runSeal(n, bitlength, b)
- }
-}
-
-func BenchmarkRun3on5bit(b *testing.B) { benchmarkMulti(3, 5, b) }
-func BenchmarkRun10on8bit(b *testing.B) { benchmarkMulti(10, 8, b) }
-func BenchmarkRun10on16bit(b *testing.B) { benchmarkMulti(10, 16, b) }
-func BenchmarkRun10on24bit(b *testing.B) { benchmarkMulti(10, 24, b) }
-func BenchmarkRun100on8bit(b *testing.B) { benchmarkMulti(100, 8, b) }
-func BenchmarkRun100on16bit(b *testing.B) { benchmarkMulti(100, 16, b) }
-func BenchmarkRun100on24bit(b *testing.B) { benchmarkMulti(100, 24, b) }
-func BenchmarkRun500on8bit(b *testing.B) { benchmarkMulti(500, 8, b) }
-func BenchmarkRun500on16bit(b *testing.B) { benchmarkMulti(500, 16, b) }
-func BenchmarkRun500on24bit(b *testing.B) { benchmarkMulti(500, 24, b) }
-func BenchmarkRun1000on8bit(b *testing.B) { benchmarkMulti(1000, 8, b) }
-func BenchmarkRun1000on16bit(b *testing.B) { benchmarkMulti(1000, 16, b) }
-func BenchmarkRun1000on24bit(b *testing.B) { benchmarkMulti(1000, 24, b) }
diff --git a/nizk/commit.go b/nizk/commit.go
deleted file mode 100644
index b68c0f4..0000000
--- a/nizk/commit.go
+++ /dev/null
@@ -1,150 +0,0 @@
-package nizk
-
-import (
- . "kesim.org/seal/common"
- "kesim.org/seal/nizk/schnorr"
-)
-
-type Bit struct {
- id Bytes
- set bool
- α *Scalar
- β *Scalar
-
- *Commitment
- Proof *Proof
-
- *Stage
-}
-
-type Commitment struct {
- A *Point // g^α
- B *Point // g^β
- C *Point // g^(ab)g^(set)
-}
-
-// This is a construction of a proof of a statement of the form
-//
-// [(C = g^(αβ)) && (A = g^α) && (Β = g^β)]
-// || [(C = g^(αβ+1)) && (A = g^α) && (Β = g^β)]
-//
-// for given C, A and B
-type Proof struct {
- A *schnorr.Proof // Proof for knowledge of α in A = G^α
- B *schnorr.Proof // Proof for knowledge of β in B = G^β
- C struct { // Proof for knowledge of statement above
- Ch [2]*Scalar
- R [2]*Scalar
- }
-}
-
-func NewBit(id Bytes, set bool) *Bit {
- α, β := Curve.RandomScalar(), Curve.RandomScalar()
- return NewBitFromScalars(id, set, α, β)
-}
-
-func NewBitFromScalars(id Bytes, set bool, α, β *Scalar) *Bit {
- b := &Bit{
- id: id,
- set: set,
- α: α,
- β: β,
- }
- b.commit()
- b.proof()
- return b
-}
-
-func Int2Bits(id Bytes, val int, bitlength int) []*Bit {
- if bitlength < 0 || bitlength > 32 {
- return nil
- }
-
- bits := make([]*Bit, bitlength)
- for i := range bitlength {
- bits[i] = NewBit(id, (val>>(bitlength-i-1))&1 != 0)
- }
- return bits
-}
-
-func (b *Bit) IsSet() bool {
- return b.set
-}
-
-func (b *Bit) commit() {
- if b.Commitment != nil {
- return
- }
-
- var C *Point
- c := b.α.Mul(b.β)
-
- if b.set {
- C = G.Exp(c.Add(One))
- } else {
- C = G.Exp(c)
- }
- b.Commitment = &Commitment{
- C: C,
- A: G.Exp(b.α),
- B: G.Exp(b.β),
- }
-}
-
-func (s *Bit) proof() {
- if s.Proof != nil {
- return
- }
-
- var e [2][2]*Point
- var r1, r2, w *Scalar
- r1 = Curve.RandomScalar()
- r2 = Curve.RandomScalar()
- w = Curve.RandomScalar()
- s.commit()
- c := s.Commitment
-
- if s.set {
- e[0][0] = G.Exp(r1)
- e[0][1] = c.B.Exp(r1).Mul(G.Exp(w))
- e[1][0] = G.Exp(r2)
- e[1][1] = c.B.Exp(r2)
- } else {
- e[0][0] = G.Exp(r1)
- e[0][1] = c.B.Exp(r1)
- e[1][0] = G.Exp(r2).Mul(c.A.Exp(w))
- e[1][1] = c.B.Exp(r2).Mul(c.C.Div(G).Exp(w))
- }
-
- ch := Challenge(G, c.C, c.A, c.B, e[0][0], e[0][1], e[1][0], e[1][1], s.id)
- pr := &Proof{}
-
- if s.set {
- pr.C.Ch[0] = w
- pr.C.Ch[1] = ch.Sub(w)
- pr.C.R[0] = r1.Sub(s.α.Mul(pr.C.Ch[0]))
- pr.C.R[1] = r2.Sub(s.α.Mul(pr.C.Ch[1]))
- } else {
- pr.C.Ch[0] = ch.Sub(w)
- pr.C.Ch[1] = w
- pr.C.R[0] = r1.Sub(s.α.Mul(pr.C.Ch[0]))
- pr.C.R[1] = r2
- }
- pr.A = (*schnorr.Statement)(s.α).Proof(s.id)
- pr.B = (*schnorr.Statement)(s.β).Proof(s.id)
-
- s.Proof = pr
-}
-
-func (c *Commitment) Verify(id Bytes, p *Proof) bool {
- var e [2][2]*Point
-
- e[0][0] = G.Exp(p.C.R[0]).Mul(c.A.Exp(p.C.Ch[0]))
- e[0][1] = c.B.Exp(p.C.R[0]).Mul(c.C.Exp(p.C.Ch[0]))
- e[1][0] = G.Exp(p.C.R[1]).Mul(c.A.Exp(p.C.Ch[1]))
- e[1][1] = c.B.Exp(p.C.R[1]).Mul(c.C.Div(G).Exp(p.C.Ch[1]))
- ch := Challenge(G, c.C, c.A, c.B, e[0][0], e[0][1], e[1][0], e[1][1], id)
- return p.C.Ch[0].Add(p.C.Ch[1]).Equal(ch) &&
- (*schnorr.Commitment)(c.A).Verify(p.A, id) &&
- (*schnorr.Commitment)(c.B).Verify(p.B, id)
-}
diff --git a/nizk/commit_test.go b/nizk/commit_test.go
deleted file mode 100644
index 909d010..0000000
--- a/nizk/commit_test.go
+++ /dev/null
@@ -1,57 +0,0 @@
-package nizk
-
-import (
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-func TestStatement(t *testing.T) {
- id := Curve.RandomScalar()
-
- b1 := NewBit(id, true)
- b2 := NewBit(id, false)
-
- if !b1.Commitment.Verify(id, b1.Proof) {
- t.Fatal("Could not verify st1 with c1, plus=true case")
- }
- if !b2.Commitment.Verify(id, b2.Proof) {
- t.Fatal("Could not verify st2 with c2, plus=false case")
- }
-
- // Use the wrong proof
- if b2.Commitment.Verify(id, b1.Proof) {
- t.Fatal("Verify with wrong proof should have failed!")
- }
-
- // Use wrong id
- x := Curve.RandomScalar()
- if b1.Commitment.Verify(x, b1.Proof) || b2.Commitment.Verify(x, b2.Proof) {
- t.Fatal("Verify with wrong id should have failed!")
- }
-}
-
-func TestStatementFromScalar(t *testing.T) {
- var α, β, id = Curve.RandomScalar(), Curve.RandomScalar(), Curve.RandomScalar()
-
- b1 := NewBitFromScalars(id, true, α, β)
- b2 := NewBitFromScalars(id, false, α, β)
-
- if !b1.Commitment.Verify(id, b1.Proof) {
- t.Fatal("Could not verify st1 with c1, plus=true case")
- }
- if !b2.Commitment.Verify(id, b2.Proof) {
- t.Fatal("Could not verify st2 with c2, plus=false case")
- }
-
- // Use the wrong proof
- if b2.Commitment.Verify(id, b1.Proof) {
- t.Fatal("Verify with wrong proof should have failed!")
- }
-
- // Use the wrong Id
- x := Curve.RandomScalar()
- if b1.Commitment.Verify(x, b2.Proof) || b2.Commitment.Verify(x, b2.Proof) {
- t.Fatal("Verify with wrong id should have failed!")
- }
-}
diff --git a/nizk/doc.go b/nizk/doc.go
deleted file mode 100644
index 1df58d4..0000000
--- a/nizk/doc.go
+++ /dev/null
@@ -1,7 +0,0 @@
-package nizk
-
-/*
-
-This is an implementation of... TODO
-
-*/
diff --git a/nizk/schnorr/schnorr.go b/nizk/schnorr/schnorr.go
deleted file mode 100644
index ad42770..0000000
--- a/nizk/schnorr/schnorr.go
+++ /dev/null
@@ -1,77 +0,0 @@
-// Proof of knowledge of a for given A = G^a
-
-package schnorr
-
-import (
- . "kesim.org/seal/common"
-)
-
-type Statement Scalar
-
-type Commitment Point
-
-// A Schnorr signature to prove knowledge of v for given g^v.
-// 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 {
- V *Point `json:"V"`
- R *Scalar `json:"r"`
-}
-
-// Generates a commitment
-
-// 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 (s *Statement) Proof(id Bytes) (pr *Proof) {
- x := (*Scalar)(s)
-
- // choose random v
- v := Curve.RandomScalar()
-
- pr = &Proof{}
-
- // calculate g^v
- pr.V = Curve.Exp(v)
-
- // calculate g^x
- gx := G.Exp(x)
-
- // calculate h := H(g, g^v, g^x, i)
- h := Challenge(pr.V, gx, id)
-
- // Calculate r := v - x*h
- xh := x.Mul(h)
- r := v.Sub(xh)
- pr.R = r
-
- return pr
-}
-
-// Verifies that g^v == g^r*g^(x*h)
-func (c *Commitment) Verify(p *Proof, id Bytes) bool {
- Gx := (*Point)(c)
-
- // Calculate h = H(g, g^v, g^x, id)
- h := Challenge(p.V, Gx, id)
-
- // Calculate g^(x*h) = (g^x)^h
- gxh := Gx.Exp(h)
-
- // Calculate g^r
- gr := G.Exp(p.R)
-
- // Calculate g^r*g^(x*h)
- grgxh := gr.Mul(gxh)
-
- // Return true if g^v == g^r*g^(x*h)
- return p.V.Equal(grgxh)
-}
diff --git a/nizk/schnorr/schnorr_test.go b/nizk/schnorr/schnorr_test.go
deleted file mode 100644
index 2adec8e..0000000
--- a/nizk/schnorr/schnorr_test.go
+++ /dev/null
@@ -1,34 +0,0 @@
-package schnorr
-
-import (
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-func TestSchnorr(t *testing.T) {
- a, e := Curve.ScalarFromReader(nil)
- if e != nil {
- t.Fatal(e)
- }
- A := G.Exp(a)
-
- id, e := Curve.ScalarFromReader(nil)
- if e != nil {
- t.Fatal(e)
- }
- ID := G.Exp(id)
-
- s := (*Statement)(a)
- c := (*Commitment)(A)
-
- pr := s.Proof(ID)
-
- if !c.Verify(pr, ID) {
- t.Fatalf("Verification failed!")
- }
-
- if c.Verify(pr, ID.Exp(a)) {
- t.Fatal("Verification didn't fail!")
- }
-}
diff --git a/nizk/stage1.go b/nizk/stage1.go
deleted file mode 100644
index f58a4ac..0000000
--- a/nizk/stage1.go
+++ /dev/null
@@ -1,196 +0,0 @@
-package nizk
-
-import (
- . "kesim.org/seal/common"
-)
-
-type Stage struct {
- x *Scalar
- r *Scalar
-
- *StageCommitment
- *StageReveal
- Sent bool
-}
-
-type StageCommitment struct {
- R *Point
- X *Point
-}
-
-type StageReveal struct {
- Y *Point
- Z *Point
-}
-
-// Represents the proof of statements of the following form:
-//
-// [ Z=g^(xy) && X=g^x && Y=g^y && C=g^(αβ) && A=g^α && B=g^β ]
-// || [ Z=g^(xr) && X=g^x && R=g^r && C=g^(αβ+1) && A=g^α && B=g^β ]
-//
-// for given Z, X, Y, R, C, A and B
-type Stage1Proof struct {
- Ch [2]*Scalar
- Rho [2][2]*Scalar
-}
-
-func (b *Bit) stage(x, r *Scalar) {
- b.Stage = &Stage{
- x: x,
- r: r,
- }
-}
-
-func (s *Stage) commit() *StageCommitment {
- if s.StageCommitment != nil {
- return s.StageCommitment
- }
-
- s.StageCommitment = &StageCommitment{
- X: G.Exp(s.x),
- R: G.Exp(s.r),
- }
- return s.StageCommitment
-}
-
-func (b *Bit) StageCommit() (s *StageCommitment) {
- if b.Stage != nil {
- return b.Stage.StageCommitment
- }
- x := Curve.RandomScalar()
- r := Curve.RandomScalar()
- return b.StageFromScalars(x, r)
-}
-
-func (b *Bit) StageFromScalars(x, r *Scalar) (c *StageCommitment) {
- b.stage(x, r)
- return b.Stage.commit()
-}
-
-func (b *Bit) reveal(prev_true bool, Xs ...*Point) (r *StageReveal) {
- s := b.Stage
-
- // Calculate Y based on the Xs and our own X_i
- // as Π_(i<k) X_k / Π_(i>k) X_k
- // (basically leaving our own X_i out in the calculation).
- // We are assuming that Xs is ordered already.
- Y := Curve.Identity()
- found := false
- for _, X := range Xs {
- if !found && X.Equal(b.Stage.X) {
- found = true
- continue
- }
- if !found {
- Y = Y.Mul(X)
- } else {
- Y = Y.Div(X)
- }
- }
- if !found {
- panic("own X not found in Xs")
- }
-
- r = &StageReveal{Y: Y}
-
- if prev_true && b.IsSet() {
- r.Z = s.R.Exp(s.x)
- s.Sent = true
- } else {
- r.Z = Y.Exp(s.x)
- s.Sent = false
- }
-
- return r
-}
-
-func (b *Bit) RevealStage1(Xs ...*Point) (rev *StageReveal, pr *Stage1Proof) {
- if b.Stage == nil {
- b.StageCommit()
- }
- s := b.Stage
-
- var ε [2][4]*Point
- var r1, r2, ρ1, ρ2, ω *Scalar
- for _, s := range []**Scalar{&r1, &r2, &ρ1, &ρ2, &ω} {
- *s = Curve.RandomScalar()
- }
- c := s.commit()
-
- rev = b.reveal(true, Xs...)
-
- if b.IsSet() {
- ε[0][0] = G.Exp(r1).Mul(c.X.Exp(ω))
- ε[0][1] = G.Exp(r2).Mul(b.A.Exp(ω))
- ε[0][2] = rev.Y.Exp(r1).Mul(rev.Z.Exp(ω))
- ε[0][3] = b.B.Exp(r2).Mul(b.C.Exp(ω))
- ε[1][0] = G.Exp(ρ1)
- ε[1][1] = G.Exp(ρ2)
- ε[1][2] = c.R.Exp(ρ1)
- ε[1][3] = b.B.Exp(ρ2)
- } else {
- ε[0][0] = G.Exp(r1)
- ε[0][1] = G.Exp(r2)
- ε[0][2] = rev.Y.Exp(r1)
- ε[0][3] = b.B.Exp(r2)
- ε[1][0] = G.Exp(ρ1).Mul(c.X.Exp(ω))
- ε[1][1] = G.Exp(ρ2).Mul(b.A.Exp(ω))
- ε[1][2] = c.R.Exp(ρ1).Mul(rev.Z.Exp(ω))
- ε[1][3] = b.B.Exp(ρ2).Mul(b.C.Div(G).Exp(ω))
- }
-
- p := []Bytes{G, b.A, b.B, b.C, c.R, c.X, rev.Y, rev.Z}
- for _, ε := range ε[0] {
- p = append(p, ε)
- }
- for _, ε := range ε[1] {
- p = append(p, ε)
- }
-
- ch := Challenge(p...)
- pr = &Stage1Proof{}
-
- if b.IsSet() {
- pr.Ch[0] = ω
- pr.Ch[1] = ch.Sub(ω)
- pr.Rho[0][0] = r1
- pr.Rho[0][1] = r2
- pr.Rho[1][0] = ρ1.Sub(s.x.Mul(pr.Ch[1]))
- pr.Rho[1][1] = ρ2.Sub(b.α.Mul(pr.Ch[1]))
- } else {
- pr.Ch[0] = ch.Sub(ω)
- pr.Ch[1] = ω
- pr.Rho[0][0] = r1.Sub(s.x.Mul(pr.Ch[0]))
- pr.Rho[0][1] = r2.Sub(b.α.Mul(pr.Ch[0]))
- pr.Rho[1][0] = ρ1
- pr.Rho[1][1] = ρ2
- }
-
- s.StageReveal = rev
- return rev, pr
-}
-
-func (c *Commitment) VerifyStage1(sc *StageCommitment, r *StageReveal, p *Stage1Proof) bool {
- var ε [2][4]*Point
-
- ε[0][0] = G.Exp(p.Rho[0][0]).Mul(sc.X.Exp(p.Ch[0]))
- ε[0][1] = G.Exp(p.Rho[0][1]).Mul(c.A.Exp(p.Ch[0]))
- ε[0][2] = r.Y.Exp(p.Rho[0][0]).Mul(r.Z.Exp(p.Ch[0]))
- ε[0][3] = c.B.Exp(p.Rho[0][1]).Mul(c.C.Exp(p.Ch[0]))
- ε[1][0] = G.Exp(p.Rho[1][0]).Mul(sc.X.Exp(p.Ch[1]))
- ε[1][1] = G.Exp(p.Rho[1][1]).Mul(c.A.Exp(p.Ch[1]))
- ε[1][2] = sc.R.Exp(p.Rho[1][0]).Mul(r.Z.Exp(p.Ch[1]))
- ε[1][3] = c.B.Exp(p.Rho[1][1]).Mul(c.C.Div(G).Exp(p.Ch[1]))
-
- points := []Bytes{G, c.A, c.B, c.C, sc.R, sc.X, r.Y, r.Z}
- for _, e := range ε[0] {
- points = append(points, e)
- }
- for _, e := range ε[1] {
- points = append(points, e)
- }
-
- ch := Challenge(points...)
-
- return p.Ch[0].Add(p.Ch[1]).Equal(ch)
-}
diff --git a/nizk/stage1_test.go b/nizk/stage1_test.go
deleted file mode 100644
index d17956d..0000000
--- a/nizk/stage1_test.go
+++ /dev/null
@@ -1,56 +0,0 @@
-package nizk
-
-import (
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-func TestStage1Simple(t *testing.T) {
- id := Curve.RandomScalar()
- b1 := NewBit(id, true)
- b2 := NewBit(id, false)
-
- c1 := b1.StageCommit()
- c2 := b2.StageCommit()
- r1, pr1 := b1.RevealStage1(c1.X, c2.X)
- r2, pr2 := b2.RevealStage1(c2.X)
- if !b1.Commitment.VerifyStage1(c1, r1, pr1) {
- t.Fatal("Could not verify st1 with c1 and pr1, plus=true case")
- }
- if !b2.Commitment.VerifyStage1(c2, r2, pr2) {
- t.Fatal("Could not verify st2 with c2 and pr2, plus=false case")
- }
- // Wrong proof test
- if b1.Commitment.VerifyStage1(c1, r1, pr2) {
- t.Fatal("Shouldn't be able to verify c1 with pr2")
- }
-}
-
-func TestStage1FromScalars(t *testing.T) {
- var id, α, β, x, r *Scalar
- for _, s := range []**Scalar{&id, &α, &β, &x, &r} {
- *s = Curve.RandomScalar()
- }
-
- b1 := NewBitFromScalars(id, true, α, β)
- b2 := NewBitFromScalars(id, false, α, β)
-
- c1 := b1.StageFromScalars(r, x)
- c2 := b2.StageFromScalars(x, r)
- r1, pr1 := b1.RevealStage1(c1.X)
- r2, pr2 := b2.RevealStage1(c2.X)
- if !b1.Commitment.VerifyStage1(c1, r1, pr1) {
- t.Fatal("Could not verify st1 with c1 and pr1, plus=true case")
- }
- if !b2.Commitment.VerifyStage1(c2, r2, pr2) {
- t.Fatal("Could not verify st2 with c2 and pr2, plus=false case")
- }
- // Wrong proof test
- if b2.Commitment.VerifyStage1(c1, r1, pr2) ||
- b1.Commitment.VerifyStage1(c2, r2, pr2) ||
- b2.Commitment.VerifyStage1(c1, r1, pr2) ||
- b2.Commitment.VerifyStage1(c2, r2, pr1) {
- t.Fatal("Shouldn't be able to verify bc_i with c_j or pr_j")
- }
-}
diff --git a/nizk/stage2.go b/nizk/stage2.go
deleted file mode 100644
index d5e8070..0000000
--- a/nizk/stage2.go
+++ /dev/null
@@ -1,221 +0,0 @@
-package nizk
-
-import (
- . "kesim.org/seal/common"
-)
-
-// Represents the proof of a statement of the following form:
-//
-// ( Z=g^(x*y) && X=g^x && Y=g^y && Z_=g^(x_*y_) && X_=g^x_ && Y_=g^y_ ) // case "lost"
-// || ( Z=g^(x*y) && X=g^x && Y=g^y && Z_=g^(x_*r_) && X_=g^x_ && R_=g^r_ && C=g^(a*b) && A=g^a && B=g^b ) // case "unset"
-// || ( Z=g^(x*r) && X=g^x && R=g^r && Z_=g^(x_*r_) && X_=g^x_ && R_=g^r_ && C=g^(a*b+1) && A=g^a && B=g^b ) // case "set"
-//
-// for given A, B, C, R, X, Y, Z, R_, X_, Y_, Z_ on the curve
-type Stage2Proof struct {
- Ch [3]*Scalar
- R1 [3]*Scalar
- R2 [3]*Scalar
- R3 [2]*Scalar
-}
-
-func (b *Bit) RevealStage2(lost bool, prev *Bit, Xs ...*Point) (rv2 *StageReveal, pr *Stage2Proof) {
- if b.Stage == nil {
- b.StageCommit()
- }
- s := b.Stage
-
- var (
- ε1, ε1_ [3]Bytes
- ε2, ε2_ [3]Bytes
- ε3, ε3_ [2]Bytes
-
- ρ1, ρ2 [3]*Scalar
- ρ3 [2]*Scalar
- ω [2]*Scalar
- )
-
- for _, s := range [][]*Scalar{ρ1[:], ρ2[:], ρ3[:], ω[:]} {
- for i := range s {
- s[i] = Curve.RandomScalar()
- }
- }
-
- c1 := prev.StageCommitment
- c2 := s.StageCommitment
- rv1 := prev.StageReveal
- b.StageReveal = b.reveal(prev.Sent, Xs...)
- rv2 = b.StageReveal
-
- if lost {
- ε1[0] = G.Exp(ρ1[0]).Mul(c2.X.Exp(ω[0]))
- ε1[1] = G.Exp(ρ1[1]).Mul(c1.X.Exp(ω[0]))
- ε1[2] = G.Exp(ρ1[2]).Mul(b.A.Exp(ω[0]))
-
- ε1_[0] = c2.R.Exp(ρ1[0]).Mul(rv2.Z.Exp(ω[0]))
- ε1_[1] = c1.R.Exp(ρ1[1]).Mul(rv1.Z.Exp(ω[0]))
- ε1_[2] = b.B.Exp(ρ1[2]).Mul(b.C.Div(G).Exp(ω[0]))
-
- ε2[0] = G.Exp(ρ2[0]).Mul(c2.X.Exp(ω[1]))
- ε2[1] = G.Exp(ρ2[1]).Mul(c1.X.Exp(ω[1]))
- ε2[2] = G.Exp(ρ2[2]).Mul(b.A.Exp(ω[1]))
-
- ε2_[0] = rv2.Y.Exp(ρ2[0]).Mul(rv2.Z.Exp(ω[1]))
- ε2_[1] = c1.R.Exp(ρ2[1]).Mul(rv1.Z.Exp(ω[1]))
- ε2_[2] = b.B.Exp(ρ2[2]).Mul(b.C.Exp(ω[1]))
-
- ε3[0] = G.Exp(ρ3[0])
- ε3[1] = G.Exp(ρ3[1])
-
- ε3_[0] = rv2.Y.Exp(ρ3[0])
- ε3_[1] = rv1.Y.Exp(ρ3[1])
- } else {
- if b.IsSet() {
- ε1[0] = G.Exp(ρ1[0])
- ε1[1] = G.Exp(ρ1[1])
- ε1[2] = G.Exp(ρ1[2])
-
- ε1_[0] = c2.R.Exp(ρ1[0])
- ε1_[1] = c1.R.Exp(ρ1[1])
- ε1_[2] = b.B.Exp(ρ1[2])
-
- ε2[0] = G.Exp(ρ2[0]).Mul(c2.X.Exp(ω[0]))
- ε2[1] = G.Exp(ρ2[1]).Mul(c1.X.Exp(ω[0]))
- ε2[2] = G.Exp(ρ2[2]).Mul(b.A.Exp(ω[0]))
-
- ε2_[0] = rv2.Y.Exp(ρ2[0]).Mul(rv2.Z.Exp(ω[0]))
- ε2_[1] = c1.R.Exp(ρ2[1]).Mul(rv1.Z.Exp(ω[0]))
- ε2_[2] = b.B.Exp(ρ2[2]).Mul(b.C.Exp(ω[0]))
-
- ε3[0] = G.Exp(ρ3[0]).Mul(c2.X.Exp(ω[1]))
- ε3[1] = G.Exp(ρ3[1]).Mul(c1.X.Exp(ω[1]))
-
- ε3_[0] = rv2.Y.Exp(ρ3[0]).Mul(rv2.Z.Exp(ω[1]))
- ε3_[1] = rv1.Y.Exp(ρ3[1]).Mul(rv1.Z.Exp(ω[1]))
- } else {
- ε1[0] = G.Exp(ρ1[0]).Mul(c2.X.Exp(ω[0]))
- ε1[1] = G.Exp(ρ1[1]).Mul(c1.X.Exp(ω[0]))
- ε1[2] = G.Exp(ρ1[2]).Mul(b.A.Exp(ω[0]))
-
- ε1_[0] = c2.R.Exp(ρ1[0]).Mul(rv2.Z.Exp(ω[0]))
- ε1_[1] = c1.R.Exp(ρ1[1]).Mul(rv1.Z.Exp(ω[0]))
- ε1_[2] = b.B.Exp(ρ1[2]).Mul(b.C.Div(G).Exp(ω[0]))
-
- ε2[0] = G.Exp(ρ2[0])
- ε2[1] = G.Exp(ρ2[1])
- ε2[2] = G.Exp(ρ2[2])
-
- ε2_[0] = rv2.Y.Exp(ρ2[0])
- ε2_[1] = c1.R.Exp(ρ2[1])
- ε2_[2] = b.B.Exp(ρ2[2])
-
- ε3[0] = G.Exp(ρ3[0]).Mul(c2.X.Exp(ω[1]))
- ε3[1] = G.Exp(ρ3[1]).Mul(c1.X.Exp(ω[1]))
-
- ε3_[0] = rv2.Y.Exp(ρ3[0]).Mul(rv2.Z.Exp(ω[1]))
- ε3_[1] = rv1.Y.Exp(ρ3[1]).Mul(rv1.Z.Exp(ω[1]))
- }
- }
-
- points := []Bytes{G, b.A, b.B, b.C, c2.R, c2.X, rv2.Y, rv2.Z, c1.R, c1.X, rv1.Y, rv1.Z}
- points = append(points, ε1[:]...)
- points = append(points, ε2[:]...)
- points = append(points, ε3[:]...)
- points = append(points, ε1_[:]...)
- points = append(points, ε2_[:]...)
- points = append(points, ε3_[:]...)
-
- ch := Challenge(points...)
- pr = &Stage2Proof{}
-
- if lost {
- pr.Ch[0] = ω[0]
- pr.Ch[1] = ω[1]
- pr.Ch[2] = ch.Sub(ω[0]).Sub(ω[1])
-
- pr.R1[0] = ρ1[0]
- pr.R1[1] = ρ1[1]
- pr.R1[2] = ρ1[2]
-
- pr.R2[0] = ρ2[0]
- pr.R2[1] = ρ2[1]
- pr.R2[2] = ρ2[2]
-
- pr.R3[0] = ρ3[0].Sub(s.x.Mul(pr.Ch[2]))
- pr.R3[1] = ρ3[1].Sub(prev.x.Mul(pr.Ch[2]))
- } else {
- if b.IsSet() {
- pr.Ch[0] = ch.Sub(ω[0]).Sub(ω[1])
- pr.Ch[1] = ω[0]
- pr.Ch[2] = ω[1]
-
- pr.R1[0] = ρ1[0].Sub(s.x.Mul(pr.Ch[0]))
- pr.R1[1] = ρ1[1].Sub(prev.x.Mul(pr.Ch[0]))
- pr.R1[2] = ρ1[2].Sub(b.α.Mul(pr.Ch[0]))
-
- pr.R2[0] = ρ2[0]
- pr.R2[1] = ρ2[1]
- pr.R2[2] = ρ2[2]
-
- pr.R3[0] = ρ3[0]
- pr.R3[1] = ρ3[1]
- } else {
- pr.Ch[0] = ω[0]
- pr.Ch[1] = ch.Sub(ω[0]).Sub(ω[1])
- pr.Ch[2] = ω[1]
-
- pr.R1[0] = ρ1[0]
- pr.R1[1] = ρ1[1]
- pr.R1[2] = ρ1[2]
-
- pr.R2[0] = ρ2[0].Sub(s.x.Mul(pr.Ch[1]))
- pr.R2[1] = ρ2[1].Sub(prev.x.Mul(pr.Ch[1]))
- pr.R2[2] = ρ2[2].Sub(b.α.Mul(pr.Ch[1]))
-
- pr.R3[0] = ρ3[0]
- pr.R3[1] = ρ3[1]
- }
- }
-
- return rv2, pr
-}
-
-func (c *Commitment) VerifyStage2(c1, c2 *StageCommitment, r1, r2 *StageReveal, p *Stage2Proof) bool {
- var (
- e1, e1_ [3]Bytes
- e2, e2_ [3]Bytes
- e3, e3_ [2]Bytes
- )
- e1[0] = G.Exp(p.R1[0]).Mul(c2.X.Exp(p.Ch[0]))
- e1[1] = G.Exp(p.R1[1]).Mul(c1.X.Exp(p.Ch[0]))
- e1[2] = G.Exp(p.R1[2]).Mul(c.A.Exp(p.Ch[0]))
-
- e1_[0] = c2.R.Exp(p.R1[0]).Mul(r2.Z.Exp(p.Ch[0]))
- e1_[1] = c1.R.Exp(p.R1[1]).Mul(r1.Z.Exp(p.Ch[0]))
- e1_[2] = c.B.Exp(p.R1[2]).Mul(c.C.Div(G).Exp(p.Ch[0]))
-
- e2[0] = G.Exp(p.R2[0]).Mul(c2.X.Exp(p.Ch[1]))
- e2[1] = G.Exp(p.R2[1]).Mul(c1.X.Exp(p.Ch[1]))
- e2[2] = G.Exp(p.R2[2]).Mul(c.A.Exp(p.Ch[1]))
-
- e2_[0] = r2.Y.Exp(p.R2[0]).Mul(r2.Z.Exp(p.Ch[1]))
- e2_[1] = c1.R.Exp(p.R2[1]).Mul(r1.Z.Exp(p.Ch[1]))
- e2_[2] = c.B.Exp(p.R2[2]).Mul(c.C.Exp(p.Ch[1]))
-
- e3[0] = G.Exp(p.R3[0]).Mul(c2.X.Exp(p.Ch[2]))
- e3[1] = G.Exp(p.R3[1]).Mul(c1.X.Exp(p.Ch[2]))
-
- e3_[0] = r2.Y.Exp(p.R3[0]).Mul(r2.Z.Exp(p.Ch[2]))
- e3_[1] = r1.Y.Exp(p.R3[1]).Mul(r1.Z.Exp(p.Ch[2]))
-
- points := []Bytes{G, c.A, c.B, c.C, c2.R, c2.X, r2.Y, r2.Z, c1.R, c1.X, r1.Y, r1.Z}
- points = append(points, e1[:]...)
- points = append(points, e2[:]...)
- points = append(points, e3[:]...)
- points = append(points, e1_[:]...)
- points = append(points, e2_[:]...)
- points = append(points, e3_[:]...)
-
- ch := Challenge(points...)
-
- return p.Ch[0].Add(p.Ch[1]).Add(p.Ch[2]).Equal(ch)
-}
diff --git a/nizk/stage2_test.go b/nizk/stage2_test.go
deleted file mode 100644
index a22fa94..0000000
--- a/nizk/stage2_test.go
+++ /dev/null
@@ -1,267 +0,0 @@
-package nizk
-
-import (
- "slices"
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-func TestStage2Simple1(t *testing.T) {
- id := Curve.RandomScalar()
-
- for _, lost := range []bool{true, false} {
- b1 := NewBit(id, !lost)
- c1 := b1.StageCommit()
- r1, _ := b1.RevealStage1(c1.X)
-
- // Because the first index is a junction, any subsequent
- // combination of Bits must verify with 'lost' set to true
- // in the RevealStage2 calls.
- for _, s := range [][2]bool{
- {false, false},
- {true, false},
- {false, true},
- {true, true},
- } {
- b2 := NewBit(id, s[0])
- b3 := NewBit(id, s[1])
- b4 := NewBit(id, s[1]) // same as b3
-
- c2 := b2.StageCommit()
- c3 := b3.StageCommit()
- c4 := b4.StageCommit()
-
- r2, p2 := b2.RevealStage2(lost, b1, c1.X, c2.X, c3.X)
- if !b2.Commitment.VerifyStage2(c1, c2, r1, r2, p2) {
- t.Fatalf("failed to verify b2: %t b3: %t bc2/b1", s[0], s[1])
- }
-
- r3, p3 := b3.RevealStage2(lost, b1, c1.X, c2.X, c3.X)
- if !b3.Commitment.VerifyStage2(c1, c3, r1, r3, p3) {
- t.Fatalf("failed to verify b1: %t b3: %t bc3/b1", s[0], s[1])
- }
-
- r4, p4 := b4.RevealStage2(lost, b1, c1.X, c2.X, c3.X, c4.X)
- if !b4.Commitment.VerifyStage2(c1, c4, r1, r4, p4) {
- t.Fatalf("failed to verify b1: %t b4: %t bc4/b1", s[0], s[1])
- }
- }
- }
-}
-
-func int2bits(bid int, bitlength int) []*Bit {
- id := Curve.RandomScalar()
-
- bits := make([]*Bit, bitlength)
- for i := range bitlength {
- bits[i] = NewBit(id, (bid>>bitlength-i)&1 != 0)
- }
- return bits
-}
-
-func TestStage2Complex(t *testing.T) {
- bid1 := 0b0101
- bid2 := 0b0010
- t.Logf("testing bid1: %05b vs. bid2: %05b", bid1, bid2)
-
- bitlength := 4
-
- bits1 := int2bits(bid1, bitlength)
- bits2 := int2bits(bid2, bitlength)
-
- lost1 := false
- lost2 := false
-
- if len(bits1) != len(bits2) || len(bits1) != bitlength {
- t.Fatalf("oops")
- }
-
- instage1 := true
- junction := -1
- result := 0
-
- for c := 0; c < len(bits1); c++ {
- b1 := bits1[c]
- b2 := bits2[c]
-
- c1 := b1.StageCommit()
- c2 := b2.StageCommit()
-
- if instage1 {
- t.Logf("Testing bit b1[%d] = %t vs b2[%d] = %t", c, b1.IsSet(), c, b2.IsSet())
-
- r1, p1 := b1.RevealStage1(c1.X, c2.X)
- r2, p2 := b2.RevealStage1(c1.X, c2.X)
-
- if !b1.Commitment.VerifyStage1(c1, r1, p1) {
- t.Fatalf("b1 commitment failed to verify in stage1")
- }
- if !b2.Commitment.VerifyStage1(c2, r2, p2) {
- t.Fatalf("b2 commitment failed to verify in stage1")
- }
-
- Z := Curve.Product(r1.Z, r2.Z)
- if !Id.Equal(Z) {
- t.Logf("Aha! Z[%d] != Id, switch to stage2", c)
- junction = c
- instage1 = false
-
- if !lost1 && !b1.IsSet() {
- t.Logf("setting lost1 to true")
- lost1 = true
- }
-
- if !lost2 && !b2.IsSet() {
- t.Logf("setting lost2 to true")
- lost2 = true
- }
- result |= 1 << (bitlength - 1 - c)
- } else {
- t.Logf("Z[%d] == Id, staying in stage1", c)
- }
- } else {
- t.Logf("Testing bit b1[%d]∧lost1 = %t vs b2[%d]∧lost2 = %t", c, b1.IsSet() && !lost1, c, b2.IsSet() && !lost2)
-
- bj1 := bits1[junction]
- bj2 := bits2[junction]
-
- r1, p1 := b1.RevealStage2(lost1, bj1, c1.X, c2.X)
- r2, p2 := b2.RevealStage2(lost2, bj2, c1.X, c2.X)
-
- if !b1.Commitment.VerifyStage2(bj1.StageCommitment, c1, bj1.StageReveal, r1, p1) {
- t.Fatalf("b1 commitment failed to verify in stage1")
- }
- if !b2.Commitment.VerifyStage2(bj2.StageCommitment, c2, bj2.StageReveal, r2, p2) {
- t.Fatalf("b2 commitment failed to verify in stage1")
- }
-
- Z := Curve.Product(r1.Z, r2.Z)
- if !Id.Equal(Z) {
- t.Logf("Aha! Z[%d] != Id, new junction!", c)
- junction = c
-
- if !lost1 && !b1.IsSet() {
- t.Logf("setting lost1 to true")
- lost1 = true
- }
-
- if !lost2 && !b2.IsSet() {
- t.Logf("setting lost2 to true")
- lost2 = true
- }
- result |= 1 << (bitlength - 1 - c)
- }
- }
- }
- if result != bid1 {
- t.Fatalf("wrong result: %05b", result)
- }
-}
-
-func TestFromPaper(t *testing.T) {
- bitlength := 5
- vals := []int{
- 0b01001,
- 0b01010,
- 0b00111,
- }
-
- t.Logf("testing bits: %05b, %05b, %05b", vals[0], vals[1], vals[2])
-
- var bits = [3][]*Bit{}
- for i, b := range vals {
- bits[i] = int2bits(b, bitlength)
- }
-
- var lost = [3]bool{}
- instage1 := true
- junction := -1
- result := 0
-
- for idx := 0; idx < bitlength; idx++ {
- var c = [3]*StageCommitment{}
- var r = [3]*StageReveal{}
-
- for i, b := range bits {
- c[i] = b[idx].StageCommit()
- }
-
- if instage1 {
- t.Logf("bit[%d] b1 = %t vs b2 = %t vs b3 = %t", idx,
- bits[0][idx].IsSet(), bits[1][idx].IsSet(), bits[2][idx].IsSet())
-
- var p = [3]*Stage1Proof{}
- for i := range bits {
- r[i], p[i] = bits[i][idx].RevealStage1(c[0].X, c[1].X, c[2].X)
- t.Logf("bits[%d][%d] has sent %t", i, idx, bits[i][idx].Sent)
- if !bits[i][idx].Commitment.VerifyStage1(c[i], r[i], p[i]) {
- t.Fatalf("bits[%d][%d] commitment failed to verify in stage1", i, idx)
- }
- }
-
- Z := Curve.Product(r[0].Z, r[1].Z, r[2].Z)
- if !Id.Equal(Z) {
- t.Logf("Aha! Z[%d] != Id, switch to stage2", idx)
- junction = idx
- instage1 = false
-
- for i := range bits {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- t.Logf("bit %d, set lost[%d] to true, so far: %v", idx, i, lost)
- }
- }
- result |= 1 << (bitlength - 1 - idx)
- } else {
- t.Logf("Z[%d] == Id, staying in stage1", idx)
- }
- } else {
- t.Logf("\nTesing bit[%d]:\n"+
- "set 0: %t\t1: %t\t2: %t\n"+
- "lost 0: %t\t1 %t\t2: %t\n",
- idx,
- bits[0][idx].IsSet(), bits[1][idx].IsSet(), bits[2][idx].IsSet(),
- lost[0], lost[1], lost[2])
-
- var bj = [3]*Bit{}
- for i := range bits {
- bj[i] = bits[i][junction]
- }
-
- var p = [3]*Stage2Proof{}
- for i := range bits {
- r[i], p[i] = bits[i][idx].RevealStage2(lost[i], bj[i], c[0].X, c[1].X, c[2].X)
- t.Logf("bits[%d][%d] has sent %t", i, idx, bits[i][idx].Sent)
- if !bits[i][idx].Commitment.VerifyStage2(bj[i].StageCommitment, c[i], bj[i].StageReveal, r[i], p[i]) {
- t.Fatalf("bits[%d][%d] commitment failed to verify in stage2, result so far: %05b", i, idx, result)
- }
- }
-
- Z := Curve.Product(r[0].Z, r[1].Z, r[2].Z)
- if !Id.Equal(Z) {
- t.Logf("Aha! Z[%d] != Id, new junction!", idx)
- junction = idx
-
- for i := range bits {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- t.Logf("bits[%d][%d], set lost[%d] to true, so far: %v", i, idx, i, lost)
- }
- }
- result |= 1 << (bitlength - 1 - idx)
- }
- }
- }
- max := slices.Max(vals)
- if result != max {
- t.Fatalf("wrong result: %05b, expected: %05b", result, max)
- }
-
-}
-
-/*
-func TestRun3on5bit(t *testing.T) { runSeal(3, 5, t) }
-func TestRun10on16bit(t *testing.T) { runSeal(10, 16, t) }
-func TestRun100on16bit(t *testing.T) { runSeal(100, 16, t) }
-*/
diff --git a/nizk/vickrey_test.go b/nizk/vickrey_test.go
deleted file mode 100644
index 089e389..0000000
--- a/nizk/vickrey_test.go
+++ /dev/null
@@ -1,209 +0,0 @@
-package nizk
-
-import (
- "math/rand"
- "slices"
- "strings"
- "sync"
- "sync/atomic"
- "testing"
-
- . "kesim.org/seal/common"
-)
-
-type stage int
-
-const (
- stage1 stage = iota
- stage2
-)
-
-func (s stage) String() string {
- if s == stage1 {
- return "stage1"
- }
- return "stage2"
-}
-
-func runVickrey(n int, bitlength int, tb testing.TB) {
- var vals = make([]int, n)
- var ids = make([]Bytes, n)
- for i := range n {
- vals[i] = rand.Intn(1<<(bitlength-1) - 1)
- ids[i] = Curve.RandomScalar()
- }
- max := slices.Max(vals)
- max_idx := slices.Index(vals, max)
- max2 := slices.Max(slices.Delete(slices.Clone(vals), max_idx, max_idx+1))
- if max == max2 {
- max_idx = -1
- }
-
- tb.Logf("running vickrey for vals:\n%0[1]*[2]b\nmax: %0[1]*[3]b, max2: %0[1]*[4]b, winner: %d\n", bitlength, vals, max, max2, max_idx)
-
- var bits = make([][]*Bit, n)
- for i, b := range vals {
- bits[i] = Int2Bits(ids[i], b, bitlength)
- }
-
- var c = make([]*StageCommitment, n)
- var Xs = make([]*Point, n)
- var r = make([]*StageReveal, n)
- var p1 = make([]*Stage1Proof, n)
- var Zs = make([]*Point, n)
- var bj = make([]*Bit, n)
- var p2 = make([]*Stage2Proof, n)
- var lost = make([]bool, n)
- stage := stage1
- junction := -1
- winner := -1
- result := 0
-
- isWinner := func(Z *Point, i int, idx int) bool {
- z := Z.Div(Zs[i])
- xu := Curve.Identity()
- xl := Curve.Identity()
- found := false
-
- for k := range n {
- if k == winner {
- continue
- }
- if k < i {
- xu = xu.Mul(Xs[k])
- } else if k > i {
- xl = xl.Mul(Xs[k])
- }
- }
- xu = xu.Exp(bits[i][idx].Stage.x)
- xl = xl.Exp(bits[i][idx].Stage.x)
- x := xu.Div(xl)
-
- if x.Equal(z) {
- tb.Logf("equal by value")
- found = true
- }
-
- if winner < 0 {
- // BUG! TODO!
- s1 := x.String()
- s2 := z.String()
- if strings.HasPrefix(s1, s2[:len(s2)-2]) {
- tb.Logf("BUG! TODO! equal only by string")
- found = true
- }
- }
- // tb.Logf("testing max_idx %d, i %d, bit %d:\n%v vs %v", max_idx, i, idx, x, z)
- return found
- }
-
- for idx := range bitlength {
- for i := range n {
- if i == winner {
- Xs[i] = Id
- Zs[i] = Id
- continue
- }
- c[i] = bits[i][idx].StageCommit()
- Xs[i] = c[i].X
- if stage == stage2 {
- bj[i] = bits[i][junction]
- }
- }
-
- var wg sync.WaitGroup
- wg.Add(n)
- fail := &atomic.Bool{}
- for i := range n {
- if i == winner {
- tb.Logf("%s, idx: %d, skipping winner %d", stage, idx, winner)
- wg.Done()
- continue
- }
- go func(i int) {
- defer wg.Done()
- if stage == stage1 {
- r[i], p1[i] = bits[i][idx].RevealStage1(Xs...)
- if !bits[i][idx].Commitment.VerifyStage1(c[i], r[i], p1[i]) {
- fail.Store(true)
- tb.Fatalf("bits[i: %d][idx: %d] commitment failed to verify in stage1", i, idx)
- }
- } else {
- r[i], p2[i] = bits[i][idx].RevealStage2(lost[i], bj[i], Xs...)
- if !bits[i][idx].Commitment.VerifyStage2(bj[i].StageCommitment, c[i], bj[i].StageReveal, r[i], p2[i]) {
- fail.Store(true)
- tb.Fatalf("bits[i: %d][idx: %d] (junction: %d) verify failed in stage2, lost: %t, result so far: %05b\nXs: %v", i, idx, junction, lost[i], result, Xs)
- }
- }
- Zs[i] = r[i].Z
- }(i)
- }
- wg.Wait()
- if fail.Load() {
- tb.Fail()
- return
- }
-
- Z := Curve.Product(Zs...)
- tb.Logf("Z[idx: %d]: %v", idx, Z)
- reset := false
- if !Id.Equal(Z) {
- var lost_round = make([]bool, n)
- for i := range n {
- if i == winner {
- continue
- }
- if !lost[i] && !bits[i][idx].IsSet() {
- lost_round[i] = true
- }
-
- // Winner test
- if winner < 0 && !lost_round[i] && !lost[i] {
- reset = isWinner(Z, i, idx)
- if reset {
- tb.Logf("found winner %d %s, idx %d", i, stage, idx)
- winner = i
- // stage = stage1
- break
- }
- }
- }
- if !reset {
- result |= 1 << (bitlength - 1 - idx)
- junction = idx
- stage = stage2
- for i := range n {
- lost[i] = lost[i] || lost_round[i]
- }
- }
- }
- tb.Logf("lost: %t, result: %08b", lost, result)
- }
- if result != max2 {
- tb.Fatalf("wrong result: %0[1]*[2]b, exp. max2: %0[1]*[3]b, max: %0[1]*[4]b\nvals: %0[1]*[5]b", bitlength, result, max2, max, vals)
- }
- if max_idx != winner {
- tb.Fatalf("wrong winner, max_idx: %d vs winner: %d val %08b\nvals: %08b", max_idx, winner, max2, vals)
- }
-}
-
-func TestSeal4on6bit(t *testing.T) { runSeal(4, 6, t) }
-func TestSeal100on24bit(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping vickrey 100, 16")
- }
- runSeal(100, 24, t)
-}
-
-func TestVickrey4on6bit(t *testing.T) { runVickrey(4, 6, t) }
-func TestVickrey100on16bit(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping vickrey 100, 16")
- }
- runVickrey(100, 16, t)
-}
-func BenchmarkVickrey100on24bit(b *testing.B) {
- for range b.N {
- runVickrey(100, 24, b)
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-09-11 17:48:15 +0000