merkle/merkle.go

   1 package merkle
   2
   3 import (
   4         "crypto/sha256"
   5         "fmt"
   6         "math/bits"
   7
   8         g "github.com/anacrolix/generics"
   9 )
  10
  11 // The leaf block size for BitTorrent v2 Merkle trees.
  12 const BlockSize = 1 << 14 // 16KiB
  13
  14 func Root(hashes [][sha256.Size]byte) [sha256.Size]byte {
  15         switch len(hashes) {
  16         case 0:
  17                 return sha256.Sum256(nil)
  18         case 1:
  19                 return hashes[0]
  20         }
  21         numHashes := uint(len(hashes))
  22         if numHashes != RoundUpToPowerOfTwo(uint(len(hashes))) {
  23                 panic(fmt.Sprintf("expected power of two number of hashes, got %d", numHashes))
  24         }
  25         var next [][sha256.Size]byte
  26         for i := 0; i < len(hashes); i += 2 {
  27                 left := hashes[i]
  28                 right := hashes[i+1]
  29                 h := sha256.Sum256(append(left[:], right[:]...))
  30                 next = append(next, h)
  31         }
  32         return Root(next)
  33 }
  34
  35 func RootWithPadHash(hashes [][sha256.Size]byte, padHash [sha256.Size]byte) [sha256.Size]byte {
  36         for uint(len(hashes)) < RoundUpToPowerOfTwo(uint(len(hashes))) {
  37                 hashes = append(hashes, padHash)
  38         }
  39         return Root(hashes)
  40 }
  41
  42 func CompactLayerToSliceHashes(compactLayer string) (hashes [][sha256.Size]byte, err error) {
  43         g.MakeSliceWithLength(&hashes, len(compactLayer)/sha256.Size)
  44         for i := range hashes {
  45                 n := copy(hashes[i][:], compactLayer[i*sha256.Size:])
  46                 if n != sha256.Size {
  47                         err = fmt.Errorf("compact layer has incomplete hash at index %d", i)
  48                         return
  49                 }
  50         }
  51         return
  52 }
  53
  54 func RoundUpToPowerOfTwo(n uint) (ret uint) {
  55         return 1 << bits.Len(n-1)
  56 }
  57
  58 func Log2RoundingUp(n uint) (ret uint) {
  59         return uint(bits.Len(n - 1))
  60 }