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 CompactLayerToSliceHashes(compactLayer string) (hashes [][sha256.Size]byte, err error) {
  36         g.MakeSliceWithLength(&hashes, len(compactLayer)/sha256.Size)
  37         for i := range hashes {
  38                 n := copy(hashes[i][:], compactLayer[i*sha256.Size:])
  39                 if n != sha256.Size {
  40                         err = fmt.Errorf("compact layer has incomplete hash at index %d", i)
  41                         return
  42                 }
  43         }
  44         return
  45 }
  46
  47 func RoundUpToPowerOfTwo(n uint) (ret uint) {
  48         return 1 << bits.Len(n-1)
  49 }
  50
  51 func Log2RoundingUp(n uint) (ret uint) {
  52         return uint(bits.Len(n - 1))
  53 }