diff options
author | Özgür Kesim <oec@codeblau.de> | 2024-11-21 17:13:47 +0100 |
---|---|---|
committer | Özgür Kesim <oec@codeblau.de> | 2024-11-21 17:13:47 +0100 |
commit | 0ada8c47427bfe604024d383ed7a250b04c82fee (patch) | |
tree | 4bc5e6432512a8060308413d303b675b0658bd1b /nizk | |
parent | 32cee46e39527a09504615b822cc61969c46184d (diff) |
Diffstat (limited to 'nizk')
-rw-r--r-- | nizk/bench_test.go | 191 | ||||
-rw-r--r-- | nizk/commit.go | 150 | ||||
-rw-r--r-- | nizk/commit_test.go | 57 | ||||
-rw-r--r-- | nizk/doc.go | 7 | ||||
-rw-r--r-- | nizk/schnorr/schnorr.go | 77 | ||||
-rw-r--r-- | nizk/schnorr/schnorr_test.go | 34 | ||||
-rw-r--r-- | nizk/stage1.go | 196 | ||||
-rw-r--r-- | nizk/stage1_test.go | 56 | ||||
-rw-r--r-- | nizk/stage2.go | 221 | ||||
-rw-r--r-- | nizk/stage2_test.go | 267 | ||||
-rw-r--r-- | nizk/vickrey_test.go | 209 |
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) - } -} |