vendor/github.com/tendermint/tmlibs/merkle/simple_tree.go

   1 /*
   2 Computes a deterministic minimal height merkle tree hash.
   3 If the number of items is not a power of two, some leaves
   4 will be at different levels. Tries to keep both sides of
   5 the tree the same size, but the left may be one greater.
   6
   7 Use this for short deterministic trees, such as the validator list.
   8 For larger datasets, use IAVLTree.
   9
  10                         *
  11                        / \
  12                      /     \
  13                    /         \
  14                  /             \
  15                 *               *
  16                / \             / \
  17               /   \           /   \
  18              /     \         /     \
  19             *       *       *       h6
  20            / \     / \     / \
  21           h0  h1  h2  h3  h4  h5
  22
  23 */
  24
  25 package merkle
  26
  27 import (
  28         "bytes"
  29         "fmt"
  30         "sort"
  31
  32         "golang.org/x/crypto/ripemd160"
  33
  34         "github.com/tendermint/go-wire"
  35         . "github.com/tendermint/tmlibs/common"
  36 )
  37
  38 func SimpleHashFromTwoHashes(left []byte, right []byte) []byte {
  39         var n int
  40         var err error
  41         var hasher = ripemd160.New()
  42         wire.WriteByteSlice(left, hasher, &n, &err)
  43         wire.WriteByteSlice(right, hasher, &n, &err)
  44         if err != nil {
  45                 PanicCrisis(err)
  46         }
  47         return hasher.Sum(nil)
  48 }
  49
  50 func SimpleHashFromHashes(hashes [][]byte) []byte {
  51         // Recursive impl.
  52         switch len(hashes) {
  53         case 0:
  54                 return nil
  55         case 1:
  56                 return hashes[0]
  57         default:
  58                 left := SimpleHashFromHashes(hashes[:(len(hashes)+1)/2])
  59                 right := SimpleHashFromHashes(hashes[(len(hashes)+1)/2:])
  60                 return SimpleHashFromTwoHashes(left, right)
  61         }
  62 }
  63
  64 // Convenience for SimpleHashFromHashes.
  65 func SimpleHashFromBinaries(items []interface{}) []byte {
  66         hashes := make([][]byte, len(items))
  67         for i, item := range items {
  68                 hashes[i] = SimpleHashFromBinary(item)
  69         }
  70         return SimpleHashFromHashes(hashes)
  71 }
  72
  73 // General Convenience
  74 func SimpleHashFromBinary(item interface{}) []byte {
  75         hasher, n, err := ripemd160.New(), new(int), new(error)
  76         wire.WriteBinary(item, hasher, n, err)
  77         if *err != nil {
  78                 PanicCrisis(err)
  79         }
  80         return hasher.Sum(nil)
  81 }
  82
  83 // Convenience for SimpleHashFromHashes.
  84 func SimpleHashFromHashables(items []Hashable) []byte {
  85         hashes := make([][]byte, len(items))
  86         for i, item := range items {
  87                 hash := item.Hash()
  88                 hashes[i] = hash
  89         }
  90         return SimpleHashFromHashes(hashes)
  91 }
  92
  93 // Convenience for SimpleHashFromHashes.
  94 func SimpleHashFromMap(m map[string]interface{}) []byte {
  95         kpPairsH := MakeSortedKVPairs(m)
  96         return SimpleHashFromHashables(kpPairsH)
  97 }
  98
  99 //--------------------------------------------------------------------------------
 100
 101 /* Convenience struct for key-value pairs.
 102 A list of KVPairs is hashed via `SimpleHashFromHashables`.
 103 NOTE: Each `Value` is encoded for hashing without extra type information,
 104 so the user is presumed to be aware of the Value types.
 105 */
 106 type KVPair struct {
 107         Key   string
 108         Value interface{}
 109 }
 110
 111 func (kv KVPair) Hash() []byte {
 112         hasher, n, err := ripemd160.New(), new(int), new(error)
 113         wire.WriteString(kv.Key, hasher, n, err)
 114         if kvH, ok := kv.Value.(Hashable); ok {
 115                 wire.WriteByteSlice(kvH.Hash(), hasher, n, err)
 116         } else {
 117                 wire.WriteBinary(kv.Value, hasher, n, err)
 118         }
 119         if *err != nil {
 120                 PanicSanity(*err)
 121         }
 122         return hasher.Sum(nil)
 123 }
 124
 125 type KVPairs []KVPair
 126
 127 func (kvps KVPairs) Len() int           { return len(kvps) }
 128 func (kvps KVPairs) Less(i, j int) bool { return kvps[i].Key < kvps[j].Key }
 129 func (kvps KVPairs) Swap(i, j int)      { kvps[i], kvps[j] = kvps[j], kvps[i] }
 130 func (kvps KVPairs) Sort()              { sort.Sort(kvps) }
 131
 132 func MakeSortedKVPairs(m map[string]interface{}) []Hashable {
 133         kvPairs := []KVPair{}
 134         for k, v := range m {
 135                 kvPairs = append(kvPairs, KVPair{k, v})
 136         }
 137         KVPairs(kvPairs).Sort()
 138         kvPairsH := []Hashable{}
 139         for _, kvp := range kvPairs {
 140                 kvPairsH = append(kvPairsH, kvp)
 141         }
 142         return kvPairsH
 143 }
 144
 145 //--------------------------------------------------------------------------------
 146
 147 type SimpleProof struct {
 148         Aunts [][]byte `json:"aunts"` // Hashes from leaf's sibling to a root's child.
 149 }
 150
 151 // proofs[0] is the proof for items[0].
 152 func SimpleProofsFromHashables(items []Hashable) (rootHash []byte, proofs []*SimpleProof) {
 153         trails, rootSPN := trailsFromHashables(items)
 154         rootHash = rootSPN.Hash
 155         proofs = make([]*SimpleProof, len(items))
 156         for i, trail := range trails {
 157                 proofs[i] = &SimpleProof{
 158                         Aunts: trail.FlattenAunts(),
 159                 }
 160         }
 161         return
 162 }
 163
 164 // Verify that leafHash is a leaf hash of the simple-merkle-tree
 165 // which hashes to rootHash.
 166 func (sp *SimpleProof) Verify(index int, total int, leafHash []byte, rootHash []byte) bool {
 167         computedHash := computeHashFromAunts(index, total, leafHash, sp.Aunts)
 168         if computedHash == nil {
 169                 return false
 170         }
 171         if !bytes.Equal(computedHash, rootHash) {
 172                 return false
 173         }
 174         return true
 175 }
 176
 177 func (sp *SimpleProof) String() string {
 178         return sp.StringIndented("")
 179 }
 180
 181 func (sp *SimpleProof) StringIndented(indent string) string {
 182         return fmt.Sprintf(`SimpleProof{
 183 %s  Aunts: %X
 184 %s}`,
 185                 indent, sp.Aunts,
 186                 indent)
 187 }
 188
 189 // Use the leafHash and innerHashes to get the root merkle hash.
 190 // If the length of the innerHashes slice isn't exactly correct, the result is nil.
 191 func computeHashFromAunts(index int, total int, leafHash []byte, innerHashes [][]byte) []byte {
 192         // Recursive impl.
 193         if index >= total {
 194                 return nil
 195         }
 196         switch total {
 197         case 0:
 198                 PanicSanity("Cannot call computeHashFromAunts() with 0 total")
 199                 return nil
 200         case 1:
 201                 if len(innerHashes) != 0 {
 202                         return nil
 203                 }
 204                 return leafHash
 205         default:
 206                 if len(innerHashes) == 0 {
 207                         return nil
 208                 }
 209                 numLeft := (total + 1) / 2
 210                 if index < numLeft {
 211                         leftHash := computeHashFromAunts(index, numLeft, leafHash, innerHashes[:len(innerHashes)-1])
 212                         if leftHash == nil {
 213                                 return nil
 214                         }
 215                         return SimpleHashFromTwoHashes(leftHash, innerHashes[len(innerHashes)-1])
 216                 } else {
 217                         rightHash := computeHashFromAunts(index-numLeft, total-numLeft, leafHash, innerHashes[:len(innerHashes)-1])
 218                         if rightHash == nil {
 219                                 return nil
 220                         }
 221                         return SimpleHashFromTwoHashes(innerHashes[len(innerHashes)-1], rightHash)
 222                 }
 223         }
 224 }
 225
 226 // Helper structure to construct merkle proof.
 227 // The node and the tree is thrown away afterwards.
 228 // Exactly one of node.Left and node.Right is nil, unless node is the root, in which case both are nil.
 229 // node.Parent.Hash = hash(node.Hash, node.Right.Hash) or
 230 //                                                                        hash(node.Left.Hash, node.Hash), depending on whether node is a left/right child.
 231 type SimpleProofNode struct {
 232         Hash   []byte
 233         Parent *SimpleProofNode
 234         Left   *SimpleProofNode // Left sibling  (only one of Left,Right is set)
 235         Right  *SimpleProofNode // Right sibling (only one of Left,Right is set)
 236 }
 237
 238 // Starting from a leaf SimpleProofNode, FlattenAunts() will return
 239 // the inner hashes for the item corresponding to the leaf.
 240 func (spn *SimpleProofNode) FlattenAunts() [][]byte {
 241         // Nonrecursive impl.
 242         innerHashes := [][]byte{}
 243         for spn != nil {
 244                 if spn.Left != nil {
 245                         innerHashes = append(innerHashes, spn.Left.Hash)
 246                 } else if spn.Right != nil {
 247                         innerHashes = append(innerHashes, spn.Right.Hash)
 248                 } else {
 249                         break
 250                 }
 251                 spn = spn.Parent
 252         }
 253         return innerHashes
 254 }
 255
 256 // trails[0].Hash is the leaf hash for items[0].
 257 // trails[i].Parent.Parent....Parent == root for all i.
 258 func trailsFromHashables(items []Hashable) (trails []*SimpleProofNode, root *SimpleProofNode) {
 259         // Recursive impl.
 260         switch len(items) {
 261         case 0:
 262                 return nil, nil
 263         case 1:
 264                 trail := &SimpleProofNode{items[0].Hash(), nil, nil, nil}
 265                 return []*SimpleProofNode{trail}, trail
 266         default:
 267                 lefts, leftRoot := trailsFromHashables(items[:(len(items)+1)/2])
 268                 rights, rightRoot := trailsFromHashables(items[(len(items)+1)/2:])
 269                 rootHash := SimpleHashFromTwoHashes(leftRoot.Hash, rightRoot.Hash)
 270                 root := &SimpleProofNode{rootHash, nil, nil, nil}
 271                 leftRoot.Parent = root
 272                 leftRoot.Right = rightRoot
 273                 rightRoot.Parent = root
 274                 rightRoot.Left = leftRoot
 275                 return append(lefts, rights...), root
 276         }
 277 }