1
2
3 package testonly
4
5 import (
6 "bytes"
7 "math"
8 "testing"
9
10 "github.com/google/go-cmp/cmp"
11 "github.com/google/go-cmp/cmp/cmpopts"
12 "github.com/transparency-dev/merkle/proof"
13 )
14
15
16 func FuzzConsistencyProofAndVerify(f *testing.F) {
17 for size := 0; size <= 8; size++ {
18 for end := 0; end <= size; end++ {
19 for begin := 0; begin <= end; begin++ {
20 f.Add(uint64(size), uint64(begin), uint64(end))
21 }
22 }
23 }
24 f.Fuzz(func(t *testing.T, size, begin, end uint64) {
25
26 if size >= math.MaxUint16 {
27 return
28 }
29 t.Logf("size=%d, begin=%d, end=%d", size, begin, end)
30 if begin > end || end > size {
31 return
32 }
33 tree := newTree(genEntries(size))
34 p, err := tree.ConsistencyProof(begin, end)
35 t.Logf("proof=%v", p)
36 if err != nil {
37 t.Error(err)
38 }
39 err = proof.VerifyConsistency(tree.hasher, begin, end, p, tree.HashAt(begin), tree.HashAt(end))
40 if err != nil {
41 t.Error(err)
42 }
43 })
44 }
45
46
47 func FuzzInclusionProofAndVerify(f *testing.F) {
48 for size := 0; size <= 8; size++ {
49 for index := 0; index <= size; index++ {
50 f.Add(uint64(index), uint64(size))
51 }
52 }
53 f.Fuzz(func(t *testing.T, index, size uint64) {
54 if size >= math.MaxUint16 {
55 return
56 }
57 t.Logf("index=%d, size=%d", index, size)
58 if index >= size {
59 return
60 }
61 tree := newTree(genEntries(size))
62 p, err := tree.InclusionProof(index, size)
63 t.Logf("proof=%v", p)
64 if err != nil {
65 t.Error(err)
66 }
67 err = proof.VerifyInclusion(tree.hasher, index, size, tree.LeafHash(index), p, tree.Hash())
68 if err != nil {
69 t.Error(err)
70 }
71 })
72 }
73
74 func FuzzHashAtAgainstReferenceImplementation(f *testing.F) {
75 for size := 0; size <= 8; size++ {
76 for index := 0; index <= size; index++ {
77 f.Add(uint64(index), uint64(size))
78 }
79 }
80 f.Fuzz(func(t *testing.T, index, size uint64) {
81 if size >= math.MaxUint16 {
82 return
83 }
84 t.Logf("index=%d, size=%d", index, size)
85 if index >= size {
86 return
87 }
88 entries := genEntries(size)
89 mt := newTree(entries)
90 got := mt.HashAt(uint64(size))
91 want := refRootHash(entries[:size], mt.hasher)
92 if !bytes.Equal(got, want) {
93 t.Errorf("HashAt(%d): %x, want %x", size, got, want)
94 }
95 })
96 }
97
98 func FuzzInclusionProofAgainstReferenceImplementation(f *testing.F) {
99 for size := 0; size <= 8; size++ {
100 for index := 0; index <= size; index++ {
101 f.Add(uint64(index), uint64(size))
102 }
103 }
104 f.Fuzz(func(t *testing.T, index, size uint64) {
105 if size >= math.MaxUint16 {
106 return
107 }
108 t.Logf("index=%d, size=%d", index, size)
109 if index >= size {
110 return
111 }
112 entries := genEntries(size)
113 tree := newTree(entries)
114 got, err := tree.InclusionProof(index, size)
115 t.Logf("proof=%v", got)
116 if err != nil {
117 t.Error(err)
118 }
119 want := refInclusionProof(entries, index, tree.hasher)
120 if diff := cmp.Diff(got, want, cmpopts.EquateEmpty()); diff != "" {
121 t.Errorf("InclusionProof(%d, %d): diff (-got +want)\n%s", index, size, diff)
122 }
123 })
124 }
125
126 func FuzzConsistencyProofAgainstReferenceImplementation(f *testing.F) {
127 for size := 0; size <= 8; size++ {
128 for end := 0; end <= size; end++ {
129 for begin := 0; begin <= end; begin++ {
130 f.Add(uint64(size), uint64(begin), uint64(end))
131 }
132 }
133 }
134 f.Fuzz(func(t *testing.T, size, begin, end uint64) {
135 if size >= math.MaxUint16 {
136 return
137 }
138 t.Logf("size=%d, begin=%d, end=%d", size, begin, end)
139 if begin > end || end > size {
140 return
141 }
142 entries := genEntries(size)
143 tree := newTree(entries)
144 got, err := tree.ConsistencyProof(begin, end)
145 if err != nil {
146 t.Errorf("ConsistencyProof: %v", err)
147 }
148 want := refConsistencyProof(entries[:end], end, begin, tree.hasher, true)
149 if diff := cmp.Diff(got, want, cmpopts.EquateEmpty()); diff != "" {
150 t.Errorf("ConsistencyProof: diff (-got +want)\n%s", diff)
151 }
152 })
153 }
154
View as plain text