1package merkletree
  2
  3import (
  4	"bytes"
  5	"encoding/hex"
  6	"fmt"
  7	"math/big"
  8	"testing"
  9
 10	"github.com/iden3/go-iden3-core/db"
 11	"github.com/stretchr/testify/assert"
 12	"github.com/stretchr/testify/require"
 13)
 14
 15var debug = false
 16
 17type Fatalable interface {
 18	Fatal(args ...interface{})
 19}
 20
 21func newTestingMerkle(f Fatalable, numLevels int) *MerkleTree {
 22	mt, err := NewMerkleTree(db.NewMemoryStorage(), numLevels)
 23	if err != nil {
 24		f.Fatal(err)
 25		return nil
 26	}
 27	return mt
 28}
 29
 30func TestHashParsers(t *testing.T) {
 31	h0 := NewHashFromBigInt(big.NewInt(0))
 32	assert.Equal(t, "0", h0.String())
 33	h1 := NewHashFromBigInt(big.NewInt(1))
 34	assert.Equal(t, "1", h1.String())
 35	h10 := NewHashFromBigInt(big.NewInt(10))
 36	assert.Equal(t, "10", h10.String())
 37
 38	h7l := NewHashFromBigInt(big.NewInt(1234567))
 39	assert.Equal(t, "1234567", h7l.String())
 40	h8l := NewHashFromBigInt(big.NewInt(12345678))
 41	assert.Equal(t, "12345678...", h8l.String())
 42
 43	b, ok := new(big.Int).SetString("4932297968297298434239270129193057052722409868268166443802652458940273154854", 10)
 44	assert.True(t, ok)
 45	h := NewHashFromBigInt(b)
 46	assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154854", h.BigInt().String())
 47	assert.Equal(t, "49322979...", h.String())
 48	assert.Equal(t, "0ae794eb9c3d8bbb9002e993fc2ed301dcbd2af5508ed072c375e861f1aa5b26", h.Hex())
 49}
 50
 51func TestNewTree(t *testing.T) {
 52	mt, err := NewMerkleTree(db.NewMemoryStorage(), 10)
 53	assert.Nil(t, err)
 54	assert.Equal(t, "0", mt.Root().String())
 55
 56	// test vectors generated using https://github.com/iden3/circomlib smt.js
 57	err = mt.Add(big.NewInt(1), big.NewInt(2))
 58	assert.Nil(t, err)
 59	assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154854", mt.Root().BigInt().String())
 60
 61	err = mt.Add(big.NewInt(33), big.NewInt(44))
 62	assert.Nil(t, err)
 63	assert.Equal(t, "13563340744765267202993741297198970774200042973817962221376874695587906013050", mt.Root().BigInt().String())
 64
 65	err = mt.Add(big.NewInt(1234), big.NewInt(9876))
 66	assert.Nil(t, err)
 67	assert.Equal(t, "16970503620176669663662021947486532860010370357132361783766545149750777353066", mt.Root().BigInt().String())
 68
 69	proof, err := mt.GenerateProof(big.NewInt(33), nil)
 70	assert.Nil(t, err)
 71
 72	assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(44)))
 73	assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(45)))
 74}
 75
 76func TestAddDifferentOrder(t *testing.T) {
 77	mt1 := newTestingMerkle(t, 140)
 78	defer mt1.db.Close()
 79	for i := 0; i < 16; i++ {
 80		k := big.NewInt(int64(i))
 81		v := big.NewInt(0)
 82		if err := mt1.Add(k, v); err != nil {
 83			t.Fatal(err)
 84		}
 85	}
 86
 87	mt2 := newTestingMerkle(t, 140)
 88	defer mt2.db.Close()
 89	for i := 16 - 1; i >= 0; i-- {
 90		k := big.NewInt(int64(i))
 91		v := big.NewInt(0)
 92		if err := mt2.Add(k, v); err != nil {
 93			t.Fatal(err)
 94		}
 95	}
 96
 97	assert.Equal(t, mt1.Root().Hex(), mt2.Root().Hex())
 98	assert.Equal(t, "0967b777d660e54aa3a0f0f3405bb962504d3d69d6b930146cd212dff9913bee", mt1.Root().Hex())
 99}
