NewMerkle generate a merkle tree according to some hashable values like transactions or blocks.
(items []*hash.Hash)
| 43 | // NewMerkle generate a merkle tree according |
| 44 | // to some hashable values like transactions or blocks. |
| 45 | func NewMerkle(items []*hash.Hash) *Merkle { |
| 46 | if len(items) == 0 { |
| 47 | items = []*hash.Hash{{}} |
| 48 | } |
| 49 | |
| 50 | // the max number of merkle tree node = len(items) * 2 + 2 |
| 51 | upperPoT := upperPowOfTwo(uint64(len(items))) |
| 52 | maxMerkleSize := upperPoT*2 - 1 |
| 53 | hashArray := make([]*hash.Hash, maxMerkleSize) |
| 54 | |
| 55 | // generate merkle tree |
| 56 | copy(hashArray, items) |
| 57 | offset := upperPoT |
| 58 | for i := uint64(0); i < maxMerkleSize-1; i += 2 { |
| 59 | if hashArray[i] != nil && hashArray[i+1] != nil { |
| 60 | hashArray[offset] = MergeTwoHash(hashArray[i], hashArray[i+1]) |
| 61 | } else if hashArray[i] != nil { |
| 62 | // only left node |
| 63 | hashArray[offset] = MergeTwoHash(hashArray[i], hashArray[i]) |
| 64 | } else { |
| 65 | // left and right are both nil |
| 66 | hashArray[offset] = nil |
| 67 | } |
| 68 | offset++ |
| 69 | } |
| 70 | merkle := &Merkle{hashArray} |
| 71 | return merkle |
| 72 | } |
| 73 | |
| 74 | // GetRoot returns the root of merkle tree. |
| 75 | func (merkle *Merkle) GetRoot() *hash.Hash { |