oihash

README

(O)rder-(I)ndependent Hash

A definitely-not-cryptographically-secure hash algorithm designed to
allow you to answer the following question:

Do these two enormous lists of []bytes have the same elements in the
same numbers? i.e. if you have a pair of multisets represented as
lists, are they the same?

It's assumed that it's infeasible to sort the two input lists, which
means that we want a hash function into which you can mix the elements
in any order, and the result will be the same regardless of mixing
order. One helpful construction for this is to select two functions
with the following signatures:

Hash: MultiSet<[]byte> -> HashType
Combine: HashType x HashType -> HashType

that satisfy the following property:

Combine(Hash(A), Hash(B)) == Hash(Union(A, B))


Then you can compute incrementally as follows:

var combinedHash HashType
for _, x := range items {
  itemHash := Hash({x})
  combinedHash = Combine(combinedHash, itemHash)
}

Documentation

Index

• Constants
• func NilHashToEmpty(h []byte) []byte
• type OiHash
  • func Combine(lhs, rhs OiHash) OiHash
  • func Hash(items [][]byte) OiHash
  • func (h *OiHash) Digest() []byte
  • func (h *OiHash) Insert(item []byte)
  • func (h *OiHash) InsertHash(hash []byte)
  • func (h *OiHash) MarshalBinary() ([]byte, error)
  • func (h *OiHash) Remove(item []byte)
  • func (h *OiHash) RemoveHash(itemHash []byte)
  • func (h *OiHash) UnmarshalBinary(data []byte) error

Constants

const (
	Size    = sha256.Size
	Columns = Size / 4
)

Functions

func NilHashToEmpty

func NilHashToEmpty(h []byte) []byte

Types

type OiHash

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

func Combine

func Combine(lhs, rhs OiHash) OiHash

func Hash

func Hash(items [][]byte) OiHash

func (*OiHash) Digest

func (h *OiHash) Digest() []byte

Get the actual hash output.

Happens to be the same as the MarshalBinary output, but named differently for API clarity.

func (*OiHash) Insert

func (h *OiHash) Insert(item []byte)

func (*OiHash) InsertHash

func (h *OiHash) InsertHash(hash []byte)

Insert the sha256 sum of an item into the hash or a different marshalled oihash.

func (*OiHash) MarshalBinary

func (h *OiHash) MarshalBinary() ([]byte, error)

Save an intermediate hash state for later.

func (*OiHash) Remove

func (h *OiHash) Remove(item []byte)

func (*OiHash) RemoveHash

func (h *OiHash) RemoveHash(itemHash []byte)

Remove the sha256 sum of an item from the hash

func (*OiHash) UnmarshalBinary

func (h *OiHash) UnmarshalBinary(data []byte) error

Load a persisted hash state. Overwrites the internal state of h.