go-merkletree-old/merkletree_test.go
merkletree_test.goRaw
1package merkletree
2
3import (
4 "encoding/hex"
5 "fmt"
6 "strconv"
7 "testing"
8 "time"
9
10 "github.com/dchest/uniuri"
11 common3 "github.com/iden3/go-iden3/common"
12 "github.com/stretchr/testify/assert"
13 "github.com/syndtr/goleveldb/leveldb"
14)
15
16type testBase struct {
17 Length [4]byte
18 Namespace Hash
19 Type Hash
20 Version uint32
21}
22type testLeaf struct {
23 testBase
24 extraIndex struct {
25 Data []byte
26 }
27}
28
29func parseTestLeafBytes(b []byte) testLeaf {
30 var c testLeaf
31 copy(c.testBase.Length[:], b[0:4])
32 copy(c.testBase.Namespace[:], b[4:36])
33 copy(c.testBase.Type[:], b[36:68])
34 versionBytes := b[68:72]
35 c.testBase.Version = common3.BytesToUint32(versionBytes)
36 c.extraIndex.Data = b[72:]
37 return c
38}
39func (c testLeaf) Bytes() (b []byte) {
40 b = append(b, c.testBase.Length[:]...)
41 b = append(b, c.testBase.Namespace[:]...)
42 b = append(b, c.testBase.Type[:]...)
43 versionBytes := common3.Uint32ToBytes(c.testBase.Version)
44 b = append(b, versionBytes[:]...)
45 b = append(b, c.extraIndex.Data[:]...)
46 return b
47}
48func (c testLeaf) IndexLength() uint32 {
49 return uint32(len(c.Bytes()))
50}
51func (c testLeaf) hi() Hash {
52 h := HashBytes(c.Bytes())
53 return h
54}
55func newTestLeaf(namespaceStr, typeStr string, data []byte) testLeaf {
56 var c testLeaf
57 c.testBase.Length = [4]byte{0x00, 0x00, 0x00, 0x48}
58 c.testBase.Namespace = HashBytes([]byte(namespaceStr))
59 c.testBase.Type = HashBytes([]byte(typeStr))
60 c.testBase.Version = 0
61 c.extraIndex.Data = data
62 return c
63}
64
65type Fatalable interface {
66 Fatal(args ...interface{})
67}
68
69func newTestingMerkle(f Fatalable, numLevels int) *MerkleTree {
70 tim := time.Now().Unix()
71 tstr := fmt.Sprint(tim)
72 s := uniuri.New()
73 db, err := leveldb.OpenFile("tmp/db"+s+"-"+tstr, nil)
74 if err != nil {
75 f.Fatal(err)
76 return nil
77 }
78 // defer db.Close()
79 mt, err := New(db, numLevels)
80 if err != nil {
81 f.Fatal(err)
82 return nil
83 }
84 return mt
85}
86
87func TestNewMT(t *testing.T) {
88
89 //create a new MT
90 mt := newTestingMerkle(t, 140)
91 defer mt.storage.Close()
92 assert.Equal(t, "0x0000000000000000000000000000000000000000000000000000000000000000", mt.Root().Hex())
93}
94
95func TestAddLeaf(t *testing.T) {
96
97 mt := newTestingMerkle(t, 140)
98 defer mt.storage.Close()
99
100 leaf := newTestLeaf("iden3.io", "typespec", []byte("c1"))
101 assert.Equal(t, "0x939862c94ca9772fc9e2621df47128b1d4041b514e19edc969a92d8f0dae558f", leaf.hi().Hex())
102
103 assert.Nil(t, mt.Add(leaf))
104 assert.Equal(t, "0x9d3c407ff02c813cd474c0a6366b4f7c58bf417a38268f7a0d73a8bca2490b9b", mt.Root().Hex())
105}
106
107func TestAddLeafs(t *testing.T) {
108
109 mt := newTestingMerkle(t, 140)
110 defer mt.storage.Close()
111
112 leaf := newTestLeaf("iden3.io", "typespec", []byte("c1"))
113 assert.Equal(t, "0x939862c94ca9772fc9e2621df47128b1d4041b514e19edc969a92d8f0dae558f", leaf.hi().Hex())
114 assert.Nil(t, mt.Add(leaf))
115
116 assert.Nil(t, mt.Add(newTestLeaf("iden3.io2", "typespec2", []byte("c2"))))
117 assert.Equal(t, "0xebae8fb483b48ba6c337136535198eb8bcf891daba40ac81e28958c09b9b229b", mt.Root().Hex())
118
119 mt.Add(newTestLeaf("iden3.io3", "typespec3", []byte("c3")))
120 mt.Add(newTestLeaf("iden3.io4", "typespec4", []byte("c4")))
121 assert.Equal(t, "0xb4b51aa0c77a8e5ed0a099d7c11c7d2a9219ef241da84f0689da1f40a5f6ac31", mt.Root().Hex())
122}
123
124func TestAddLeafsCollision(t *testing.T) {
125
126 mt := newTestingMerkle(t, 140)
127 defer mt.storage.Close()
128
129 leaf := newTestLeaf("iden3.io", "typespec", []byte("c1"))
130 assert.Nil(t, mt.Add(leaf))
131
132 root1 := mt.Root()
133 assert.EqualError(t, mt.Add(leaf), ErrNodeAlreadyExists.Error())
134
135 assert.Equal(t, root1.Hex(), mt.Root().Hex())
136}
137
138func TestAddLeafsDifferentOrders(t *testing.T) {
139
140 mt1 := newTestingMerkle(t, 140)
141 defer mt1.storage.Close()
142
143 mt1.Add(newTestLeaf("iden3.io", "typespec", []byte("c1")))
144 mt1.Add(newTestLeaf("iden3.io2", "typespec2", []byte("c2")))
145 mt1.Add(newTestLeaf("iden3.io3", "typespec3", []byte("c3")))
146 mt1.Add(newTestLeaf("iden3.io4", "typespec4", []byte("c4")))
147 mt1.Add(newTestLeaf("iden3.io5", "typespec5", []byte("c5")))
148
149 mt2 := newTestingMerkle(t, 140)
150 defer mt2.storage.Close()
151
152 mt2.Add(newTestLeaf("iden3.io3", "typespec3", []byte("c3")))
153 mt2.Add(newTestLeaf("iden3.io2", "typespec2", []byte("c2")))
154 mt2.Add(newTestLeaf("iden3.io", "typespec", []byte("c1")))
155 mt2.Add(newTestLeaf("iden3.io4", "typespec4", []byte("c4")))
156 mt2.Add(newTestLeaf("iden3.io5", "typespec5", []byte("c5")))
157
158 assert.Equal(t, mt1.Root().Hex(), mt2.Root().Hex())
159}
160func TestBenchmarkAddingLeafs(t *testing.T) {
161
162 mt := newTestingMerkle(t, 140)
163 defer mt.storage.Close()
164
165 start := time.Now()
166 numToAdd := 1000
167 for i := 0; i < numToAdd; i++ {
168 leaf := newTestLeaf("iden3.io"+strconv.Itoa(i), "typespec"+strconv.Itoa(i), []byte("c"+strconv.Itoa(i)))
169 mt.Add(leaf)
170 }
171 fmt.Print("time elapsed adding " + strconv.Itoa(numToAdd) + " leafs: ")
172 fmt.Println(time.Since(start))
173}
174func BenchmarkAddingLeafs(b *testing.B) {
175
176 mt := newTestingMerkle(b, 140)
177 defer mt.storage.Close()
178
179 b.ResetTimer()
180 for i := 0; i < b.N; i++ {
181 leaf := newTestLeaf("iden3.io"+strconv.Itoa(i), "typespec"+strconv.Itoa(i), []byte("c"+strconv.Itoa(i)))
182 if err := mt.Add(leaf); err != nil {
183 b.Fatal(err)
184 }
185 }
186}
187
188func TestGenerateProof(t *testing.T) {
189 mt := newTestingMerkle(t, 140)
190 defer mt.storage.Close()
191
192 mt.Add(newTestLeaf("iden3.io_3", "typespec_3", []byte("c3")))
193 mt.Add(newTestLeaf("iden3.io_2", "typespec_2", []byte("c2")))
194
195 leaf1 := newTestLeaf("iden3.io_1", "typespec_1", []byte("c1"))
196 assert.Nil(t, mt.Add(leaf1))
197
198 mp, err := mt.GenerateProof(parseTestLeafBytes(leaf1.Bytes()).hi())
199 assert.Nil(t, err)
200
201 mpHexExpected := "0000000000000000000000000000000000000000000000000000000000000002beb0fd6dcf18d37fe51cf34beacd4c524d9c039ef9da2a27ccd3e7edf662c39c"
202 assert.Equal(t, mpHexExpected, hex.EncodeToString(mp))
203}
204
205func TestCheckProof(t *testing.T) {
206 mt := newTestingMerkle(t, 140)
207 defer mt.storage.Close()
208
209 leaf1 := newTestLeaf("iden3.io_1", "typespec_1", []byte("c1"))
210 assert.Nil(t, mt.Add(leaf1))
211
212 leaf3 := newTestLeaf("iden3.io_3", "typespec_3", []byte("c3"))
213 assert.Nil(t, mt.Add(leaf3))
214
215 mp, err := mt.GenerateProof(parseTestLeafBytes(leaf1.Bytes()).hi())
216 assert.Nil(t, err)
217 verified := CheckProof(mt.Root(), mp, leaf1.hi(), HashBytes(leaf1.Bytes()), mt.NumLevels())
218 assert.True(t, verified)
219
220}
221
222func TestProofOfEmpty(t *testing.T) { // proof of a non revocated leaf, prove that is empty the hi position of the leaf.version+1
223 mt := newTestingMerkle(t, 140)
224 defer mt.storage.Close()
225
226 leaf1 := newTestLeaf("iden3.io_1", "typespec_1", []byte("c1"))
227 // proof when there is nothing in the tree
228 mp, err := mt.GenerateProof(leaf1.hi())
229 assert.Nil(t, err)
230 verified := CheckProof(mt.Root(), mp, leaf1.hi(), EmptyNodeValue, mt.NumLevels())
231 assert.True(t, verified)
232
233 // add the first leaf
234 assert.Nil(t, mt.Add(leaf1))
235
236 // proof when there is only one leaf in the tree
237 leaf2 := newTestLeaf("iden3.io_2", "typespec_2", []byte("c2"))
238 mp, err = mt.GenerateProof(leaf2.hi())
239 assert.Nil(t, err)
240 verified = CheckProof(mt.Root(), mp, leaf2.hi(), EmptyNodeValue, mt.NumLevels())
241 assert.True(t, verified)
242
243 // check that the value in Hi is Empty
244 valueInPos, err := mt.GetValueInPos(leaf2.hi())
245 assert.Nil(t, err)
246 assert.Equal(t, EmptyNodeValue.Bytes(), valueInPos)
247}
248
249func DifferentNonExistenceProofs(t *testing.T) {
250 mt1 := newTestingMerkle(t, 140)
251 defer mt1.storage.Close()
252
253 mt2 := newTestingMerkle(t, 140)
254 defer mt2.storage.Close()
255
256 leaf1 := newTestLeaf("iden3.io_1", "typespec_1", []byte("c1"))
257 leaf2 := newTestLeaf("iden3.io_1", "typespec_1", []byte("c2"))
258
259 assert.Nil(t, mt1.Add(leaf1))
260 assert.Nil(t, mt2.Add(leaf2))
261
262 leaf1.Version++
263 leaf2.Version++
264
265 np1, err := mt1.GenerateProof(leaf1.hi())
266 assert.Nil(t, err)
267 np2, err := mt2.GenerateProof(leaf2.hi())
268 assert.Nil(t, err)
269
270 assert.True(t, CheckProof(mt1.Root(), np1, leaf1.hi(), EmptyNodeValue, mt1.NumLevels()))
271 assert.True(t, CheckProof(mt2.Root(), np2, leaf2.hi(), EmptyNodeValue, mt2.NumLevels()))
272
273 assert.Equal(t, "0000000000000000000000000000000000000000000000000000000000000010a40617c8c3390736831d00b2003e2133353190f5d3b3a586cf829f0f2009aacc", hex.EncodeToString(np1))
274 assert.Equal(t, "0000000000000000000000000000000000000000000000000000000000000001b274a34a3bd95915fe982a0163e3e0a2f79a371b8307661341f8914e22b313e1", hex.EncodeToString(np2))
275
276}
277
278func TestGetLeafInPos(t *testing.T) {
279 mt := newTestingMerkle(t, 140)
280 defer mt.storage.Close()
281
282 for i := 0; i < 50; i++ {
283 leaf := newTestLeaf("iden3.io"+strconv.Itoa(i), "typespec"+strconv.Itoa(i), []byte("c"+strconv.Itoa(i)))
284 mt.Add(leaf)
285
286 }
287 leaf1 := newTestLeaf("iden3.io_x", "typespec_x", []byte("cx"))
288 assert.Nil(t, mt.Add(leaf1))
289
290 leaf := parseTestLeafBytes(leaf1.Bytes())
291 leafInPosBytes, err := mt.GetValueInPos(leaf.hi())
292 assert.Nil(t, err)
293 assert.Equal(t, leaf1.Bytes(), leafInPosBytes)
294
295 // empty value in position
296 leaf2 := newTestLeaf("iden3.io_y", "typespec_y", []byte("cy"))
297 leafInPosBytes, err = mt.GetValueInPos(leaf2.hi())
298 assert.Nil(t, err)
299 assert.Equal(t, EmptyNodeValue[:], leafInPosBytes)
300}
301
302type vt struct {
303 v []byte
304 idxlen uint32
305}
306
307func (v vt) IndexLength() uint32 {
308 return v.idxlen
309}
310func (v vt) Bytes() []byte {
311 return v.v
312}
313
314func TestVector4(t *testing.T) {
315 mt := newTestingMerkle(t, 4)
316 defer mt.storage.Close()
317
318 zeros := make([]byte, 32, 32)
319 zeros[31] = 1 // to avoid adding Empty element
320 assert.Nil(t, mt.Add(vt{zeros, uint32(1)}))
321 v := vt{zeros, uint32(2)}
322 assert.Nil(t, mt.Add(v))
323 proof, _ := mt.GenerateProof(HashBytes(v.Bytes()[:v.IndexLength()]))
324 assert.True(t, CheckProof(mt.Root(), proof, HashBytes(v.Bytes()[:v.IndexLength()]), HashBytes(v.Bytes()), mt.NumLevels()))
325 assert.Equal(t, 4, mt.NumLevels())
326 assert.Equal(t, "0000000000000000000000000000000000000000000000000000000000000001", hex.EncodeToString(v.Bytes()))
327 assert.Equal(t, "0xc1b95ffbb999a6dd7a472a610a98891ffae95cc973d1d1e21acfdd68db830b51", mt.Root().Hex())
328 assert.Equal(t, "00000000000000000000000000000000000000000000000000000000000000023cf025e4b4fc3ebe57374bf0e0c78ceb0009bdc4466a45174d80e8f508d1a4e3", hex.EncodeToString(proof))
329}
330
331func TestVector140(t *testing.T) {
332 mt := newTestingMerkle(t, 140)
333 defer mt.storage.Close()
334
335 zeros := make([]byte, 32, 32)
336 zeros[31] = 1 // to avoid adding Empty element
337 for i := 1; i < len(zeros)-1; i++ {
338 v := vt{zeros, uint32(i)}
339 assert.Nil(t, mt.Add(v))
340 proof, err := mt.GenerateProof(HashBytes(v.Bytes()[:v.IndexLength()]))
341 assert.Nil(t, err)
342 assert.True(t, CheckProof(mt.Root(), proof, HashBytes(v.Bytes()[:v.IndexLength()]), HashBytes(v.Bytes()), mt.NumLevels()))
343 if i == len(zeros)-2 {
344 assert.Equal(t, 140, mt.NumLevels())
345 assert.Equal(t, uint32(30), v.IndexLength())
346 assert.Equal(t, "0000000000000000000000000000000000000000000000000000000000000001", hex.EncodeToString(v.Bytes()))
347 assert.Equal(t, "0x35f83288adf03bfb61d8d57fab9ed092da79833b58bbdbe9579b636753494ebd", mt.Root().Hex())
348 assert.Equal(t, "000000000000000000000000000000000000000000000000000000000000001f0d1f363115f3333197a009b6674f46bba791308af220ad71515567702b3b44a2b540c1abad0ff81386a78b77e8907a56b7268d24513928ae83497adf4ad93a55e380267ead8305202da0640c1518e144dee87717c732b738fa182c6ef458defd6baf50022b01e3222715d4fca4c198e94536101f6ac314b3d261d3aaa0684395c1db60626e01c39fe4f69418055c2ebd70e0c07b6d9db5c4aed0a11ed2b6a773", hex.EncodeToString(proof))
349 }
350 }
351}