protocol/bc/merkle.go

   1 package bc
   2
   3 import (
   4         "math"
   5
   6         "chain/crypto/sha3pool"
   7 )
   8
   9 var (
  10         leafPrefix     = []byte{0x00}
  11         interiorPrefix = []byte{0x01}
  12 )
  13
  14 // MerkleRoot creates a merkle tree from a slice of transactions
  15 // and returns the root hash of the tree.
  16 func MerkleRoot(transactions []*Tx) (root Hash, err error) {
  17         switch {
  18         case len(transactions) == 0:
  19                 return EmptyStringHash, nil
  20
  21         case len(transactions) == 1:
  22                 h := sha3pool.Get256()
  23                 defer sha3pool.Put256(h)
  24
  25                 h.Write(leafPrefix)
  26                 transactions[0].ID.WriteTo(h)
  27                 root.ReadFrom(h)
  28                 return root, nil
  29
  30         default:
  31                 k := prevPowerOfTwo(len(transactions))
  32                 left, err := MerkleRoot(transactions[:k])
  33                 if err != nil {
  34                         return root, err
  35                 }
  36
  37                 right, err := MerkleRoot(transactions[k:])
  38                 if err != nil {
  39                         return root, err
  40                 }
  41
  42                 h := sha3pool.Get256()
  43                 defer sha3pool.Put256(h)
  44                 h.Write(interiorPrefix)
  45                 left.WriteTo(h)
  46                 right.WriteTo(h)
  47                 root.ReadFrom(h)
  48                 return root, nil
  49         }
  50 }
  51
  52 // prevPowerOfTwo returns the largest power of two that is smaller than a given number.
  53 // In other words, for some input n, the prevPowerOfTwo k is a power of two such that
  54 // k < n <= 2k. This is a helper function used during the calculation of a merkle tree.
  55 func prevPowerOfTwo(n int) int {
  56         // If the number is a power of two, divide it by 2 and return.
  57         if n&(n-1) == 0 {
  58                 return n / 2
  59         }
  60
  61         // Otherwise, find the previous PoT.
  62         exponent := uint(math.Log2(float64(n)))
  63         return 1 << exponent // 2^exponent
  64 }