1package merkletree
 2
 3import (
 4	"errors"
 5	"math/big"
 6	"sync"
 7
 8	"github.com/iden3/go-iden3-core/common"
 9	"github.com/iden3/go-iden3-core/db"
10)
11
12const (
13	// proofFlagsLen is the byte length of the flags in the proof header (first 32
14	// bytes).
15	proofFlagsLen = 2
16	// ElemBytesLen is the length of the Hash byte array
17	ElemBytesLen = 32
18)
19
20var (
21	// ErrNodeKeyAlreadyExists is used when a node key already exists.
22	ErrNodeKeyAlreadyExists = errors.New("node already exists")
23	// ErrEntryIndexNotFound is used when no entry is found for an index.
24	ErrEntryIndexNotFound = errors.New("node index not found in the DB")
25	// ErrNodeDataBadSize is used when the data of a node has an incorrect
26	// size and can't be parsed.
27	ErrNodeDataBadSize = errors.New("node data has incorrect size in the DB")
28	// ErrReachedMaxLevel is used when a traversal of the MT reaches the
29	// maximum level.
30	ErrReachedMaxLevel = errors.New("reached maximum level of the merkle tree")
31	// ErrInvalidNodeFound is used when an invalid node is found and can't
32	// be parsed.
33	ErrInvalidNodeFound = errors.New("found an invalid node in the DB")
34	// ErrInvalidProofBytes is used when a serialized proof is invalid.
35	ErrInvalidProofBytes = errors.New("the serialized proof is invalid")
36	// ErrInvalidDBValue is used when a value in the key value DB is
37	// invalid (for example, it doen't contain a byte header and a []byte
38	// body of at least len=1.
39	ErrInvalidDBValue = errors.New("the value in the DB is invalid")
40	// ErrEntryIndexAlreadyExists is used when the entry index already
41	// exists in the tree.
42	ErrEntryIndexAlreadyExists = errors.New("the entry index already exists in the tree")
43	// ErrNotWritable is used when the MerkleTree is not writable and a write function is called
44	ErrNotWritable = errors.New("Merkle Tree not writable")
45
46	rootNodeValue = []byte("currentroot")
47	HashZero      = Hash{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
48)
49
50type Hash [32]byte
51
52func (h Hash) String() string {
53	return new(big.Int).SetBytes(h[:]).String()
54}
55func (h *Hash) BigInt() *big.Int {
56	return new(big.Int).SetBytes(common.SwapEndianness(h[:]))
57}
58
59func NewHashFromBigInt(b *big.Int) *Hash {
60	r := &Hash{}
61	copy(r[:], common.SwapEndianness(b.Bytes()))
62	return r
63}
64
65type MerkleTree struct {
66	sync.RWMutex
67	db        db.Storage
68	rootKey   *Hash
69	writable  bool
70	maxLevels int
71}
72
73func NewMerkleTree(storage db.Storage, maxLevels int) (*MerkleTree, error) {
74	mt := MerkleTree{db: storage, maxLevels: maxLevels, writable: true}
75
76	v, err := mt.db.Get(rootNodeValue)
77	if err != nil {
78		tx, err := mt.db.NewTx()
79		if err != nil {
80			return nil, err
81		}
82		mt.rootKey = &HashZero
83		tx.Put(rootNodeValue, mt.rootKey[:])
84		err = tx.Commit()
85		if err != nil {
86			return nil, err
87		}
88		return &mt, nil
89	}
90	mt.rootKey = &Hash{}
91	copy(mt.rootKey[:], v)
92	return &mt, nil
93}
94
95func (mt *MerkleTree) Root() *Hash {
96	return mt.rootKey
97}