hashtree

Documentation

Overview

package hashtree implements merkle hash trees based on sha256 and sha244 from sha2's family.

At a glance:

Leaf Nodes: 1 to 1024 bytes hashed to 32 bytes using sha256. (lh)

Inner Nodes: merges 2 32 byte hashes to 1 using sha244's initial hash values
	and sha256 without any padding. (ih)

A file or blob is then identified by the root inner hash and data length.

Root Hash =        ih(d,c)
                    /    \
d, c      =     ih(a,b),   c
                 /    \       \
a, b, c   =   lh(b1), lh(b2), lh(b3)

Where b1 and b2 are blocks of 1024 bytes, and b3 must be 1 to 1024 Bytes

Index

• Constants
• Variables
• func HashNumber(leafs Nodes, l Level, n Nodes) int64
• func HashPosition(leafs Nodes, l Level, n Nodes) int64
• func HashTreeSize(leafs Nodes) int64
• func NoPad32bytes(d io.Writer, len int64)
• func SplitLength(b int64) (l, r int64)
• func SplitLocalSummable(hashes []byte, hashSize int, levelWidth Nodes, off Nodes) [][]byte
• func ZeroPad32bytes(d io.Writer, len int64)
• type CopyableHashTree
  • func NewNoPadTree() CopyableHashTree
  • func NewTree() CopyableHashTree
  • func NewTree2(padder func(d io.Writer, len int64), compressor func(l, r *H256) *H256) CopyableHashTree
• type H256
  • func FromBytes(bytes []byte) *H256
  • func (h *H256) ToBytes() []byte
• type HashTree
  • func NewFile() HashTree
  • func NewFile2(leafBlockSize int64, leaf hash.Hash, tree CopyableHashTree) HashTree
• type Level
  • func Levels(n Nodes) Level
• type Nodes
  • func LevelWidth(n Nodes, l Level) Nodes

Constants

const HashSize = 32

sha256 is 32 bytes

const (
	//LeafBlockSize is the max size in bytes
	//of a data block on the leaf of a hash tree.
	LeafBlockSize = 1024
)

const MaxLevel = 64

the max depth of a hash tree

Variables

var I = fileDigestSample{NewFile()}

I is a sample of the standared HashTree, to make some methods accessable without creating a new HashTree. Do not use it's write or sum functions.

Functions

func HashNumber

func HashNumber(leafs Nodes, l Level, n Nodes) int64

HashNumber gives each node in a tree an unique number from 0 up

func HashPosition

func HashPosition(leafs Nodes, l Level, n Nodes) int64

HashPosition uses hash HashNumber to tell you where you can put/get an inner hash in a byte array, without overlaps or unused space.

func HashTreeSize

func HashTreeSize(leafs Nodes) int64

HashTreeSize is the total number of nodes in a tree

func NoPad32bytes

func NoPad32bytes(d io.Writer, len int64)

NoPad32bytes is a special case of ZeroPad32bytes when content is known to be in one or more multiples of 32 byte blocks, panic otherwise

func SplitLength

func SplitLength(b int64) (l, r int64)

SplitLength split the length of covered by an inner node in the tree to the length covered by it's childs. Such that:

b must be larger than LeafBlockSize (1024)
b = l + r
l is the largest possible power of 2, and l < b
r > 0

func SplitLocalSummable

func SplitLocalSummable(hashes []byte, hashSize int, levelWidth Nodes, off Nodes) [][]byte

Split inner hashes based on highest derivable ancestors

func ZeroPad32bytes

func ZeroPad32bytes(d io.Writer, len int64)

ZeroPad32bytes pads with 0 or more of bytes 0x00. Use this when the size is known externally and the shortness of content makes padding the size too expansive.

Types

type CopyableHashTree

type CopyableHashTree interface {
	HashTree
	Copy() CopyableHashTree
}

CopyableHashTree allows copying of the internal state. Because the Sum function might pad, but can't reset.

func NewNoPadTree

func NewNoPadTree() CopyableHashTree

func NewTree

func NewTree() CopyableHashTree

func NewTree2

func NewTree2(padder func(d io.Writer, len int64), compressor func(l, r *H256) *H256) CopyableHashTree

Create a binary tree hash using padder and compressor. Padder mush pad to intervals of 256 bits. Compressor mush hash 2 H256s to 1.

type H256

type H256 [8]uint32 //the internal hash

func FromBytes

func FromBytes(bytes []byte) *H256

FromBytes create a hash from bytes bytes must have a length of HashSize (32)

func (*H256) ToBytes

func (h *H256) ToBytes() []byte

ToBytes reads out bytes from a hash bytes will have a length of HashSize (32)

type HashTree

type HashTree interface {
	hash.Hash

	//Nodes returns the number of nodes on the
	//bottom level of a hash tree covering len
	//bytes of data.
	//The padder is used by this function.
	Nodes(len int64) Nodes

	//SetInnerHashListener set a listener that receive
	//callbacks everytime an inner hash is calculated.
	//
	//On level 1, left and right child hashes are nil.
	//
	//On right-most nodes that are promoted without hashing,
	//left child is the same hash, and right is nil.
	SetInnerHashListener(l func(level Level, index Nodes, hash, left, right *H256))
}

func NewFile

func NewFile() HashTree

Create the standard file tree hash using leaf blocks of LeafBlockSize (1kB) and "crypto/sha256", and inner hash using sha256 (244's IHV) without padding.

func NewFile2

func NewFile2(leafBlockSize int64, leaf hash.Hash, tree CopyableHashTree) HashTree

Create any tree hash using leaf blocks of size and leaf hash, and inner hash using tree hash, the tree stucture is internal to the tree hash.

type Level

type Level int

Level is the depth of tree counted from bottom up. The lowest level is 0. Level is signed to allow representation of deltas.

func Levels

func Levels(n Nodes) Level

Levels return the number of Levels (1 or more) of a hash tree with n leaf nodes

type Nodes

type Nodes int

Nodes is the number of Nodes in a level, or the index of a node in a level. Nodes is signed to allow representation of deltas.

func LevelWidth

func LevelWidth(n Nodes, l Level) Nodes

LevelWidth returns the number of nodes in a level, with the requested number of level (0 or more) above a base with n Nodes.