100
101func TestAddRepeatedIndex(t *testing.T) {
102	mt := newTestingMerkle(t, 140)
103	defer mt.db.Close()
104	k := big.NewInt(int64(3))
105	v := big.NewInt(int64(12))
106	if err := mt.Add(k, v); err != nil {
107		t.Fatal(err)
108	}
109	err := mt.Add(k, v)
110	assert.NotNil(t, err)
111	assert.Equal(t, err, ErrEntryIndexAlreadyExists)
112}
113
114func TestGenerateAndVerifyProof128(t *testing.T) {
115	mt, err := NewMerkleTree(db.NewMemoryStorage(), 140)
116	require.Nil(t, err)
117	defer mt.db.Close()
118
119	for i := 0; i < 128; i++ {
120		k := big.NewInt(int64(i))
121		v := big.NewInt(0)
122		if err := mt.Add(k, v); err != nil {
123			t.Fatal(err)
124		}
125	}
126	proof, err := mt.GenerateProof(big.NewInt(42), nil)
127	assert.Nil(t, err)
128	assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(42), big.NewInt(0)))
129}
130
131func TestTreeLimit(t *testing.T) {
132	mt, err := NewMerkleTree(db.NewMemoryStorage(), 5)
133	require.Nil(t, err)
134	defer mt.db.Close()
135
136	for i := 0; i < 16; i++ {
137		err = mt.Add(big.NewInt(int64(i)), big.NewInt(int64(i)))
138		assert.Nil(t, err)
139	}
140
141	// here the tree is full, should not allow to add more data as reaches the maximum number of levels
142	err = mt.Add(big.NewInt(int64(16)), big.NewInt(int64(16)))
143	assert.NotNil(t, err)
144	assert.Equal(t, ErrReachedMaxLevel, err)
145}
146
147func TestSiblingsFromProof(t *testing.T) {
148	mt, err := NewMerkleTree(db.NewMemoryStorage(), 140)
149	require.Nil(t, err)
150	defer mt.db.Close()
151
152	for i := 0; i < 64; i++ {
153		k := big.NewInt(int64(i))
154		v := big.NewInt(0)
155		if err := mt.Add(k, v); err != nil {
156			t.Fatal(err)
157		}
158	}
159
160	proof, err := mt.GenerateProof(big.NewInt(4), nil)
161	if err != nil {
162		t.Fatal(err)
163	}
164
165	siblings := SiblingsFromProof(proof)
166	assert.Equal(t, 6, len(siblings))
167	assert.Equal(t, "23db1f6fb07af47d7715f18960548c215fc7a2e6d25cb4a7eb82c9d3cf69bc26", siblings[0].Hex())
168	assert.Equal(t, "2156e64dedcb76719ec732414dd6a8aa4348dafb24c19351a68fbc4158bb7fba", siblings[1].Hex())
169	assert.Equal(t, "04a8e9b34d5a8b55268ca96b0b8c7c5aaef4f606ec3437ec67e4152d9b323913", siblings[2].Hex())
170	assert.Equal(t, "0ff484133e0d25deb4a7c0cb46d90432e00fcc280948c2fab6fed9476f1e26b2", siblings[3].Hex())
171	assert.Equal(t, "015dff482e87eb2046b8f5323049afd05f8dd8554e2c9aa1ef28991cf205c9b6", siblings[4].Hex())
172	assert.Equal(t, "1e4da486ad68b07acec1406bed5a60732de5ff72d63910f7afbb491f953a8769", siblings[5].Hex())
173}
174
175func TestVerifyProofCases(t *testing.T) {
176	mt := newTestingMerkle(t, 140)
177	defer mt.DB().Close()
178
179	for i := 0; i < 8; i++ {
180		if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
181			t.Fatal(err)
182		}
183	}
184
185	// Existence proof
186
187	proof, err := mt.GenerateProof(big.NewInt(4), nil)
188	if err != nil {
189		t.Fatal(err)
190	}
191	assert.Equal(t, proof.Existence, true)
192	assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(4), big.NewInt(0)))
193	assert.Equal(t, "000300000000000000000000000000000000000000000000000000000000000728ea2b267d2a9436657f20b5827285175e030f58c07375535106903b16621630b9104d995843c7cffa685009a1b28dcd371022a3b27b3a4d6987f7c8b39b0f2fffc165330710754ca0fc24451bdd5d5f82a05f42f1427fbdf17879c0b84be60f", hex.EncodeToString(proof.Bytes()))
194
195	for i := 8; i < 32; i++ {
196		proof, err = mt.GenerateProof(big.NewInt(int64(i)), nil)
197		assert.Nil(t, err)
198		if debug {
199			fmt.Println(i, proof)
200		}
201	}
202	// Non-existence proof, empty aux
203	proof, err = mt.GenerateProof(big.NewInt(12), nil)
204	if err != nil {
205		t.Fatal(err)
206	}
207	assert.Equal(t, proof.Existence, false)
208	// assert.True(t, proof.nodeAux == nil)
209	assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(12), big.NewInt(0)))
210	assert.Equal(t, "030300000000000000000000000000000000000000000000000000000000000728ea2b267d2a9436657f20b5827285175e030f58c07375535106903b16621630b9104d995843c7cffa685009a1b28dcd371022a3b27b3a4d6987f7c8b39b0f2fffc165330710754ca0fc24451bdd5d5f82a05f42f1427fbdf17879c0b84be60f04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes()))
211
212	// Non-existence proof, diff. node aux
213	proof, err = mt.GenerateProof(big.NewInt(10), nil)
214	if err != nil {
215		t.Fatal(err)
216	}
217	assert.Equal(t, proof.Existence, false)
218	assert.True(t, proof.NodeAux != nil)
219	assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(10), big.NewInt(0)))
220	assert.Equal(t, "030300000000000000000000000000000000000000000000000000000000000728ea2b267d2a9436657f20b5827285175e030f58c07375535106903b1662163097fcf8f911b271df196e0a75667b8a4f3024ef39f87201ed2b7cda349ba202296b7aeba35dc19ab0d4f65e175536c9952a90b6de18c3205611c3cd4fb408f01602000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes()))
221}
222
223func TestVerifyProofFalse(t *testing.T) {
224	mt := newTestingMerkle(t, 140)
225	defer mt.DB().Close()
226
227	for i := 0; i < 8; i++ {
228		if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
229			t.Fatal(err)
230		}
231	}
232
233	// Invalid existence proof (node used for verification doesn't
234	// correspond to node in the proof)
235	proof, err := mt.GenerateProof(big.NewInt(int64(4)), nil)
236	if err != nil {
237		t.Fatal(err)
238	}
239	assert.Equal(t, proof.Existence, true)
240	assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(5)), big.NewInt(int64(5))))
241
242	// Invalid non-existence proof (Non-existence proof, diff. node aux)
243	proof, err = mt.GenerateProof(big.NewInt(int64(4)), nil)
244	if err != nil {
245		t.Fatal(err)
246	}
247	assert.Equal(t, proof.Existence, true)
248	// Now we change the proof from existence to non-existence, and add e's
249	// data as auxiliary node.
250	proof.Existence = false
251	proof.NodeAux = &NodeAux{Key: NewHashFromBigInt(big.NewInt(int64(4))), Value: NewHashFromBigInt(big.NewInt(4))}
252	assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(4)), big.NewInt(0)))
253}
254
255func TestGraphViz(t *testing.T) {
256	mt, err := NewMerkleTree(db.NewMemoryStorage(), 10)
257	assert.Nil(t, err)
258
259	mt.Add(big.NewInt(1), big.NewInt(0))
260	mt.Add(big.NewInt(2), big.NewInt(0))
261	mt.Add(big.NewInt(3), big.NewInt(0))
262	mt.Add(big.NewInt(4), big.NewInt(0))
263	mt.Add(big.NewInt(5), big.NewInt(0))
264	mt.Add(big.NewInt(100), big.NewInt(0))
265
266	// mt.PrintGraphViz(nil)
267
268	expected := `digraph hierarchy {
269node [fontname=Monospace,fontsize=10,shape=box]
270"60195538..." -> {"19759736..." "18893277..."}
271"19759736..." -> {"16152312..." "43945008..."}
272"16152312..." -> {"empty0" "13952255..."}
273"empty0" [style=dashed,label=0];
274"13952255..." -> {"61769925..." "empty1"}
275"empty1" [style=dashed,label=0];
276"61769925..." -> {"92723289..." "empty2"}
277"empty2" [style=dashed,label=0];
278"92723289..." -> {"21082735..." "82784818..."}
279"21082735..." [style=filled];
280"82784818..." [style=filled];
281"43945008..." [style=filled];
282"18893277..." -> {"19855703..." "17718670..."}
283"19855703..." -> {"11499909..." "15828714..."}
284"11499909..." [style=filled];
285"15828714..." [style=filled];
286"17718670..." [style=filled];
287}
288`
289	w := bytes.NewBufferString("")
290	mt.GraphViz(w, nil)
291	assert.Equal(t, []byte(expected), w.Bytes())
292}