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 Digest
• type Hash
  • func FromData(data []byte) Hash
  • func FromSlice(data []byte) Hash
  • func MaybeParse(s string) (Hash, bool)
  • func New(digest Digest) Hash
  • func Parse(s string) Hash
  • func (r Hash) Digest() Digest
  • func (r Hash) DigestSlice() []byte
  • func (r Hash) Greater(other Hash) bool
  • func (r Hash) IsEmpty() bool
  • func (r Hash) Less(other Hash) bool
  • func (r Hash) String() string
• type 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) 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 Digest

type Digest [ByteLen]byte

Digest is used for the underlying data of the Hash.

type Hash

type Hash struct {
	// contains filtered or unexported fields
}

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

func FromData

func FromData(data []byte) Hash

FromData computes a new Hash from data.

func FromSlice

func FromSlice(data []byte) Hash

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

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(digest Digest) Hash

New creates a new Hash from a Digest.

func Parse

func Parse(s string) Hash

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

func (Hash) Digest

func (r Hash) Digest() Digest

Digest returns a *copy* of the digest that backs Hash.

func (Hash) DigestSlice

func (r Hash) DigestSlice() []byte

DigestSlice returns a slice of the digest that backs A NEW COPY of Hash, because the receiver of this method is not a pointer.

func (Hash) Greater

func (r Hash) Greater(other Hash) bool

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

func (Hash) IsEmpty

func (r Hash) IsEmpty() bool

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

func (Hash) Less

func (r Hash) Less(other Hash) bool

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

func (Hash) String

func (r 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 (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) 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)