windowed_test.go raw

   1  package cayley
   2  
   3  import (
   4  	"fmt"
   5  	"math"
   6  	"math/rand"
   7  	"testing"
   8  )
   9  
  10  type WindowedSigner struct {
  11  	GB       *GenerativeBasis
  12  	StdWords map[Mat2][]int8
  13  	W        int
  14  	StdPF    *PathFinder
  15  }
  16  
  17  func BuildWindowedSigner(gb *GenerativeBasis, W int) *WindowedSigner {
  18  	stdPF := StandardGens(gb.GS.P).BFS(-1)
  19  	ws := &WindowedSigner{GB: gb, W: W, StdPF: stdPF,
  20  		StdWords: make(map[Mat2][]int8, int(math.Pow(4, float64(W))))}
  21  	for v, d := range stdPF.Dist {
  22  		if d > W { continue }
  23  		path, ok := gb.GPF.PathTo(v)
  24  		if ok { ws.StdWords[v] = path }
  25  	}
  26  	return ws
  27  }
  28  
  29  func (ws *WindowedSigner) Sign(target Mat2) ([]int8, bool) {
  30  	P := ws.GB.GS.P
  31  	eucPath, ok := ws.StdPF.PathTo(target)
  32  	if !ok { return nil, false }
  33  
  34  	var sig []int8
  35  	for i := 0; i < len(eucPath); i += ws.W {
  36  		end := i + ws.W
  37  		if end > len(eucPath) { end = len(eucPath) }
  38  
  39  		// Block contribution: product of block steps FROM IDENTITY.
  40  		blockContribution := ID()
  41  		for j := i; j < end; j++ {
  42  			var gen Mat2
  43  			switch eucPath[j] {
  44  			case 0: gen = modMat2(StdG0, P)
  45  			case 1: gen = modMat2(StdG1, P)
  46  			case 2: gen = modMat2(StdG0I, P)
  47  			case 3: gen = modMat2(StdG1I, P)
  48  			default: return nil, false
  49  			}
  50  			blockContribution = blockContribution.Mul(gen, P)
  51  		}
  52  
  53  		word, ok := ws.StdWords[blockContribution]
  54  		if !ok { return nil, false }
  55  		sig = append(sig, word...)
  56  	}
  57  	if ws.GB.GS.Walk(ID(), sig).Eq(target) { return sig, true }
  58  	return nil, false
  59  }
  60  
  61  func TestWindowedDebug(t *testing.T) {
  62  	P := int64(31); rng := rand.New(rand.NewSource(42))
  63  	gs := randomGens(P, 4, rng)
  64  	gb := BuildGenerativeBasis(gs)
  65  	if gb == nil { t.Fatal("no basis") }
  66  
  67  	ws := BuildWindowedSigner(gb, 1)
  68  	fmt.Printf("W=1 stdWords count: %d\n", len(ws.StdWords))
  69  
  70  	target := randomSL2Fast(P, rng)
  71  	eucPath, ok := ws.StdPF.PathTo(target)
  72  	if !ok { t.Fatal("target not reachable") }
  73  	fmt.Printf("Euclidean path: %d steps\n", len(eucPath))
  74  
  75  	sig, ok := ws.Sign(target)
  76  	if !ok { t.Fatal("sign failed") }
  77  	fmt.Printf("Signature: %d steps\n", len(sig))
  78  	fmt.Printf("Verify: %v\n", gs.Walk(ID(), sig).Eq(target))
  79  }
  80  
  81  func TestWindowedBlowup(t *testing.T) {
  82  	P := int64(251)
  83  	if testing.Short() { t.Skip("P=251 BFS slow") }
  84  	rng := rand.New(rand.NewSource(42))
  85  	gs := randomGens(P, 4, rng)
  86  	gb := BuildGenerativeBasis(gs)
  87  	if gb == nil { t.Fatal("no basis") }
  88  
  89  	for _, W := range []int{1, 2, 4} {
  90  		ws := BuildWindowedSigner(gb, W)
  91  		var sigT, optT int; n := 0
  92  		for i := 0; i < 20; i++ {
  93  			target := randomSL2Fast(P, rng)
  94  			opt, ok := gb.GPF.PathTo(target)
  95  			if !ok { continue }
  96  			sig, ok := ws.Sign(target)
  97  			if !ok { continue }
  98  			sigT += len(sig); optT += len(opt); n++
  99  		}
 100  		if n > 0 {
 101  			t.Logf("W=%d blocks=%d n=%d: sig=%.1f opt=%.1f ratio=%.2f",
 102  				W, len(ws.StdWords), n, float64(sigT)/float64(n),
 103  				float64(optT)/float64(n), float64(sigT)/float64(optT))
 104  		}
 105  	}
 106  }
 107