hash

Documentation

Overview

Package hash implements the hash function used throughout Noms.

Noms serialization from version 4-onward uses the first 20 bytes of sha-512 for hashes.

sha-512 was chosen because:

- sha-1 is no longer recommended. - sha-3 is brand new, not a lot of platform support. - blake is not commonly used, not a lot of platform support. - within sha-2, sha-512 is faster than sha-256 on 64 bit.

Our specific truncation scheme (first 20 bytes) was chosen because:

- The "standard" truncation schemes are not widely supported. For example, at time of writing, there is no fast native implementation of sha512/256 on Node. - The smallest standard truncation of sha512 is 28 bytes, but we don't need this many. And because we are a database, the size of the hashes matters. Bigger hashes mean less data in each chunk, which means less tree fan-out, which means slower iteration and searching. 20 bytes is a good balance between collision resistance and wide trees. - 20 bytes leads to a nice round number of base32 digits: 32.

The textual serialization of hashes uses big-endian base32 with the alphabet {0-9,a-v}. This scheme was chosen because:

- It's easy to convert to and from base32 without bignum arithemetic. - No special chars: you can double-click to select in GUIs. - Sorted hashes will be sorted textually, making it easy to scan for humans.

In Noms, the hash function is a component of the serialization version, which is constant over the entire lifetime of a single database. So clients do not need to worry about encountering multiple hash functions in the same database.

Index

• Constants
• type Hash
  • func MaybeParse(s string) (Hash, bool)
  • func New(data []byte) Hash
  • func Of(data []byte) Hash
  • func Parse(s string) Hash
  • func (h Hash) Greater(other Hash) bool
  • func (h Hash) IsEmpty() bool
  • func (h Hash) Less(other Hash) bool
  • func (h Hash) String() string
• type HashSet
  • func NewHashSet(hashes ...Hash) HashSet
  • func (hs HashSet) Has(hash Hash) (has bool)
  • func (hs HashSet) Insert(hash Hash)
  • func (hs HashSet) Remove(hash Hash)
• type HashSlice
  • func (rs HashSlice) Equals(other HashSlice) bool
  • func (rs HashSlice) HashSet() HashSet
  • func (rs HashSlice) Len() int
  • func (rs HashSlice) Less(i, j int) bool
  • func (rs HashSlice) Swap(i, j int)

Constants

const (
	// ByteLen is the number of bytes used to represent the Hash.
	ByteLen = 20

	// StringLen is the number of characters need to represent the Hash using Base32.
	StringLen = 32 // 20 * 8 / log2(32)
)

Types

type Hash

type Hash [ByteLen]byte

Hash is used to represent the hash of a Noms Value.

func MaybeParse

func MaybeParse(s string) (Hash, bool)

MaybeParse parses a string representing a hash as a Base32 encoded byte array. If the string is not well formed then this returns (emptyHash, false).

func New

func New(data []byte) Hash

New creates a new Hash backed by data, ensuring that data is an acceptable length.

func Of

func Of(data []byte) Hash

Of computes a new Hash from data.

func Parse

func Parse(s string) Hash

Parse parses a string representing a hash as a Base32 encoded byte array. If the string is not well formed then this panics.

func (Hash) Greater

func (h Hash) Greater(other Hash) bool

Greater compares two hashes returning whether this Hash is greater than other.

func (Hash) IsEmpty

func (h Hash) IsEmpty() bool

IsEmpty determines if this Hash is equal to the empty hash (all zeroes).

func (Hash) Less

func (h Hash) Less(other Hash) bool

Less compares two hashes returning whether this Hash is less than other.

func (Hash) String

func (h Hash) String() string

String returns a string representation of the hash using Base32 encoding.

type HashSet

type HashSet map[Hash]struct{}

HashSet is a set of Hashes.

func NewHashSet

func NewHashSet(hashes ...Hash) HashSet

func (HashSet) Has

func (hs HashSet) Has(hash Hash) (has bool)

Has returns true if the HashSet contains hash.

func (HashSet) Insert

func (hs HashSet) Insert(hash Hash)

Insert adds a Hash to the set.

func (HashSet) Remove

func (hs HashSet) Remove(hash Hash)

Remove removes hash from the HashSet.

type HashSlice

type HashSlice []Hash

func (HashSlice) Equals

func (rs HashSlice) Equals(other HashSlice) bool

func (HashSlice) HashSet

func (rs HashSlice) HashSet() HashSet

func (HashSlice) Len

func (rs HashSlice) Len() int

func (HashSlice) Less

func (rs HashSlice) Less(i, j int) bool

func (HashSlice) Swap

func (rs HashSlice) Swap(i, j int)