1package merkletree
  2
  3/*
  4This is just an example of basic tests for the iden3-merkletree-specification.
  5The methods and variables names can be different.
  6*/
  7
  8import (
  9	"strconv"
 10	"testing"
 11
 12	common3 "github.com/iden3/go-iden3/common"
 13	"github.com/stretchr/testify/assert"
 14)
 15
 16type testBytesLeaf struct {
 17	data        []byte
 18	indexLength uint32
 19}
 20
 21func (c testBytesLeaf) Bytes() (b []byte) {
 22	return c.data
 23}
 24func (c testBytesLeaf) IndexLength() uint32 {
 25	return c.indexLength
 26}
 27func (c testBytesLeaf) Hi() Hash {
 28	h := HashBytes(c.Bytes()[:c.IndexLength()])
 29	return h
 30}
 31func newTestBytesLeaf(data string, indexLength uint32) testBytesLeaf {
 32	return testBytesLeaf{
 33		data:        []byte(data),
 34		indexLength: indexLength,
 35	}
 36}
 37
 38// Test to check the iden3-merkletree-specification
 39func TestIden3MerkletreeSpecification(t *testing.T) {
 40	h := HashBytes([]byte("test")).Hex()
 41	assert.Equal(t, "0x9c22ff5f21f0b81b113e63f7db6da94fedef11b2119b4088b89664fb9a3cb658", h)
 42
 43	h = HashBytes([]byte("authorizeksign")).Hex()
 44	assert.Equal(t, "0x353f867ef725411de05e3d4b0a01c37cf7ad24bcc213141a05ed7726d7932a1f", h)
 45
 46	mt := newTestingMerkle(t, 140)
 47	defer mt.storage.Close()
 48
 49	// empty tree
 50	assert.Equal(t, "0x0000000000000000000000000000000000000000000000000000000000000000", mt.Root().Hex())
 51
 52	// add leaf
 53	leaf := testBytesLeaf{
 54		data:        []byte("this is a test leaf"),
 55		indexLength: 15,
 56	}
 57	assert.Nil(t, mt.Add(leaf))
 58	assert.Equal(t, "0xb4fdf8a653198f0e179ccb3af7e4fc09d76247f479d6cfc95cd92d6fda589f27", mt.Root().Hex())
 59
 60	// proof with only one leaf in the MerkleTree
 61	proof, err := mt.GenerateProof(leaf.Hi())
 62	assert.Nil(t, err)
 63	assert.Equal(t, "0x0000000000000000000000000000000000000000000000000000000000000000", common3.BytesToHex(proof))
 64
 65	// add a second leaf
 66	leaf2 := testBytesLeaf{
 67		data:        []byte("this is a second test leaf"),
 68		indexLength: 15,
 69	}
 70	err = mt.Add(leaf2)
 71	assert.Nil(t, err)
 72	assert.Equal(t, "0x8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82", mt.Root().Hex())
 73
 74	// proof of the second leaf, with two leafs in the MerkleTree
 75	proof2, err := mt.GenerateProof(leaf2.Hi())
 76	assert.Nil(t, err)
 77	assert.Equal(t, "0x0000000000000000000000000000000000000000000000000000000000000001fd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", common3.BytesToHex(proof2))
 78
 79	// proof of emptyLeaf
 80	leaf3 := testBytesLeaf{
 81		data:        []byte("this is a third test leaf"),
 82		indexLength: 15,
 83	}
 84	proof3, err := mt.GenerateProof(leaf3.Hi())
 85	assert.Nil(t, err)
 86	assert.Equal(t, "0x000000000000000000000000000000000000000000000000000000000000000389741fa23da77c259781ad8f4331a5a7d793eef1db7e5200ddfc8e5f5ca7ce2bfd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", common3.BytesToHex(proof3))
 87
 88	// getLeafByHi/GetValueInPos
 89	bytesInHi, err := mt.GetValueInPos(leaf2.Hi())
 90	assert.Nil(t, err)
 91	assert.Equal(t, leaf2.Bytes(), bytesInHi)
 92
 93	// check proof
 94	rootBytes, err := common3.HexToBytes("0x7d7c5e8f4b3bf434f3d9d223359c4415e2764dd38de2e025fbf986e976a7ed3d")
 95	assert.Nil(t, err)
 96	mp, err := common3.HexToBytes("0x0000000000000000000000000000000000000000000000000000000000000002d45aada6eec346222eaa6b5d3a9260e08c9b62fcf63c72bc05df284de07e6a52")
 97	assert.Nil(t, err)
 98	hiBytes, err := common3.HexToBytes("0x786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878")
 99	assert.Nil(t, err)
100	htBytes, err := common3.HexToBytes("0x786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878")
101	assert.Nil(t, err)
102	var root, hi, ht Hash
103	copy(root[:], rootBytes)
104	copy(hi[:], hiBytes)
105	copy(ht[:], htBytes)
106	verified := CheckProof(root, mp, hi, ht, 140)
107	assert.True(t, verified)
108
109	// check proof of empty
110	rootBytes, err = common3.HexToBytes("0x8f021d00c39dcd768974ddfe0d21f5d13f7215bea28db1f1cb29842b111332e7")
111	assert.Nil(t, err)
112	mp, err = common3.HexToBytes("0x0000000000000000000000000000000000000000000000000000000000000004bf8e980d2ed328ae97f65c30c25520aeb53ff837579e392ea1464934c7c1feb9")
113	assert.Nil(t, err)
114	hiBytes, err = common3.HexToBytes("0xa69792a4cff51f40b7a1f7ae596c6ded4aba241646a47538898f17f2a8dff647")
115	assert.Nil(t, err)
116	htBytes, err = common3.HexToBytes("0x0000000000000000000000000000000000000000000000000000000000000000")
117	assert.Nil(t, err)
118	copy(root[:], rootBytes)
119	copy(hi[:], hiBytes)
120	copy(ht[:], htBytes)
121	verified = CheckProof(root, mp, hi, ht, 140)
122	assert.True(t, verified)
123
124	// check the proof generated in the previous steps
125	verified = CheckProof(mt.Root(), proof2, leaf2.Hi(), HashBytes(leaf2.Bytes()), 140)
126	assert.True(t, verified)
127	// check proof of no existence (emptyLeaf), as we are prooving an empty leaf, the Ht is an empty value (0x000...0)
128	verified = CheckProof(mt.Root(), proof3, leaf3.Hi(), EmptyNodeValue, 140)
129	assert.True(t, verified)
130
131	// add leafs in different orders
132	mt1 := newTestingMerkle(t, 140)
133	defer mt.storage.Close()
134
135	mt1.Add(newTestBytesLeaf("0 this is a test leaf", 15))
136	mt1.Add(newTestBytesLeaf("1 this is a test leaf", 15))
137	mt1.Add(newTestBytesLeaf("2 this is a test leaf", 15))
138	mt1.Add(newTestBytesLeaf("3 this is a test leaf", 15))
139	mt1.Add(newTestBytesLeaf("4 this is a test leaf", 15))
140
141	mt2 := newTestingMerkle(t, 140)
142	defer mt.storage.Close()
143
144	mt2.Add(newTestBytesLeaf("2 this is a test leaf", 15))
145	mt2.Add(newTestBytesLeaf("1 this is a test leaf", 15))
146	mt2.Add(newTestBytesLeaf("0 this is a test leaf", 15))
147	mt2.Add(newTestBytesLeaf("3 this is a test leaf", 15))
148	mt2.Add(newTestBytesLeaf("4 this is a test leaf", 15))
149
150	assert.Equal(t, mt1.Root().Hex(), mt2.Root().Hex())
151
152	// adding 1000 leafs
153	mt1000 := newTestingMerkle(t, 140)
154	defer mt.storage.Close()
155
156	numToAdd := 1000
157	for i := 0; i < numToAdd; i++ {
158		leaf := newTestBytesLeaf(strconv.Itoa(i)+" this is a test leaf", 15)
159		mt1000.Add(leaf)
160	}
161	assert.Equal(t, "0x6e2da580b2920cd78ed8d4e4bf41e209dfc99ef28bc19560042f0ac803e0d6f7", mt1000.Root().Hex())
162}