hash

Documentation

Index

• Constants
• func CalculateSegments(fileSize uint64) (numSegments uint64)
• func VerifyReaderProof(baseSegment [SegmentSize]byte, hashSet []Hash, numSegments, proofIndex uint64, ...) bool
• type Hash
  • func BuildReaderProof(rs io.ReadSeeker, numSegments, proofIndex uint64) (baseSegment [SegmentSize]byte, hashSet []Hash, err error)
  • func BytesMerkleRoot(data []byte) (hash Hash, err error)
  • func HashAll(data ...[]byte) Hash
  • func HashBytes(data []byte) Hash
  • func HashObject(obj interface{}) Hash
  • func JoinHash(left, right Hash) Hash
  • func MerkleRoot(leaves []Hash) Hash
  • func ReaderMerkleRoot(reader io.Reader, numSegments uint64) (hash Hash, err error)

Constants

const (
	HashSize    = 32
	SegmentSize = 64 // Size of smallest piece of a file which gets hashed when building the Merkle tree.
)

Functions

func CalculateSegments

func CalculateSegments(fileSize uint64) (numSegments uint64)

Calculates the number of segments in the file when building a merkle tree. Should probably be renamed to CountLeaves() or something.

TODO: Why is this in package hash?

func VerifyReaderProof

func VerifyReaderProof(baseSegment [SegmentSize]byte, hashSet []Hash, numSegments, proofIndex uint64, expectedRoot Hash) bool

verifyProof traverses a StorageProof, hashing elements together to produce the root-level hash, which is then checked against the expected result. Care must be taken to ensure that the correct ordering is used when concatenating hashes.

Implementation note: the "left-right" ordering for a given proofIndex can be determined from its little-endian binary representation, where a 0 indicates "left" and a 1 indicates "right." However, this must be modified slightly for trees with "orphans," since they cause certain lefts/rights to be skipped. As it turns out, the branches to skip can be determined from the binary representation of numSegments-1, where a 0 indicates "skip" and a 1 indicates "keep." I don't know why this works, I just noticed the pattern.

TODO: Gain higher certainty of correctness.

Types

type Hash

type Hash [HashSize]byte

func BuildReaderProof

func BuildReaderProof(rs io.ReadSeeker, numSegments, proofIndex uint64) (baseSegment [SegmentSize]byte, hashSet []Hash, err error)

buildProof constructs a list of hashes using the following procedure. The storage proof requires traversing the Merkle tree from the proofIndex node to the root. On each level of the tree, we must provide the hash of the "sister" node. (Since this is a binary tree, the sister node is the other node with the same parent as us.) To obtain this hash, we call ReaderMerkleRoot on the segment of data corresponding to the sister. This segment will double in size on each iteration until we reach the root.

TODO: Gain higher certianty of correctness.

func BytesMerkleRoot

func BytesMerkleRoot(data []byte) (hash Hash, err error)

BytesMerkleRoot takes a byte slice and returns the merkle root created by splitting the slice into small pieces and then treating each piece as an element of the tree.

func HashAll

func HashAll(data ...[]byte) Hash

func HashBytes

func HashBytes(data []byte) Hash

func HashObject

func HashObject(obj interface{}) Hash

func JoinHash

func JoinHash(left, right Hash) Hash

Helper function for Merkle trees; takes two hashes, concatenates them, and hashes the result.

func MerkleRoot

func MerkleRoot(leaves []Hash) Hash

MerkleRoot calculates the "root hash" formed by repeatedly concatenating and hashing a binary tree of hashes. If the number of leaves is not a power of 2, the orphan hash(es) are not rehashed. Examples:

     ┌───┴──┐       ┌────┴───┐         ┌─────┴─────┐
  ┌──┴──┐   │    ┌──┴──┐     │      ┌──┴──┐     ┌──┴──┐
┌─┴─┐ ┌─┴─┐ │  ┌─┴─┐ ┌─┴─┐ ┌─┴─┐  ┌─┴─┐ ┌─┴─┐ ┌─┴─┐   │
   (5-leaf)         (6-leaf)             (7-leaf)

func ReaderMerkleRoot

func ReaderMerkleRoot(reader io.Reader, numSegments uint64) (hash Hash, err error)

ReaderMerkleRoot splits the provided data into segments. It then recursively transforms these segments into a Merkle tree, and returns the root hash. See MerkleRoot for a diagram of how Merkle trees are constructed.