aboutsummaryrefslogtreecommitdiff
path: root/nizk
diff options
context:
space:
mode:
Diffstat (limited to 'nizk')
-rw-r--r--nizk/bench_test.go72
-rw-r--r--nizk/vickrey_test.go167
2 files changed, 99 insertions, 140 deletions
diff --git a/nizk/bench_test.go b/nizk/bench_test.go
index 9d1cc4b..3ee30a8 100644
--- a/nizk/bench_test.go
+++ b/nizk/bench_test.go
@@ -117,7 +117,7 @@ func runSeal(n int, bitlength int, tb testing.TB) {
var bj = make([]*Bit, n)
var p2 = make([]*Stage2Proof, n)
var lost = make([]bool, n)
- instage1 := true
+ stage := stage1
junction := -1
result := 0
@@ -125,64 +125,44 @@ func runSeal(n int, bitlength int, tb testing.TB) {
for i := range n {
c[i] = bits[i][idx].StageCommit()
Xs[i] = c[i].X
+ if stage == stage2 {
+ bj[i] = bits[i][junction]
+
+ }
}
- if instage1 {
- var wg sync.WaitGroup
- wg.Add(n)
+ var wg sync.WaitGroup
+ wg.Add(n)
- for i := range n {
- go func() {
+ 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)
}
- Zs[i] = r[i].Z
- wg.Done()
- }()
- }
- wg.Wait()
-
- Z := Curve.Product(Zs...)
- 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 {
- for i := range bits {
- bj[i] = bits[i][junction]
- }
-
- var wg sync.WaitGroup
- wg.Add(n)
- for i := range n {
- go func() {
+ } 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.Done()
- }()
- }
- wg.Wait()
-
- Z := Curve.Product(Zs...)
- if !Id.Equal(Z) {
- junction = idx
+ }
+ Zs[i] = r[i].Z
+ }()
+ }
+ wg.Wait()
- for i := range n {
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- }
+ 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)
}
+ result |= 1 << (bitlength - 1 - idx)
}
}
if result != max {
diff --git a/nizk/vickrey_test.go b/nizk/vickrey_test.go
index 69df365..0584359 100644
--- a/nizk/vickrey_test.go
+++ b/nizk/vickrey_test.go
@@ -6,11 +6,26 @@ import (
"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)
@@ -20,11 +35,13 @@ func runVickrey(n int, bitlength int, tb testing.TB) {
}
max := slices.Max(vals)
max_idx := slices.Index(vals, max)
- max2 := slices.Max(slices.Delete(vals, max_idx, max_idx+1))
+ 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)
@@ -38,7 +55,7 @@ func runVickrey(n int, bitlength int, tb testing.TB) {
var bj = make([]*Bit, n)
var p2 = make([]*Stage2Proof, n)
var lost = make([]bool, n)
- instage1 := true
+ stage := stage1
junction := -1
winner := -1
result := 0
@@ -47,6 +64,7 @@ func runVickrey(n int, bitlength int, tb testing.TB) {
z := Z.Div(Zs[i])
xu := Curve.Identity()
xl := Curve.Identity()
+ found := false
for k := range n {
if k == winner {
@@ -64,7 +82,7 @@ func runVickrey(n int, bitlength int, tb testing.TB) {
if x.Equal(z) {
tb.Logf("equal by value")
- winner = i
+ found = true
}
if winner < 0 {
@@ -73,146 +91,107 @@ func runVickrey(n int, bitlength int, tb testing.TB) {
s2 := z.String()
if strings.HasPrefix(s1, s2[:len(s2)-2]) {
log.Printf("BUG! TODO! equal only by string")
- winner = i
+ found = true
}
-
}
- tb.Logf("testing max_idx %d, i %d, bit %d:\n%v vs %v", max_idx, i, idx, x, z)
- return winner >= 0
+ // 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 {
+ c[i] = nil
+ bj[i] = nil
Xs[i] = Id
Zs[i] = Id
continue
}
c[i] = bits[i][idx].StageCommit()
Xs[i] = c[i].X
- }
-
- if instage1 {
- var wg sync.WaitGroup
- m := n
- if winner >= 0 {
- m -= 1
- }
- wg.Add(m)
- for i := range n {
- if i == winner {
- continue
- }
- go func() {
- 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)
- }
- Zs[i] = r[i].Z
- wg.Done()
- }()
- }
- wg.Wait()
-
- Z := Curve.Product(Zs...)
- reset := false
- if !Id.Equal(Z) {
- for i := range n {
- if i == winner {
- continue
- }
- if !lost[i] && !bits[i][idx].IsSet() {
- lost[i] = true
- }
-
- // Winner test
- if !lost[i] {
- reset = isWinner(Z, i, idx)
- if reset {
- Xs[i] = Id
- Zs[i] = Id
- }
- }
- }
- if !reset {
- result |= 1 << (bitlength - 1 - idx)
- }
+ if stage == stage2 {
+ bj[i] = bits[i][junction]
}
- if !reset {
- junction = idx
- instage1 = false
- }
- continue
- }
-
- // Stage 2
-
- for i := range n {
- if i == winner {
- Xs[i] = Id
- Zs[i] = Id
- continue
- }
- bj[i] = bits[i][junction]
}
var wg sync.WaitGroup
- m := n
- if winner >= 0 {
- m -= 1
- }
- wg.Add(m)
+ 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() {
- 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)
+ 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
- wg.Done()
- }()
+ }(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[i] = true
+ lost_round[i] = true
}
// Winner test
- if !lost[i] && winner < 0 {
+ if winner < 0 && !lost_round[i] && !lost[i] {
reset = isWinner(Z, i, idx)
if reset {
- Xs[i] = Id
- Zs[i] = Id
+ 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]
+ }
}
-
- }
- if !reset {
- junction = idx
}
+ tb.Logf("lost: %t, result: %08b", lost, result)
}
- if result != max {
- tb.Fatalf("wrong result: %0[1]*[2]b, expected: %0[1]*[3]b", bitlength, result, max)
+ 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, max, vals)
+ tb.Fatalf("wrong winner, max_idx: %d vs winner: %d val %08b\nvals: %08b", max_idx, winner, max2, vals)
}
}
-func TestVickrey100on16bit(t *testing.T) { runVickrey(3, 5, t) }
+func TestAuction4on6bit(t *testing.T) { runSeal(4, 6, t) }
+
+// func TestAuction100on24bit(t *testing.T) { runSeal(100, 24, t) }
+
+func TestVickrey4on6bit(t *testing.T) { runVickrey(4, 6, t) }
generated by cgit v1.2.3 (git 2.39.1) at 2025-09-11 13:10:06 +0000